Abstract
We present a method for performing sampling from a Boltzmann distribution of an ill-conditioned quadratic action. This method is based on heat-bath thermalization along a set of conjugate directions, generated via a conjugate-gradient procedure. The resulting scheme outperforms local updates for matrices with very high condition number, since it avoids the slowing down of modes with lower eigenvalue, and has some advantages over the global heat-bath approach, compared to which it is more stable and allows for more freedom in devising case-specific optimizations.
The Challenge of Ill-Conditioned Actions
In many fields of computational physics, such as Quantum Chromodynamics (QCD) or linear-scaling electronic structure methods, researchers need to sample configurations from a Gaussian probability distribution defined by a large matrix $\mathbf{A}$. The challenge arises when $\mathbf{A}$ is "ill-conditioned," meaning the ratio between its largest and smallest eigenvalues (the condition number $\kappa$) is very high.
In these cases, standard sampling methods face significant hurdles:
- Local Heat Bath methods (updating one variable at a time) are slow because "soft" modes (small eigenvalues) take a very long time to decorrelate.
- Global Heat Bath methods (inverting the whole matrix) are computationally expensive and can be numerically unstable if the iterative solver doesn't fully converge.
The CGHB Method
The core innovation of the Conjugate Gradient Heat Bath (CGHB) is to perform heat bath moves along conjugate directions. Two directions $\mathbf{d}_i$ and $\mathbf{d}_j$ are conjugate with respect to a matrix $\mathbf{A}$ if $\mathbf{d}_i^T \mathbf{A} \mathbf{d}_j = 0$ for $i \neq j$. By updating along these directions, the sampling of each mode becomes independent, ensuring that all physical modes decorrelate at the same rate regardless of their "stiffness."
The Block Algorithm
To ensure the method explores the entire space (ergodicity), especially when there are degenerate eigenvalues where standard CG might stall, the authors propose a hybrid "block" scheme. This algorithm mixes CG with a Gram-Schmidt process on a small pool of random vectors to maintain a diverse set of search directions.
Unlike global methods that might require a Metropolis-Hastings correction if the solver isn't converged, every single move in this conjugate scheme preserves the exact Boltzmann distribution by construction.
Linear Decorrelation and Performance
A key theoretical insight of the CGHB method is the nature of the autocorrelation function. While most Monte Carlo methods show an exponential decay in autocorrelation, the authors prove that for conjugate directions, the autocorrelation function is linear and drops to exactly zero after $N$ steps (a full sweep).
The authors evaluated their method using a 1D chain of spring-connected masses with periodic boundary conditions. By adjusting the spring constants and adding a diagonal term, they could precisely control the condition number $\kappa$ and the system size $N$. For a system with $\kappa = 10^4$, the CGHB method was roughly 100 times more efficient than a local heat bath for calculating observables that depend on soft modes, such as the trace of the inverse matrix.
Conclusion
The Conjugate Gradient Heat Bath provides a robust middle ground between local and global sampling techniques. It is particularly effective for highly ill-conditioned systems where it avoids critical slowing down. While currently restricted to quadratic actions, the method's stability and efficiency suggest potential for future extensions to anharmonic systems, which would be a major breakthrough for general molecular dynamics and sampling.
Summary updated