USPARS – FOR SOLVING LARGE SPARSE SLAE
The software package is a direct optimized solver of large sparse systems of linear algebraic equations (SLAE) on multiprocessor systems with shared memory.
Sparse systems of equations are systems with coefficient matrices in which the number of non-zero elements is much less than the size of the matrix. Depending on the size of the available memory, the dimensions of the matrices of the solved systems can reach several million, with several hundred million non-zero elements.
Such a volume of data arises in problems related to numerical modeling of physical processes (heat transfer, acoustic, elastic and electromagnetic wave processes), mathematical modeling in various fields (economics, logistics, medicine), when performing engineering calculations in CAD/CAE systems.
To improve performance, calculations are parallelized using the OpenMP library. This allows you to speed up work when increasing the number of computing cores.
USPARS software can be used as an independent computing program or as a computing core in IT application systems.
Implementation
The USPARS package uses the entire set of computational techniques that have proven their effectiveness for solving SLAEs with sparse coefficient matrices – these are permutations of different types (matching, pivoting, etc.), balancing of coefficients, iterative refinement, global permutations.
A number of original components have been developed. For example, to find permutations of matrices in order to reduce the occupancy of triangular factors, the Atlant component has been created. It uses a combined algorithm based on the multi-level method of nested sections and the effective author’s method of reordering small-sized subgraphs.
Using multithreading
To improve performance, calculations in USPARS are parallelized using the tools of the OpenMP library. This allows you to speed up work when increasing the number of computing cores. You can set the number of omp streams used in the program yourself.
Two modes of operation
The package is available in two modes:
In-Core (IC) – a mode in which all intermediate results are stored in RAM of the computer system;
Out-Of-Core (OOC) – a mode in which a disk is used to store part of the intermediate data.
The use of disk memory in the OOC mode makes it possible to somewhat increase the size of the SLAEs available for the solution. However, due to the inclusion of data exchange between the RAM and the disk in the solution process, the computation time increases compared to the IC mode.
USPARS versions and related services
Basic version – new releases are launched several times a year.
Custom versions – built on the basis of the basic version, they include additional functionality.
SLAE custom calculations are performed as well.
Documentation
USPARS software has a user manual that describes in detail its full range of functionality.
Competitors
The most well-known analogues of the USPARS solver are software packages MKL PARDISO, MUMPS, PARDISO, SuperLU, TAUCS, UMFPACK.
Mathematical overview
Sometimes matrices are called sparse, when information about the structure of non-zero elements leads to a gain in the performance of algorithms for solving systems of linear equations with corresponding coefficient matrices.
To store sparse matrices, there are special structures that allow you to minimize the amount of memory required for such matrices and ensure efficient work with them. USPARS uses the CSR (compressed sparse row) format to store and process sparse matrices. In USPARS, the input matrices for calculations must be submitted in this format, and as a result, dense vector solutions are produced.
To solve a system of linear equations
A X = F
with a sparse matrix of coefficients A of size NxN and a dense matrix F of size Nxk, the matrix A is decomposed into the product of several matrices that are lower- or upper-triangular and diagonal, followed by solving the obtained systems of equations with triangular matrices. USPARS uses several types of triangular factorization of sparse matrices; the specific type is determined by whether the matrix belongs to a particular class, depending on the symmetry properties and positive definiteness of the coefficient matrix.
USPARS allows you to solve single and double precision systems of linear equations. Double-precision matrices require twice as much memory to store, and calculations can take twice as long. But using double precision allows you to perform arithmetic operations more accurately, which can be essential for matrices with large condition numbers.
Publications
1. M. Cherepanov, V.Kostin, A.Semenov, S.Solovyev. Developing a direct sparse solver for the Elbrus processors. // Abstracts of the international conference “Marchuk scientific readings-2021”, p.121, Novosibirsk, 2021.
2. M. Cherepanov, V.Kostin, A.Semenov, S.Solovyev. Efficient direct sparse solver for different processor architectures. // Abstracts of the international conference “Marchuk scientific readings-2022”, p.99, Novosibirsk, 2022.
3. D. Bykov, V.Kostin, S.Solovyev. USPARS software package for large sparse systems. // Тезисы I Всероссийской школы-семинара НЦФМ “Центр исследования архитектур суперкомпьютеров” Abstracts of the First all-Russian NSPM school-seminar “Center for the study of supercomputer architectures”, p. 24-25, Sarov, 2023
4. D. Bykov, V.Kostin, S.Solovyev, USPARS – parallel direct sparse SLAE solver // Proceedings of the international conference “Supercomputing Days in Russia”, Moscow, 2023.
5. Bykov D., Kostin V., Solovyev S. Software Package USPARS for Large Sparse Systems of Linear Equations //Russian Supercomputing Days, p. 232-244. Cham : Springer Nature Switzerland, 2023.
6. USPARS PC is distributed with an academic license // 12.12.2023, IT-World portal
7. V.Kostin, S.Solovyev, I.Golosov, Y. Danilova, A.Semenov, D. Bykov, M.Cherepanov. USPARS software package for solving systems of linear algebraic equations in modeling problems.// Science and Technology of Siberia, p.24-28, Novosibirsk, 2023.
Communication
If you are interested in information about this product, please write to us.