article

Improving the performance of reduction to Hessenberg form

Authors:

Gregorio Quintana-Ortí,

Robert van de GeijnAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 32, Issue 2

Pages 180 - 194

https://doi.org/10.1145/1141885.1141887

Published: 01 June 2006 Publication History

Abstract

In this article, a modification of the blocked algorithm for reduction to Hessenberg form is presented that improves performance by shifting more computation from less efficient matrix-vector operations to highly efficient matrix-matrix operations. Significant performance improvements are reported relative to the performance achieved by the current LAPACK implementation.

References

[1]

Anderson, E., Bai, Z., Demmel, J., Dongarra, J. E., DuCroz, J., Greenbaum, A., Hammarling, S., McKenney, A. E., Ostrouchov, S., and Sorensen, D. 1999. LAPACK Users' Guide 3rd Ed. SIAM, Philadelphia, PA.

[2]

Bartels, R. and Stewart, G. 1972. Solution of the matrix equation AX + XB = C: Algorithm 432. Commun. ACM 15, 820--826.

[3]

Bientinesi, P., Gunnels, J. A., Myers, M. E., Quintana-Ortí, E. S., and van de Geijn, R. A. 2005. The science of deriving dense linear algebra algorithms. ACM Trans. Math. Soft. 31, 1, 1-- 26.

[4]

Bientinesi, P., Quintana-Ortí, E. S., and van de Geijn, R. A. 2005. Representing linear algebra algorithms in code: The FLAME APIs. ACM Trans. Math. Soft. 31, 1, 27--59.

[5]

Dongarra, J. J., Du Croz, J., Hammarling, S., and Duff, I. 1990. A set of level 3 basic linear algebra subprograms. ACM Trans. Math. Soft. 16, 1 (March), 1--17.

[6]

Dongarra, J. J., Du Croz, J., Hammarling, S., and Hanson, R. J. 1988. An extended set of FORTRAN basic linear algebra subprograms. ACM Trans. Math. Soft. 14, 1 (March), 1--17.

[7]

Dongarra, J. J., Hammarling, S. J., and Sorensen, D. C. 1989. Block reduction of matrices to condensed forms for eigenvalue computations. J. Comput. Appl. Math. 27.

[8]

Golub, G. H., Nash, S., and Van Loan, C. F. 1979. A Hessenberg--Schur method for the problem AX + XB = C. AC-24, 909--913.

[9]

Golub, G. H. and Van Loan, C. F. 1996. Matrix Computations, 3rd Ed. The Johns Hopkins University Press, Baltimore, MD.

[10]

Goto, K. 2004. http://www.cs.utexas.edu/users/kgoto.

[11]

Householder, A. S. 1958. Unitary triangularization of a nonsymmetric matrix. J. ACM 5, 339--42.

[12]

Joffrain, T., Low, T. M., Quintana-Ortí, E. S., van de Geijn, R., and Van Zee, F. G. 2006. On accumulating householder transformations. ACM Trans. Math. Soft. 32, 2, 169--179.

[13]

Martin, R. S. and Wilkinson, J. H. 1968. Similarity reduction of a general matrix to Hessenberg form. Numer. Math. 12, 349--68.

[14]

Puglisi, C. 1992. Modification of the householder method based on the compact wy representation. SIAM J. Sci. Stat. Comput. 13, 723--726.

[15]

Schreiber, R. and Van Loan, C. 1989. A storage-efficient WY representation for products of Householder transformations. SIAM J. Sci. Stat. Comput. 10, 1 (Jan.), 53--57.

[16]

Sima, V. 1996. Algorithms for Linear-Quadratic Optimization. Pure and Applied Mathematics, vol. 200. Marcel Dekker, Inc., New York, NY.

[17]

Walker, H. F. 1988. Implementation of the GMRES method using Householder transformations. SIAM J. Sci. Stat. Comput. 9, 1, 152--163.

[18]

Wilkinson, J. H. 1965. The Algebraic Eigenvalue Problem. Oxford University Press, Oxford, UK.

Cited By

Balasubramanian VMagan JWu Q(2023)Tridiagonalizing random matricesPhysical Review D10.1103/PhysRevD.107.126001107:12Online publication date: 6-Jun-2023
https://doi.org/10.1103/PhysRevD.107.126001
Balasubramanian VCaputa PMagan JWu Q(2022)Quantum chaos and the complexity of spread of statesPhysical Review D10.1103/PhysRevD.106.046007106:4Online publication date: 22-Aug-2022
https://doi.org/10.1103/PhysRevD.106.046007
Kågström BKressner DQuintana-Ortí EQuintana-Ortí G(2022)Blocked algorithms for the reduction to Hessenberg-triangular form revisited BIT10.1007/s10543-008-0180-148:3(563-584)Online publication date: 11-Mar-2022
https://dl.acm.org/doi/10.1007/s10543-008-0180-1
Show More Cited By

Index Terms

Improving the performance of reduction to Hessenberg form
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Linear algebra algorithms
2. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on matrices
  2. Mathematical software

Recommendations

Efficient eigenvalue and singular value computations on shared memory machines
Special issue on parallelization techniques for numerical modelling

We describe two techniques for speeding up eigenvalue and singular value computations on shared memory parallel computers. Depending on the information that is required, different steps in the overall process can be made more efficient. If only the ...
Block Gauss Reduction to Hessenberg Form

The latest developments in matrix software generally confine the block methods based on stabilized elementary (Gauss) transformations to the solution of linear equations, in a concern for numerical stability. For example, LAPACK relies entirely on ...
Orthogonal Hessenberg Reduction and Orthogonal Krylov Subspace Bases

We study necessary and sufficient conditions that a nonsingular matrix A can be B-orthogonally reduced to upper Hessenberg form with small bandwidth. By this we mean the existence of a decomposition AV=VH, where H is upper Hessenberg with few nonzero ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 32, Issue 2

June 2006

205 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/1141885

Issue’s Table of Contents

Copyright © 2006 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2006

Published in TOMS Volume 32, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
577
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)1

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Balasubramanian VMagan JWu Q(2023)Tridiagonalizing random matricesPhysical Review D10.1103/PhysRevD.107.126001107:12Online publication date: 6-Jun-2023
https://doi.org/10.1103/PhysRevD.107.126001
Balasubramanian VCaputa PMagan JWu Q(2022)Quantum chaos and the complexity of spread of statesPhysical Review D10.1103/PhysRevD.106.046007106:4Online publication date: 22-Aug-2022
https://doi.org/10.1103/PhysRevD.106.046007
Kågström BKressner DQuintana-Ortí EQuintana-Ortí G(2022)Blocked algorithms for the reduction to Hessenberg-triangular form revisited BIT10.1007/s10543-008-0180-148:3(563-584)Online publication date: 11-Mar-2022
https://dl.acm.org/doi/10.1007/s10543-008-0180-1
Myllykoski M(2021)Algorithm 1019: A Task-based Multi-shift QR/QZ Algorithm with Aggressive Early DeflationACM Transactions on Mathematical Software10.1145/349500548:1(1-36)Online publication date: 15-Dec-2021
https://dl.acm.org/doi/10.1145/3495005
Myllykoski MKjelgaard Mikkelsen C(2020)Task‐based, GPU‐accelerated and robust library for solving dense nonsymmetric eigenvalue problemsConcurrency and Computation: Practice and Experience10.1002/cpe.591533:11Online publication date: 6-Aug-2020
https://doi.org/10.1002/cpe.5915
Mohanty SSajith G(2019)An Input/Output Efficient Algorithm for Hessenberg ReductionInternational Journal of Foundations of Computer Science10.1142/S012905411950026630:08(1279-1300)Online publication date: 12-Dec-2019
https://doi.org/10.1142/S0129054119500266
Alonso PCatalán SHerrero JQuintana-Ortí ERodríguez-Sánchez R(2018)Two-sided orthogonal reductions to condensed forms on asymmetric multicore processorsParallel Computing10.1016/j.parco.2018.03.00578:C(85-100)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1016/j.parco.2018.03.005
Eljammaly MKarlsson LKågström B(2018)On the Tunability of a New Hessenberg Reduction Algorithm Using Parallel Cache AssignmentParallel Processing and Applied Mathematics10.1007/978-3-319-78024-5_50(579-589)Online publication date: 23-Mar-2018
https://doi.org/10.1007/978-3-319-78024-5_50
Trangenstein JTrangenstein J(2018)Eigenvalues and EigenvectorsScientific Computing10.1007/978-3-319-69107-7_1(1-201)Online publication date: 15-May-2018
https://doi.org/10.1007/978-3-319-69107-7_1
Jia YLuszczek PDongarra J(2016)Hessenberg Reduction with Transient Error Resilience on GPU-Based Hybrid Architectures2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)10.1109/IPDPSW.2016.34(653-662)Online publication date: May-2016
https://doi.org/10.1109/IPDPSW.2016.34
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents