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(105) on
desktop computers.
In this paper a method for solving large-scale Sylvester equations is presented. The method is based on the sign function iteration and is particularly
effective for Sylvester equations with factorized right-hand side. In this case, the solution will be computed in factored form as it is for instance required in model reduction.
The hierarchical matrix format and the corresponding formatted arithmetic is integrated in the iteration scheme to make the method feasible for large-scale computations.