Computing the complete CS decomposition

DOI10.1007/S11075-008-9215-6zbMATH Open1167.65360arXiv0707.1838OpenAlexW2132206191MaRDI QIDQ1014355FDOQ1014355

Authors: Brian D. Sutton 

Publication date: 27 April 2009

Published in: Numerical Algorithms (Search for Journal in Brave)

Abstract: An algorithm is developed to compute the complete CS decomposition (CSD) of a partitioned unitary matrix. Although the existence of the CSD has been recognized since 1977, prior algorithms compute only a reduced version (the 2-by-1 CSD) that is equivalent to two simultaneous singular value decompositions. The algorithm presented here computes the complete 2-by-2 CSD, which requires the simultaneous diagonalization of all four blocks of a unitary matrix partitioned into a 2-by-2 block structure. The algorithm appears to be the only fully specified algorithm available. The computation occurs in two phases. In the first phase, the unitary matrix is reduced to bidiagonal block form, as described by Sutton and Edelman. In the second phase, the blocks are simultaneously diagonalized using techniques from bidiagonal SVD algorithms of Golub, Kahan, and Demmel. The algorithm has a number of desirable numerical features.

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

Recommendations

• Stable computation of the CS decomposition: Simultaneous bidiagonalization
• Simultaneous multidiagonalization for the CS decomposition
• History and generality of the CS decomposition
• Computing the Generalized Singular Value Decomposition
• Divide and conquer the CS decomposition

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Factorization of matrices (15A23) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Numerical solutions to overdetermined systems, pseudoinverses (65F20)

Cites Work

• LAPACK Users' Guide
• The Rotation of Eigenvectors by a Perturbation. III
• Title not available (Why is that?)
• On the Perturbation of Pseudo-Inverses, Projections and Linear Least Squares Problems
• Calculating the Singular Values and Pseudo-Inverse of a Matrix
• Singular value decomposition and least squares solutions
• Some Perspectives on the Eigenvalue Problem
• Accurate Singular Values of Bidiagonal Matrices
• The beta-Jacobi matrix model, the CS decomposition, and generalized singular value problems
• Towards a Generalized Singular Value Decomposition
• History and generality of the CS decomposition
• Computing the CS decomposition of a partitioned orthonormal matrix
• Accelerating the SVD block-Jacobi method
• Computing the Generalized Singular Value Decomposition
• Computing the Generalized Singular Value Decomposition
• Some new bounds on perturbation of subspaces
• Computing the CS and the generalized singular value decompositions

Cited In (15)

• Simultaneous multidiagonalization for the CS decomposition
• A Backward Stable Algorithm for Computing the CS Decomposition via the Polar Decomposition
• History and generality of the CS decomposition
• Computing the CS and the generalized singular value decompositions
• An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian Simulation
• Quantum games: a review of the history, current state, and interpretation
• A note on factoring unitary matrices
• Large deviations and a new sum rule for spectral matrix measures of the Jacobi ensemble
• Quantum circuits synthesis using Householder transformations
• A canonical CS representation of a pair of subspaces
• Stable computation of the CS decomposition: Simultaneous bidiagonalization
• \(Qcompiler\): quantum compilation with the CSD method
• A CS decomposition for orthogonal matrices with application to eigenvalue computation
• Synthesis of quantum circuits based on supervised learning and correlations
• Unitary matrix decompositions for optimal and modular linear optics architectures

Uses Software

• LAPACK
• CLAPACK

This page was built for publication: Computing the complete CS decomposition

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