Николай Павлович Кузьмин (Институт радиотехники и электроники им. В.А.Котельникова Российской академии наук) :
Статьи:
Кузьмин Н. П. (Институт радиотехники и электроники им. В.А.Котельникова Российской академии наук), Курганов Д. С. (ООО «Телеком.ру»), Курганов С. А. (Ульяновский государственный технический университет), Филаретов В. В. (Ульяновский государственный технический университет)
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. Половинное деление реализовано в программе символьного раскрытия и вычисления определителя матрицы, но может быть использовано для простой параллельной модификации любой программы численного решения систем линейных алгебраических уравнений.
Кузьмин Н. П., Курганов Д. С., Курганов С. А., Филаретов В. В. Алгоритмы параллельного расчета определителей разреженных матриц на основе поло-винного деления. Математическое моделирование и численные методы, 2025, № 3, с. 117–141.