Recursive blocked algorithms for solving triangular systems—Part I: one-sided and coupled Sylvester-type matrix equations

ABSTRACT

Triangular matrix equations appear naturally in estimating the condition numbers of matrix equations and different eigenspace computations, including block-diagonalization of matrices and matrix pairs and computation of functions of matrices. To solve a triangular matrix equation is also a major step in the classical Bartels--Stewart method for solving the standard continuous-time Sylvester equation (AX − XB = C). We present novel recursive blocked algorithms for solving one-sided triangular matrix equations, including the continuous-time Sylvester and Lyapunov equations, and a generalized coupled Sylvester equation. The main parts of the computations are performed as level-3 general matrix multiply and add (GEMM) operations. In contrast to explicit standard blocking techniques, our recursive approach leads to an automatic variable blocking that has the potential of matching the memory hierarchies of today's HPC systems. Different implementation issues are discussed, including when to terminate the recursion, the design of new optimized superscalar kernels for solving leaf-node triangular matrix equations efficiently, and how parallelism is utilized in our implementations. Uniprocessor and SMP parallel performance results of our recursive blocked algorithms and corresponding routines in the state-of-the-art libraries LAPACK and SLICOT are presented. The performance improvements of our recursive algorithms are remarkable, including 10-fold speedups 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: Z. Bai , James Demmel , A. McKenney, On computing condition numbers for the nonsymmetric eigenproblem, ACM Transactions on Mathematical Software (TOMS), v.19 n.2, p.202-223, June 1993 [doi>10.1145/152613.152617]
• 3: 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]
• 4: 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.
• 5: 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]
• 6: J. J. Dongarra , Jeremy Du Croz , Sven Hammarling , I. S. Duff, A set of level 3 basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.1-17, March 1990 [doi>10.1145/77626.79170]
• 7: J. J. Dongarra , Jermey Du Cruz , Sven Hammerling , I. S. Duff, Algorithm 679; a set of level 3 basic linear algebra subprograms: model implementation and test programs, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.18-28, March 1990 [doi>10.1145/77626.77627]
• 8: Erik Elmroth , Fred G. Gustavson, High-Performance Library Software for QR Factorization, Proceedings of the 5th International Workshop on Applied Parallel Computing, New Paradigms for HPC in Industry and Academia, p.53-63, June 18-20, 2000
• 9: 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]
• 10: 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]
• 11: 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.
• 12: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 13: F. G. Gustavson, Recursion leads to automatic variable blocking for dense linear-algebra algorithms, IBM Journal of Research and Development, v.41 n.6, p.737-756, Nov. 1997
• 14: Fred G. Gustavson , André Henriksson , Isak Jonsson , Bo Kågström , Per Ling, Recursive Blocked Data Formats and BLAS's for Dense Linear Algebra Algorithms, Proceedings of the 4th International Workshop on Applied Parallel Computing, Large Scale Scientific and Industrial Problems, p.195-206, June 14-17, 1998
• 15: Fred G. Gustavson , André Henriksson , Isak Jonsson , Bo Kågström , Per Ling, Superscalar GEMM-based Level 3 BLAS - The On-going Evolution of a Portable and High-Performance Library, Proceedings of the 4th International Workshop on Applied Parallel Computing, Large Scale Scientific and Industrial Problems, p.207-215, June 14-17, 1998
• 16: Gustavson, F. and Jonsson, I. 2000. Minimal-storage high-performance Cholesky factorization via blocking and recursion, IBM J. Res. Dev. 44, 6 (Nov.), 823--849.
• 17: Hager, W. W. 1984. Condition estimates. SIAM J. Sci. Stat. Comp. 5, 311--316.
• 18: Hammarling, S. J. 1982. Numerical solution of the stable, non-negative definite Lyapunov equation. IMA J. Numer. Anal. 2, 303--323.
• 19: 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]
• 20: Higham, N. J. 1993. Perturbation theory and backward error for AX -- XB = C. BIT 33, 124--136.
• 21: Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1996
• 22: Isak Jonsson , Bo Kågström, Parallel Triangular Sylvester-Type Matrix Equation Solvers for SMP Systems Using Recursive Blocking, Proceedings of the 5th International Workshop on Applied Parallel Computing, New Paradigms for HPC in Industry and Academia, p.64-73, June 18-20, 2000
• 23: Jonsson, I. and Kågström, B. 2001b. Recursive blocked algorithms for solving triangular matrix equations---Part I: One-sided and coupled Sylvester-type equations. SLICOT Working Note 2001-4. Dept. of Computing Science, Umeå University, SE-901 87 Umeå, Sweden.
• 24: Isak Jonsson , Bo Kågström, Recursive blocked algorithms for solving triangular systems—Part II: two-sided and generalized Sylvester and Lyapunov matrix equations, ACM Transactions on Mathematical Software (TOMS), v.28 n.4, p.416-435, December 2002 [doi>10.1145/592843.592846]
• 25: Kågström, B. 1977a. Bounds and perturbation bounds for the matrix exponential. BIT 17, 39--57.
• 26: Kågström, B. 1977b. Numerical computation of matrix functions. Tech. Rep. UMINF-58.77, Institute of Information Processing, Umeå University, S-901 87 Umeå , Sweden.
• 27: Kågström, B. 1993. A direct method for reordering eigenvalues in the generalized real Schur form of a regular matrix pair (A, B). In Linear Algebra for Large Scale and Real--Time Applications, Kluwer Academic, Amsterdam, 195--218.
• 28: 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]
• 29: Bo Kågström , Per Ling , Charles van Loan, GEMM-based level 3 BLAS: high-performance model implementations and performance evaluation benchmark, ACM Transactions on Mathematical Software (TOMS), v.24 n.3, p.268-302, Sept. 1998 [doi>10.1145/292395.292412]
• 30: Bo Kågström , Charles van Loan, Algorithm 784: GEMM-based level 3 BLAS: portability and optimization issues, ACM Transactions on Mathematical Software (TOMS), v.24 n.3, p.303-316, Sept. 1998 [doi>10.1145/292395.292426]
• 31: Bo Kågström , Peter Poromaa, Distributed and shared memory block algorithms for the triangular Sylvester equation with sep-1 estimators, SIAM Journal on Matrix Analysis and Applications, v.13 n.1, p.90-101, Jan. 1992 [doi>10.1137/0613009]
• 32: 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]
• 33: Kågström, B. and Poromaa, P. 1996b. Computing eigenspaces with specified eigenvalues of a regular matrix pair (A, B) and condition estimation. Numer. Alg. 12, 369--407.
• 34: Kågström, B. and Van Dooren, P. 1992. A generalized state-space approach for the additive decomposition of a transfer matrix. Int. J. Numer. Linear Algebra Appl. 1, 165--181.
• 35: 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.
• 36: Kressner, D., Mehrmann, V., and Penzl, T. 1999a. CTLEX---A collection of benchmark examples for continuous-time Lyapunov equations. SLICOT Working Note 1999-6.
• 37: Kressner, D., Mehrmann, V., and Penzl, T. 1999b. DTLEX---A collection of benchmark examples for discrete-time Lyapunov equations. SLICOT Working Note 1999-7.
• 38: Lindkvist, A. 2000. High-performance recursive BLAS kernels using new data formats for the QR factorization. Master's Thesis, Rep. UMNAD-325.00, Department of Computing Science, Umeå University, SE-901 87 Umeå, Sweden.
• 39: Moler, C. B. and Stewart, G. W. 1973. An algorithm for generalized matrix eigenvalue problems. SIAM J. Numer. Anal. 10, 241--256.
• 40: Moler, C. B. and Van Loan, C. F. 1978. Nineteen dubious ways to compute the exponential of a matrix. SIAM Rev. 20, 801--836.
• 41: Bradford Nichols , Dick Buttlar , Jacqueline Proulx Farrell, Pthreads programming, O'Reilly & Associates, Inc., Sebastopol, CA, 1996
• 42: OpenMP 2000. Fortran Application Program Interface, Version 2.0, November, www.openmp. org/specs/.
• 43: Penzl, T. 1998. Numerical solution of generalized Lyapunov equations. Adv. Comp. Math. 8, 33--48.
• 44: Poromaa, P. 1997. High performance computing: Algorithms and library software for Sylvester equations and certain eigenvalue problems with applications in condition estimation. PhD Thesis UMINF-97.16, Department of Computing Science, Umeå University, SE-901 87 Umeå, Sweden, June.
• 45: Peter Poromaa, Parallel Algorithms for Triangular Sylvester Equations: Design, Scheduling and Saclability Issues, Proceedings of the 4th International Workshop on Applied Parallel Computing, Large Scale Scientific and Industrial Problems, p.438-446, June 14-17, 1998
• 46: SLICOT 2001. Library and the numerics in control network (NICONET) Web site: www.win. tue.nl/niconet/index.html, Academic Press, San Diego, Calif.
• 47: Stewart, G. W. and Sun, J-G. 1990. Matrix Perturbation Theory. Academic, San Diego.
• 48: Sivan Toledo, Locality of Reference in LU Decomposition with Partial Pivoting, SIAM Journal on Matrix Analysis and Applications, v.18 n.4, p.1065-1081, Oct. 1997 [doi>10.1137/S0895479896297744]
• 49: Van Loan, C. F. 1977. The sensitivity of the matrix exponential. SIAM J. Numer. Anal. 14, 971--981.

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: Efficiency; Parallel and vector implementations; Reliability and robustness

General Terms:
Algorithms, Performance

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