Fast solution of a certain Riccati equation through Cauchy-like matrices
Dario A. Bini, Beatrice Meini, Federico Poloni · CINECA IRIS Institutial research information system (University of Pisa) · 2009
Abstract. We consider a special instance of the algebraic Riccati equation XCX − XE − AX + B = 0 encountered in transport theory, where the n × n matrix coefficients A, B, C, E are rank structured matrices. The equation is reduced to unilateral form A2X 2 + A1X + A0X = 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 to get rid of the singularity. Numerical experiments and comparisons which confirm the effectiveness of the new approach are reported. Key words. Nonsymmetric algebraic Riccati equation, cyclic reduction, Cauchy matrix, matrix equation, fast algorithm, M-matrix. AMS subject classifications. 15A24, 65F05, 65H10 1. Introduction. The