CUDA Assignment #4 Решение краевых задач, системы линейных алгебраических уравнений

Задание zОсновное: yРешение 1D/2D задачи диффузии zДополнительное: yРешение СЛАУ с треугольной разряженной матрицей

Задача диффузии zУравнение теплопроводности: z - коэффициент теплопроводности yПостоянный: yЛинейный: yНелинейный:

Постановка 1D задачи zОбласть определения – отрезок zУравнение теплопроводности на zНачальные условия: zГраничные условия:

Методы решения zМетод конечных разностей явные схемынеявные схемы На каждом шаге необходимо решать трехдиагональную СЛАУ

Постановка 2D задачи zОбласть определения: zУравнение теплопроводности: zНачальные и граничные условия (W,0) (0,H) (0,0) (W,H)

Метод по-координатного расщепления zВременной шаг разбивается на два дробных для каждого фикс. y для каждого фикс. x

Пример разностной аппроксимации zРасщепление по X: zНезависимые трехдиагональные СЛАУ для каждого j = 0.. N_y yЛегко параллелится

Трехдиагональные СЛАУ zПрямые методы: yМетод прогонки xОптимальный по числу операций, но последовательный yМетод редукции xПараллельный, но больше операций

Итерационные методы zЯкоби, Гаусса-Зейделя zGMRES, CG zПреобуславливатель (preconditioner)

Дополнительное задание zВерхне-треугольная разряженная матрица NxN zЧисло ненулевых элементов = NNZ X X X X X X X X X X X X X X X X X XX X X XX X

Формат хранения zCompressed Sparse Row (CSR) yData[NNZ] – массив ненулевых элементов yIndices[NNZ] – индексы столбцов для каждого ненулевого элемента yPtr[N+1] – смещение в массиве данных для каждой строки xPtr[i+1]-Ptr[i]: число ненулевых эл-тов в i-строке xPtr[N] = NNZ : общее число ненулевых элементов

Пример матрицы N=5 NNZ=7 Data Indices Ptr024567

Задание zПридумать эффективный алгоритм для реализации на CUDA/GPU zМатрица задается в формате MatrixMarket ( #MMformat) #MMformat

Полезные ссылки zУмножение разряженной матрицы на столбец: pub_001.html pub_001.html

Вопросы