A sparse parallel hybrid Monte Carlo algorithm for matrix computations

Branford, S., Weihrauch, C. and Alexandrov, V. (2005) A sparse parallel hybrid Monte Carlo algorithm for matrix computations. Lecture Notes in Computer Science, 3516. pp. 743-751. ISSN 0302-9743

Abstract/Summary

In this paper we introduce a new algorithm, based on the successful work of Fathi and Alexandrov, on hybrid Monte Carlo algorithms for matrix inversion and solving systems of linear algebraic equations. This algorithm consists of two parts, approximate inversion by Monte Carlo and iterative refinement using a deterministic method. Here we present a parallel hybrid Monte Carlo algorithm, which uses Monte Carlo to generate an approximate inverse and that improves the accuracy of the inverse with an iterative refinement. The new algorithm is applied efficiently to sparse non-singular matrices. When we are solving a system of linear algebraic equations, Bx = b, the inverse matrix is used to compute the solution vector x = B(-1)b. We present results that show the efficiency of the parallel hybrid Monte Carlo algorithm in the case of sparse matrices.