Параллельные алгоритмы для симплициального подразделения области с итерационным измельчением вблизи границы Кафедра параллельных алгоритмов Математико-Механический. - презентация

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

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

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

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

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

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

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

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

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

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

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

12