start iteration in DGEEV from a user prescribed eigensystem

Post here if you have a question about LAPACK or ScaLAPACK algorithm or data format

start iteration in DGEEV from a user prescribed eigensystem

Postby mauvalora » Sun Apr 03, 2016 7:13 am

My research activity involves the development of solvers for stiff system of equations on the basis of explicit methods of numerical integration.
One bottleneck of my approach is the identification of the eigen-system at each integration time step, which is clearly a very computationally demanding task.
However, the set of eigenvectors varies smoothly with time.
Therefore, I am expecting that the convergence of any iterative method (power method, QR, …) to find the eigensystem might be enhanced if one could start the iterative procedure using the eigenvectors of the previous time step as first guess, as in a continuation method.

After many years of unsuccessful attempts to find any one routine (such as DGEEV) that will allow the user to prescribe the first guess, I eventually decided to invoke your expert advise on this regard.

My questions are:
1) in your experience, could you tell if the cost to find the eigensystem will indeed be lower if the initial guess is very close to the correct answer ?
2) do you know if there exists a routine (such as DGEEV), where one can prescribe the first guess in the iterative process to find the eigensystem of a certain matrix J ?
3) if such a routine does not exist yet, how difficult would be to modify DGEEV according to this my request?

I would really very much appreciate any help you could provide on this matter.
mauvalora
 
Posts: 1
Joined: Sun Apr 03, 2016 6:58 am

Re: start iteration in DGEEV from a user prescribed eigensys

Postby CyLith » Thu Apr 07, 2016 2:32 am

I have tested the idea of warm starting an eigenvalue solve with a previous solution (my case involved smoothly varying eigensolutions as well). I saw up to a 40% reduction in computation time when using ZGEEV. As far as I know, there is no plan to include such a feature in Lapack; I had to implement this myself by modifying the code directly. In my case, it was easier because I have a cleanly recoded version of the Lapack routine in C++ (with 0-based indexing, recursive functions, refactored functionality...) to base my modifications off of.

The basic interface is that the W vector is an inout parameter instead of being solely an output array. I added a parameter nguess for the number of entries in W that I wanted to use as warm-start values in the eigensolver. In the first iteration of each QR iteration, I pull a value out of W if there is one left to use as the initial shift value. This is tricky when there is Aggressive Early Deflation since you need to pass the guesses down to the AED sub-problem as well. The code structure in Fortran does not make this easy at all; you would need to modify ZLAQR0, ZLAQR3-5, as well as ZLAHQR (the non-AED, single shift variant).

It would be great if support for this were in the mainline codebase, but I just don't see anyone doing it. I certainly don't feel compelled to backport my changes to Fortran.
CyLith
 
Posts: 40
Joined: Sun Feb 08, 2009 7:23 am
Location: Stanford, CA


Return to Algorithm / Data

Who is online

Users browsing this forum: No registered users and 2 guests