A Monte Carlo Approach to Sparse Approximate Inverse Matrix Computations
Janko Straßburg, Vassil Alexandrov · Procedia Computer Science · 2013
In this paper we present a stochastic SPAI pre-conditioner. In contrast to the standard deterministic SPAI pre-conditioners that use the Frobenius norm, we present a Monte Carlo pre-conditioner that relies on the use of Markov Chain Monte Carlo methods to compute a rough matrix inverse ( MI ). Monte Carlo methods quantify the uncertainties by enabling us to estimate the non-zero elements of the inverse matrix with a given precision and certain probability. The advantage of this approach is that we use sparse Monte Carlo matrix inversion whose complexity is linear to the size of the matrix. The behaviour of the proposed algorithm is studied, its performance is measured and compared with the standard deterministic SPAI approach, as well as the optimized and parallel MSPAI version. An analysis of the results is also presented.