# Reduction to condensed form¶

Computing the eigenvalues or singular values of a matrix, as a general rule,
boils down to an iterative procedure. Naive applications of this iterative
algorithm would often both require \(O(n^4)\) work for \(n \times n\)
matrices and be less numerically stable than first spending \(O(n^3)\) work
to *condense* the matrix to a form where each of roughly \(O(n)\) iterations
requires at most \(O(n^2)\) work. In the case of a full eigenvalue
decomposition of a Hermitian matrix, a similarity transformation composed of
Householder transformations is applied to condense the matrix down to
real symmetric tridiagonal form, where an iterative algorithm can be quickly
(read: in at most cubic time) applied.
Similarly, it is standard practice to condense a general matrix to bidiagonal
form in order to compute its Singular Value Decomposition, and to reduce a
general square matrix to upper Hessenberg form in order to compute its Schur
decomposition. In each of these cases, it is possible cast a significant portion
of the reduction to condensed form into high-performance
matrix-matrix multiplications [DSH1989].

## References¶

[DSH1989] | Jack J. Dongarra, Danny C. Sorensen, and Sven J. Hammarling, Block reduction of matrices to condensed forms for eigenvalue computations, Journal of Computational and Applied Mathematics, Vol. 27, Issues 1–2, pp. 215–227, 1989. DOI: http://dx.doi.org/10.1016/0377-0427(89)90367-1 |