Title: Ubiquitous Doubling Algorithms, General Theory, and Applications

Abstract: 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 $\alpha^{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 research 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 research  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.