Enhancing Monte Carlo Preconditioning Methods for Matrix Computations
Janko Straßburg, Vassil Alexandrov · Procedia Computer Science · 2014
An enhanced version of a stochastic SParse Approximate Inverse (SPAI) preconditioner for general matrices is presented. This method is used in contrast to the standard deterministic preconditioners computed by the deterministic SPAI, and its further optimized parallel variant- Modified SParse Approximate Inverse Preconditioner (MSPAI). Thus we present a Monte Carlo preconditioner that relies on the use of Markov Chain Monte Carlo (MCMC) methods to com- pute a rough matrix inverse first, which is further optimized by an iterative filter process and a parallel refinement, to enhance the accuracy of the preconditioner. Monte Carlo methods quantify the uncertainties by enabling us to estimate the non-zero elements of the inverse ma- trix with a given precision and certain probability. The advantage of this approach is that we use sparse Monte Carlo matrix inversion whose computational complexity is linear of the size of the matrix. The behaviour of the proposed algorithm is studied, its performance measured and compared with MSPAI.