Geodesic
Fast solution of a certain Riccati equation through Cauchy-like matrices
Electronic transactions on numerical analysis, Tome 33 (2009)
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 A1X2 + A0X + 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(n2)$ arithmetic operations (ops) with quadratic convergence. The structured doubling algorithm is analyzed in the same framework and accelerated to $O(n2)$ 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.
Classification : 15A24, 65F05, 65H10
Keywords: nonsymmetric algebraic Riccati equation, cyclic reduction, Cauchy matrix, matrix equation, fast algorithm, M-matrix 
@article{ETNA_2009__33__a6,
     author = {Bini,  Dario A. and Meini,  Beatrice and Poloni,  Federico},
     title = {Fast solution of a certain {Riccati} equation through {Cauchy-like} matrices},
     journal = {Electronic transactions on numerical analysis},
     year = {2009},
     volume = {33},
     zbl = {1189.65075},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ETNA_2009__33__a6/}
}
TY  - JOUR
AU  - Bini,  Dario A.
AU  - Meini,  Beatrice
AU  - Poloni,  Federico
TI  - Fast solution of a certain Riccati equation through Cauchy-like matrices
JO  - Electronic transactions on numerical analysis
PY  - 2009
VL  - 33
UR  - http://geodesic.mathdoc.fr/item/ETNA_2009__33__a6/
LA  - en
ID  - ETNA_2009__33__a6
ER  - 
%0 Journal Article
%A Bini,  Dario A.
%A Meini,  Beatrice
%A Poloni,  Federico
%T Fast solution of a certain Riccati equation through Cauchy-like matrices
%J Electronic transactions on numerical analysis
%D 2009
%V 33
%U http://geodesic.mathdoc.fr/item/ETNA_2009__33__a6/
%G en
%F ETNA_2009__33__a6
Bini,  Dario A.; Meini,  Beatrice; Poloni,  Federico. Fast solution of a certain Riccati equation through Cauchy-like matrices. Electronic transactions on numerical analysis, Tome 33 (2009). http://geodesic.mathdoc.fr/item/ETNA_2009__33__a6/