Computing and deflating eigenvalues while solving multiple right hand side linear systems in Quantum Chromodynamics

Abstract

We present a new algorithm that computes eigenvalues and eigenvectors of a Hermitian positive definite matrix while solving a linear system of equations with Conjugate Gradient (CG). Traditionally, all the CG iteration vectors could be saved and recombined through the eigenvectors of the tridiagonal projection matrix, which is equivalent theoretically to unrestarted Lanczos. Our algorithm capitalizes on the iteration vectors produced by CG to update only a small window of vectors that approximate the eigenvectors. While this window is restarted in a locally optimal way, the CG algorithm for the linear system is unaffected. Yet, in all our experiments, this small window converges to the required eigenvectors at a rate identical to unrestarted Lanczos. After the solution of the linear system, eigenvectors that have not accurately converged can be improved in an incremental fashion by solving additional linear systems. In this case, eigenvectors identified in earlier systems can be used to deflate, and thus accelerate, the convergence of subsequent systems. We have used this algorithm with excellent results in lattice QCD applications, where hundreds of right hand sides may be needed. Specifically, about 70 eigenvectors are obtained to full accuracy after solving 24 right hand sides. Deflating these from the large number of subsequent right hand sides removes the dreaded critical slowdown, where the conditioning of the matrix increases as the quark mass reaches a critical value. Our experiments show almost a constant number of iterations for our method, regardless of quark mass, and speedups of 8 over original CG for light quark masses.

22 pages, 26 eps figures

References in corpus (1)

• Deflated Iterative Methods for Linear Equations with Multiple Right-Hand Sides

Cited by in corpus (41)

• Domain wall QCD with physical quark masses
• Effective noise reduction techniques for disconnected loops in Lattice QCD
• Adaptive multigrid algorithm for the lattice Wilson-Dirac operator
• $K\to \pi \pi$ $\Delta I=3/2$ decay amplitude in the continuum limit
• Disconnected quark loop contributions to nucleon observables in lattice QCD
• High Statistics Analysis using Anisotropic Clover Lattices: (III) Baryon-Baryon Interactions
• The Low Energy Constants of $SU(2)$ Partially Quenched Chiral Perturbation Theory from $N_f=2+1$ Domain Wall QCD
• Long distance contribution to the $K_L-K_S$ mass difference
• Krylov Subspace Recycling for Sequences of Shifted Linear Systems
• Lattice QCD study of mixed systems of pions and kaons
• Deflation as a Method of Variance Reduction for Estimating the Trace of a Matrix Inverse
• Neutron electric dipole moment using $N_f=2+1+1$ twisted mass fermions
• Evaluation of disconnected quark loops for hadron structure using GPUs
• Estimating the Trace of the Matrix Inverse by Interpolating from the Diagonal of an Approximate Inverse
• Application of block Krylov subspace algorithms to the Wilson-Dirac equation with multiple right-hand sides in lattice QCD
• Quantum annealing for systems of polynomial equations
• Multigrid for Staggered Lattice Fermions
• Uncertainty Quantification in Lattice QCD Calculations for Nuclear Physics
• Pushing Memory Bandwidth Limitations Through Efficient Implementations of Block-Krylov Space Solvers on GPUs
• Improved Seed Methods for Symmetric Positive Definite Linear Equations with Multiple Right-hand Sides
• Multigrid deflation for Lattice QCD
• Extending the eigCG algorithm to nonsymmetric Lanczos for linear systems with multiple right-hand sides
• Application of preconditioned block BiCGGR to the Wilson-Dirac equation with multiple right-hand sides in lattice QCD
• Stagnation of block GMRES and its relationship to block FOM
• Towards a direct lattice calculation of m_d - m_u
• Solving DWF Dirac Equation Using Multi-splitting Preconditioned Conjugate Gradient with Tensor Cores on NVIDIA GPUs
• Deflation for the off-diagonal block in symmetric saddle point systems
• Structured condition number for multiple right-hand side linear systems with parameterized quasiseparable coefficient matrix
• The role of multigrid algorithms for LQCD
• Meson and baryon masses with low mode averaging
• The eigSUMR inverter for overlap fermion
• Recent developments in the tmLQCD software suite
• Charged Hadron Properties in Background Electric Fields
• Recycling BiCG with an Application to Model Reduction
• The removal of critical slowing down
• Projection techniques to update the truncated SVD of evolving matrices
• PLQCD library for Lattice QCD on multi-core machines
• Recycling BiCG for families of shifted linear systems
• Numerical experiments using deflation with the HISQ action
• Two-Grid Deflated Krylov Methods for Linear Equations
• A new deflated block GCROT($m,k$) method for the solution of linear systems with multiple right-hand sides