Volume 33, pp. 84-104, 2008-2009.

Fast solution of a certain Riccati equation through Cauchy-like matrices

Dario A. Bini, Beatrice Meini, and Federico Poloni


We consider a special instance of the algebraic Riccati equation $XCX-XE-AX+B=0$ encountered in transport theory, where the $n\times n$ matrix coefficients $A,B,C,E$ are rank structured matrices. The equation is reduced to unilateral form $A_1X^2+A_0X+A_{-1}=0$ and solved by means of Cyclic Reduction (CR). It is shown that the matrices generated by CR are Cauchy-like with respect to a suitable singular operator and their displacement structure is explicitly determined. The application of the GKO algorithm provides a method for solving this Riccati equation in $O(n^2)$ arithmetic operations (ops) with quadratic convergence. The structured doubling algorithm is analyzed in the same framework and accelerated to $O(n^2)$ ops as well. In critical cases where convergence turns to linear, we present an adaptation of the shift technique which allows us to get rid of the singularity. Numerical experiments and comparisons which confirm the effectiveness of the new approach are reported.

Full Text (PDF) [247 KB], BibTeX

Key words

nonsymmetric algebraic Riccati equation, cyclic reduction, Cauchy matrix, matrix equation, fast algorithm, M-matrix.

AMS subject classifications

15A24, 65F05, 65H10

< Back