Параллельные алгоритмы для симплициального подразделения области с итерационным измельчением вблизи границы Кафедра параллельных алгоритмов Математико-Механический факультет Санкт-Петербургский Государственный Университет Дипломная работа студента 543 группы Хрусталева Дмитрия Максимовича Научный руководитель: д. ф.-м. н., проф. Юрий Казимирович Демьянович

Введение Основные концепции: Симплициальное подразделение области Применения: Решение задач аппроксимации Вейвлетная обработка сигналов Численное решение задач математической физики Аппроксимация функции на области Курантовская аппроксимация функции Уточнение аппроксимации функции на границе области Измельчение симплициального подразделения области при приближении к границе Рис.1:Триангуляция области. Рис. 2:Неравномерное разбиение.

Постановка задачи Создание параллельной версии алгоритмов измельчения симплициального подразделения при приближении к одному из оснований заданного прямоугольного параллелепипеда. Построение модели курантовской аппроксимации функции на полученном симплициальном подразделении. Разработка пакета программ, реализующих предложенные алгоритмы для реальных вычислительных систем.

Формализация условий Входные данные: параллелепипед П = { (x,y,z) | -S

Последовательная версия алгоритма - Алгоритмы невырожденного симплициального подразделения с измельчением вблизи границы, Е.П. Арсентьева, Ю.К. Демьянович. - Основная идея: разделить параллелепипед на горизонтальные полосы, и строить отдельное симплициальное подразделение для полос по очереди. - Полученный симплициальный комплекс бесконечен; критерий остановки алгоритма – достижение требуемой точности

Последовательная версия алгоритма: Симплициальное подразделение полосы Рис. 3:Алгоритм симплициального подразделения полосы.

Последовательная версия алгоритма: Симплициальное подразделение полосы Рис. 4:Симплициальное подразделение вертикальной треугольной призмы.

Распараллеливание алгоритма Количество треугольников растет экспоненциально Для вычислений, связанных с вершиной, требуются данные только о соседних вершинах Разбив слой на области, можно выполнять расчеты независимо Рис. 5:Схемы разбиений последовательных горизонтальных слоев. Рис. 6:Разбиение текущего слоя на области.

Реализация Позволяет задавать алгоритмы Выбора точки при разбиении ребра Оценки достигнутой точности аппроксимации Разбиения текущего слоя на области Не зависит от платформы Может использоваться как отдельное приложение и как библиотека

Полученные данные Число шагов1 поток2 потока3 потока4 потока Таблица: время работы программы в различных условиях. Рис. 7:Перспективные проекции полученной адаптивной сетки.

Результаты В данной работе создан параллельный алгоритм, выполняющий построение симплициального подразделения области с итерационным измельчением вблизи границы. Результатом работы полученного алгоритма является топологически правильное симплициальное подразделение заданного прямоугольного параллелепипеда, измельчающееся при приближении к его нижнему основанию. Разработан программный пакет, реализующий предложенный алгоритм Предложены направления для дальнейшего улучшения полученного алгоритма.