Семинар научного отдела вычислительной физики

Системы линейных алгебраических уравнений (СЛАУ) с ленточными матрицами коэффициентов возникают во многих научных, инженерных и работающих в реальном времени приложениях, зачастую занимая большую часть вычислительного времени в задачах метода конечных элементов и метода конечных разностей. В связи с этим разработка эффективных алгоритмов решения таких систем является актуальной задачей.

Данная работа основывается на параллельном алгоритме разбиения для трехдиагональных СЛАУ, предложенном в работе Austin et al., LA-VR-03-4149 (2004), изначально разработанном для систем с числом процессоров до 250. Алгоритм был реализован на CUDA с применением ряда оптимизаций, включая эвристики на основе машинного обучения для определения оптимального числа CUDA-потоков, размера подсистемы и числа рекурсивных шагов. Впоследствии алгоритм был расширен для работы с несколькими правыми частями, реализован в виде многографического (multi-GPU) решателя, а также обобщен на пента- и гептадиагональные СЛАУ; на всех этапах проводился анализ производительности.

Также были разработаны символьные алгоритмы для СЛАУ с ленточной матрицей, позволяющие устранить проблему корректности, характерную для классических алгоритмов типа метода Томаса, без наложения каких-либо ограничений на характеристики матрицы коэффициентов; условия корректности алгоритмов были сформулированы и доказаны в виде теорем.

Наконец, разработан и реализован на CUDA алгоритм решения начально-краевой задачи для уравнения теплопроводности, описывающего тепловые процессы в устройствах подачи рабочего газа для источника ионов. Алгоритм основан на методе переменных направлений (ADI), что приводит к трехдиагональным системам на каждом полушаге. Для численного моделирования были реализованы на CUDA четыре подхода к решению трехдиагональных систем: метод прогонки, метод встречной прогонки, метод разбиения и решатель cuSPARSE. Для всех алгоритмов проведен и представлен анализ производительности на платформе HybriLIT.