Efficient parallel Monte Carlo methods for matrix computations

V.N. Alexandrov

Mathematics and Computers in Simulation (MATCOM), 1998, vol. 47, issue 2, 113-122

Abstract: Three Monte Carlo methods for matrix inversion (MI) and finding a solution vector of a system of linear algebraic equations (SLAE) are considered: with absorption, without absorption with uniform transition frequency function, and without absorption with almost optimal transition frequency function. Recently Alexandrov, Megson, and Dimov have shown that an n×n matrix can be inverted in 3n/2+N+T steps on a regular array with O(n2NT) cells. Alexandrov and Megson have also shown that a solution vector of SLAE can be found in n+N+T steps on a regular array with the same number of cells. A number of bounds on N and T have been established (N is the number of chains and T is the length of the chain in the stochastic process; these are independent of n), which show that these designs are faster than existing designs for large values of n. In this paper we take another implementation approach; we consider parallel Monte Carlo algorithms for MI and solving SLAE in MIMD environment, e.g. running on a cluster of workstations under PVM. The Monte Carlo method with almost optimal frequency function performs best of the three methods; it needs about six to ten times fewer chains for the same precision.

Keywords: Monte Carlo methods; Parallel algorithms; Matrix inversion; System of linear algebraic equations (search for similar items in EconPapers)
Date: 1998
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378475498000974
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:matcom:v:47:y:1998:i:2:p:113-122

DOI: 10.1016/S0378-4754(98)00097-4

Access Statistics for this article

Mathematics and Computers in Simulation (MATCOM) is currently edited by Robert Beauwens

More articles in Mathematics and Computers in Simulation (MATCOM) from Elsevier
Bibliographic data for series maintained by Catherine Liu ().