Simultaneous multidiagonalization for the CS decomposition
The authors deal with the simultaneous reduction of the four blocks of a two-by-two block partitioned orthogonal matrix to a desired low-bandwidth. A nice motivation from the standard simultaneous bidiagonalization method is presented. Notice that in such a case the input matrix is reduced to quasi-triangular form with Householder reflectors and Givens rotations. In the next step the fact that a quasi-triangular matrix orthogonal with positive diagonal entries is the identity matrix is used. Finally, the Givens rotations are inverted. By a diagonalization of the blocks, the CS decomposition is obtained. A new simultaneous multidiagonalization algorithm for such a decomposition is introduced. Its numerical backward stability is deduced. It is important to point out that this algorithm works with submatrices instead of individual entries, QR factorizations instead of single Householder reflectors, block Givens rotations instead of classical ones in such a way that, finally, banded forms are built. As a subproduct, the angles of the Givens rotations may prove to have analytic or geometric significance as the angles in the bidiagonal case reveal orthogonal polynomial recurrences, as in the case of CMV matrices which are banded orthogonal matrices representing the multiplication operator in terms of an orthonormal basis of Laurent polynomials (see [\textit{D. S. Watkins}, SIAM Rev. 35, No. 3, 430--471 (1993; Zbl 0786.65032)] and [\textit{B. Simon}, J. Comput. Appl. Math. 208, No. 1, 120--154 (2007; Zbl 1125.15027)] as well as the references therein). The algorithm relies heavily on Level 3 BLAS routines (specifically on the QR decomposition and matrix multiplication) opening new possible applications for cache utilization, parallel computation and restrained communication.
- scientific article; zbMATH DE number 1330401
- On Tridiagonalizing and Diagonalizing Symmetric Matrices with Repeated Eigenvalues
- Parallel reduction of banded matrices to bidiagonal form
- Computational Science – ICCS 2005
- Block reduction of matrices to condensed forms for eigenvalue computations
- A framework for symmetric band reduction
- Efficient parallel reduction to bidiagonal form.
- Block Gram-Schmidt orthogonalization
- scientific article; zbMATH DE number 3999132
- scientific article; zbMATH DE number 833711
- A Tangent Algorithm for Computing the Generalized Singular Value Decomposition
- Accelerating the SVD block-Jacobi method
- Accuracy and Stability of Numerical Algorithms
- CMV matrices: Five years after
- Communication-optimal parallel and sequential QR and LU factorizations
- Computing the complete CS decomposition
- Computing the CS and the generalized singular value decompositions
- Computing the CS decomposition of a partitioned orthonormal matrix
- Computing the Generalized Singular Value Decomposition
- Computing the Generalized Singular Value Decomposition
- Five-diagonal matrices and zeros of orthogonal polynomials on the unit circle
- History and generality of the CS decomposition
- Numerical Methods for Computing Angles Between Linear Subspaces
- On accurate quotient singular value computation in floating-point arithmetic
- On Positive Harmonic Functions: A Contribution to the Algebra of Fourier Series
- On the Perturbation of Pseudo-Inverses, Projections and Linear Least Squares Problems
- Schur parameter pencils for the solution of the unitary eigenproblem
- Some new bounds on perturbation of subspaces
- Some Perspectives on the Eigenvalue Problem
- Stable computation of the CS decomposition: Simultaneous bidiagonalization
- The beta-Jacobi matrix model, the CS decomposition, and generalized singular value problems
This page was built for publication: Simultaneous multidiagonalization for the CS decomposition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q398589)
