A Householder-Based Algorithm for Hessenberg-Triangular Reduction

DOI10.1137/17M1153637MaRDI QIDQ4584921zbMATH OpenOpenAlexWikidataFDO

Authors Zvonimir Bujanović, Daniel Kressner, Lars Karlsson

Publication date 5 September 2018

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1710.08538

zbMATH Keywords

Householder reflectorsiterative refinementHessenberg-triangular reduction

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Factorization of matrices (15A23) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Matrix pencils (15A22)

Abstract: The QZ algorithm for computing eigenvalues and eigenvectors of a matrix pencil $A-lambdaB$ requires that the matrices first be reduced to Hessenberg-triangular (HT) form. The current method of choice for HT reduction relies entirely on Givens rotations regrouped and accumulated into small dense matrices which are subsequently applied using matrix multiplication routines. A non-vanishing fraction of the total flop count must nevertheless still be performed as sequences of overlapping Givens rotations alternately applied from the left and from the right. The many data dependencies associated with this computational pattern leads to inefficient use of the processor and poor scalability. In this paper, we therefore introduce a fundamentally different approach that relies entirely on (large) Householder reflectors partially accumulated into block reflectors, by using (compact) WY representations. Even though the new algorithm requires more floating point operations than the state of the art algorithm, extensive experiments on both real and synthetic data indicate that it is still competitive, even in a sequential setting. The new algorithm is conjectured to have better parallel scalability, an idea which is partially supported by early small-scale experiments using multi-threaded BLAS. The design and evaluation of a parallel formulation is future work.

Recommendations

• Algorithms for Hessenberg-triangular reduction of Fiedler linearization of matrix polynomials
• Restructuring the tridiagonal and bidiagonal QR algorithms for performance
• scientific article; zbMATH DE number 7640509
• The periodic QR algorithm is a disguised QR algorithm
• Algorithm 1019: A Task-based Multi-shift QR/QZ Algorithm with Aggressive Early Deflation
• A parallel implementation of the QR-algorithm
• ON A BLOCK IMPLEMENTATION OF HESSENBERG MULTISHIFT QR ITERATION
• Solving the generalized eigenvalue problem on a synchronous linear processor array
• Implicit QR for companion-like pencils
• A multi-phase parallel algorithm for the eigenelements problem

Cites work

• scientific article; zbMATH DE number 6159604 (Why is no real title available?)
• A Householder-Based Algorithm for Hessenberg-Triangular Reduction
• A Storage-Efficient WY Representation for Products of Householder Transformations
• A framework for symmetric band reduction
• A novel parallel QR algorithm for hybrid distributed memory HPC systems
• A parallel QZ algorithm for distributed memory HPC systems
• Accuracy and Stability of Numerical Algorithms
• An Algorithm for Generalized Matrix Eigenvalue Problems
• Balanced Truncation Model Reduction for a Class of Descriptor Systems with Application to the Oseen Equations
• Block reduction of matrices to condensed forms for eigenvalue computations
• Blocked algorithms for the reduction to Hessenberg-triangular form revisited
• Improving the performance of reduction to Hessenberg form
• Multishift Variants of the QZ Algorithm with Aggressive Early Deflation
• Parallel two-stage reduction to Hessenberg form using dynamic scheduling on shared-memory architectures
• Performance of the QZ algorithm in the presence of infinite eigenvalues
• Surveys in differential-algebraic equations IV
• The WY Representation for Products of Householder Matrices
• The multishift QR algorithm. II: Aggressive early deflation

Cited in

(9)

• Blocked algorithms for the reduction to Hessenberg-triangular form revisited
• Hyperbolic Householder Algorithms for Factoring Structured Matrices
• scientific article; zbMATH DE number 7640509 (Why is no real title available?)
• Parallel two-stage reduction to Hessenberg-triangular form
• A Householder-Based Algorithm for Hessenberg-Triangular Reduction
• Algorithms for Hessenberg-triangular reduction of Fiedler linearization of matrix polynomials
• scientific article; zbMATH DE number 2089175 (Why is no real title available?)
• A Hessenberg Reduction Algorithm for Rank Structured Matrices
• Accurate computation of generalized eigenvalues of regular SR-BP pairs

Describes a project that uses

Uses Software

• benchmodred
• ELPA
• mctoolbox

This page was built for publication: A Householder-Based Algorithm for Hessenberg-Triangular Reduction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4584921)