Search

In lattice QCD the calculation of disconnected quark loops from the trace of the inverse quark matrix has large noise variance. A multilevel Monte Carlo method is proposed for this problem that uses different degree polynomials on a multilevel system. The polynomials are developed from the GMRES algorithm for solving linear equations. To reduce orthogonalization expense, the highest degree polynomial is a composite or double polynomial found with a polynomial preconditioned GMRES iteration. Matrix deflation is used in three different ways: in the Monte Carlo levels, in the main solves, and in the deflation of the highest level double polynomial. A numerical comparison with optimized Hutchinson is performed on a quenched \(24^4\) lattice. The results demonstrate that the new Multipolynomial Monte Carlo method can significantly improve the trace computation for matrices that have a difficult spectrum due to small eigenvalues.}, Comment: To be published in Proceedings of Science, 40th International Symposium on Lattice Field Theory (Lattice 2023)

Estimating the trace of the inverse of a large matrix is an important problem in lattice quantum chromodynamics. A multilevel Monte Carlo method is proposed for this problem that uses different degree polynomials for the levels. The polynomials are developed from the GMRES algorithm for solving linear equations. To reduce orthogonalization expense, the highest degree polynomial is a composite or double polynomial found with a polynomial preconditioned GMRES iteration. Added to some of the Monte Carlo pieces is deflation of eigenvalues that reduces the variance. Deflation is also used for finding a reduced degree deflated polynomial. The new Multipolynomial Monte Carlo method can significantly improve the trace computation for matrices that have a difficult spectrum due to small eigenvalues.

In lattice QCD, the calculation of physical quantities from disconnected quark loop calculations have large variance due to the use of Monte Carlo methods for the estimation of the trace of the inverse lattice Dirac operator. In this work, we build upon our POLY and HFPOLY variance reduction methods by using high-degree polynomials. Previously, the GMRES polynomials used were only stable for low-degree polynomials, but through application of a new, stable form of the GMRES polynomial, we have achieved higher polynomial degrees than previously used. While the variance is not dependent on the trace correction term within the methods, the evaluation of this term will be necessary for forming the vacuum expectation value estimates. This requires computing the trace of high-degree polynomials, which can be evaluated stochastically through our new Multipolynomial Monte Carlo method. With these new high-degree noise subtraction polynomials, we obtained a variance reduction for the scalar operator of nearly an order of magnitude over that of no subtraction on a $24^3 \times 32$ quenched lattice at $\beta = 6.0$ and $\kappa = 0.1570 \approx \kappa_{crit}$. Additionally, we observe that for sufficiently high polynomial degrees, POLY and HFPOLY approach the same level of effectiveness. We also explore the viability of using double polynomials for variance reduction as a means of reducing the required orthogonalization and memory costs associated with forming high-degree GMRES polynomials.

An approach is given for solving large linear systems that combines Krylov methods with use of two different grid levels. Eigenvectors are computed on the coarse grid and used to deflate eigenvalues on the fine grid. GMRES-type methods are first used on both the coarse and fine grids. Then another approach is given that has a restarted BiCGStab (or IDR) method on the fine grid. While BiCGStab is generally considered to be a non-restarted method, it works well in this context with deflating and restarting. Tests show this new approach can be very efficient for difficult linear equations problems., Comment: 19 pages, 8 figures

Lattice QCD solvers encounter critical slowing down for fine lattice spacings and small quark mass. Traditional matrix eigenvalue deflation is one approach to mitigating this problem. However, to improve scaling we study the effects of deflating on the coarse grid in a hierarchy of three grids for adaptive mutigrid applications of the two dimensional Schwinger model. We compare deflation at the fine and coarse levels with other non deflated methods. We find the inclusion of a partial solve on the intermediate grid allows for a low tolerance deflated solve on the coarse grid. We find very good scaling in lattice size near critical mass when we deflate at the coarse level using the GMRES-DR and GMRES-Proj algorithms., Comment: 12 pages, 5 figures

Noise subtraction methods are a set of techniques that aim to reduce the variance of signals in LQCD which are often flooded with noise. The standard approach is a pertubative subtraction. In this work, we demonstrate the abilities of our new noise subtraction methods with methods which show considerable improvement over pertubative subtraction in the reduction of the variance for the set of LQCD operators that were studied. The methods were tested at $\kappa_{crit}$ on quenched configurations, as well as on dynamical quark configurations at $\kappa = 0.1453$. A significant improvement in the reduction of operator variance was observed in both cases., Comment: 6 pages, 6 figures

We present a polynomial preconditioner for solving large systems of linear equations. The polynomial is derived from the minimum residual polynomial (the GMRES polynomial) and is more straightforward to compute and implement than many previous polynomial preconditioners. Our current implementation of this polynomial using its roots is naturally more stable than previous methods of computing the same polynomial. We implement further stability control using added roots, and this allows for high degree polynomials. We discuss the effectiveness and challenges of root-adding and give an additional check for stability. In this paper, we study the polynomial preconditioner applied to GMRES; however it could be used with any Krylov solver. This polynomial preconditioning algorithm can dramatically improve convergence for some problems, especially for difficult problems, and can reduce dot products by an even greater margin., Comment: Published online in Numerical Linear Algebra with Applications, December 2021

Lattice QCD calculations of disconnected quark loop operators are extremely computer time-consuming to evaluate. To compute these diagrams using lattice techniques, one generally uses stochastic noise methods. These employ a randomly generated set of noise vectors to project out physical signals. In order to strengthen the signal in these calculations, various noise subtraction techniques may be employed. In addition to the standard method of perturbative subtraction, one may also employ matrix deflation techniques using the GMRES-DR and MINRES-DR algorithms as well as polynomial subtraction techniques to reduce statistical uncertainty. Our matrix deflation methods play two roles: they both speed up the solution of the linear equations as well as decrease numerical noise. We show how to combine deflation with either perturbative and polynomial methods to produce extremely powerful noise suppression algorithms. We use a variety of lattices to study the effects. In order to set a benchmark, we first use the Wilson matrix in the quenched approximation. We see strong low eigenmode dominance at kappa critical ($\kappa_{crit}$) in the variance of the vector and scalar operators. We also use MILC dynamic lattices, where we observe deflation subtraction results consistent with the effectiveness seen in the quenched data., Comment: 49 pages, 28 figues

Polynomial preconditioning can improve the convergence of the Arnoldi method for computing eigenvalues. Such preconditioning significantly reduces the cost of orthogonalization; for difficult problems, it can also reduce the number of matrix-vector products. Parallel computations can particularly benefit from the reduction of communication-intensive operations. The GMRES algorithm provides a simple and effective way of generating the preconditioning polynomial. For some problems high degree polynomials are especially effective, but they can lead to stability problems that must be mitigated. A two-level "double polynomial preconditioning" strategy provides an effective way to generate high-degree preconditioners., Comment: 25 pages

Noise subtraction techniques can help reduce the statistical uncertainty in the extraction of hard to detect signals. We describe new noise subtraction methods in Lattice QCD which apply to disconnected diagram evaluations. Some of the noise suppression techniques include polynomial quark matrix methods, eigenspectrum deflation methods, and combination methods. Our most promising technique combines polynomial and Hermitian deflation subtraction methods. The overall goal is to improve the efficiency of Lattice QCD noise method algorithms., Comment: 7 pages, 3 figures, Lattice 2016

The convergence of the restarted GMRES method can be significantly improved, for some problems, by using a weighted inner product that changes at each restart. How does this weighting affect convergence, and when is it useful? We show that weighted inner products can help in two distinct ways: when the coefficient matrix has localized eigenvectors, weighting can allow restarted GMRES to focus on eigenvalues that otherwise slow convergence; for general problems, weighting can break the cyclic convergence pattern into which restarted GMRES often settles. The eigenvectors of matrices derived from differential equations are often not localized, thus limiting the impact of weighting. For such problems, incorporating the discrete cosine transform into the inner product can significantly improve GMRES convergence, giving a method we call W-GMRES-DCT. Integrating weighting with eigenvalue deflation via GMRES-DR also can give effective solutions., Comment: Revision containing edits to the text, corrections, and removal of the section on Arnoldi in weighted inner products (to reduce the manuscript's length)

We propose a new noise subtraction method, which we call "eigenspectrum subtraction", which uses low eigenmode information to suppress statistical noise at low quark mass. This is useful for lattice calculations involving disconnected loops or all-to-all propagators. It has significant advantages over perturbative subtraction methods. We compare unsubtracted, eigenspectrum and perturbative error bar results for the scalar operator on a small Wilson QCD matrix., Comment: 8 pages

We consider three improvements to seed methods for Hermitian linear systems with multiple right-hand sides: only the Krylov subspace for the first system is used for seeding subsequent right-hand sides, the first right-hand side is solved past convergence, and periodic re-orthogonalization is used in order to control roundoff errors associated with the Conjugate Gradient algorithm. The method is tested for the case of Wilson fermions near kappa critical and a considerable speed up in the convergence is observed., Comment: 7 pages, 2 figures. Presented at the 26th International Symposium on Lattice Field Theory, Williamsburg, VA, USA, 14-19 Jul 2008. Fixed a hyperlink to one of the references

A deflated and restarted Lanczos algorithm to solve hermitian linear systems, and at the same time compute eigenvalues and eigenvectors for application to multiple right-hand sides, is described. For the first right-hand side, eigenvectors with small eigenvalues are computed while simultaneously solving the linear system. Two versions of this algorithm are given. The first is called Lan-DR and is based on conjugate gradient (CG) implementation of the Lanczos algorithm. This version will be optimal for the hermitian positive definite case. The second version is called MinRes-DR and is based on the minimum residual (MinRes) implementation of Lanczos algorithm. This version is optimal for indefinite hermitian systems where the CG algorithm is subject to instabilities. For additional right-hand sides, we project over the calculated eigenvectors to speed up convergence. The algorithms used for subsequent right-hand sides are called D-CG and D-MinRes respectively. After some introductory examples are given, we show tests for the case of Wilson fermions at kappa critical. A considerable speed up in the convergence is observed compared to unmodified CG and MinRes., Comment: Presented at 26th International Symposium on Lattice Field Theory, Williamsburg, VA, USA, 14-19 Jul 2008

We consider symmetric positive definite systems of linear equations with multiple right-hand sides. The seed conjugate gradient method solves one right-hand side with the conjugate gradient method and simultaneously projects over the Krylov subspace thus developed for the other right-hand sides. Then the next system is solved and used to seed the remaining ones. Rounding error in the conjugate gradient method limits how much the seeding can improve convergence. We propose three changes to the seed conjugate gradient method: only the first right-hand side is used for seeding, this system is solved past convergence, and the roundoff error is controlled with some reorthogonalization. We will show that results are actually better with only one seeding, even in the case of related right-hand sides. Controlling rounding error gives the potential for rapid convergence for the second and subsequent right-hand sides., Comment: 11 pages, 7 figures

A deflated restarted Lanczos algorithm is given for both solving symmetric linear equations and computing eigenvalues and eigenvectors. The restarting limits the storage so that finding eigenvectors is practical. Meanwhile, the deflating from the presence of the eigenvectors allows the linear equations to generally have good convergence in spite of the restarting. Some reorthogonalization is necessary to control roundoff error, and several approaches are discussed. The eigenvectors generated while solving the linear equations can be used to help solve systems with multiple right-hand sides. Experiments are given with large matrices from quantum chromodynamics that have many right-hand sides., Comment: 20 pages, 13 figures

The large systems of complex linear equations that are generated in QCD problems often have multiple right-hand sides (for multiple sources) and multiple shifts (for multiple masses). Deflated GMRES methods have previously been developed for solving multiple right-hand sides. Eigenvectors are generated during solution of the first right-hand side and used to speed up convergence for the other right-hand sides. Here we discuss deflating non-restarted methods such as BiCGStab. For effective deflation, both left and right eigenvectors are needed. Fortunately, with the Wilson matrix, left eigenvectors can be derived from the right eigenvectors. We demonstrate for difficult problems with kappa near kappa_c that deflating eigenvalues can significantly improve BiCGStab. We also will look at improving solution of twisted mass problems with multiple shifts. Projecting over previous solutions is an easy way to reduce the work needed., Comment: 7 pages, 4 figures, presented at the XXV International Symposium on Lattice Field Theory, 30 July - 4 August 2007, Regensburg, Germany

A new approach is discussed for solving large nonsymmetric systems of linear equations with multiple right-hand sides. The first system is solved with a deflated GMRES method that generates eigenvector information at the same time that the linear equations are solved. Subsequent systems are solved by combining restarted GMRES with a projection over the previously determined eigenvectors. This approach offers an alternative to block methods, and it can also be combined with a block method. It is useful when there are a limited number of small eigenvalues that slow the convergence. An example is given showing significant improvement for a problem from quantum chromodynamics. The second and subsequent right-hand sides are solved much quicker than without the deflation. This new approach is relatively simple to implement and is very efficient compared to other deflation methods., Comment: 13 pages, 5 figures

We consider solution of multiply shifted systems of nonsymmetric linear equations, possibly also with multiple right-hand sides. First, for a single right-hand side, the matrix is shifted by several multiples of the identity. Such problems arise in a number of applications, including lattice quantum chromodynamics where the matrices are complex and non-Hermitian. Some Krylov iterative methods such as GMRES and BiCGStab have been used to solve multiply shifted systems for about the cost of solving just one system. Restarted GMRES can be improved by deflating eigenvalues for matrices that have a few small eigenvalues. We show that a particular deflated method, GMRES-DR, can be applied to multiply shifted systems. In quantum chromodynamics, it is common to have multiple right-hand sides with multiple shifts for each right-hand side. We develop a method that efficiently solves the multiple right-hand sides by using a deflated version of GMRES and yet keeps costs for all of the multiply shifted systems close to those for one shift. An example is given showing this can be extremely effective with a quantum chromodynamics matrix., Comment: 19 pages, 9 figures

A new approach is discussed for solving large nonsymmetric systems of linear equations with multiple right-hand sides. The first system is solved with a deflated GMRES method that generates eigenvector information at the same time that the linear equations are solved. Subsequent systems are solved by combining an iterative method with a projection over the previously determined eigenvectors. Restarted GMRES is considered for the iterative method as well as non-restarted methods such as BiCGSTAB. These methods offer an alternative to block methods, and they can also be combined with a block approach. An example is given showing significant improvement for a problem from quantum chromodynamics., Comment: 28 pages, 9 figures; support acknowledgments added

Work on generalizing the deflated, restarted GMRES algorithm, useful in lattice studies using stochastic noise methods, is reported. We first show how the multi-mass extension of deflated GMRES can be implemented. We then give a deflated GMRES method that can be used on multiple right-hand sides of $Ax=b$ in an efficient manner. We also discuss and give numerical results on the possibilty of combining deflated GMRES for the first right hand side with a deflated BiCGStab algorithm for the subsequent right hand sides., Comment: Lattice2003(machine)

Versions of GMRES with deflation of eigenvalues are applied to lattice QCD problems. Approximate eigenvectors corresponding to the smallest eigenvalues are generated at the same time that linear equations are solved. The eigenvectors improve convergence for the linear equations, and they help solve other right-hand sides., Comment: Lattice2001(algorithms)