## 3 Approaches to Building a Parallel Algorithm and Its Software Implementation
### Distribution of Data by MPI Processes Participating in Computations  
We will assume that the software implementation of the developed parallel algorithm will use the MPI parallel programming technology and run on the number of MPI processes equal to numprocs. All these processes will be included in the communicator \(\mathtt{comm}\equiv\mathtt{MPI.COM.WORLD}\), inside which they will have their number/identifier \(\mathtt{rank}\in\overline{0,\mathtt{numprocs}-1}\). Let us distribute all elements of the matrix \(A\) into blocks between the processes involved in the calculations using the two-dimensional division of the matrix into blocks (see Figure 2). In this case, the number of splits along the vertical will be denoted as \(\mathtt{num\_row}\) (short for _number of rows_), and the number of splits along the horizontal--\(\mathtt{num\_col}\) (short for _number of columns_). As a result, matrix \(A\) of dimension \(M\times N\) will be divided into parts \(A_{part(\mathtt{rank})}\) of dimension \(M_{part(m)}\times N_{part(n)}\). Here, the process number \(\mathtt{rank}\) is related to indices \(m\) and \(n\) as follows:  
\[m=\left\lfloor\frac{\mathtt{rank}}{\mathtt{num\_col}}\right\rfloor,\quad n= \mathtt{rank}-\left\lfloor\frac{\mathtt{rank}}{\mathtt{num\_col}}\right\rfloor \cdot\mathtt{num\_col}.\]  
**Remark 3**. : _Let us immediately pay attention to the fact that the chosen indexing method assumes that all processes will take part in the calculations, that is, \(\mathtt{num\_row}\cdot\mathtt{num\_col}\equiv\mathtt{numprocs}\)._  
Note also that  
\[\sum_{m=0}^{\mathtt{num\_row}-1}M_{part(m)}=M,\quad\sum_{n=0}^{\mathtt{num\_col }-1}N_{part(n)}=N.\]  
Thus, it is assumed that each MPI process contains the array A_part, which contains one of the parts \(A_{part(. )}\) of matrix \(A\). In addition, each process contains arrays x_part and b_part, which contain one of the parts \(x_{part(. )}\) and \(b_{part(. )}\) of vectors \(x\) and \(b\), respectively. The storage structure of the vectors \(x\) and \(b\) on different processes is also shown in Figure 2. It is clearly seen that the part \(x_{part(n)}\) of the vector \(x\) for a fixed index \(n\) is stored in all cells of the process grid column with index \(n\). Similarly, the part \(b_{part(m)}\) of vector \(b\) for a fixed index \(m\) is stored in all cells of the process grid row with index \(m\). Figure 2: An example of data distribution among nine MPI processes that form a \(3\times 3\) grid. Parallel Algorithm for Matrix-Vector Multiplication in the Case of Two-Dimensional Division of the Matrix into Blocks  
The terms that arise when calculating the product of a matrix and a vector can be divided into groups as follows (we give an example corresponding to Figure 3, when only nine MPI processes are involved in the calculations). This form of representation of the multiplication of a matrix by a vector was chosen in order to clearly show that the vector \(x\) (it is assumed that it consists of \(N\) elements) does not need to be stored entirely on each process. Each process needs only its own part \(x_{part(n)}\) of this vector with \(N_{part(n)}\) elements, where \(n\in\overline{0,\texttt{num\_col}-1}\). Then, each process participating in the calculations will perform the operation of multiplying its part \(A_{part(\texttt{rank})}\) of matrix \(A\) by its part \(x_{part(n)}\) of vector \(x\). As a result of this operation, the vector \(b_{part\_temp(m,n)}\) will be calculated, which will be one of the terms of the part \(b_{part(m)}\) of the final vector \(b\). Each process participating in the calculation can perform this action independently of other processes while operating only with the data that are  
Figure 3: A parallel algorithm for matrix–vector multiplication in the case of a two-dimensional division of the matrix into blocks. located in the memory of this process. These calculation actions can be implemented in parallel.