𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Specialized Parallel Algorithms for Solving Lyapunov and Stein Equations

✍ Scribed by Enrique S. Quintana-Ortı́; Robert van de Geijn

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
215 KB
Volume
61
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

✦ Synopsis

Lyapunov and Stein matrix equations arise in many important analysis and synthesis 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 function and the squared Smith iteration which are highly efficient on parallel distributed computers. We also show that by coding using the Parallel Linear Algebra Package (PLAPACK) it is possible to exploit the structure in the matrices and reduce the cost of these solvers. While the performance improvements due to the optimizations are modest, so is the coding effort. One of the optimizations, the updating of a QR factorization, has important applications elsewhere, e.g., in applications requiring the solution of a linear least-squares problem when the linear system is periodically updated. The experimental results on a Cray T3E attest to the high efficiency of these parallel solvers.

📜 SIMILAR VOLUMES

Parallel adaptive wavefront algorithms s
Parallel adaptive wavefront algorithms solving Lyapunov equations for the Cholesky factor on message passing multiprocessors
✍ Claver, Jose M.; Hernandez, Vicente 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 123 KB 👁 2 views

The order of the matrices involved in several algebraic problems decreases during the solution process. In these cases, parallel algorithms which use adaptive solving block sizes offer better performance results than the ones obtained on parallel algorithms using traditional constant block sizes. Re

On Efficient Parallel Algorithms for Sol
On Efficient Parallel Algorithms for Solving Set Recurrence Equations
✍ O.H. Ibarra; H. Wang; T. Jiang 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 545 KB

We present two EREW PRAM algorithms and one CREW PRAM algorithm for solving set recurrence equations of the type commonly used in dynamic programming solutions to many problems in pattern matching, sequence comparison, and language recognition. All three algorithms run in \(O\left(\log ^{2} n\right)