More accurate bidiagonal reduction for computing the singular value decomposition

DOI10.1137/S0895479898343541MaRDI QIDQ2784379zbMATH OpenFDO

Authors Jesse L. Barlow

Publication date 23 April 2002

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

Full work available at URL https://doi.org/10.1137/S0895479898343541

zbMATH Keywords

algorithmsbidiagonal reduction methoderror boundsGivens rotationsHouseholder factorization methodorthogonal reduction methodsingular value decomposition

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Numerical solutions to overdetermined systems, pseudoinverses (65F20)

Review text

As a preliminary stage for computing the singular value decomposition of a matrix \(A \in R^{m \times n}\) (\(m \geq n\)) the reduction of \(A\) to a bidiagonal form is discussed, i.e. one has to find orthogonal matrices \(U \in R^{n \times n}\) and \(V \in R^{m \times m}\) such that \(U^T A^T V = (B 0)\) with a bidiagonal \((n \times n)\) matrix \(B\). Then, several algorithms for computing the singular value decomposition of bidiagonal matrices are known. NEWLINENEWLINENEWLINEThe reduction algorithm consists of two steps. In the first step the matrix \(A\) is reduced to a lower triangular matrix \(C \in R^{n \times n}\) by using a Householder factorization method. In the second step a new bidiagonal reduction algorithm is applied to the matrix \(C\). In the new algorithm Givens rotations instead of Householder transformations are used in the construction of the right orthogonal transformation matrix. A detailed error analysis of the new algorithm is presented. The proposed algorithm allows to compute the singular value decomposition with more guaranteed accuracy than by standard bidiagonal reduction procedures.

Recommendations

• A new stable bidiagonal reduction algorithm
• Accurate Singular Values of Bidiagonal Matrices
• Efficient parallel reduction to bidiagonal form.
• Computing the Bidiagonal SVD Using Multiple Relatively Robust Representations
• The Bidiagonal Singular Value Decomposition and Hamiltonian Mechanics

Cited in

(19)

• Accurate ordering of eigenvectors and singular vectors without eigenvalues and singular values.
• A new stable bidiagonal reduction algorithm
• An \({\mathcal O}(n^{2})\) algorithm for the bidiagonal SVD
• One-sided reduction to bidiagonal form
• Reorthogonalization for the Golub-Kahan-Lanczos bidiagonal reduction
• Numerical methods for accurate computation of the eigenvalues of Hermitian matrices and the singular values of general matrices
• Improving the Accuracy of Computed Singular Values
• Accurate Singular Values of Bidiagonal Matrices
• scientific article; zbMATH DE number 18990 (Why is no real title available?)
• Reducing the Computations of the Singular Value Decomposition Array Given by Brent and Luk
• The Bidiagonal Singular Value Decomposition and Hamiltonian Mechanics
• The singular value decomposition: anatomy of optimizing an algorithm for extreme scale
• scientific article; zbMATH DE number 2163272 (Why is no real title available?)
• scientific article; zbMATH DE number 4001323 (Why is no real title available?)
• Growth factors of orthogonal matrices and local behavior of Gaussian elimination with partial and complete pivoting
• A contribution to the theory and practice of the block Kogbetliantz method for computing the SVD
• A QR-method for computing the singular values via semiseparable matrices
• Computation of exact inertia and inclusions of eigenvalues (singular values) of tridiagonal (bidiagonal) matrices
• The ERES method for computing the approximate GCD of several polynomials

This page was built for publication: More accurate bidiagonal reduction for computing the singular value decomposition

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