search

lattice / quda

QUDA is a library for performing calculations in lattice QCD on GPUs.
https://lattice.github.io/quda
Other
289 stars 97 forks source link

Eigenvector solver implementation #90

Closed maddyscientist closed 10 years ago

maddyscientist commented 11 years ago

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 commented 11 years ago

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 https://github.com/lattice/quda/issues/90.

daschaich commented 11 years ago

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 commented 11 years ago

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 commented 11 years ago

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 commented 11 years ago

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 commented 10 years ago

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.).