512.644 Алгоритмы параллельного расчета определителей разреженных матриц на основе половинного деления

Кузьмин Н. П. (Институт радиотехники и электроники им. В.А.Котельникова Российской академии наук), Курганов Д. С. (ООО «Телеком.ру»), Курганов С. А. (Ульяновский государственный технический университет), Филаретов В. В. (Ульяновский государственный технический университет)

ОПРЕДЕЛИТЕЛЬ МАТРИЦЫ, ТЕОРЕМА ЛАПЛАСА, БЛОЧНАЯ МАТРИЦА, КВАЗИДИАГОНАЛЬНАЯ МАТРИЦА, ЛЕНТОЧНАЯ МАТРИЦА, ДВОИЧНЫЙ ВЕКТОР, ПОЛОВИННОЕ ДЕЛЕНИЕ, СИМВОЛЬНОЕ ВЫЧИСЛЕНИЕ, ПАРАЛЛЕЛЬНЫЙ РАСЧЕТ, ЭЛЕКТРИЧЕСКАЯ СЕТЬ


doi: 10.18698/2309-3684-2025-3-117141


Предложено разложение определителя разреженной, в том числе ленточной, матрицы на сумму определителей квазидиагональных матриц. Разработаны и реализованы алгоритмы рекурсивного разложения определителя матрицы, представленной в виде двух диагональных блоков или половин от деления по горизонтали или вертикали с учетом нулевых строк и столбцов для параллельного расчета. Доказано, что при делении ленточной матрицы с шириной ленты 2m+1 пополам горизонтально (вертикально) на равное или отличающееся на единицу число строк (столбцов) миноры одной подматрицы соответствуют сочетаниям из 2m столбцов (строк) по m, а сопряженные миноры – дополнениям этих сочетаний в другой подматрице, что упрощает применение теоремы Лапласа. Введено понятие матричного двоичного вектора. Установлена связь сочетаний номеров строк и столбцов матрицы с половинами двоичных векторов, содержащими равное количество единиц. Использование миноров половинного порядка приводит решение задачи к подзадачам минимальной одинаковой размерности, обеспечивая равномерную загрузку процессоров (вычислительных ядер). Многократно уменьшается время расчета как целочисленных, так и численных (с ограниченным числом десятичных разрядов) определителей. При одно-, 6-ти и 12-ти поточных режимах время целочисленного расчета определителей матриц порядка 400…999 уменьшается по сравнению со временем оператора Det сиcтемы Maple в 5…3, 23…15 и 40…27 раз, а вре-мя численного расчета – в 1,3…2,8 и 2,5…5,5 раз при числе потоков 6 и 12 и порядке матриц 900…2000. Половинное деление реализовано в программе символьного раскрытия и вычисления определителя матрицы, но может быть использовано для простой параллельной модификации любой программы численного решения систем линейных алгебраических уравнений.


[1] Зарубин В.С., Кувыркин Г.Н. Особенности математического моделирования технических устройств. Математическое моделирование и численные методы, 2014, № 1, с. 5–17.
[2] Гергель В.П. Теория и практика параллельных вычислений. Электронная книга. Н. Новгород, ИНТУИТ, 2007, 355 c.
[3] Ортега Дж. Введение в параллельные и векторные методы решения ли-нейных систем. Москва, Мир, 1991, 367 с.
[4] Беляев Н.А. Автоматическое конструирование высокопроизводительных параллельных программ для задач разреженной линейной алгебры в системе LuNA. Проблемы информатики, 2022, №3 (56), с. 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] Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. Москва, Наука,1974, 831 с.
[7] Сигорский В.П. Математический аппарат инженера. Киев, Техника, 1975, 768 с.
[8] Гантмахер Ф.Р. Теория матриц. Москва, Наука, 1966, 577 с.
[9] Тоу Д. Составление уравнений цепи с помощью методов разбиения.
ТИИЭР, 1967, т. 55, № 11, с. 263–265.
[10] Филаретов В. В. Теорема Сигорского об определителе суммы матриц и диакоптика. Электроника и связь. Выпуск "Электроника и нанотехнологии", 2010, № 2, с. 5–13.
[11] Филаретов В.В. Метод двоичных векторов для топологического анализа электронных схем по частям. Электричество, 2001, № 8, с. 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] Бухбергера Б., Коллинза Дж., Лооса Р. Компьютерная алгебра: Символьные и алгебраические вычисления. Москва, Мир, 1986, 392 с.
[15] Дьяконов В.П. Maple 10/11/12/13/14 в математических расчетах. Москва, ДМК Пресс, 2011, 800 с.
[16] Филаретов В.В. Синтез оптимальных формул схемных функций электрических цепей. Электричество, 1995, № 4, с. 36-43.
[17] Филаретов В.В. Схемное отображение матрицы для символьного решения систем линейных алгебраических уравнений. Логико-алгебраические методы, модели, прикладные применения: Труды международународной конференции КЛИН–2001. Ульяновск, УлГТУ, 2001, т. 3, с. 13–15.
[18] Королев Ф.А., Филаретов В.В. Сравнение способов наращивания и половинного деления при символьном раскрытии матричных определителей. Синтез, анализ и диагностика электронных цепей: Международный сборник научных трудов. Ульяновск, УлГТУ, 2009, вып. 7, с. 183–193.
[19] Филаретов В.В. Генерация компактных формул для матричных опреде-лителей. Синтез, анализ и диагностика электронных цепей: Международный сборник научных трудов. Ульяновск, УлГТУ, 2012, вып. 10, с. 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] Недорезов М. В., Филаретов В. В. Минимальные формулы определителей полных матриц на основе их половинного деления. Синтез, анализ и диагностика электронных цепей: Международный сборник научных трудов. Ульяновск, УлГТУ, 2020, вып. 16, с. 124–144.
[22] Недорезов П. В., Филаретов В. В. Оптимизация символьных определителей разреженных матриц. Синтез, анализ и диагностика электронных цепей: Международный сборник научных трудов. Ульяновск, УлГТУ, 2020, вып. 16, с. 153–163.
[23] Недорезов М. В., Тимофеев В. Ф., Филаретов В. В. Вычисление символьных определителей полных матриц на основе их половинного деления и наращивания строк. Синтез, анализ и диагностика электронных цепей: Международный сборник научных трудов. Ульяновск, УлГТУ, 2022, вып. 17, с. 120–134.
[24] Кузьмин Н. П., Курганов Д. С., Филаретов В. В. Параллельный расчет символьных определителей полных матриц высокого порядка при произвольном числе процессоров. Синтез, анализ и диагностика электрон-ных цепей: Международный сборник научных трудов. Ульяновск, УлГТУ, 2022, вып. 17, с. 135–141.
[25] Горшков К. С., Недорезов П. В., Филаретов В. В. Генерация и вычисление компактных символьных определителей для разреженных матриц высокого порядка. Синтез, анализ и диагностика электронных цепей: Международный сборник научных трудов. Ульяновск, УлГТУ, 2022, вып. 17, с. 142–151.
[26] Брамеллер А., Алан Р., Хэмэм Я. Слабозаполненные матрицы. Анализ электроэнергетических систем. Москва, Энергия, 1979, 192 с.
[27] Димо П. Узловой анализ электрических систем. Москва, Мир, 1973, 264 с.
[28] Уилкинсон Д., Райнш К. Справочник по алгоритмам на языке Алгол. Линейная алгебра. Москва, Машиностроение, 1976, 389 c.


Кузьмин Н. П., Курганов Д. С., Курганов С. А., Филаретов В. В. Алгоритмы параллельного расчета определителей разреженных матриц на основе поло-винного деления. Математическое моделирование и численные методы, 2025, № 3, с. 117–141.



Скачать статью

Количество скачиваний: 8