Isak Jonsson and Bo Kågström

SLICOT Working Note 2001-5: September 2001.

We continue our study on high-performance algorithms for solving triangular matrix equations. They appear naturally in different condition estimation problems for matrix equations and various eigenspace computations, and as reduced systems in standard algorithms. Building on our successful recursive approach applied to one-sided matrix equations (Part I), we now present recursive blocked algorithms for two-sided matrix equations, which include matrix product terms such as AXB T . Examples are the discrete-time standard and generalized Sylvester and Lyapunov equations. The means for high-performance are the recursive variable blocking, which has the potential of matching the memory hierarchies of today's high-performance computing systems, and level 3 computations which mainly are performed as GEMM operations. Different implementation issues are discussed, focusing on similarities and differences between one-sided and two-sided matrix equations. We present uniprocessor and SMP parallel performance results of recursive blocked algorithms and routines in the state-of-the-art SLICOT library. The performance improvements of our recursive algorithms are remarkable, including 10-folded speedups or more, compared to standard algorithms.