## 3 Approaches to Building a Parallel Algorithm and Its Software Implementation
### Distribution of Data by MPI Processes Participating in Computations
Each process participating in the calculation can perform this action independently of other processes while operating only with the data that are located in the memory of this process. We are implementing these actions in parallel. Then, the corresponding summands \(x_{part\_temp(m,n)}\) along each column of the process grid (i.e., index \(n\) is fixed) must be collected (due to message exchange between processes) and measured on at least one process and summed up. Thus, this parallel algorithm (taking into account the two-dimensional division of matrix \(A\) into blocks) contains the following features. 1. Each process should store not the whole vector \(b\), but only a part \(b_{part(m)}\) of this vector. The vector \(b_{part(m)}\) will have to be sent not to all the processes of the communicator comm, but only to a part of the processes of this communicator--to the processes of the row with index \(m\) of the process grid. In this case, the transfer of data among the processes of each row of the process grid can be organized in parallel with the transfer of data among the processes of other rows of the grid of processes, which will give a gain in time. 2. When calculating the part \(x_{part(n)}\) of the final vector \(x\), it is necessary to exchange messages not with all processes of the communicator comm, but only with part of the processes of this communicator--with the processes of the column with index \(n\) of the introduced grid of processes. In this case, the data transfer along each column of the process grid can be organized in parallel with the transfer of data among the processes of other columns of the process grid, which will also give a gain in time. As you can clearly see, the parallel algorithm for multiplying a transposed matrix by a vector in the case of a two-dimensional division of a matrix into blocks has symmetry with respect to the parallel algorithm for multiplying a matrix by a vector, considered in the previous section. This algorithm is obtained from the previous one by replacing \(m\leftrightarrow n\) and \"rows\"\(\leftrightarrow\) \"columns\". In this case, all actions are performed not with parts of the matrix \(A_{part(\text{rank})}\), but with their transposed parts \(A^{T}_{part(\text{rank})}\). Thus, the softwareimplementation of this algorithm will not differ much from the software implementation of the parallel algorithm for matrix-vector multiplication (including the need to work with additional communicators that will contain only those groups of processes among which we want to organize data exchange interactions using the functions of the collective process interactions). Thus, a parallel software implementation of multiplying a transposed matrix by a vector (taking into account the fact that we operate with elements of the original non-transposed matrix) can be formalized in the following form:  
x_part_temp = dot(A_part.T, b_part)  x_part = empty(N_part, dtype=float64)  comm_col.Allreduce([x_part_temp, N_part, MPI.DOUBLE],  [x_part, N_part, MPI.DOUBLE], op=MPI.SUM)  
Note that the result of such a multiplication (vector \(x\)) will be stored on all processes in parts: part \(x_{part(n)}\) of the vector \(x\) for a fixed index \(n\) will be stored in all cells of the process grid column with index \(n\).