Specialized parallel algorithms for solving Lyapunov and Stein equations

Lyapunov and Stein matrix equations arise in many important analysis and sy nthesis applications in control theory. The traditional approach to solving these equations relies on the QR algorithm which is notoriously difficult to parallelize. We investigate iterative solvers based on the matrix sign f unction and the squared Smith iteration which are highly efficient on paral lel distributed computers. We also show that by coding using the Parallel L inear Algebra Package (PLAPACK) it is possible to exploit the structure in the matrices and reduce the cost of these solvers. While the performance im provements due to the optimizations are modest, so is the coding effort. On e of the optimizations, the updating of a QR factorization, has important a pplications elsewhere, e.g., in applications requiring the solution of a li near least-squares problem when the linear system is periodically updated. The experimental results on a Cray T3E attest to the high efficiency of the se parallel solvers. (C) 2001 Academic Press.