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)
MATRIX DETERMINANT, LAPLACE'S THEOREM, BLOCK MATRIX, QUASI-DIAGONAL MATRIX, RIBBON MATRIX, BINARY VECTOR, HALF DIVISION, SYMBOLIC COMPUTATION, PARALLEL CALCULATION, ELECTRICAL NETWORK
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
[1] Zarubin V.S., Kuvyrkin G.N. Special features of mathematical modeling of technical instruments. Маthematical Modeling and Computational Methods, 2014, no. 1, pp. 5–17.
[2] Gergel V.P. Teorya i praktika parallelnyh vychislenij. Elektronnaya kniga [Theory and practice of parallel computing. E–book]. N. Novgorod, INTU-IT Publ., 355 p.
[3] Ortega J. Introduction to Parallel and Vector Solution of Linear Systems. Springer, 1988, 316 p.
[4] Belyaev N.A. Avtomaticheskoe konstruirovanie vysokoproizvoditel’nyh paralel’nyh program dlya zadach lineynoj razryazhennoj algebry v sisteme LuNA [Automatic design of high-performance parallel programs for sparse linear algebra problems in the LuNA system]. Problems of computer science, 2022, no. 3 (56), pp. 46–60.
[5] Middeke J., Jeffrey D.J., Koutschan C. Common factors in fraction-free matrix decompositions. Mathematics in Computer Science, 2020, vol. 15, no. 103, pp. 589–608.
[6] Korn G., Korn T. Mathematical Handbook for scientists and engineers. McGraw-Hill Book Company, 1968, 1130 p.
[7] Sigorskij V.P. Matematicheskij apparat inzhenera [Mathematical apparatus of an engineer]. Kiev, Technika, 1975, 768 p.
[8] Gantmaher F.R. Teoriya matrits [Matrix theory]. Moskva, Nauka Publ., 1966, 577 p.
[9] Tou D. Sostavlenie uravnenij tsepi s pomoschʹyu metodov razbieniya [Compilation of circuit equations using partitioning methods]. TIIER, 1967, vol. 55, no. 11, pp. 263–265.
[10] Filaretov V. V. Teorema Sigorskogo ob opredelitele summy matric i diakoptika [Sigorsky’s theorem on the determinant of the sum of matrices and diakoptic]. Elektronika i svyaz'. Vypusk «Elektronika i nanotekhnologii» [Electronics and communications. Issue "Electronics and nanotechnology"], 2010, no. 2, pp. 5–13.
[11] Filaretov V.V. A method of binary vectors for a topological analysis of electronic circuits by parts. Electrical Technology Russia, 2001, no. 8, pp. 33–42.
[12] Filaretov V.V., Gorshkov K.S., Kurganov S.A., Nedorezov M.V. Generalized Parameter Extraction Method for Symbolic Analysis of Analog Circuits Containing Pathological Elements. Lecture Notes in Electrical Engineering, 2018, vol. 479 (Pathological Elements in Analog Circuit Design), pp. 31–70.
[13] Filaretov V., Gorshkov K. Efficient generation of compact symbolic network functions in a nested rational form. International Journal of Circuit Theory and Applications: Research articles, 2020, vol. 48, no. 7, pp. 1032-1056.
[14] Buchberger B., Collins J., Loos R. Kompʹyuternaya algebra: simvolnye i algebraicheskie vychisleniya [Computer algebra: Symbolic and algebraic calculations]. Moscow, MIR Publ., 1986, 392 p.
[15] Dyakonov V.P. Maple 10/11/12/13/14 v matematicheskih raschetah [Maple 10/11/12/13/14 in mathematical calculations]. Moscow, DMK Press, 2011, 800 p.
[16] Filaretov V.V. Synthesis of optimal formulae for functions of electrical circuit. Electrical Technology Russia, 1995, no. 4, pp. 36–43.
[17] Filaretov V.V. Skhemnoe otobrazhenie matricy dlya simvolnogo resheniya system linejnyh algebraicheskih uravnenij [Schematic representation of a matrix for symbolic solution of systems of linear algebraic equations]. Logical-algebraic Methods, Models, Applied Using. Proc. Int. Conf. KLIN–2001. Ulyanovsk: UlSTU, 2001, vol. 3, pp. 13–15.
[18] Korolev F.A., Filaretov V.V. Sravnenie metodov naraschivaniya i polovinnogo deleniya pri simvol’nom raskrytii matrichnyh opredeliteley [Com-parison of methods of extension and poly-wine division with symbolic disclosure of matrix determinants]. Synthesis, analysis and diagnostics of electronic circuits: Int. Collection of scientific papers. Ulyanovsk, UlSTU publ., 2009, iss. 7, pp. 183–193.
[19] Filaretov V.V. Generatsiya kompaktnyh formul dlya matrichnyh opredelitelej [Generation of compact formulas for matrix determinants]. Synthesis, analysis and diagnostics of electronic circuits: Int. Collection of scientific papers. Ulyanovsk, UlSTU publ., 2012, issue 10, pp. 120–133.
[20] Shi G. Computational complexity analysis of determinant decision diagram. IEEE Transactions on Circuits and Systems II: Express Briefs, 2010, vol. 57, no. 10, pp. 828–832.
[21] Nedorezov M. V., Filaretov V. V. Minimalnye formuly opredelitelej polnykh matrits na osnove ikh polovinnogo deleniya [Minimal formulas of determinants of complete matrices based on their half division]. Synthesis, analysis and diagnostics of electronic circuits: Int. Collection of scientific papers. Ulyanovsk, Ul-GTU publ., 2020, issue 16, pp. 124–144.
[22] Nedorezov P. V., Filaretov V. V. Optimizatsiya simvolnyh opredelitelej razrezhennyh matric [Optimization of symbolic definitions of sparse matrices]. Synthesis, analysis and diagnostics of electronic circuits: Int. Collection of scientific papers. Ulyanovsk, UlSTU publ., 2020, issue 16, pp. 153–163.
[23] Nedorezov M. V., Timofeev V. F., Filaretov V. V. Vychislenie simvolnykh opredelitelej polnykh matrits na osnove [Calculation of symbolic determinants of complete matrices on the basis of their half division and line extension]. Synthesis, analysis and diagnostics of electronic circuits: Int. Collection of scientific papers. Ulyanovsk. UlSTU publ., 2022, issue 17, pp. 120–134.
[24] Kuzmin N. P., Kurganov D. S., Filaretov V. V. Parallelnyj raschet simvolnyh opredelitelej polnyh matric vysokogo poryadka pri proizvolnom chisle processorov [Parallel calculation of symbolic determinants of complete high-order matrices with a free number of processors]. Synthesis, analysis and diagnostics of electronic circuits: Int. Collection of scientific papers. Ulyanovsk, UlSTU publ, 2022, issue 17, pp. 135–141.
[25] Gorshkov K. S., Nedorezov P. V., Filaretov V. V. Generaciya i vychislenie kompaktnyh simvolnyh opredelitelej dlya razrezhennyh matric vysokogo poryadka [Generation and calculation of compact symbolic determinants for sparse matrices of high order]. Synthesis, analysis and diagnostics of electronic circuits: Int. Collection of scientific papers. Ulyanovsk, UlSTU publ., 2022, issue 17, pp. 142–151.
[26] Brameller A., Alan R., Hamam Ya. Sparsity. Its Practical Application to Systems Analysis. London, Pitman publ., 1976, 177 p.
[27] Dimo P. L'analyse nodale des réseaux d'énergie. Paris, Eyrolles, 1971, 269 p.
[28] Wilkinson J. H., Reinsch C. Handbook for Automatic Computation. Linear Algebra. Berlin, Springer-Verlag, New York, Heidelberg, 1971, 441 p.
Кузьмин Н. П., Курганов Д. С., Курганов С. А., Филаретов В. В. Алгоритмы параллельного расчета определителей разреженных матриц на основе поло-винного деления. Математическое моделирование и численные методы, 2025, № 3, с. 117–141.
Download article
Количество скачиваний: 118