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
Abstract
We consider a special instance of the algebraic Riccati equation
encountered in transport theory, where the matrix coefficients are rank structured matrices. The
equation is reduced to unilateral form 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 arithmetic operations
(ops) with quadratic convergence. The structured doubling algorithm
is analyzed in the same framework and accelerated to 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