article

Accumulating Householder transformations, revisited

Authors:

Thierry Joffrain,

Tze Meng Low,

Enrique S. Quintana-Ortí,

Robert van de Geijn,

Field G. Van ZeeAuthors Info & Claims

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

Pages 169 - 179

https://doi.org/10.1145/1141885.1141886

Published: 01 June 2006 Publication History

Get Access

Abstract

A theorem related to the accumulation of Householder transformations into a single orthogonal transformation known as the compact WY transform is presented. It provides a simple characterization of the computation of this transformation and suggests an alternative algorithm for computing it. It also suggests an alternative transformation, the UT transform, with the same utility as the compact WY Transform which requires less computation and has similar stability properties. That alternative transformation was first published over a decade ago but has gone unnoticed by the community.

References

[1]

Bischof, C. and Van Loan, C. 1987. The WY representation for products of Householder matrices. SIAM J. Sci. Stat. Comput. 8, 1 (Jan.), 2--13.

Crossref

Google Scholar

[2]

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 (Mar.), 1--17.

Crossref

Google Scholar

[3]

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 (Mar.), 1--17.

Crossref

Google Scholar

[4]

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

Google Scholar

[5]

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

Crossref

Google Scholar

[6]

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

Crossref

Google Scholar

[7]

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.

Crossref

Google Scholar

[8]

Sun, X. 1996. Aggregations of elementary transformations. Tech. Rep. Tech. rep. DUKE-TR-1996-03, Duke University.

Crossref

Google Scholar

[9]

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

Crossref

Google Scholar

Cited By

View all

Carretero Perez JRodríguez-Sánchez RCastelló ACatalán SIgual FQuintana-Ortí E(2024)Experiences with nested parallelism in task-parallel applications using malleable BLAS on multicore processorsInternational Journal of High Performance Computing Applications10.1177/1094342023115765338:2(55-68)Online publication date: 10-Apr-2024
https://dl.acm.org/doi/10.1177/10943420231157653
Kaloorazi MLiu KChen Jde Lamare RRahardja S(2023)Randomized Rank-Revealing QLP for Low-Rank Matrix DecompositionIEEE Access10.1109/ACCESS.2023.328888911(63650-63666)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3288889
Hasegawa YImamura TIna TOnodera NAsahi YIdomura Y(2022)GPU Optimization of Lattice Boltzmann Method with Local Ensemble Transform Kalman Filter2022 IEEE/ACM Workshop on Latest Advances in Scalable Algorithms for Large-Scale Heterogeneous Systems (ScalAH)10.1109/ScalAH56622.2022.00007(10-17)Online publication date: Nov-2022
https://doi.org/10.1109/ScalAH56622.2022.00007
Show More Cited By

Index Terms

Accumulating Householder transformations, revisited
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

Quaternion singular value decomposition based on bidiagonalization to a real or complex matrix using quaternion Householder transformations

We present a practical and efficient means to compute the singular value decomposition (SVD) of a real or complex quaternion matrix A based on bidiagonalization of A to a real or complex bidiagonal matrix B using quaternionic Householder ...
Communication-optimal Parallel and Sequential QR and LU Factorizations

We present parallel and sequential dense QR factorization algorithms that are both optimal (up to polylogarithmic factors) in the amount of communication they perform and just as stable as Householder QR. We prove optimality by deriving new lower bounds ...
A Recursive Complex Householder Transformation Algorithm and its Applications
ICICTA '11: Proceedings of the 2011 Fourth International Conference on Intelligent Computation Technology and Automation - Volume 02

The paper put forwards a recursive complex matrix Householder transformation for transforming the complex matrix into upper triangle matrix. The fundamental complex matrix transformation is given firstly, then the recursive complex Householder ...

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

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

25
Total Citations
View Citations
810
Total Downloads

Downloads (Last 12 months)16
Downloads (Last 6 weeks)3

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Carretero Perez JRodríguez-Sánchez RCastelló ACatalán SIgual FQuintana-Ortí E(2024)Experiences with nested parallelism in task-parallel applications using malleable BLAS on multicore processorsInternational Journal of High Performance Computing Applications10.1177/1094342023115765338:2(55-68)Online publication date: 10-Apr-2024
https://dl.acm.org/doi/10.1177/10943420231157653
Kaloorazi MLiu KChen Jde Lamare RRahardja S(2023)Randomized Rank-Revealing QLP for Low-Rank Matrix DecompositionIEEE Access10.1109/ACCESS.2023.328888911(63650-63666)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3288889
Hasegawa YImamura TIna TOnodera NAsahi YIdomura Y(2022)GPU Optimization of Lattice Boltzmann Method with Local Ensemble Transform Kalman Filter2022 IEEE/ACM Workshop on Latest Advances in Scalable Algorithms for Large-Scale Heterogeneous Systems (ScalAH)10.1109/ScalAH56622.2022.00007(10-17)Online publication date: Nov-2022
https://doi.org/10.1109/ScalAH56622.2022.00007
Quintana-Ortí GChillarón MVidal VVerdú G(2022)High-performance reconstruction of CT medical images by using out-of-core methods in GPUComputer Methods and Programs in Biomedicine10.1016/j.cmpb.2022.106725218:COnline publication date: 1-May-2022
https://dl.acm.org/doi/10.1016/j.cmpb.2022.106725
Castelló ACatalán SIgual FQuintana-Ortí ERodríguez-Sánchez R(2022)QR Factorization Using Malleable BLAS on Multicore ProcessorsHigh Performance Computing. ISC High Performance 2022 International Workshops10.1007/978-3-031-23220-6_12(176-189)Online publication date: 29-May-2022
https://dl.acm.org/doi/10.1007/978-3-031-23220-6_12
Abdelfattah AAnzt HBoman ECarson ECojean TDongarra JFox AGates MHigham NLi XLoe JLuszczek PPranesh SRajamanickam SRibizel TSmith BSwirydowicz KThomas STomov STsai YYang U(2021)A survey of numerical linear algebra methods utilizing mixed-precision arithmeticInternational Journal of High Performance Computing Applications10.1177/1094342021100331335:4(344-369)Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.1177/10943420211003313
Tomás AQuintana-Ortí E(2020)Tall-and-skinny QR factorization with approximate Householder reflectors on graphics processorsThe Journal of Supercomputing10.1007/s11227-020-03176-376:11(8771-8786)Online publication date: 24-Jan-2020
https://dl.acm.org/doi/10.1007/s11227-020-03176-3
Świrydowicz KLangou JAnanthan SYang UThomas S(2020)Low synchronization Gram–Schmidt and generalized minimal residual algorithmsNumerical Linear Algebra with Applications10.1002/nla.234328:2Online publication date: 22-Oct-2020
https://doi.org/10.1002/nla.2343
Martinsson PQuintana-Ortí GHeavner N(2019)randUTVACM Transactions on Mathematical Software10.1145/324267045:1(1-26)Online publication date: 14-Mar-2019
https://dl.acm.org/doi/10.1145/3242670
Tomás ARodríguez-Sánchez RCatalán SCarratalá-Sáez RQuintana-Ortí E(2019)Dynamic look-ahead in the reduction to band form for the singular value decompositionParallel Computing10.1016/j.parco.2018.11.00181(22-31)Online publication date: Jan-2019
https://doi.org/10.1016/j.parco.2018.11.001
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.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Quaternion singular value decomposition based on bidiagonalization to a real or complex matrix using quaternion Householder transformations

Communication-optimal Parallel and Sequential QR and LU Factorizations

A Recursive Complex Householder Transformation Algorithm and its Applications

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations