Математическое и алгоритмическое обеспечение программно-аппаратного комплекса "Топологический процессор"

• Автор: Семин, Владимир Валерьевич
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Москва
• Количество страниц: 140 с. : ил.

Содержание
Введение

Г лава 1. Исследование принципов и методов построения симплициальных моделей

1.1 Области применения симплициальных моделей данных

1.2 Анализ структурных решений симплициальных моделей данных

1.3 Анализ методов построения симплициальных моделей

1.4 Исследование методов унифицированного представления симплициальных и решёточных моделей
1.5 Анализ принципов построения математического и алгоритмического обеспечения программных комплексов, ориентированных на обработку геометрико-топологичеких данных большой размерности

1.6 Содержательная постановка задачи исследования

Глава 2. Разработка статистического метода анализа многомерных триангулированных решёток

2.1 Алгоритмизация процесса стохастической триангуляции

2.2 Вероятностное описание моделей преобразований в пространстве типов триангуляции /”
2.3 Оценка предельного распределения типов триангуляции /п в п-мерном пространстве
2.4 Разработка метода статистического анализа триангулированных решёток

Глава 3. Разработка алгоритмов построения и оптимизации симплициальных комплексов
3.1 Основные факторы влияния на процесс построениясимплициальных моделей
3.2 Разработка алгоритма построения симплициальной модели
3.3 Разработка критерия оптимизации симплициальных моделей
3.4 Общее решение задачи оптимизации построения симплициальных моделей по заданному критерию
3.5 Сравнительный анализ и обоснование процедуры выбора оптимального решения исследуемой задачи
Глава 4. Разработка программно-аппаратного комплекса «Топологический процессор»
4.1 Разработка концептуальной структуры комплекса «Топологический процессор»
4.2 Алгебраические основы представления многомерных симплициальных моделей
4.3 Реализация алгоритмов на основе алгебраических преобразований симплициальных моделей
4.4 Параллельная реализация разработанных алгоритмов
4.5.1 Специфика параллельной реализации алгоритмов для систем с общей памятью и кластерных систем
4.5.2 Специфика параллельной реализации алгоритмов на графических процессорах
Заключение
Список использованной литературы
Приложение 1. Описание схемы работы программных средств комплекса

Введение Актуальность работы
В настоящее время исследование и разработка методов формального синтеза, машинного представления и алгоритмической обработки геометрико-топологической информации в классе симплициальных моделей представляет значительный практический интерес. Часто поиск решения актуальных прикладных задач анализа; моделирования и оптимизации структурно сложных систем большой размерности приводит необходимости применения формального аппарата симплициальных комплексов. Так трехмерные симплициальные комплексы' нашли широкое применение в многочисленных методиках моделирования физических процессов, реалистичного моделирования деформации объектов в компьютерной графике, а также в решении большинства основных, разностных дифференциальных уравнении на основе методов конечных элементов или конечных объемов. Значительные результаты получены, в области создания инструментальных средств решения задач автоматизированного моделирования транспортных систем в различных физических средах. Анализ, областей- применения исследуемых методов представлениея. геометрико-топлогических данных указывает на- устойчивую тенденцию повышения необходимой размерности геометрико-топологического представления объектов. Например; размерности модели- глобальной
циркуляции океан-атмосфера (МЕГgem) - 109'11 узлов, перколяционных задач
Q |2 * О 1Q
10 " узлов, научно-технической визуализации - 10-10 узлов, модели-динамической гравитации (Space-Time models) - 1063.
Существует ряд близких по тематике работ, в которых получены существенные результаты, в. том числе работы T.F. Рябова, П. Коллета, Ml Десбруна, Д. Кохен-Штейнера, А. Эдкрофта, но вопросы, связанные с унифицированным представлением и аппаратной поддержкой обработки геометрико-топологических структур недостаточно исследованы.

дифференциальных уравнений, задач гидродинамики и аэродинамики. Кроме того триангуляция является одной из базовых структур вычислительной геометрии. Триангуляция играет большую роль в компьютерной графике и системе современных графических процессоров. Также триангуляция играет важную роль в различных геоинформационных системах, таких как М1Т§ст [1], при моделировании* поверхности и решении различных пространственных задач.
Среди- двух основных классов методов триангуляции - прямых и итерационных - последние обладают достаточной универсальностью и поэтому, в* отличие от прямых, могут быть, применены для триангуляции областей достаточно произвольного вида. Но благодаря такой универсальности приходится расплачиваться существенно большим потреблением ресурсов и более трудоемкой реализацией метода в конкретном алгоритме.
В настоящее время разработано большое количество программных пакетов на основе того или иного итерационного метода, реализующих построение сеток (частично или полностью) в.автоматическом режиме.
Сетки, построенные итерационными методами, как правило, неструктурированны и* неоднородны. Не структурированность обусловлена тем, что топология сетки формируется- в. процессе построения, и поэтому естественно может варьироваться даже в пределах одной подобласти. По этой же причине однородность,если и может возникнуть, то только случайно.
Поскольку перед построением сетки ничего нельзя сказать о ее будущей структуре, нельзя гарантировать и ее качества. Часто построенную сетку можно существенно улучшить с помощью одного из известных многочисленных методов оптимизации. Этой возможностью обычно-не пренебрегают, так как время, затрачиваемое на оптимизацию, как правило, существенно меньше времени, затрачиваемого на построение. Неплохой обзор алгоритмов триангуляции Делоне можно найти в работе [3]. Также внимания заслуживает работа [4], в которой рассмотрены итерационные методы трехмерной дискретизации пространственных областей, содержатся варианты алгоритмов.