N P Kuzmin (Institute of Radio Engineering and Electronics of the Russian Academy of Sciences) :
Articles:
512.644 Parallel calculation of determinants of sparse matrices based on half minors
Kuzmin N. P. (Institute of Radio Engineering and Electronics of the Russian Academy of Sciences), Kurganov D. S. («Telekom.ru» LLC), Kurganov S. A. (Ulyanovsk State Technical University), Filaretov V. V. (Ulyanovsk State Technical University)
doi: 10.18698/2309-3684-2025-3-117141
The decomposition of the determinant of a sparse, including ribbon, matrix into the sum of the determinants of quasi-diagonal matrices is proposed. Algorithms for recursive decomposition of the determinant of a matrix presented in the form of two diagonal blocks or halves from horizontal or vertical division, taking into account zero rows and columns for parallel calculation, have been developed and implemented. It is proved that when dividing a ribbon matrix with a ribbon width of 2m+1 in half horizontally (vertically) into an equal or different number of rows (columns), the minors of one submatrix correspond to combinations of 2m columns (rows) in m, and the conjugate minors correspond to the complements of these combinations in another submatrix, which simplifies the application of Laplace's theorem. The concept of a matrix binary vector is introduced. The relationship of combinations of row and column numbers of the matrix with halves of binary vectors containing an equal number of units is established. The use of half-order minors leads the solution of the problem to subtasks of the minimum identical dimension, ensuring uniform loading of processors (computing cores). The calculation time for both integer and numerical (with a limited number of decimal places) determinants is reduced many times. With one, 6 and 12 inline modes, the time of integer calculation of matrix determinants of the order of 400...999 decreases in comparison with the time of the Det operator of the Maple system by 5...3, 23...15 and 40...27 times, and the time of numerical calculation by 1.3...2.8 and 2.5...5.5 times with the number of threads 6 and 12 and the order of the matrices 900...2000. Half division is implemented in the program of symbolic disclosure and calculation of the determinant of the matrix, but can be used for a simple parallel modification of any program for the numerical solution of systems of linear algebraic equations
Кузьмин Н. П., Курганов Д. С., Курганов С. А., Филаретов В. В. Алгоритмы параллельного расчета определителей разреженных матриц на основе поло-винного деления. Математическое моделирование и численные методы, 2025, № 3, с. 117–141.