Введение 4
1. Постановка задачи 5
2. Обзор литературы 6
3. Метод конечных элементов 7
4. Многосеточный метод 11
5. Метод декомпозиции области 12
6. Реализация метода декомпозиции области 15
Заключение 17
Список литературы 18
Для современных физических задач часто необходимо быстро решать уравнения в частных производных. При этом физические задачи могут характеризоваться абсолютно разными уравнениями на разных областях. Хотелось бы иметь метод, позволяющий на параллельной машине быстро решать подобные задачи, также учитывающий некоторые физические ее особенности, например, разнородность рассматриваемого материала.
В настоящее время наиболее популярными методами для численного решения уравнений в частных производных являются метод конечных разностей или метод конечных элементов. Таким образом, решение уравнения в частных производных сводится к решению большой алгебраической системы уравнений. Размер системы зависит от плотности сетки. Столь плотные сетки (порядка миллиона узлов и больше) оказываются необходимы для получения достаточно точных физических параметров рассматриваемого объекта, например, напряжения. Эти системы оказываются очень разреженными, и для их решения могут применяться различные методы, такие как метод LU-разложения, метод Якоби, метод Гаусса-Зейделя, варианты метода сопряженных градиентов. Также хочется иметь достаточно быстрый метод для решения больших СЛАУ, так как могут ставиться задачи мониторинга некоторой физической системы в живом времени. Однако указанные выше методы являются недостаточно хорошо гранулируемыми, поэтому отдельно хотелось бы выделить многосеточный метод, показывающий лучшую асимптотику на многопроцессорных системах.
Особенно хочется отметить метод декомпозиции области, использующийся для решения указанных систем линейных алгебраических уравнений и имеющий хорошие теоретические оценки времени исполнения. Он может включать в качестве своей части различные методы, указанные выше. В данной работе исследуются его оптимальные параметры при различных входных данных.
В рамках данной работы был рассмотрен метод конечных элементов. Для решения получившейся системы использовался метод декомпозиции области и многосеточный метод. Была реализована параллельная программа и запущена на вычислительном кластере.
Рассмотренный алгоритм позволяет быстро решать уравнение Пуассона. Также он показывает значительное ускорение при увеличении числа подобластей, что доказывает возможность его эффективной параллелизации и высокую гранулярность. Использование метода декомпозиции области может эффективно использоваться для быстрого численного решения эллиптических задач на параллельных компьютерах и кластерах.
