Open AccessOn the use of conjugate gradient to calculate the eigenvalues and singular values of large, sparse matrices
Author(s) -
Scales John A.
Publication year - 1989
Publication title -
geophysical journal international
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.302
H-Index - 168
eISSN - 1365-246X
pISSN - 0956-540X
DOI - 10.1111/j.1365-246x.1989.tb00494.x
Subject(s) - conjugate gradient method , eigenvalues and eigenvectors , mathematics , matrix (chemical analysis) , conjugate residual method , tridiagonal matrix , derivation of the conjugate gradient method , symmetric matrix , singular value decomposition , singular value , orthogonalization , biconjugate gradient method , linear algebra , gradient descent , algorithm , computer science , geometry , materials science , machine learning , artificial neural network , physics , quantum mechanics , composite material
Summary 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 times 400 matrix originating in seismic reflection tomography.