Eigenvector solver implementation

[maddyscientist]

QUDA is sorely lacking an eigenvector solver. We need to investigate what type of solver is most appropriate for including in QUDA. What are the relative merits of Ritz and Lanczos solvers?

Ritz solvers can be used with mixed precision but are not suitable for solving for hundreds of eigenvectors. Lanczos solvers are great for solving for many eigenvectors but cannot (to my knowledge) be used with mixed precision.

What type of solvers do MILC and Chroma use?

[jpfoley]

I'm not very familiar with Ritz solvers,
but if it's a question of either-or, I would tend toward Lanczos.
I think it's important to be able to easily knock out two or three hundred
eigenvectors. Also, in the long term, it might be worth implementing an
algorithm
for non-hermitian matrices, e.g., Arnoldi rather than Lanczos, but
optimised so that
no unneccesary operations are performed in the hermitian case.

While we're on this, we should also implement the 3D gauge-covariant
laplacian used in distillation/Laph smearing.
The Laplacian eigenvectors have the same structure as staggered quark
fields, so not too much
extra work to do, and this code would likely be heavily used in
spectroscopy calculations.
At Carnegie-Mellon, we coded up a thick-restarted Lanczos algorithm for
this. Seemed to work
much better than the restart procedure used in ARPACK.

I'll check to see what MILC uses.

On 11/20/2012 11:52 PM, mikeaclark wrote:

QUDA is sorely lacking an eigenvector solver. We need to investigate
what type of solver is most appropriate for including in QUDA. What
are the relative merits of Ritz and Lanczos solvers?

Ritz solvers can be used with mixed precision but are not suitable for
solving for hundreds of eigenvectors. Lanczos solvers are great for
solving for many eigenvectors but cannot (to my knowledge) be used
with mixed precision.

What type of solvers do MILC and Chroma use?

—
Reply to this email directly or view it on GitHub
#90.

[daschaich]

So I'm using a couple of different eigensolvers in MILC. The original is Kostas's implementation of Kalkreuter's Ritz-based algorithm for staggered fermions in application directory ks_eigen (a more general version of which should be in application directory arb_dirac_eigen). Kostas, however, recommended plugging in PRIMME, where I'm calling an Arnoldi solver.

[maddyscientist]

Just had a request for Jacobi-Davidson style solver from Carsten Urbach. A fairly nice explanation of this seems to be here: http://mntek3.ulb.ac.be/pub/docs/reports/pdf/jdgamm.pdf

[urbach]

The reason for JD is that I found it to be more reliable than Arnoldi. And its basically using an iterative solver, so one could reuse all the optimisations already implemented for the solvers.

Another source of info might be http://arxiv.org/abs/hep-lat/0609023 and inparticular references 37-39 in that paper.

[maddyscientist]

Writing this down before I forget about it. An eigensolver that might be worth looking at is LOBPCG, which apparently can be used with multi-source mat-vec operations. This could be beneficial once we have multi-source dslash operators present.

[maddyscientist]

Between the Lanczos solver by Hyung-Jin and the eig-CG solver of Alexei, I think I will close this bug now. These solvers also now gives us a framework upon which to build future eigenvector solvers. Both of the these solvers are in the quda-0.7 branch, and will be part of the 0.7 release. We can assign future issues for specific eigenvector solvers (e.g., Jacobi-Davidson, LOBPCG, etc.).