2
$\begingroup$

Suppose that we are given a random, symmetric matrix $A$, and a random vector $q$. For concreteness, assume the dimensions of $q$ and $A$ are both $1,000$. I would like to use the Lanczos algorithm to compute the tridiagonal matrix, $T$, which is uniquely defined by $A$ and $q$. I don't necessarily need access to the entirety of $T$, but I want to understand any systematic errors which appear in the algorithm due to finite-precision arithmetic.

So far, I have computed the first $100$ rows and columns of $T$ by two methods. The first uses high-precision arithmetic: I instantiate $A$ and $q$ with a huge number of digits of accuracy, and carry out the Lanczos algorithm as though numerical precision is effectively infinite. This should generate essentially exact results, and I have checked that orthogonality and normalization of Ritz vectors is maintained in this process. So far, so good.

My second approach uses standard machine precision, and in order to counter the loss of orthogonality among Ritz vectors, I explicitly re-orthogonalize each vector with respect to previously encountered vectors using the Gram-Schmidt procedure. I thought this would yield the same result as method (1), but in general it does not: I have found that after the first 50 or so iterations (this depends slightly on the initial matrix/vector), there is a significant divergence between the results of these two methods. I don't understand why this is the case; my understanding was that the loss of accuracy in the Lanczos algorithm was primarily attributable to the loss of orthogonality among these vectors.

So, my question: when is the tridiagonal matrix $T$, generated by standard precision arithmetic, reliable? Why isn't complete re-orthogonalization of the generated vectors sufficient?

$\endgroup$
4
  • $\begingroup$ I don't know for sure, but my suspicion is that you're effectively forced to use (classical) Gram-Schmidt, not modified, because all the "later" vectors are not yet known/available. I'd expect Lanczos+CGS to certainly do better than no orthogonalization whatsoever, but it too is ultimately an unstable algorithm. $\endgroup$ May 17, 2023 at 16:04
  • $\begingroup$ @rchilton1980 thanks for your comment. As for Lanczos+CGS being unstable, do you have a reference on that? I'm a little new to the subject and I was under the impression that this case would be stable, just painfully resource intensive. $\endgroup$
    – miggle
    May 17, 2023 at 16:55
  • 1
    $\begingroup$ Not for that specific combination of algorithms, not really. My claim/suspicion is rooted in the instability of CGS even just by itself (which Wikipedia elaborates, see en.wikipedia.org/wiki/… ). If you mash CGS with something else (ie Lanczos), I'd expect to encounter similar difficulties. $\endgroup$ May 17, 2023 at 17:43
  • $\begingroup$ Ah, I see. It's interesting because in the literature I've seen, it is often said that the use of CGS for re-orthogonalization is clearly sufficient. Most schemes are built around implementing it as little as possible, but ultimately uses CGS when necessary. I haven't seen discussion of modified GS at all in that context $\endgroup$
    – miggle
    May 18, 2023 at 15:09

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.