Event News

Talk by Prof. Ren-Cang Li: "Doubling Algorithms, General Theory, and Applications"

Prof. Ren-Cang Li (University of Texas at Arlington) will give a seminar talk about doubling algorithms for solving matrix equations, an important class of algorithms in linear algebra. His title and abstract are below (see also attachment).

Prof. Li is an established numerical analyst working primarily in numerical linear algebra. Please feel free to disseminate the information to anyone who might be interested.


May 28 (Mon.)




National Institute of Informatics
Room 1208, 12th floor


Prof. Ren-Cang Li (University of Texas at Arlington)


Doubling Algorithms, General Theory, and Applications


Iterative methods are widely and indispensably used in numerical approximations. Basically, any iterative method is a rule that produces a sequence of approximations and with a reasonable expectation that newer approximations in the sequence are better. The goal of a doubling algorithm is to significantly speed up the approximation process by seeking ways to skip computing most of the approximations in the sequence but sporadically few, in fact, extremely very few: only the 2^i -th approximations in the sequence, kind of like computing α^2^i via repeatedly squaring. However, this idea is only worthwhile if there is a much cheaper way to directly obtain the 2^i -th approximation from the 2^i-1 -st one than simply following the rule to generate every approximation between the 2^i-1 -st and 2^i -th approximations in order to obtain the 2^i -th approximation. Anderson (1978) had sought the idea to speed up the simple fixed point iteration for solving the discrete-time algebraic Riccati equation via repeatedly compositions of the fixed point iterative function. As can be imagined, under repeatedly compositions, even a simple function can usually and quickly turn into nonetheless a complicated and unworkable one. In the last 20 years or so in large part due to an extremely elegant way of formulation and analysis, the researches in doubling algorithms thrived and continues to be very active, leading to numerical effective and robust algorithms not only for the continuous-time and discrete-time algebraic Riccati equations from optimal control that motivated the researches in the first place but also for M-matrix algebraic Riccati equations (MARE), structured eigenvalue problems, and other nonlinear matrix equations. But the resulting theory is somewhat fragmented and sometimes ad hoc. In this talk, we will seek to provide a general and coherent theory, discuss new highly accurate doubling algorithm for MARE, and look at several important applications.



Yuji Nakatsukasa
nakatsukasa [at] nii.ac.jp