Simultaneous multidiagonalization for the CS decomposition (Q398589)

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.