2
$\begingroup$

Suppose that we are given a large, real-symmetric matrix $L$, which is simply too large to perform exact diagonalization on numerically. If we want to study its spectrum, one tool we can use is the Lanczos algorithm. This algorithm takes $L$ and an initial vector, call it $q_0$, and uses $q_0$ to produces a tridiagonal representation of $L$. A clear review of the algorithm is available on wikipedia. Call the orthonormal basis which spans this subspace the "Lanczos basis" with respect to $q_0$. Usually, this tridiagonal form and the Lanczos basis are just byproducts produced along the way towards computing eigenvalues of $L$.

I am in the strange position where my goal is to invert this procedure. For my problem, $L$ is a very large matrix that I happen to have good analytic control over, so I can compute its eigenvalues and eigenvectors by hand. My question is, is it possible to use this knowledge to efficiently construct the Lanczos basis and corresponding tridiagonalization of $L$ with respect to (a given but in principle arbitrary) $q_0$?

It's hard to imagine that knowledge of the complete spectrum doesn't give a computational advantage, but so far I have not been able to figure out how to use it. It's an unfortunate position to be in, because the Lanczos algorithm suffers from severe numerical stability issues and I would rather avoid running it; there should be a basis transformation which relates the Lanczos basis of $L$ with respect to $q_0$ to its eigenspace, but I don't know how to construct it. Any ideas from linear algebra practitioners?

Edit: It was asked in the comments (1) if the initial Lanczos vector is fixed or arbitrary and (2) what exactly is needed from the output of my computations. The initial Lanczos vector (call it $q_0$) I'll look at will depend on the precise application, but I think it's sufficiently generic to consider the case where $q_0$ is not an eigenvector of $L$.

As for the output that I need, what I am ultimately after are the off-diagonal elements of $L$ when it is put in tridiagonal form. That is, I don't need specific knowledge of the Lanczos basis per se, only the elements of $L$ in that basis. If that makes things simpler, that's great, I just don't see how we could get one without the other.

Edit 2: There has been some confusion over what constitutes a valid tridiagonal form; as pointed out in the comments, all diagonal matrices are tridiagonal. I have clarified my question above to emphasize that I am after the Lanczos basis with respect to a particular vector, $q_0$. This uniquely specifies a tridiagonal form of $L$, but unless $q_0$ happens to be an eigenvector of $L$, the eigenspace of $L$ is not a valid Lanczos basis of $L$ with respect to $q_0$.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ To compute a Lanczos basis you also need a starting vector (usually called $b$ or $q_0$. Do you have the freedom to choose that, or is it given? $\endgroup$
    – Federico Poloni
    Mar 24 at 13:34
  • 1
    $\begingroup$ Also, obligatory question: what do you need the Lanczos basis for? Maybe there is a better way to compute what you need without involving Lanczos at all. $\endgroup$
    – Federico Poloni
    Mar 24 at 13:34
  • 1
    $\begingroup$ Right, good points, I'll add edits to address them. My application will eventually fix a particular vector to start with, but for now let's just assume that $q_0$ is not an eigenvector of $L$. Also, what I need out of this are the off-diagonal elements of $L$ following tridiagonalization. I don't actually need the Lanczos basis itself, but it's hard to imagine getting one without the other. $\endgroup$
    – miggle
    Mar 24 at 13:40
  • 1
    $\begingroup$ If you know all eigenvectors and -values, why would you want the Lanczos basis? There isn't a thing you can't do if you have the eigen-decomposition of the matrix. $\endgroup$
    – Wolfgang Bangerth
    Mar 24 at 17:09
  • 1
    $\begingroup$ @hardmath thanks for the comment. I thought it would be clear from context, but this point has led me to clarify what constitutes a valid Lanczos basis; see the edit and reframed question above. The punchline: you're right that the eigenspace is a Lanczos basis, but only with respect to initial vectors which happen to be eigenvectors of $L$. $\endgroup$
    – miggle
    Mar 27 at 0:35

0

Reset to default

Your Answer

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