Abstract
We present recursive blocked algorithms for solving triangular Sylvester-type matrix equations. Recursion leads to automatic blocking that is variable and “squarish”. The main part of the computations are performed as level 3 general matrix multiply and add (GEMM) operations. We also present new highly optimized superscalar kernels for solving small-sized matrix equations stored in level 1 cache. Hereby, a larger part of the total execution time will be spent in GEMM operations. In turn, this leads to much better performance, especially for small to medium-sized problems, and improved parallel effciency on shared memory processor (SMP) systems. Uniprocessor and SMP parallel performance results are presented and compared with results from existing LAPACK routines for solving this type of matrix equations.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
E. Anderson, Z. Bai, J. Demmel, J. Dongarra, J. DuCroz, A. Greenbaum, S. Ham-marling, A. McKenny, S. Ostrouchov, and D. Sorensen LAPACK Users Guide, Third Edition. SIAM Publications, 1999.
E. Elmroth and F. Gustavson. New Serial and Parallel Recursive QRFactoriza-tion Algorithms for SMP Systems, In Kågström et al. (eds), Applied Parallel Computing, PARA’98, Lecture Notes in Computer Science, Vol. 1541, pp 120–128, Springer-Verlag, 1998.
E. Elmroth and F. Gustavson. Applying Recursion to Serial and Parallel QR Facto-rization Leads to Better Performance. IBM Journal of Research and Development, 44, No. 4, 605–624, 2000.
F. Gustavson. Recursion leads to automatic variable blocking for dense linear algebra. IBM J. Res. Develop, 41(6):737–755, November 1997.
F. Gustavson, A. Henriksson, I. Jonsson, B. Kågström and P. Ling. Recursive Blocked Data Formats and BLAS’s for Dense Linear Algebra Algorithms. In Kågström et al. (eds), Applied Parallel Computing, PARA’98, Lecture Notes in Computer Science, Vol. 1541, pp 195–206, Springer-Verlag, 1998.
F. Gustavson, A. Henriksson, I. Jonsson, B. Kågström and P. Ling. Supers-calar GEMM-based Level 3 BLAS-The On-going Evolution of a Portable and High-Performance Library. In Kågström et al. (eds), Applied Parallel Computing, PARA’98, Lecture Notes in Computer Science, Vol. 1541, pp 207–215, Springer-Verlag, 1998.
B. Kågström, P. Ling, and C. Van Loan. GEMM-based level 3 BLAS: High-performance model implementations and performance evaluation benchmark. ACM Trans. Math. Software, 24(3):268–302, 1998.
B. Kågström, P. Ling, and C. Van Loan. GEMM-based level 3 BLAS: Portability and optimization issues. ACM Trans. Math. Software, 24(3):303–316, 1998.
B. Kågström and P. Poromaa. Distributed and Shared Memory Block Algorithms for the Triangular Sylvester Equation with sep −1 Estimator. SIAM Journal on Matrix Analysis and Application, 13(1):90–101, January 1992.
B. Kågström and P. Poromaa. LAPACK-Style Algorithms and Software for Solving the Generalized Sylvester Equation and Estimating the Separation between Regular Matrix Pairs. ACM Trans. Math. Software, 22(1):78–103, March 1996.
B. Kågström and P. Poromaa. Computing Eigenspaces with Specified Eigenvalues of a Regular Matrix Pair (A;B) and Condition Estimation: Theory, Algorithms and Software. Numerical Algorithms, 12:369–407, 1996.
B. Kågström and L. Westin. Generalized Schur methods with condition estimators for solving the generalized Sylvester equation. IEEE Trans. Autom. Contr., 34(4):745–751, 1989.
P. Poromaa. Parallel Algorithms for Triangular Sylvester Equations: Design, Scheduling and Scalability Issues. In Kågström et al. (eds), Applied Parallel Computing, PARA’98, Lecture Notes in Computer Science, Vol. 1541, pp 438–446, Springer-Verlag, 1998.
G.W. Stewart and J-G. Sun. Matrix Perturbation Theory. Academic Press, 1990.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jonsson, I., Kågström, B. (2001). Parallel Triangular Sylvester-Type Matrix Equation Solvers for SMP Systems Using Recursive Blocking. In: Sørevik, T., Manne, F., Gebremedhin, A.H., Moe, R. (eds) Applied Parallel Computing. New Paradigms for HPC in Industry and Academia. PARA 2000. Lecture Notes in Computer Science, vol 1947. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-70734-4_10
Download citation
DOI: https://doi.org/10.1007/3-540-70734-4_10
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41729-3
Online ISBN: 978-3-540-70734-9
eBook Packages: Springer Book Archive