-
Notifications
You must be signed in to change notification settings - Fork 126
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Lanczos Restarting question #146
Comments
Hi @peekxc, sorry for the late reply. I was not able to get the time looking at the issues here. Let me try to understand your question. Basically you want to compute all eigenvalues of a sparse matrix with only |
Yes. I was confused at the time as the material I was reading suggested this was possible, but none of the Lanczos software I could find seemed to support this, which I thought seemed like a huge discrepancy. I ended up finding PRIMME actually achieves this with variations of the Jacobi-Davidson method; you can set parameters like maxBasisSize |
Right. The reason is that implicitly restarted Arnoldi/Lanczos algorithm is a Krylov space method, and the restart needs to maintain the upper Hessenberg (or tridiagonal in the Lanczos case) structure of the Jacobi-Davidson no longer maintains the upper Hessenberg structure of the In my experience, the |
Right I realize most people just require a few eigenvalues but I encountered a situation where I needed to estimate all of the non-zero eigenvalues (but not the eigenvectors) of a nearly-full-rank
Yes I've had quite a difficult time figuring out how to adjust the hyper-parameters to keep them competitive time-wise with direct methods or with the ARPACK implementation (e.g. havent had any luck with preconditioning, really). Nonetheless, it seems if the |
Hi @yixuan,
I'm trying to understand the Lanczos method, mostly via Golub & Van Loan's Matrix Computations and various other articles.
Following this breakdown, my understanding is that the basic Lanczos (Algorithm 1) can compute the full spectrum of eigenvalues of a (n x n) sparse symmetric matrix using just O(n) workspace memory via the three-term recurrence, but only in exact arithmetic. That reference calls the 3-term-recurrence approach local orthogonalization.
Rounding errors that occur in the eigenvalue estimation procedure are due to loss of orthogonality in the Lanczos vectors, so we must either use more Lanczos vectors or some other means of retaining orthogonality using finite-precision arithmetic. Reorthogonalization via every Lanczos vector is possible, but this implies an O(n^2) memory overhead per-iteration. Other approaches seem to include, but are not limited to, block-Lanczos methods which effectively use O(nb) memory, polynomial filtering schemes, and the so-called implicit restart scheme used here.
I'm wondering whether it's possible to use Spectra (or ARPACK) to do either an explicit restart-like scheme, similar to Algorithm 4 from here, or possibly the O(nb) block Lanczos approach. Essentially, I want to have the ability to fix the number of Lanczos vectors used to acquire the Ritz values. Both Spectra and e.g. the SciPy port of ARPACK has a parameter option
ncv
, but it must be larger than the number of requested eigenvalues! I'm would like to be able to fix some valuek
, such that the implementation doesn't exceed O(nk) memory, at the possible sacrifice of needing more iterations to obtain alln
eigenvalues up totol
precision.Is this possible to do in Spectra, possibly via some loop that uses a shift-and-invert solver?
EDIT: To give more context, I know that shifting can be used obtain eigenvalues in the vicinity of the chosen shift. For example, if I wanted an iterative-solver-based approach to obtaining the full spectrum of some psd matrix that used at most
k=2
lanczos vectors, I could use something like:But of course the shifts were chosen manually here, and I'm sure there exists better ways of doing this. It seems quite similar to the explicit restart method that partitions the lanczos vectors into "locked" and "active" sets, but it's not clear to me how everything connects together. Do you have any good references on this? Or is the ability to do this already embedded in spectra, just not at the interface level?
The text was updated successfully, but these errors were encountered: