ILAS2016 — 11–15 July 2016 — KU Leuven, Belgium

20th Conference of the International Linear Algebra Society (ILAS)

20th ILAS Conference

In minisymposium: Matrix Equations

Tue 17:00–17:30, Room AV 02.17
On the accelerated solution of dense matrix equations on modern hardware
Jens Saak (Max Planck Institute for Dynamics of Complex Technical Systems)
Joint work with Martin Köhler (Max Planck Institute for Dynamics of Complex Technical Systems)

The solution of dense Lyapunov equations has been considered a solved problem after the seminal paper by Bartels and Stewart. A number of variants of their algorithm have increased the efficiency by rearranging the operation. None of them goes beyond a BLAS level-2 formulation, though. The RECSY method follows a slightly different path using recursive subdivision into smaller problems. It can thus accelerate the solution process on many processors, but it has a rather irregular memory access pattern.

We present an formulation that uses BLAS level-3 calls after the reduction of the coefficients to Schur form. It can thus drastically accelerate the triangular solution phase compared to the BLAS level-2 methods. Our method acts as a wrapper around the existing solvers that are employed for solving the block problems. Using the RECSY solver as the inner method, we regularize its memory access pattern and thus get a notable acceleration also with respect to this solver.

For a single Lyapunov equation the runtime is dominated by the reduction to the Schur form. Therefore, the overall performance gain is limited. However, the gain can be increased, e.g, for the solution of autonomous differential matrix equations, or when the spectral divide and conquer method is used to accelerate the Schur reduction.