A systolic algorithm for Riccati and Lyapunov equations (Q1122310)

An efficient algorithm is presented for solving the Lyapunov matrix equation \(A^ TP+PA+Q=0\) and the more general algebraic Riccati equation \(A^ TP+PA+Q-PBR^{-1}B^ TP=0\) under the assumptions \(Q>0\), \(R>0\). The solution is obtained using the recursive matrix sign function method in a modification which involves only symmetric matrices, constructed from the corresponding Hamiltonian matrix. An efficient systolic implementation of this algorithm is described which relies on the \(LDL^ T\) and \(UDU^ T\) decompositions of those symmetric matrices. The implementation differs from the earlier works by propagating two coupled factorizations simultaneously. As a result the solution can be obtained in O(n) time steps on a triangular grid of \(O(n^ 2)\) processors, leading to an optimal speedup. The algorithm may also perform on pipeline machines.