No label defined (Q4512245)

Let us consider a realization of the Seidel method for the solution of a system of linear algebraic equations via a special computing system consisting of \(n\) processors. The authors propose the following algorithm. Let every processor compute \(x_{i}^{(k+1)}\), \(i=1,\dots, n\). Then on the any step, without taking into account the transmit, we'll have: 1st step: calculation of \(e_{in}^{(k)}=\alpha_{in} x_{n}^{(k)}\), \(i=1,\dots, n-1\); 2nd step: calculation of \(s_{in}^{(k)}=\beta_{i}+ e_{in}^{(k)}\), \(i=1,\dots, n-1\); 3rd step: calculation of \(e_{in-1}^{(k)}=\alpha_{in-1} x_{n-1}^{(k)}\), \(i=1,\dots, n-2\); 4th step: calculation of \(s_{in-1}^{(k)}= s_{in}^{(k)}+ e_{in-1}^{(k)}\), \(i=1,\dots, n-2\); \(2n\)th step: calculation of \(x_{i}^{(k+1)}= s_{12}^{(k)}\); \(2n+1\)st step: calculation of \(e_{i1}^{(k+1)}=\alpha_{i1} x_{1}^{(k+1)}\), \(i=2,\dots, n\); \(2n+2\)nd step: calculation of \(s_{i1}^{(k+1)}= s_{i,i-1}^{(k)}+ e_{i1}^{(k+1)}\), \(i=2,\dots, n\); \(4n\)th step: calculation of \(x_{n}^{(k+1)}= s_{n,n- 1}^{(k+1)}\). Then we calculate \(\Delta x_{i}^{(k+1)}=|x_{i}^{(k+1)}- x_{i}^{(k)}|\), \(i=1,\dots, n\) and the conditional transfer is made. In comparison with sequential computations the acceleration is equal to \(S_{n}=2n(n+1)/2(2n+1)=n/2+o(1)\).