A Randomized Algorithm for Preconditioner Selection

arXiv1908.00633MaRDI QIDQ6512005FDOQ6512005

Conner DiPaolo, Wei-qing Gu

Abstract: The task of choosing a preconditioner $$ to use when solving a linear system $$ with iterative methods is difficult. For instance, even if one has access to a collection $$ of candidate preconditioners, it is currently unclear how to practically choose the $$ which minimizes the number of iterations of an iterative algorithm to achieve a suitable approximation to $$. This paper makes progress on this sub-problem by showing that the preconditioner stability $$, known to forecast preconditioner quality, can be computed in the time it takes to run a constant number of iterations of conjugate gradients through use of sketching methods. This is in spite of folklore which suggests the quantity is impractical to compute, and a proof we give that ensures the quantity could not possibly be approximated in a useful amount of time by a deterministic algorithm. Using our estimator, we provide a method which can provably select the minimal stability preconditioner among $n$ candidates using floating point operations commensurate with running on the order of $nlogn$ steps of the conjugate gradients algorithm. Our method can also advise the practitioner to use no preconditioner at all if none of the candidates appears useful. The algorithm is extremely easy to implement and trivially parallelizable. In one of our experiments, we use our preconditioner selection algorithm to create to the best of our knowledge the first preconditioned method for kernel regression reported to never use more iterations than the non-preconditioned analog in standard tests.

Mathematics Subject Classification ID

Nonparametric regression and quantile regression (62G08) Randomized algorithms (68W20) Preconditioners for iterative methods (65F08) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

This page was built for publication: A Randomized Algorithm for Preconditioner Selection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6512005)