Recursive blocked algorithms for solving triangular systems—Part II: two-sided and generalized Sylvester and Lyapunov matrix equations

ABSTRACT

We continue our study of 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 novel 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 achieving high performance is 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, including the design of efficient new algorithms for two-sided matrix products. We present uniprocessor and SMP parallel performance results of recursive blocked algorithms and routines in the state-of-the-art SLICOT library. Although our recursive algorithms with optimized kernels for the two-sided matrix equations perform more operations, the performance improvements are remarkable, including 10-fold speedups or more, compared to standard algorithms.

REFERENCES

• 1: E. Anderson , Z. Bai , C. Bischof , L. S. Blackford , J. Demmel , Jack J. Dongarra , J. Du Croz , S. Hammarling , A. Greenbaum , A. McKenney , D. Sorensen, LAPACK Users' guide (third ed.), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 2: R. H. Bartels , G. W. Stewart, Solution of the matrix equation AX + XB = C [F4], Communications of the ACM, v.15 n.9, p.820-826, Sept. 1972 [doi>10.1145/361573.361582]
• 3: Chu, K.-W. E. 1987. The solution of the matrix equation AXB - CXD = Y and (YA − DZ, YC − BZ) = (E,F). Linear Algebra Appl. 93, 93--105.
• 4: Krister Dackland , Bo Kågström, Blocked algorithms and software for reduction of a regular matrix pair to generalized Schur form, ACM Transactions on Mathematical Software (TOMS), v.25 n.4, p.425-454, Dec. 1999 [doi>10.1145/332242.332244]
• 5: Judith D. Gardiner , Alan J. Laub , James J. Amato , Cleve B. Moler, Solution of the Sylvester matrix equation AXBT + CXDT = E, ACM Transactions on Mathematical Software (TOMS), v.18 n.2, p.223-231, June 1992 [doi>10.1145/146847.146929]
• 6: Judith D. Gardiner , Matthew R. Wette , Alan J. Laub , James J. Amato , Cleve B. Moler, Algorithm 705; a FORTRAN-77 software package for solving the Sylvester matrix equation AXBT + CXDT = E, ACM Transactions on Mathematical Software (TOMS), v.18 n.2, p.232-238, June 1992 [doi>10.1145/146847.146930]
• 7: Golub, G., Nash, S., and Van Loan, C. 1979. A Hessenberg--Schur method for the matrix problem AX + XB = C. IEEE Trans. Autom. Contr. AC-24, 6, 909--913.
• 8: Hager, W. W. 1984. Condition estimates. SIAM J. Sci. Stat. Comp. 5, 311--316.
• 9: Hammarling, S. J. 1982. Numerical solution of the stable, non-negative definite Lyapunov equation. IMA J. Numer. Anal. 2, 303--323.
• 10: Nicholas J. Higham, FORTRAN codes for estimating the one-norm of a real or complex matrix, with applications to condition estimation, ACM Transactions on Mathematical Software (TOMS), v.14 n.4, p.381-396, Dec. 1988 [doi>10.1145/50063.214386]
• 11: Higham, N. J. 1993. Perturbation theory and backward error for AX − XB = C. BIT 33, 124--136.
• 12: Jonsson, I. and Kågström, B. 2001. Recursive blocked algorithms for solving triangular matrix equations---Part II: Two-sided and generalized Sylvester and Lyapunov equations. SLICOT Working Note 2001-5. Department of Computing Science, Umeå University, SE-901 87 Umeå, Sweden.
• 13: Isak Jonsson , Bo Kågström, Recursive blocked algorithms for solving triangular systems—Part I: one-sided and coupled Sylvester-type matrix equations, ACM Transactions on Mathematical Software (TOMS), v.28 n.4, p.392-415, December 2002 [doi>10.1145/592843.592845]
• 14: Bo Kagstrom, A Perturbation Analysis of the Generalized Sylvester Equation $(AR - LB, DR - LE) = (C, F)$, SIAM Journal on Matrix Analysis and Applications, v.15 n.4, p.1045-1060, Oct. 1994 [doi>10.1137/S0895479893246212]
• 15: Bo Kågström , Peter Poromaa, LAPACK-style algorithms and software for solving the generalized Sylvester equation and estimating the separation between regular matrix pairs, ACM Transactions on Mathematical Software (TOMS), v.22 n.1, p.78-103, March 1996 [doi>10.1145/225545.225552]
• 16: Kågström, B. and Westin, L. 1989. Generalized Schur methods with condition estimators for solving the generalized Sylvester equation. IEEE Trans. Autom. Contr. 34, 4, 745--751.
• 17: Kressner, D., Mehrmann, V., and Penzl, T. 1999a. CTLEX---A collection of benchmark examples for continuous-time Lyapunov equations. SLICOT Working Note 1999--6.
• 18: Kressner, D., Mehrmann, V., and Penzl, T. 1999b. DTLEX---A collection of benchmark examples for discrete-time Lyapunov equations. SLICOT Working Note 1999--7.
• 19: Penzl, T. 1998. Numerical solution of generalized Lyapunov equations, Adv. Comp. Math. 8, 33--48.
• 20: SLICOT 2001. Library and the numerics in control network (NICONET) Web site: www.win. tue.nl/niconet/index.html.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Conditioning; Linear systems (direct and iterative methods)
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Parallel and vector implementations; Efficiency; Reliability and robustness

General Terms:
Algorithms, Design, Performance

Keywords:
GEMM-based, LAPACK, Matrix equations, SLICOT, SMP parallelization, automatic blocking, generalized Sylvester and Lyapunov, level-3 BLAS, recursion, standard discrete-time Sylvester and Lyapunov, superscalar