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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.
Michael Saunders has excellent class notes at Stanford that summarize the state of the art: http://www.stanford.edu/class/msande318/notes.html
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 netlib.org 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.