Factorized solution of Lyapunov equations based on hierarchical matrix arithmetic
We investigate the numerical solution of large-scale Lyapunov equations with the sign function method. Replacing the usual matrix inversion, addition, and multiplication by formatted arithmetic for hierarchical matrices, we obtain an implementation that has linear-polylogarithmic complexity and memory requirements. The method is well suited for Lyapunov operators arising from FEM and BEM approximations to elliptic differential operators. With the sign function method it is possible to obtain a low-rank approximation to a full-rank factor of the solution directly. The task of computing such a factored solution arises, e.g., in model reduction based on balanced truncation. The basis of our method is a partitioned Newton iteration for computing the sign function of a suitable matrix, where one part of the iteration uses formatted arithmetic while the other part directly yields approximations to the full-rank factor of the solution. We discuss some variations of our method and its application to generalized Lyapunov equations. Numerical experiments show that the method can be applied to problems of order up to O(10(5)) on workstations.
lyapunov equation hierarchical matrices model reduction matrix sign function