TY - JOUR

T1 - Solving large-scale continuous-time algebraic Riccati equations by doubling

AU - Li, Tiexiang

AU - Chu, Eric King Wah

AU - Lin, Wen-Wei

AU - Weng, Peter Chang Yi

PY - 2013/1/1

Y1 - 2013/1/1

N2 - We consider the solution of large-scale algebraic Riccati equations with numerically low-ranked solutions. For the discrete-time case, the structure-preserving doubling algorithm has been adapted, with the iterates for A not explicitly computed but in the recursive form Ak=Ak-12-Dk(1)Sk- 1[ Dk(2)]⊤, with Dk(1) and Dk(2) being low-ranked and Sk-1 being small in dimension. For the continuous-time case, the algebraic Riccati equation will be first treated with the Cayley transform before doubling is applied. With n being the dimension of the algebraic equations, the resulting algorithms are of an efficient O(n) computational complexity per iteration, without the need for any inner iterations, and essentially converge quadratically. Some numerical results will be presented. For instance in Section 5.2, Example 3, of dimension n=20209 with 204 million variables in the solution X, was solved using MATLAB on a MacBook Pro within 45 s to a machine accuracy of O(10 -16).

AB - We consider the solution of large-scale algebraic Riccati equations with numerically low-ranked solutions. For the discrete-time case, the structure-preserving doubling algorithm has been adapted, with the iterates for A not explicitly computed but in the recursive form Ak=Ak-12-Dk(1)Sk- 1[ Dk(2)]⊤, with Dk(1) and Dk(2) being low-ranked and Sk-1 being small in dimension. For the continuous-time case, the algebraic Riccati equation will be first treated with the Cayley transform before doubling is applied. With n being the dimension of the algebraic equations, the resulting algorithms are of an efficient O(n) computational complexity per iteration, without the need for any inner iterations, and essentially converge quadratically. Some numerical results will be presented. For instance in Section 5.2, Example 3, of dimension n=20209 with 204 million variables in the solution X, was solved using MATLAB on a MacBook Pro within 45 s to a machine accuracy of O(10 -16).

KW - Continuous-time algebraic Riccati equation

KW - Doubling algorithm

KW - Krylov subspace

KW - Large-scale problem

UR - http://www.scopus.com/inward/record.url?scp=84866058324&partnerID=8YFLogxK

U2 - 10.1016/j.cam.2012.06.006

DO - 10.1016/j.cam.2012.06.006

M3 - Article

AN - SCOPUS:84866058324

VL - 237

SP - 373

EP - 383

JO - Journal of Computational and Applied Mathematics

JF - Journal of Computational and Applied Mathematics

SN - 0377-0427

IS - 1

ER -