Comparison of two Parallel Monte Carlo Algorithms for Solving Systems of Linear Algebraic Equations

摘要

The problem of solving sparse Systems of Linear Algebraic. Equations (SLAE) by par-allel Monte Carlo numerical methods is considered. The Almost Optimal Monte Carlo method and Monte Carlo method with Column Reduction are presented. In the case when a copy of the nonzero matrix elements is sent to each processor, the execution, time for solving SLAE by Monte Carlo on p processors is bounded by O (nNdT/p), where N is the. number of chains, T is the length of the chain in tlic stochastic process, which are independent of matrix size n, and d is the average number of non-zero elements in the row. Finding a component of the solution vector requires O (NdT/p) time on p processors, independent of the matrix size n. In ease, of Monte Carlo with Column Reduction the time is O (N_1ml~2/p), where N_1 and m are the number of samples and iterations required to reach given precision and l < n is the reduced matrix size. Experiments and comparison on the efficiency of algorithms are presented. The algorithms were implemented, on a cluster of workstations using PVM.