A Monte Carlo method for the parallel solution of linear systems (Q1120249)

The paper presents a new parallel algorithm to solve a linear system \(Ax=q\), based on the Monte Carlo method, where A is an \(n\times n\) matrix with real entries. The used parallel model has the following features: (i) any number of processors can be used at any time: (ii) each processor may perform one of the arithmetic or logical operations; (iii) no time is required to communicate data among processors and (iv) there are no memory or data alignment penalties. The splitting \(A=I-B\) and the case (1) \(\| B\| <1\) and (2) \(\| B\| =1\) are studied. For the first case a Monte Carlo method is proposed for the computation of the components of \(x^ R=\sum^{R}_{i=1}B^ iq\). Based on this method a parallel algorithm is presented for solving the linear system by using \(\max (2n^ 2,nNR)\) processors and 2[log n]\(+[\log R]+[\log N]+O(1)\) time units, where N is the number of the computed trajectories of the Markov chain associated with the computation of \(x^ R\). Denoting by \(\bar x\) the approximated solution given by the above algorithm the following theorem is proved: if B is an \(n\times n\) matrix with \(\| B\| <1-1/o(n^ k),\) \(p_ 0\) is a positive constant, \(2^{1-d}\) is the machine precision then \(\bar x\) satisfying the condition \(P(\| x- \bar x\| /\| x\| <2^{1-d})>1-p_ 0\) can be obtained by using the previous algorithm in O(log n)\({}^ o\) time with \(O(n^{3+2k)}\) processors. Throughout the proof some rules are given to choose N and R in order to ensure the desired condition. Two methods are given also to treat the case of \(\| B\| =1\). The first one is based on the finding of an approximation of the solution of the system \(x=tBx+q\) for an appropriate value of t, while the second method consists of an algorithm for the computation of all powers of \((B^ hq)_ m\) separately.