Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
    
Thanks. I want to just make sure here, do you mean these vectors lose linearly independence or orthogonality? Because if they are not linearly independent, I can't apply Gram Schmidt kind algorithms, can I? –  tiki Feb 7 '13 at 1:52
1  
They loose both. In fact they can tend to all align. –  Dominique Feb 7 '13 at 2:12

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.

share|improve this answer
    
Thanks a lot!!! –  tiki Feb 10 '13 at 22:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.