On the use of conjugate gradient to calculate the eigenvalues and singular values of large, sparse matrices
John A. Scales · Geophysical Journal International · 1989
Inverse problems such as tomography involve the solution of very large, sparse linear systems. This can be done efficiently using a variety of iterative techniques such as conjugate gradient or the row action methods. But these methods give no information about the spectrum of the matrix, which would be useful in analysing convergence and the reliability of the solution. On the other hand, direct orthogonalization methods such as SVD cause unacceptable fill in the matrix. the purpose of this note is to point out a result which is reasonably well known in the numerical linear algebra community but which does not appear to be appreciated by practitioners of inverse theory, namely that the intermediate results of the conjugate gradient algorithm can be used to generate a symmetric tridiagonalization of the underlying matrix. This tridiagonalization can be exploited to give an efficient algorithm for computing the eigenvalues of symmetric matrices or the singular values of arbitrary rectangular matrices, by computing the eigenvalues of the related symmetric tridiagonal matrix—taking full advantage of the sparsity. an example will be given of the computation of the singular values of a 1500 × 400 matrix originating in seismic reflection tomography.