Matrix Decompositions

I recently read G. W. Stewart's perspective "Decompositional Approach to Matrix Computations" published in Computing in Science in Engineering (2000).

He extols the virtues of this approach:

• matrix decompositions solve many problems;
• they are expensive to compute the first time, but can often be reused;
• it facilitates rounding error analysis;
• it fosters the development of general-purpose linear algebra software packages.

He goes on to describe six of the most famous matrix decompositions in his paper. Let me focus on the history of three of those six. It is interesting that much of the work on decomposition of matrices predates the relatively recent emergence of matrix algebra, which was fostered by digital computers.

1. Cholesky

For a positive definite matrix, \[A = LL^T.\] The legendary German mathematician Carl Friedrich Gauss (1777-1855) sketched out a method in 1809-1810.  It was more than  a century later that Andre-Louis Cholesky's variant was published posthumously by Benoit in 1924. Interestingly, Cholesky was a French military officer and mathematician, who used the decomposition in some of his surveying work, and Benoit was a fellow officer.

The closely related generalization, pivoted LU decomposition (\(PA = LU\)) has a more obscure history, although it does appear in Jacobi's work by 1857. Interestingly, pathological cases can be designed for which Gauss elimination with partial pivoting (the most popular strategy for LU decomposition) is unstable. However, the method works with remarkable versatility for most real-life problems, although why it is so successful is not completely understood.

2. QR decomposition

The QR decomposition, \[A = QR,\] first arose in early 1900 work on integral equations by Erhard Schmidt, a Baltic-German mathematician of the "Gram-Schmidt" orthogonalization fame. Alston Householder's method to triangularize a matrix using his namesake transformations was published in 1958, while Givens published  "Computation of plane unitary rotations transforming a general matrix to triangular form", also in 1958.

Both of them were at Oak Ridge National Laboratory around the time they made their seminal contributions. Incidentally, not only did their work on QR decomposition appear in same year (1958), they both also died in the same year (1993) 35 years later.

3. SVD

The singular value decomposition \[A = U \Sigma V^{T},\] can be thought of as a generalization of the spectral decomposition of symmetric matrices. Apparently, the SVD has a longer traceable history than the QR decomposition; it was introduced independently by Beltrami and Jordan in the mid 1870s. As Stewart says,

Together, Beltrami are Jordan are the progenitors of the SVD, Beltrami by virtue of first publication, and Jordan by the completeness and elegance of his treatment.

In 1965, Golub and Kahan published the reduction to the bidiagonal form. In a subsequent paper in 1970, Golub and Reinsch presented the (currently) most popular computational algorithm to perform SVD.