"Разработка метода 'экстра-компонент' для быстрого вычисления дискретных преобразований". Андрей Валерьевич Терехов, ИВМиМГ СО РАН, 28.2.2023
Состав коллектива
- Терехов Андрей Валерьевич, ИВМиМГ СО РАН, д.ф.-м.н.
Аннотация
При расчёте дискретных преобразований необходимо иметь в своем распоряжении быстрые алгоритмы умножения векторов на матрицы, элементы которых задаются как значения специальных функций: Чебышева, Лежандра, Лагерра, Якоби, Гегенбауэра сферические, тригонометрические и многие другие. На данный момент существующие быстрые алгоритмы на порядки уступают в вычислительной экономичности процедуре быстрого преобразования Фурье. С целью увеличения производительности в проекте поставлена задача разработать высокоэффективный общий подход для вычисления матрично-векторных произведений для широкого класса задач. В итоге для вычисления матрично-векторного произведения была разработана серия быстрых алгоритмов, отличающихся простотой структуры и допускающих эффективную программную реализацию для современных микропроцессоров. Вычислительные эксперименты подтвердили, что новые процедуры имеют сложность порядка O (N log N), что позволяет сократить время счёта на несколько порядков по сравнению с прямым методом умножения вектора на матрицу.
Публикации
- Andrew V. Terekhov, Generating the Laguerre expansion coefficients by solving a one-dimensional transport equation. Numerical Algorithms 89, 303–322 (2022), DOI: 10.1007/s11075-021-01115-8.
- Andrew V. Terekhov, A divide-and-conquer algorithm for seismic data approximation by the Laguerre series//J. Phys.: Conf. Ser. 2099 012062, 2021. DOI: 10.1088/1742-6596/2099/1/012062
- Terekhov, A.V. An extra-component method for evaluating fast matrix-vector multiplication with special functions. Numer Algor (2022). DOI: 10.1007/s11075-022-01383-y