DOI: 10.17587/prin.11.242-250

Estimation of the Speed of a New Parallel Block Algorithm for Finding Solutions of the Large Sparse Linear Systems over a Large Prime Field

M. A. Cherepnev, Ph. D., Associate Professor, cherepniov@gmail.com, Lomonosov Moscow State University, Moscow, 119992, Russian Federation

Corresponding author: Cherepnev Michail A., Ph. D., Associate Professor, Lomonosov Moscow State University, Moscow, 119992, Russian Federation, E-mail: cherepniov@gmail.com

The question of how to estimate the running time of a program that implements an algorithm for solving a large sparse system of equations over a large prime field, described in [1,2], on a computer system of K independent computing nodes is considered. The article considers the topology that connects nodes of the computer network, "torus". At the same time, we believe that in each of the two directions of this torus, there are connections with different bandwidth. In reality, this may correspond to large computing clusters connected by a relatively slow Internet network, or multiple multi-core (possibly with virtual cores) processors in the same cluster. At the same time, the estimates of working time take into account not only the time for the invoice, as in [2], but also the time for forwarding. The block nature of the algorithm allows us to reduce the running time of the sequential scalar version (Montgomerys algorithm [3]) by approximately √K times, with K growing to the size of the original problem. At the same time, about half of all switching is allowed to be slow, which makes it possible to dial the necessary number of computing nodes from different clusters. A specific distributed storage of intermediate results of calculations is proposed. This results in saving not only computing resources, but also time for transmission, which is carried out in parallel over independent branches of our network. In addition, the solution of dense systems of linear equations, which must be done at each step of our algorithm, as well as the inversion of dense matrices, we suggest using parallel calculations. This will reduce the conversion time of matrices of size sxs to O(s²) and the total running time of the entire program for solving a sparse system of linear equations in a space of dimension N to O(N²/√K) for an arbitrary K, from 1 to N. Thus, theoretically, the optimal time O(N^3/2) is obtained.

Keywords: discrete logarithm method, Lanczos method, parallel computing, block algorithms

pp. 242–250

For citation:
Cherepnev M. A. Estimation of the Speed of a New Parallel Block Algorithm for Finding Solutions of the Large Sparse Linear Systems over a Large Prime Field, Programmnaya Ingeneria, 2020, vol. 11, no. 4, pp. 242—250

This work was supported by the Russian Foundation for Basic Research, project nos. 18-29-03421 мк.