Lanczos vectors

I am trying to implement the Lanczos algorithm. If I implement it in Fortran or C, (i.e. in finite precision), will the vectors generated at each iteration still preserve their linear independence? Thanks.

Solutions Collecting From Web of "Lanczos vectors"

Absolutely not. Krylov vectors will quickly loose orthogonality. This applies to all Krylov-type processes, including Lanczos, Arnoldi, Golub-Kahan, Lanczos bi-orthogonalization, etc. That is the one major difficulty with all Krylov-type algorithms (CG, MINRES, GMRES, QMR, TFQMR, Bi-CGSTAB, Bi-CG, CGS, etc, etc.)

Most implementations make provision for a reorthogonalization procedure. Full reorthogonalization (i.e., against all previously-generated Krylov vectors) is not only very expensive, it has also been shown to be unnecessary. Partial reorthogonalization is a very popular alternative that comes in different forms. Your question is very far-reaching and the negative answer has too many implications to list. I recommend reading some of the following excellent books. They point to research paper where you can find more details.

  • G. Meurant, The Lanczos and Conjugate Gradient Algorithms: From Theory to Finite Precision Computations
  • Y. Saad, Iterative Methods for Sparse Linear Systems
  • C. T. Kelley, Iterative Methods for Linear and Nonlinear Equations
  • A. Greenbaum, Iterative Methods for Solving Linear Systems

Michael Saunders has excellent class notes at Stanford that summarize the state of the art:

In finite precision, there is already an important difference in the Arnoldi process depending on whether you implement the standard Gram-Schmidt update or the modified Gram-Schmidt update. For a quick overview, google “modified gram schmidt giraud langou” in Google Scholar.

They TEND to align — they don’t become completely parallel. By all means, you can use Gram-Schmidt orthogonalization. Dr. Underwood’s classic program on does exactly that.

Given the number of Lanczos programs available, why write another one? Look into ARPACK, underwood.f, or LASO2 for a good solution.