3
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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://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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – tiki
    Feb 7 '13 at 1:52
  • 2
    $\begingroup$ They loose both. In fact they can tend to all align. $\endgroup$
    – Dominique
    Feb 7 '13 at 2:12
1
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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