## 4 Parallel Version of the Improved Algorithm and Its Software Implementation
### Taking into Account the Capabilities of the Standard MPI-4
If only nodes with good localization in the communication environment are used for computing, better results for the efficiency of software implementation can be obtained compared to the results shown in Figure 5.

### Scalability: Strong and Weak Scaling

It is well known that the weak point of parallel algorithms for solving systems of linear algebraic equations with a dense matrix is the relatively poor strong scalability of many possible software implementations (as can be seen from Figure 5). This can be explained as follows on the example of a parallel algorithm for matrix-vector multiplication (see Figure 3), which is the main operation in the considered Algorithms 3 and 4. All MPI processes participate in parallel computations, and, as a result, all computations are accelerated by \(n\) times (\(n\equiv\) numprocs). At the same time, the volume of transmitted messages is proportional to \(\dfrac{1}{\sqrt{n}}\), which means that it decreases with an increase in the number of processes involved in the calculations. However, with an increase in the number of processes participating in calculations, the number of message exchanges between the processes of auxiliary communicators increases, which is proportional to \(\log_{2}\sqrt{n}\). It turns out that with an increase in the number \(n\) of processes involved in calculations, the computation time is proportional to \(\dfrac{1}{n}\), and the time to exchange messages between processes is proportional to \(\dfrac{\log_{2}\sqrt{n}}{\sqrt{n}}\). Figure 6: Graphs of the dependence of the parallel program running time in the case of good localization of computing nodes in the communication network (solid line) and poor localization (dotted line). Thus, starting from a certain number of processes (this number depends on the computational size of the problem and on the configuration of the multiprocessor system), the portion of overhead costs for the exchange of messages between processes will begin to increase. This, as a consequence, will inevitably lead to a decrease in the efficiency of software implementation with an increase in the number of processes involved in the calculations. Therefore, additional calculations were carried out to test the proposed software implementations for weak scalability. Weak scalability means maintaining efficiency as the number of processes participating in computations increases while keeping the amount of computational work that each process performs constant. Thus, the weak scalability test was performed by simultaneously increasing the problem size (\(M:=\sqrt[3]{n}\,M\), \(N:=\sqrt[3]{n}\,N\), \(s:=\sqrt[3]{n}\,s\)) and the number \(n\) of processes involved in the computation. Figure 7 shows graphs of the parallelization efficiency \(E_{n}=\frac{T_{1}}{T_{n}}\) depending on the number of computing nodes \(n\) involved in the calculations. As can be seen from the presented graphs, the proposed software implementations of the algorithm have the property of weak scalability. This again shows the advantage of using the MPI-4 standard. ## 6 Discussion

1. All program examples are built in such a way that they can be easily rewritten using the C/C++/Fortran programming languages. This is due to the fact that all MPI functions used in Python software implementations use a syntax equivalent to the syntax of the corresponding MPI functions in the C/C++/Fortran programming languages. 2. If there are GPUs on the computing nodes, the programs can be easily modified by replacing the main calculations using the function dot() from the package numpy with calculations using a similar function from the package cupy, which will allow for the use of GPUs for calculations. Thus, it is easy to use MPI+OpenMP+CUDA hybrid parallel programming technologies. Due to the fact that changes in the software implementation will be quite simple, the program code is not shown here. 3. The algorithm is primarily designed to solve systems of linear equations with a dense matrix. It has not been tested for solving systems of linear equations with a sparse matrix.