## 3 Approaches to Building a Parallel Algorithm and Its Software Implementation
### Distribution of Data by MPI Processes Participating in Computations
Similarly, if the processes of the communicator comm form a two-dimensional grid, then the processes of communicators comm_row are rows of this two-dimensional grid of processes. Thus, a parallel software implementation of matrix-vector multiplication can be presented in the following form:  
b_part_temp = dot(A_part, x_part)  b_part = empty(M_part, dtype=float64)  comm_row.Allreduce([b_part_temp, M_part, MPI.DOUBLE],  [b_part, M_part, MPI.DOUBLE], op=MPI.SUM)  
Note that the result of such a multiplication (vector \(b\)) will be stored on all processes in parts: a part \(b_{part(m)}\) of the vector \(b\) for a fixed index \(m\) will be stored in all cells of the process grid row with index \(m\). **Remark 4**. : _Recall that the message exchange time is proportional to \(\log_{2}\texttt{numprocs}\), but the volume of transmitted messages is proportional to \(\texttt{numprocs}^{-1/2}\) in the case of a two-dimensional matrix division by blocks and is constant in the case of one-dimensional division of the matrix into blocks [1; 27]._  
The parallel algorithm for multiplying a transposed matrix by a vector in the case of a two-dimensional division of a matrix into blocks is quite similar to the algorithm considered in the previous section, and in a sense has symmetry with respect to it. Because we are interested in the multiplication of a transposed matrix by a vector in the context of the conjugate gradient method, we assume that system matrix \(A\) is stored over the processes of the grid of processes as shown in Figure 2. This is due to the fact that it is necessary to build an algorithm for multiplying matrix \(A^{T}\) by a vector in such a way as to avoid creating additional arrays in memory for the transposed matrix. Indeed, when solving real applied problems, the total available memory on all processes may not be enough. We build algorithms for solving very large problems! Therefore, the terms that arise when calculating the product of a transposed matrix by a vector can be divided into groups as follows (as in the previous section, we will give an example in which only nine MPI processes are involved in the calculations, see Figure 4):  
Figure 4: A parallel algorithm for multiplying a transposed matrix by a vector in the case of two-dimensional division of a matrix into blocks. \[A^{T}b = \begin{bmatrix}A^{T}_{part(0)}&A^{T}_{part(3)}&A^{T}_{part(6)}\\ A^{T}_{part(1)}&A^{T}_{part(4)}&A^{T}_{part(7)}\\ A^{T}_{part(2)}&A^{T}_{part(5)}&A^{T}_{part(8)}\end{bmatrix}\begin{bmatrix}b_{ part(0)}\\ b_{part(1)}\\ b_{part(2)}\end{bmatrix} =\] \[= \begin{bmatrix}A^{T}_{part(0)}b_{part(0)}+A^{T}_{part(3)}b_{part(1) }+A^{T}_{part(6)}b_{part(2)}\\ A^{T}_{part(1)}b_{part(0)}+A^{T}_{part(4)}b_{part(1)}+A^{T}_{part(7)}b_{part(2)} \\ A^{T}_{part(2)}b_{part(0)}+A^{T}_{part(5)}b_{part(1)}+A^{T}_{part(8)}b_{part(2)} \end{bmatrix} =\] \[= \begin{bmatrix}A^{T}_{part(0)}b_{part(0)}\\ A^{T}_{part(1)}b_{part(0)}\\ A^{T}_{part(2)}b_{part(0)}\end{bmatrix} + \begin{bmatrix}A^{T}_{part(3)}b_{part(1) }\\ A^{T}_{part(4)}b_{part(1)}\\ A^{T}_{part(5)}b_{part(1)}\end{bmatrix} + \begin{bmatrix}A^{T}_{part(6)}b_{part( 2)}\\ A^{T}_{part(7)}b_{part(2)}\end{bmatrix} =\] \[= \begin{bmatrix}x_{part(0)}^{T}b_{part(0)}\\ x_{part\_temp(0,1)}\\ x_{part\_temp(0,2)}\end{bmatrix} + \begin{bmatrix}x_{part\_temp(1,0)}\\ x_{part\_temp(1,1)}\\ x_{part\_temp(1,2)}\end{bmatrix} + \begin{bmatrix}x_{part\_temp(2,0)}\\ x_{part\_temp(2,1)}\\ x_{part\_temp(2,2)}\end{bmatrix} =\] \[=x_{temp(0)}+x_{temp(1)}+x_{temp(2)}= \begin{bmatrix}x_{part(0) }\\ x_{part\_temp(1)}\\ x_{part(2)}\end{bmatrix} =x.\]  
Then, each process participating in the calculations will perform the operation of multiplying its part \(A^{T}_{part(\text{rank})}\) of matrix \(A^{T}\) by its part \(b_{part(m)}\) of vector \(b\). As a result of this operation, the vector \(x_{part\_temp(m,n)}\) will be calculated, which will be one of the terms of the part \(x_{part(n)}\) of the final vector \(x\).