Inversion of sparse matrices using Monte Carlo methods

Abstract

<p>A frequent need in many scientific applications is the flexibility to compute some suitable elements of the inverse of well-conditioned, large, sparse, and positive definite matrices. In this research, we have explored some aspects of the inversion of such matrices. For this class of matrices, it has been shown that desired elements of their inverse may be evaluated with desired accuracy via a statistical approach. In this approach, each element of the inverse matrix is decomposed as the sum of two components: a fixed quantity and an expectation of a well defined random variable. This approach works directly with the original matrix W. Thus, it is devoid of the good ordering, fill-ins and choice of critical parameter problems. This approach will always yield positive estimates for variances. In addition, this approach has four attractive advantages. Firstly, it is flexible, that is, a desired entry of the inverse matrix can be evaluated, without computing any other entry. Secondly, it takes advantage of the sparsity of the matrix. Thirdly, it computes the exact value for some entries. And finally, it is easily parallelizable, which provides gains inefficiency and computing time;The expectation in the above decomposition may be computed using either the ordinary Importance Sampling technique or the Adaptive Importance Sampling;For moderate dimension of the matrix the ordinary importance sampling yields reasonable results when the importance sampler is the MVt3 with a diagonal covariance matrix;The A.I.S. may be started with three different covariance matrices. In general, A.I.S. provides 'better' results than the ordinary importance sampling and requires fewer iterations;Using an efficient sparse storage scheme, we have explored the implementation of this approach under a distributed system with PVM as a message passing protocol and under a shared memory environment using a 4 processor share memory machine. The method yields reasonable results under both environment.</p>