How to optimize preconditioners for the conjugate gradient method: a stochastic approach
For practitioners using CG with parameterized preconditioners, this provides a practical method to tune parameters for better average-case performance rather than worst-case bounds.
This paper proposes a stochastic approach to optimize preconditioner parameters for the conjugate gradient method, using trial runs with random initial guess vectors to minimize a functional that reflects mean convergence rate. Numerical experiments show that this approach yields better parameter values than optimizing based on the spectral condition number.
The conjugate gradient method (CG) is typically used with a preconditioner which improves efficiency and robustness of the method. Many preconditioners include parameters and a proper choice of a preconditioner and its parameters is often not a trivial task. Although many convergence estimates exist which can be used for optimizing preconditioners, these estimates typically hold for all initial guess vectors, in other words, they reflect the worst convergence rate. To account for the mean convergence rate instead, in this paper, we follow a stochastic approach. It is based on trial runs with random initial guess vectors and leads to a functional which can be used to monitor convergence and to optimize preconditioner parameters in CG. Presented numerical experiments show that optimization of this new functional with respect to preconditioner parameters usually yields a better parameter value than optimization of the functional based on the spectral condition number.