Theory and Algorithms Commons^™

Randomized Algorithms For Preconditioner Selection With Applications To Kernel Regression, Conner Dipaolo

HMC Senior Theses

The task of choosing a preconditioner M to use when solving a linear system Ax=b with iterative methods is often tedious and most methods remain ad-hoc. This thesis presents a randomized algorithm to make this chore less painful through use of randomized algorithms for estimating traces. In particular, we show that the preconditioner stability || I - M^-1A ||_F, 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 …