Личный кабинет
Подробное описание документа
Алгоритмы параллельного расчета определителей разреженных матриц на основе половинного деления / Кузьмин Н. П., Курганов Д. С., Курганов С. А., Филаретов В. В. - DOI 10.18698/2309-3684-2025-3-117141. - URL: https://mmcm.bmstu.ru/articles/386/ (дата обращения: 23.04.2026) // Математическое моделирование и численные методы. - 2025. - № 3. -
Скачать документ
Предложено разложение определителя разреженной, в том числе ленточной, матрицы на сумму определителей квазидиагональных матриц. Разработаны и реализованы алгоритмы рекурсивного разложения определителя матрицы, представленной в виде двух диагональных блоков или половин от деления по горизонтали или вертикали с учетом нулевых строк и столбцов для параллельного расчета. Доказано, что при делении ленточной матрицы с шириной ленты 2m+1 пополам горизонтально (вертикально) на равное или отличающееся на единицу число строк (столбцов) миноры одной подматрицы соответствуют сочетаниям из 2m столбцов (строк) по m, а сопряженные миноры – дополнениям этих сочетаний в другой подматрице, что упрощает применение теоремы Лапласа. Введено понятие матричного двоичного вектора. Установлена связь сочетаний номеров строк и столбцов матрицы с половинами двоичных векторов, содержащими равное количество единиц. Использование миноров половинного порядка приводит решение задачи к подзадачам минимальной одинаковой размерности, обеспечивая равномерную загрузку процессоров (вычислительных ядер). Многократно уменьшается время расчета как целочисленных, так и численных (с ограниченным числом десятичных разрядов) определителей. При одно-, 6-ти и 12-ти поточных режимах время целочисленного расчета определителей матриц порядка 400…999 уменьшается по сравнению со временем оператора Det системы Maple в 5…3, 23…15 и 40…27 раз, а время численного расчета – в 1,3…2,8 и 2,5…5,5 раз при числе потоков 6 и 12 и порядке матриц 900…2000. Половинное деление реализовано в программе символьного раскрытия и вычисления определителя матрицы, но может быть использовано для простой параллельной модификации любой программы численного решения систем линейных алгебраических уравнений.
Статья опубликована в следующих изданиях
№ 3. - 2025.
