Accessibility navigation

Parallel Hybrid Monte Carlo Algorithms for Matrix Computations

Alexandrov, V. N., Atanassov, E., Dimov, I., Branford, S., Thandavan, A. and Wiehrauch, C. (2005) Parallel Hybrid Monte Carlo Algorithms for Matrix Computations. Lecture Notes In Computer Science, 3516. 752 - 759.

Full text not archived in this repository.

It is advisable to refer to the publisher's version if you intend to cite from this work. See Guidance on citing.

To link to this item DOI: 10.1007/11428862_102


In this paper we consider hybrid (fast stochastic approximation and deterministic refinement) algorithms for Matrix Inversion (MI) and Solving Systems of Linear Equations (SLAE). Monte Carlo methods are used for the stochastic approximation, since it is known that they are very efficient in finding a quick rough approximation of the element or a row of the inverse matrix or finding a component of the solution vector. We show how the stochastic approximation of the MI can be combined with a deterministic refinement procedure to obtain MI with the required precision and further solve the SLAE using MI. We employ a splitting A = D – C of a given non-singular matrix A, where D is a diagonal dominant matrix and matrix C is a diagonal matrix. In our algorithm for solving SLAE and MI different choices of D can be considered in order to control the norm of matrix T = D –1C, of the resulting SLAE and to minimize the number of the Markov Chains required to reach given precision. Further we run the algorithms on a mini-Grid and investigate their efficiency depending on the granularity. Corresponding experimental results are presented.

Item Type:Article
ID Code:15101
Uncontrolled Keywords:Monte Carlo Method, Markov Chain, Matrix Inversion, Solution of System of Linear Equations, Grid Computing.

University Staff: Request a correction | Centaur Editors: Update this record

Page navigation