12. Orthogonal Matrix Factoring

This chapter is about orthogonal methods used to factor matrices. The properties of diagonal, triangular, or unitary matrix factors can simplify how a problem is solved. Numerically stable orthogonal matrix factoring algorithms trim matrices to a desired shape with unitary transformation matrices that set specified matrix elements to zero by multiplication. The factors are the trimmed matrix and products of the unitary transformation matrices, which are Givens rotation and Householder reflection matrices. This chapter describes the unitary transformation matrices and their use in factoring algorithms. Algorithms that factor matrices with the eigendecomposition and the singular value decomposition are described along with implementations. Some of the history associated with the origins of orthogonal matrix factoring and how the eigenvalue problem was solved is covered in History of the Eigenvalue Problem.

Contents

• 12.1. Matrix Factorizations
• 12.2. Unitary Transformation Matrices
  • 12.2.1. Givens Rotation Matrices
  • 12.2.2. Householder Reflection Matrices
  • 12.2.3. Numerical Stability
• 12.3. QR Decomposition
• 12.4. The Solution to the Eigenvalue Problem
  • 12.4.1. Similarity Transformations
  • 12.4.2. Diagonalization Strategy
  • 12.4.3. Hessenberg Decomposition
  • 12.4.4. Schur Decomposition
  • 12.4.5. Schur Decomposition of Symmetric Matrices
  • 12.4.6. Iterative QR Algorithm
  • 12.4.7. The eigQR Function
  • 12.4.8. The eig22 Function
  • 12.4.9. Iterative Francis Algorithm
  • 12.4.10. The eigFrancis Function
  • 12.4.11. Convergence by Similarity Transforms
  • 12.4.12. Eigenvectors Following the Schur Decomposition
  • 12.4.13. Testing Eigensystem Correctness
• 12.5. Calculating the SVD with Unitary Transformations
  • 12.5.1. Golub–Kahan 1965
  • 12.5.2. Bidiagonal Decomposition
  • 12.5.3. Golub–Reinsch 1970
  • 12.5.4. Demmel–Kahan 1990