автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Математическое и алгоритмическое обеспечение программно-аппаратного комплекса "Топологический процессор"

005002586

На правах рукописи

СЕМИН Владимир Валерьевич

МАТЕМАТИЧЕСКОЕ И АЛГОРИТМИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ПРОГРАММНО-АППАРАТНОГО КОМПЛЕКСА «ТОПОЛОГИЧЕСКИЙ ПРОЦЕССОР»

Специальность: 05.13.01 - системный анализ, управление и обработка информации

Автореферат диссертации на соискание ученой степени кандидата технических наук

1 7 НОЯ 2011

Москва 2011

005002586

Диссертационная работа выполнена на кафедре «Информационно -коммуникационные технологии» в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Московский государственный институт электроники и математики (технический университет)». Научный руководитель - доктор технических наук, профессор Азаров Владимир Николаевич

Официальные оппоненты:

- доктор физико-математических наук, профессор Лазарев Александр Алексеевич

- кандидат физико-математических наук, профессор Хакимуллин Евгений Робертович

Ведущая организация: Учреждение Российской Академии наук Институт машиноведения им. A.A. Благонравова РАН

Защита диссертации состоится «29» ноября 2011 г. в /4 часов на заседании диссертационного совета Д 212.133.01 в Московском Государственном Институте Электроники и Математики по адресу: 109028, Москва, Б. Трехсвятительский пер., д. 3.

С диссертацией и авторефератом можно ознакомиться в библиотеке Московского Института Электроники и Математики

Автореферат диссертации разослан « 2? » ОКТЯБРЯ 2011 г.

Ученый секретарь диссертационного совета к.т.н., доцент

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность работы

В настоящее время исследование и разработка методов формального синтеза, машинного представления и алгоритмической обработки геометрико-топологической информации в классе симплициальных моделей представляет значительный практический интерес. Часто поиск решения актуальных прикладных задач анализа, моделирования и оптимизации структурно сложных систем большой размерности приводит необходимости применения формального аппарата симплициальных комплексов. Так трехмерные симплици-альные комплексы нашли широкое применение в многочисленных методиках моделирования физических процессов, в моделировании процессов химического и биологического синтеза на молекулярном уровне, в решении задач гидро-и газо-динамики, в автоматизированном проектировании транспортных средств, в реалистичном моделировании деформации объектов в компьютерной графике, а также в решении большинства основных разностных дифференциальных уравнений на основе методов конечных элементов или конечных объемов. Значительные результаты получены в области создания инструментальных средств решения задач автоматизированного моделирования транспортных систем в различных физических средах. Анализ областей применения исследуемых методов представления геометрико-топлогических данных указывает на устойчивую тенденцию повышения необходимой размерности геомет-рико-топологического представления объектов. Например, размерности модели глобальной циркуляции океан-атмосфера (MITgcm) - Ю9"11 узлов, перколяцион-ных задач - 109"12 узлов, научно-технической визуализации - Ю8-1010 узлов, модели динамической гравитации (Space-Time models) - 1063.

В исследуемой области геометрико-топологического моделирования наиболее существенные научные результаты получены в работах Рябова Г .Г., П. Коллета, М. Десбруна, Д. Кохен-Штейнера, А. Эдкрофта. Однако вопросы, связанные с унифицированным представлением и аппаратной поддержкой обработки требуют дальнейшего исследования.

3

Таким образом, задача построения единого унифицированного подхода к созданию математического и алгоритмического обеспечений для анализа и обработки симплициальных структур данных, является необходимым условием реализации эффективных программно- аппаратных методов поддержки процесса решения широкого круга прикладных и научных задач.

Отличительной особенностью постановки задачи данной диссертационной работы является исследование и разработка общего формального подхода к созданию математического и алгоритмического обеспечений программно-аппаратной системы обработки геометрико-топологической информации, инвариантной по отношению к физической природе многомерных геометрико-топологических входных данных. Необходимо отметить, что эффективное решение поставленной задачи обуславливает необходимость применения средств вычислительной техники, обеспечивающих возможности параллельной обработки больших объемов данных, реального масштаба времени обработки. Таким образом, тема диссертационной работы, посвященной решению задачи построения единой формальной системы обработки геометрико-топологической информации в классе симплициальных моделей, и базовых операций с последующей аппаратной поддержкой, является актуальной.

Предлагаемые в диссертационной работе подходы реализованы на примере программно-аппаратного комплекса «Топологический процессор».

Цели работы и задачи исследования

Целью исследования является разработка математического и алгоритмического обеспечения программно-аппаратных комплексов обработки многомерных геометрико-топологических данных большой размерности в широком спектре практических задач.

Для достижения данной цели потребовалось решение следующих основных задач:

• анализа и разработки классификации по типам и видам многомерных триангулированных данных (решётки, многообразия, комплек-

сы и т.д.) с целью выявления общих характеристик для формирования унифицированного метода представления данных;

• разработки статистической модели анализа геометрико-топологических моделей на основе унифицированного представления данных;

• разработки и обоснования критериев качества геометрико-топологических моделей, синтезируемых на основе предложенного типа данных;

• разработки математического обеспечения для универсального представления данных и анализа исследуемого класса моделей;

• разработки набора базовых операций обработки данных;

• разработки базового алгоритмического обеспечения процесса обработки геометрико-топологических данных.

Объект исследования

Объектом исследования являются математические модели и программные комплексы, направленные на обработку больших объёмов многомерных триангулированных и решётчатых типов данных представления геометрико-топологической информации.

Предмет исследования

Предметом исследования является математическое и алгоритмическое обеспечение программно-аппаратных комплексов, а также перспективные методы аппаратной поддержки вычислений в подобных комплексах.

Методологическая и теоретическая основа исследования

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

Научная новизна работы заключается в следующем:

• разработан подход к унифицированному способу представления многомерных геометрико-тологических данных, сформулированы критерии применимости данного подхода;

• разработан статистический метод анализа на основе статистических распределений интегральных характеристик многомерных триангулированных решёток;

• предложены критерии оценки качества многомерных триангулированных решёток;

• разработан метод оптимизации качества триангулированной решётки;

• разработаны методы формального представления решёточных структур на основе целочисленного кодирования. Приведены табличные определения различных элементарных операций над кодами, позволяющими проводить анализ и преобразования решётки;

• предложены методы машинного представления решёточных структур;

• разработаны алгоритмы и методы, реализующие предложенные подходы в инструментальной среде программной системы «Топологический процессор».

Практическая ценность и реализация

Результаты, полученные в данной работе, могут быть использованы при построении программно-аппаратных комплексов, ориентированных на решение задач обработки больших объёмов многомерных решётчатых и триангулированных данных (гидрометеорологические исследования, задачи гидродинамики, газодинамики, моделирование поведения высокоэнергетических пучков сверхмалых частиц и т.д.).

Апробация результатов исследования

Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах:

• Научная конференция «Ломоносовские чтения», Москва, Россия, апрель 2008;

• Научно-практическая конференция «Инновации в условиях развития информационно-коммуникационных технологий» ИНФО-2009, Сочи, Россия, октябрь 2009;

• Ежегодная научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ, Москва, Россия, февраль 2010;

• Научно-практическая конференция «Инновации в условиях развития информационно-коммуникационных технологий» ИНФО-2010, Сочи, Россия, октябрь 2010;

• Ежегодная научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ, Москва, Россия, февраль 2011;

Также результаты проделанной работы (работа Программно-аппаратный комплекс «Топологический процессор» Семин В.В. МГУ, МИЭМ) были представлены на ежегодном международном конкурсе научных проектов «Максимальная масштабируемость» 2009г. проводимым корпорацией РОСНАНО и компанией Intel, где получили высокую оценку экспертов (13 место из 41 участника).

Публикации

По теме диссертации опубликовано 7 печатных работ из них 3 из перечня ВАК.

Основные положения, выносимые на защиту

Система формального представления, анализа и оптимизации многомерных решётчатых и триангулированных структур композитного типа.

Структура и объём работы

Диссертационная работа содержит введение, четыре главы, заключение, приложение, библиографию работ по теме диссертации. Диссертация содержит 38 рисунков и 10 таблиц. Общий объём диссертации 138 страниц.

Основное содержание работы

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

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

Приведены сведения о базовых понятиях, положенных в основу решения задач, теоретических исследований.

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

Рассматривается задача представления различных геометрико-топологических моделей в виде триангулированных кубических комплексов. На примере модельных пространств небольшой размерности п < 3, проводится анализ широко распространённых и характерных типовых методов организации структур данных для решения поставленной задачи.

Результаты проведённого анализа позволили обосновать выбор общего универсального метода представления геометрико-тополических моделей. В основе данного метода лежит правильная, в смысле расположения симплексов, триангуляция /3.

Приводится формальное описание и перечисление типов триангуляций /3 при помощи решений системы уравнений с целочисленными коэффициентами:

Очевидно, что рассматриваемой системе (1) с учётом требования разбиения куба на правильно расположенные симплексы, удовлетворяют следующие наборы решений:

1) х = (0, 6, 0, 2) - 1 тип,

2) х = (1,3,3, 1) - 2 тип,

3) х = (2, 0, 6, 0) - 3 тип,

4) х = (2, 2, 2, 2) - 4 тип,

5) х = (4, 0, 0, 4) - 5 тип.

Таким образом, соответствие конфигурации куба одному из выше перечисленных 5 типов является достаточным условием выполнения требования правильной триангуляции.

Ниже на рис. 1 приведено графическое изображение всех пяти типов

1 2 3 4 5 5*

3 13 12 22 13 03 О

Рис. 1. Типы правильной триангуляции /3

Таким образом, типы неконгруэнтны и других правильных триангуляции /3 не существует. Полная триангуляция /3 для типов 1 - 4 завершается построением большой диагонали внутри куба. При этом положение её однозначно для 1, 2 и 4-го типов. Третий тип допускает три различных положения большой диагонали, в то время как триангуляция граней остаётся неизменной. При триангуляции 5-го типа возможно два исхода: наличие большой диагонали внутри куба (рис. 1 (5*)), или её отсутствие (рис. 1 (5)), причём независимо от исхода, триангуляция граней остаётся неизменной.

Выбор способа представления геометрико-топлогических данных аппарата симплициальных комплексов на квазистационарных решётках, обусловлен возможностью эффективного представления, анализа, синтеза сложных топологических и геометрических структур. В работе рассматриваются квазистационарные решётки, состоящие из узлов, расположенных в целых точках Zn и

9

комплексы, составленные из симплексов на целых точках (вершинах) и простых, без внутренних целых точек, рёбрах. Понятие квазистационарности в контексте данной работы означает, что исходная решётка на целых узлах, может испытывать различные преобразования с сохранением заданных инвариантов структуры, меняя при этом расположение узлов и выходя из области целочисленной арифметики.

Для обоснования требований к разрабатываемому алгоритмическому обеспечению и структуре программно-аппаратного комплекса проводится анализ известных результатов и подходов. Выявлены общие черты и структура, характерные для современных программных комплексов, ориентированных на обработку геометрико-топологических данных.

Отмечается, что исследование структуры и принципов построения математического обеспечения популярных коммерческих продуктов затруднено, ввиду их закрытости. Однако многие используемые ими алгоритмы и методы хорошо формализованы и описаны в научной литературе.

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

Алгоритм»« «кое об «ПС»« ми»

Алгоритм* конструирования многообразий

Анюршми:

1 построение.

2. Ьориальное представление:

3. ншпз

Алгэритмы дискретизгции/о типизации

Алгоритмы:

1. дискретизация;

2. оптимизация

вычислительна«

алгоритмы

Решение задач;

1. вычислительных,

2. мздехироеания,

3 статнгтикн

Алгоритмы геометрических преобразование

1. аффинные,

2. аелннейяые

Алгоритмы конвертации данных

Алгоритмы »изуализации

X

Алгоритм« 1 йлгоригмы:

1. преобразования; 1 отображение

2. храяенвя 2. графика

Рис. 2. Структурная схема алгоритмического обеспечения

ю

Отмечается, что диссертационная работа является самостоятельной частью работ, по созданию перспективного программно-аппаратного комплекса «Топологический процессор», проводимых в НИВЦ МГУ проф. Рябовым Г.Г. На основании анализа исследуемой проблемы сформулированы основные требования к математическому и алгоритмическому обеспечению, а также приведена содержательная постановка задачи.

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

Ключевым моментом изучения триангуляции на квазистационарной решётке является исследование статистических данных, описывающих появление того или иного вида триангуляции куба /п как элемента п-мерной решётки. Показано, что для каждого типа триангуляции /3, являющегося основой для построения триангуляций /", могут быть заранее вычислены различные метрики.

Для установления соответствия между особенностями комбинаторного представления и вероятностного описания процесса триангуляции на квазистационарной решётке вводится понятие стохастической триангуляции с ограничениями, и исследуются её свойства. Для формального доказательства исследуемого соответствия проводится алгоритмизация процессов стохастической триангуляции.

Обозначим некоторую конечную область П 6 с границей дП. Определим также бесконечно большую область Л00 6 Я71, такую что, IIе0 стремится к ДП:ПСС -» Ип. Тогда моделью решётки, покрывающей может служить пара (гпУг).

Алгоритм триангуляции, применяемый в процессе триангуляции, будем обозначать через Ас, систему ограничений, накладываемых на процесс триангуляции через д = {дъ..., д{), I £ N.

Процессом триангуляции Р конечной области П 6 Я", будем называть

процесс Р(П, состоящий в применении алгоритма триангуляции Ас к ис-

11

ходному многообразию П, приводящий с учётом системы ограничений Q к построению триангулированного многообразияС1Т:

р = p<Si,At,s): ¿t(n) х g пт

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

Стохастическую триангуляцию определим на множестве (Zn,V1), как триангуляцию двумерных граней «-мерной решётки, получаемую проведением диагонали в соответствующей грани. Таким образом, построенная вероятностная модель появления определённого триангуляции Iй как элемента решётки (Zn,\1) описывает процесс стохастической триангуляции данного множества.

Для различных размерностей пполучены матрицы вероятностей появления того или иного типа триангуляции /п при изменении положения диагонали на &-ом количестве 2-граней /п, где k = 1.. п.

В работе предложен метод классификации триангулированных конфигураций /п на основе вектора количества типов 13х входящих в развёртку /". Формально х ~ (хо> - .х4), где x¡ - количество трёхмерных кубов i + 1 типа, где i = 0. .4, входящих в развёртку п -мерного куба /п. При этом выполняется

V*:IÍ=o*¡ = Ф(п_3)-

Рассмотрим множество элементарных событий fl, с элементами - кодами развёртки /п. Мощность П составляет 2П. Определим сигма-алгебру А случайных событий, как множество событий появления /п определённого типа, тогда А — {i41(..,/lK}. Вероятностную схему определим стандартным образом Р(П) = 1.

Часть элементарных событий Ль будут соответствовать случаям неправильной (неполной) триангуляции /п, которые не имеют геометрической реализации в виде некоторого симплициального комплекса. Для данного типа событий ведём событие АВТ - обобщённое событие появления неполной триангуляции /4. Тогда вновь определённая сигма-алгебра событий А* будет иметь следующий вид А' = {Ах.....А0АВТ], где Аг событие появления правильной три-

ангуляции /", I = 6 М, где I - количество событий появления правиль-

ной триангуляции /п.

Отмечается, что процесс изменения положения диагонали на к 2-гранях индуцирует семейство марковских процессов, которые описываются соответствующими матрицами вероятностей.

Далее в процессе разработки методов статистического анализа создана общая схема кодирования многомерных триангулированных кубических комплексов базирующаяся на понятии развёртки 1п приведенная на рис. 3.

Рис. 3. Развёртка /4

Развёртка /П,п >4 определяется как кубический комплекс в Я3 грани

которого однозначно соответствуют 3-граням Г, а 2-грани Iй по которым производится развёртка, соответствуют паре 2-граней развертки, по которым прилегают соответствующие 3-грани в /", остальные 2 - грани Г однозначно соответствуют граням развёртки.

Развёртка 1п,п = Зопределяется как плоская связная фигура в Я2, состоящая из квадратов, однозначно соответствующих 2-граням /3, полученная путём «разреза» /3 по рёбрам приведена рис. 4.

Рис. 4. Развёртка /3

Схема кодирования основана на однозначном сопоставлении каждой

триангулированной конфигурации /п двоичного кода, описывающего триангуляцию. Кодирование происходит по следующему правилу:

• 2-грани 1п нумеруются в некотором порядке;

• с помощью развёртки /п фиксируется ориентация грани;

• каждой 2-грани 1п ставиться в соответствие О, если грань имеет левую ориентацию и 1 если правую, в соответствии с зафиксированным порядком развёртки.

Рис. 5 иллюстрирует описанное выше правило.

0 X 1 1 1

ч / /

ч * у 5 _ 1

У

011101

Рис. 5. Развёртка куба с двоичным кодом (011101)

Применяя такой способ кодирования, легко определить количество всех возможных триангулированных конфигураций /п - 2".

Оценим общее количество всевозможных различных векторов х- Для оценки распределения п частиц по т ячейкам используется статистическая модель Бозе-Энштейна, при этом число К способов размещения п частиц по т ячейкам равно

„ _ (п+т-1)!

В рассматриваемом случае в качестве частиц выбираются типы триангу-ляций /3, входящих в развёртку I", а в качестве ячеек элементы вектора Х-

Таким образом, с учётом (2), для описания предельного распределения типов триангуляции Iй с помощью вектора х получено следующее равенство:

_ (<&<-"+4)!

Построенная статистическая модель позволяет изучать поведение триангуляции в и-мерном пространстве, для п > 4. При этом предельное распределение может быть ценено при помощи статистической модели Бозе-Эйштейна.

Предложенный метод статистического представления типа триангуляции /" на основе вектора типов х позволяет строить распределения, характеризующее количество и тип триангулированных конфигураций /3 как элементов решётки (1пУ1). Зная заранее метрические и специфические параметры I3, можно анализировать характер многомерной решётки на предмет значений вычисляемых параметров, что особенно важно, когда непосредственный визуальный анализ затруднён ввиду большой размерности и сложности решётки.

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

Пусть стохастическое распределение вектора количества типов для /", а Рп распределение вектора количества типов изучаемой модели. Мера близостиц распределений и Рл является интегральной нормой нормированных распределений Р3" и Р п:

= (4)

где П|д - распределение векторов количества типов, соответствующих триангуляции Iй с системой условий а со - событие соответствующее определённому виду Х-Р£ и Р " нормированы на отрезке [0,1].

Пользуясь тем, что распределения Р?с и Рп дискретны, (4) может быть записано в следующем виде:

71

В соответствии со значением ц симплициальная модель может быть охарактеризована следующим образом (см. таблицу 1)

Таблица 1.

__Мера близости распределений_

Значение ц Тип модели

(О, К/5) Неструктурированная модель, при ц = Орешётка представляет собой стохастическитриангулированное многообразие. К ЗК1 Структурированная модель, содержащая различные типа ® ^ триангуляции /". Исходя из комбинаторных свойств триангуляции 1п можно утверждать, что решетка содержит небольшие, относительно линейных размеров модели, области с однородной триангуляцией, образующей устойчивые транслируемые симплициальные комплексы. /ЗК ^ Сильно структурированная модель - исходя из комбинатор' ^ ных свойств 1п модель триангулированного многообразия разделена на однородные области, образующей устойчивые транслируемые симплициальные комплексы с чёткими границами между оюластями. Для сильно структурированных решёток возможно эффективное представление однородных областей с точки зрения объёма хранимой информации, а также эффективная обработка.

Мера (1 позволяет получить точную оценку, характеризующую структуру модели и отдельных её элементов. Однако на практике могут применяться и более грубые оценки, основанные на следующем правиле.

Правило 1. Пусть И = {тах- набор векторов количества типов с мак-симальньш весом в распределении Рп, тогда отношение суммы \хь\ £ Мк сумме весов остальных векторов XI принадлежащих Рп есть грубая оценка а меры у.

Оценка а определяется в соответствии со следующей таблицей:

Таблица 2.

Оценка а_

Значение у Значение а

(0, К/5) а « 1

К ЗК .5'Т. а = 1

/ЗК , а » 1

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

Установлено, что анализ триангуляции симплициальных многомерных моделей характеризуется большой вычислительной сложностью, обусловленной ростом числа возможных триангуляций Iй, с ростом размерности пространства (см. рис. 6).

Динамика роста количества триангуляции

♦ Динамика роста количества триангуляции

Рис. 6. Рост числа триангуляции /"

Втретьей главе рассмотрены основные этапы разработки алгоритмов построения и оптимизации симплициальных комплексов на квазистационарных решётках.

Рассматриваются основные факторы, влияющие на процесс построения и качество получаемой симплициальной модели.

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

1. Формирование исходного многообразия П.

2. Формирование первичного аппроксимирующего кубического комплекса.

3. Вычисление расстояний от центров кубов до границы дП.

4. Трассировка лучей и уточнение первичной аппроксимации, формирование псевдо-области йрз.

5. Формирование симплициального разбиения кубов.

6. Удаление симплексов не входящих в псевдо-область Пр5. Новизна данного подхода заключается в использовании вероятностного критерия для определения принадлежности вокселу кубического комплекса исходной области П.

Пусть Мт(„| минимальное, расстояние от центра кубического вокселас V до поверхности границы псевдо-области Пр5, а |Отах| — максимальное расстояние среди всех значений расстояний для всех вокселов, тогда вероятность события вхождения воксела в Пр5 определяется следующим образом

Р{Щп) = 1 -

\0тах\'

где Ш1П - событие вхождения воксела в псевдо-область йрз.

Вероятность Р(а>;п) используется в процессе принятия решения о вхождении или исключении воксела из псевдо области по заданному пороговому значению 1С. Так если Р(о);„) > Сс, то данный воксел помечается как кандидат на вхождение в псевдо-область, в последующем для данного воксела учитываются события, для которых Р(й>1П) < Ьс.

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

Для решения задачи разработки базового алгоритмического обеспечения разработан метод оптимизации, основанный на минимизации интегральной квадратичной нормы на симплексах, а также в качестве критерия оценки каче-

ства рассматривается значение телесного угла в вершинах симплексов разбиения.

Пусть Л некоторая конечная подобласть Я3 произвольной топологии или некоторое число её связных компонентов. При этом Л уже разбита на некоторое количество конечных элементов. Будем обозначать набор ограничений (границу) для Л как дС1. Поверхность, описываемая дП, должна представлять непрерывное триангулируемое многообразие без самопересечений и наложений. Будем рассматривать только регулярные симплициальные разбиения.

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

В качестве целевой функции для задачи минимизации рассматривается функционал вида II/ —/г11*.р(П)> рде/некая функция и /г линейная интерполяция на основе триангуляции Т области Л. Формально задача описывается следующим образом:

• Пусть 5 - некоторое конечное множество точек из /?п.

• Л - выпуклая оболочка 5 и Т5 - множество всех возможных триангуляции Л, содержащих точки из Б.

• <2(^-/'Р) = ||/ — АИ1£Р(п)' лине^ная интерполяция/ основанная на триангуляции Т исходной области Л с Яп.

При этом (}(Т, /, р) также представима в виде:

(КТ^.т) = /р-

Алгоритм оптимизации состоит из следующего набора шагов:

• Выделение очередной звёздной окрестности вершины X; - 51аг(*;) для текущей вершины из дП (Х( е ЗЛ).

• Построение локальной аппроксимирующей поверхности по инцидентным вершинам из ЗЛ.

• Применение малых локальных деформаций к подобласти (Zn, Vj) соответствующей star(Xi) с целью минимизации функционала f, при соблюдении некоторого набора условий а. Формально процедура оптимизации описывается при помощи оператора отображения с целевой функцией f и условием а над областью Л:

б:П~->Л*|а-

Q(T.f,p)

Где Q(T,f,p) - функционал описанного выше вида и <я={^¿(Л*)}, /= 1..к-набор условий ограничивающих применение целевой функции.

Обычно условия д№") определяются как неравенства для некоторых метрических отношений, например, широко используются отношения максимального модуля ребра данного симплекса к радиусу вписанной в симплекс сферы:

Q = Ьа* _ А < q< с, где А,С-const. (5)

В работе рассматриваются различные виды условий и приводится их сравнительный анализ, на основе которого, в качестве такого ограничения, предлагается использовать значение тесного угла в вершинах симплекса (6) и связь этого значения с (5):

<Pi = 2 arctg-, ' . , , . (6)

где Г( = (Xi - Xj): i,jE {0,1,2,3}, ^телесный угол при вершине х, в некотором симплексе.

Далее рассматриваются два основных подхода к определению функционала Q(T,f,p):

• центроидальные разбиения Вороного,

• оптимальная триангуляция Делоне.

Для данных подходов проводиться сравнительный анализ и обосновывается выбор подхода на основе оптимальной триангуляции Делоне.

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

(¡(Т. ||х2||, 1) = 4аг(хг)И* " *Х> ™

где X; е 5, ¡=1..Ы, яСаг^) - звёздчатая окрестность, содержащая вершину XI.

Приведём (7) к виду:

<2(7\ ||*2||, 1) = —ЕГ.!*?!^*!)! - $пхЧх- ^

Представление (8) может быть получено из (7) с учётом того, что/выпуклая и Дт > /, (/■=||х||2).

Для нахождения минимума (8) для некоторой вершины 6 Тот, где Твт -триангуляция Делоне области Л, необходимо решить следующее уравнение:

ад7\||х2||,1) = 0. (9)

Для решения представим (8) в виде: N

<?(Т, \\х2II. 1) = *?|5ЮГ(*()| - ] хЧх

¡=1 п

= I (м I

с;еисаг(х;)| \ х*еt],xk*xi /

Тогда

и искомое решение (9) представимо в виде:

X: =

г^агСх^Г

Формула (10), описывает оптимальное положение вершины положение вершины в звёздчатой окрестности |5Саг(д:г)|.

В обобщенном виде решение (10) можно записать следующим образом:

В качестве обычно выбирают некоторую функцию по смыслу являющейся функцией плотности симплексов ^ с центром масс тп, и центром описанной сферы Су, где ц некая идеальная длина ребра для симплекса. Очевидно, что плотность покрытия симплексами области Л обратно пропорционально объёму симплексов и примерно равна Проблема поиска такой преопреде-

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

Однако напрямую реализации данного метода хоть и позволяют получить решётку высокого качества, но достаточно требовательны к вычислительным ресурсам. В работе проводится сравнительный анализ подобных методов, и обосновываются выбор вида функции. Пользуясь тем фактом, что на начальном этапе решётка однородна и структурирована, в работе предложен следующей вид р(т;):

\/у.тг центр масс тетраэдра где соп/(Я) множество уникальных тетраэдров в регулярной триангуляции П\дП. Таким образом, функция р(щ) зависит только от набора уникальных, отличимых друг от друга по объёму тетраэдров и может быть вычислена только один раз. Такой подход помогает сократить накладные вычислительные расходы по сравнению с существующими методами.

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

В четвёртой главе приведена концептуальная структура программно-аппаратного комплекса реализующего разработанное математическое и алгоритмическое обеспечение (см. рис. 7). Представлены алгебраические основы представления симплициальных моделей. Предложены методы машинного представления симплициальных структур данных.

Алгоритмы обработки (волна, трассировка и т.д.) - £ "

Статастнтаеаган анализ

Алгоритмы построения и оптимизации

Базовые операция

3 £ 8 I

я а

3 = £ §

1 8 •8 * 15

I 5 » §

В Ш

о- о

Й 5

й Е

Вспомогательные модули (управление комплексом и т.д.)

Рис. 7. Концептуальная структура разрабатываемого комплекса

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

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

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

и ЦП представлены в таблице 4. Конфигурации ЭВМ, использовавшихся для проведения испытаний следующая:

1. ЭВМ 1-16 процессора Intel Xeon 5660, 32Гб оперативной памяти стандарта DDR3.

2. ЭВМ 2-2 процессора Intel Xeon 5660, 6Гб оперативной памяти стандарта DDR3, 4 вычислительных блока Nvidia Tesia С1060 с 1Гб памяти у каждого блока.

На ЭВМ 1 производились тесты реализации алгоритмов для ЦП, на ЭВМ 2 производились тесты реализации алгоритмов с поддержкой вычислений на ГП. Результаты сравнения производительности алгоритмов представлены в таблице 3.

Таблица 3.

Алгоритм Ускорение при помощи ГП.

Алгоритм статистического анализа. От 10 до 100 раз

Алгоритм построения До 5 раз

Алгоритм оптимизации До 30 раз

Алгоритм декомпозиции До 10 раз

Объёмы типовых данных, на которых производились тесты: 100 тысяч симплексов, 200 тысяч симплексов, 10 миллионов симплексов, 100 миллионов симплексов.

Таким образом, установлено что применение алгоритмов, реализованных на ГП целесообразно при больших размерах входных данных (более 100 тысяч симплексов); так как для небольших размеров входных данных (до 100 тысяч симплексов) алгоритмы, реализованные с поддержкой вычислений на ГП показывали худшие результаты по сравнению с алгоритмами, реализованными на ЦП. Данная особенность связана с тем, что при небольших объёмах данных латентность памяти ГП не может быть покрыта объёмом производимых вычис-

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

В заключении сформулированы основные результаты.

Разработана формальная система синтеза и анализа геометрико-топологических моделей, включающая в себя:

• Формальный метод унифицированного представления многомерных геометрико-топологических моделей.

• Метод статистического анализа процесса триангуляции на многомерных решётчатых структурах, метод статистического анализа симплициальных моделей.

• Предложены методы классификации структурной организации симплициальных моделей.

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

• Методы алгебраического и машинного представления многомерных решётчатых и триангулированных структур.

• Методы построения программных средств для решения задач, связанных с обработкой многомерных решётчатых и триангулированных данных.

• Разработана концептуальная структура программно-аппаратного комплекса.

Список публикаций по теме диссертации

1. Семин В.В. Представление нано-структур с помощью симплициальных комплексов. // Инновации в условиях развития информационно-коммуникационных технологий: Материалы научно-практической конференции / Под ред. В.Г. Домрачева, С.У. Увайсова, за вып. И.А. Иванов, Я.Л. Масленникова, Р.И. Увайсов, О.П. Хацкевич. М.:МИЭМ, 2009, С. 140-142.

2. Семин В.В. Симплициальные комплексы на квазистационарных решётках. // Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ: Тез. докл. конф. - М.:МИЭМ, 2010. С. 84-85.

3. Семин В.В. Алгоритмы построения и оптимизации симплициальных комплексов. // Инновации в условиях развития информационно-коммуникационных технологий: Материалы международной научно-практической конференции / Под ред. В.Г. Домрачева, С.У. Увайсова, за вып. И.А.Иванов, Я.Л. Масленникова, Р.И. Увайсов, О.П. Хацкевич. М.:МИЭМ, 2010, С. 266-268.

4. Семин В.В. Алгоритмическое и математическое обеспечение программно-аппаратного комплекса «Топологический процессор». // Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ: Тез. докл. конф. - М.:МИЭМ, 2011. С.82-83.

5. Семин В.В. Исследование поведения триангуляции на симплициальных комплексах. // Дискретная математика. Том 23. Выпуск 1. 2011. С. 119131.

6. Семин В.В. Алгоритмы построения и анализа симплициальных комплексов на квазистационарных решётках. // Информационные технологии. №5. 2011.С. 52-57.

7. Семин В.В. Моделирование поведения стохастической триангуляции на квазистационарных решетках. // Информационные технологии. №6. 2011.С. 45-50.

Подписано к печати " 25 " октября 2011г. Отпечатано в отделе оперативной полиграфии МИЭМ.

Москва, ул. М. Пионерская, д. 12. Заказ № 205 Объем 1.0 п.л. Тираж 100 экз.

Введение.

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

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

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

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

1.4 Исследование методов унифицированного представления симплициальных и решёточных моделей.

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

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

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

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

2.2 Вероятностное описание моделей преобразований в пространстве типов триангуляции Iй.

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 анализа; моделирования и оптимизации структурно сложных систем большой размерности ■ приводит необходимости применения1 формального аппарата симплициальных комплексов. Так трехмерные симплициальные комплексы' нашли, широкое применение в. многочисленных методиках моделирования физических процессов, реалистичного моделирования деформации объектов в компьютерной графике, а также в решении большинства основных, разностных дифференциальных уравнений- на основе методов* конечных- элементов или, конечных объемов. Значительные результаты получены, в области создания' инструментальных средств решения задач автоматизированного моделирования транспортных систем в различных физических средах. Анализ, областей' применения исследуемых методов представлениея, геометрико-топлогических данных указывает на- устойчивую тенденцию повышения необходимой'размерности геометрико-топологического представления объектов. Например; размерности модели- глобальной циркуляции океан-атмосфера (MITgcm) - 109"11 узлов, перколяционных задач

О 12 1 Q | Q

10 " узлов, научно-технической визуализации - 10-10 узлов, модели динамической гравитации (Space-Time models) — 1063.

Существует ряд близких по тематике работ, в которых получены существенные результаты, в, том числе работы Г.Г. Рябова, П. Коллета, М. Десбруна, Д. Кохен-Штейнера, А. Эдкрофта, но вопросы, связанные с унифицированным представлением и аппаратной поддержкой обработки геометрико-топологических структур недостаточно исследованы.

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

Отличительной особенностью постановки задачи данной диссертационной работы является исследование и разработка общего-формального подхода к созданию математического и алгоритмического * обеспечений программно-аппаратной системы обработки геометрико-топологической информации, инвариантной по отношению' к физической природе многомерных геометрико-топологических входных данных. Необходимо отметить, что эффективное решение поставленной задачи обуславливает необходимость применения^ средств вычислительной техники, обеспечивающих возможности параллельной обработки, больших объемов данных, реального масштаба времени обработки. Таким образом, тема диссертационной работы, посвященной решению задачи построения единой формальной« системы обработки- геометрико-топологической информации в классе симплициальных моделей, и базовых операций с последующей аппаратной поддержкой; является актуальной.

Предлагаемые в* диссертационной работе подходы, реализованы на примере программно-аппаратного комплекса «Топологический процессор».

Цели и задачи исследования Целью исследования является разработка математического и алгоритмического обеспечения программно-аппаратных комплексов обработки, многомерных геометрико-топологических данных большой размерности« в широком спектре практических задач.

Для достижения данной цели потребовалось решение следующих основных задач:

• анализа и разработки классификации по типам и видам многомерных триангулированных данных (решётки, многообразия, комплексы и т.д.) с целью выявления общих характеристик для формирования унифицированного метода представления данных;

• разработки статистической модели анализа геометрико-топологических моделей на основе унифицированного' представления данных;

• разработки и обоснования критериев качества геометрико-топологических моделей, синтезируемых на основе предложенного типа данных;

• разработки математического обеспечения для универсального представления данных и анализа исследуемого класса моделей;

• разработки набора базовых операций обработки, данных;

• разработки базового алгоритмического обеспечения^ процесса обработки геометрико-топологических данных.

Объект исследования Объектом исследования4 являются математические модели и программно аппаратные комплексы, направленные на обработку больших объёмов многомерных триангулированных и решётчатых типов данных и решение широкого круга численных, топологических и геометрических задач.

Предмет исследования Предметом исследования является математическое и алгоритмическое обеспечение программно-аппаратных комплексов, а также перспективные методы аппаратной-поддержки вычислений в подобных комплексах.

Методологическая и теоретическая основа' исследования При решении данных задач использовались методы математической статистики, алгебраический аппарат, элементы теории вычислений, элементы топологического аппарата, методы представления и оптимизации триангулированных решеток, математический аппарат оптимизации и в частности принцип максимума, элементы теории сложности вычислений.

Научная новизна исследования

• Разработан подход к унифицированному способу представления многомерных геометрико-тологических данных, сформулированы критерии применимости данного подхода;

• Разработан статистический метод анализа на основе статистических распределений интегральных характеристик многомерных триангулированных решёток;

• Предложены критерии оценки качества , многомерных триангулированных решёток;

• Разработан' метод оптимизации качества триангулированной решётки;

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

• Предложены методы машинного представления решёточных структур;

• Разработаны алгоритмы и методы^-реализующие предложенные подходы в инструментальной среде программной системы «Топологический процессор».

Практическая значимость работы Результаты, полученные в данной работе, могут быть использованы при построении программно-аппаратных комплексов, ориентированных на решение задач связанных с обработкой больших объёмов многомерных решётчатых и триангулированных данных (Климатические исследования, задачи гидродинамики, газодинамики, моделирование поведения высокоэнергетических пучков сверхмалых частиц и т.д.).

Апробация результатов исследования

Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах:

• Научная конференция «Ломоносовские чтения», Москва, Россия, апрель 2008;

• Научно-практическая конференция «Инновации в условиях развития информационно-коммуникационных технологий» ИНФО-2009, Сочи, Россия, октябрь 2009;

• Ежегодная научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ, Москва, Россия, февраль 2010;

• Научно-практическая международная конференция «Инновации в условиях развития информационно-коммуникационных технологий» ИНФО-2010, Сочи, Россия, октябрь 2010;

• Ежегодная научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ, Москва, Россия, февраль 2011;

Также результаты проделанной работы (работа Программно-аппаратный комплекс «Топологический процессор» Семин В.В. МГУ, МИЭМ) были представлены на ежегодном международном* конкурсе научных проектов «Максимальная масштабируемость» 2009г. проводимым корпорацией РОСНАНО и компанией Intel, где получили высокую оценку экспертов (13 место из 41 участника).

Публикации

По теме диссертации опубликовано 7 печатных работ из них 3 в журналах ВАК.

Основные положения, выносимые на защиту

Система формального представления, анализа и оптимизации многомерных решётчатых и триангулированных структур композитного типа. Краткое описание структуры диссертационной работы Диссертационная работа содержит введение, четыре главы, заключение, приложение, библиографию работ по теме диссертации. Диссертация содержит 38 рисунков и 10 таблиц. Общий объём диссертации 138 страниц.

Заключение

В данной диссертационной работе получены следующие основные результаты.

Разработана формальная система синтеза и анализа геометрико-топологических моделей, включающая в себя:

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

2. Метод статистического анализа поведения триангуляции на многомерных решётчатых структурах, метод статистического анализа симплициальных моделей, предложен метод классификации согласно пороговым значениям статистики.

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

4. Методы алгебраического и машинного представления многомерных решётчатых и триангулированных структур.

5. Методы построения программных средств для решения задач, связанных с обработкой многомерных решётчатых и триангулированных данных.

Разработана концептуальная структура программно-аппратного комплекса.

1. Alistair Adcroft, Jean-Michel Campin. Massachusetts Institute of Technology General Circulation Model, online documentation. url:http://mitgcm.org/public/r2 manual/latest/onlinedocuments/node2.html

2. Mathieu Desbrun, Eva Kanso, and Yiying Tong. Discrete Differential Forms for, Computational Modelling.url :http://www.geometrv.caltech.edu/pubs/DKT05.pdf.

3. Sharif Elcott, Mathieu, Desbrun, Eva Kanso, Yiying Tong and Peter Schroder. Dicrete, Circulation-Preserving and Stable Simplicial Fluids.url :http://multires.caltech.edu/pubs/DiscreteFluidsTOG.pdf.

4. Флетчер К. Вычислительные методы в динамике жидкостей -М:Мир, т.2, 1991, 552с.

5. Smith R.E. Algebraic Grid' Generation. Numerical Grid4 Generation- // ed. by J.F.Thompson. New York, North-Holland, 1982, P. 137-170.

6. Eisemann P.R. Coordinate generation with precise controls over mesh properties. // J. of Сотр. Phys., vol.47, N3, 1982, P.331-351.

7. Eriksson L.E. Generation of boundary-conforming grids around wing-body configurations using transfmite interpolation. // AIAA J., vol.20, N10, P. 13131320.

8. Nakamura S. Marching grid generation using parabolic partial differential equations. Numerical Grid Generation // ed. by J.F.Thompson. New York, North-Holland, 1982, P.775-786.

9. Thompson J.F. Elliptic grid generation. Numerical Grid Generation // ed. by> J.F.Thompson. New-York, North-Holland, 1982, P.79-106.

10. Shwarz W. Elliptic grid generation system for three-dimensional configurations using Poisson's equation. Numerical Grid Generation in Computational Fluid-Dynamics,// ed. by J. Hauser and C. Taylor, Swansea, 1986, P. 341-352.

11. Sorenson R.E. Elliptic generation of composite three-dimensional grids about realistic aircraft. Numerical Grid Generation in Computational- Fluid Dynamics, //ed. by J. Hauser and^C. Taylor, Swansea, 1986, P. 353-371.

12. Rubbert P.E., Lee K.D. Patched coordinate systems. Numerical Grid Generation.// ed. by< J.F.Thompson. New York, North-Holland, 1982, P.235-252.

13. Noak R.W., Steinbrenner J.P. A three-dimensional' hybrid grid generation technique. 12th AIAA Computational Fluid Dynamics Conference, San-Diego, 1995, P.413-423.

14. Connel S.D., Braaten M.E. Semi-structured mesh generation for 3D Navier-Stokes calculations. 12th AIAA Computational Fluid Dynamics Conference, San-Diego, 1995, P.369-380.

15. Benek J.A., Donegan T.L. Extended chimera grid, embedding scheme with application to viscous flows. 8th AIAA Computational Fluid Dynamics Conference, 1987, P.272-282.

16. Miyata H., Yamada Y. // Int. J. Numeric Meth. Fluids, 1992, v.14, N11, P.1261-1287.

17. Khawaja A., McMorris H., Kallinderis Y. Hybrid grids for viscous flows around complex 3-D geometries including multiply bodies. 12th AIAA Computational Fluid Dynamics Conference, San-Diego, 1995, P.424-441.

18. Федоренко Р.П. Введение в вычислительную физику. М.: Изд. МФТИ, 1994.

19. Астраханцев Г.П. Об одном итерационном методе. // ЖВМиМФ. 1971. Т. 11, N.2.

20. Бахвалов- Н.В. О сходимости одного, релаксационного метода. // ЖВМиМФ. 1966. Т.6, N.5.

21. Brandt A. Multigrid Techniques: 1984 Guide with Applications to Fluid Dynamics. GMD-Studien; N.85, 1984.

22. Brandt A. Multi-level Adaptive Computations in FluidDynamics. AIAA J. 18 (1980), P. 1165-1172.

23. Hackbusch V. Multigrid method and applications.« Berlin etc.: Springer -Verlag, 1985.

24. Hackbusch V., Trottenberg U. Multigrid Methods. Lecture Notes in, Math. 960, Springer Verlag, 1982.

25. Stuben K., Trottenberg U. Multigrid Methods: Fundamental Algorithms, Model Problem Analysis and Applications. GMD-Studien, N.96,1984.

26. S. Mijalkovic, W. Joppich. Multigrid method for Process Simulation. Series "Computational Microelectronics" edited by S. Selberherr, Springer Verlag, New York, Vienna, 1993.

27. Хэлси Н.Д. Использование конформных отображений при построении сеток для расчета обтекания трехмерных аэродинамических компоновок сложной формы.// АКТ ,N11, 1988, С.11-18.

28. Ryskin-G., Leal L.G. Orthogonal mapping. // J. of Сотр. Phys., vol.50, N1, 1983, P.71-100.

29. Chen L., Xu, J. Optimal Delaunay triangulations. // Journal of Computational Mathematics 22, 2004.2.P.299-308.

30. Tautges J. T., Blacker T., Mitchel S.A. The whisker weaving algorithm: A connectivitybased method for constructing all-hexahedral finite element meshes. // Int. J. Numeric Meth. In Engineering, 1996, V39, Issue 19, P. 33273349.

31. Staten M.L., Owen S.J., Blacker T.D. Unconstrained1 Paving & Plastering: A New Idea for All Hexahedral Mesh Generation. // Proceedings of the 14th International Meshing Roundtable / Hanks B.W., 2005, Part 5, P. 399-416.

32. Owen S. J. Constrained triangulation: Application to hex-dominant mesh generation // Proceedings of the 8th International" Meshing Roundtable. South Lake Tahoe, California: 1999. October. P. 31-41.

33. Babushka I., Rheinboldt W.C. A-posteriori Error Estimates for Finite Element Method // Int. J. Numer. Meth. Eng., 1978,Vol. 12, P. 1597-1615.

34. Шайдуров B.Bi Многосеточные методы конечных элементов. M.: Наука, 1989. - 288с.

35. Lewis R.W., Yao Zheng, Gethin D.T. Three-Dimensional Unstructured Mesh Generation: Part 3. Volume Meshes // Computer Methods In Applied Mechanics And Engineering, Elsevier, 1996, Vol 134, P. 285-310.

36. Новиков С.П., Топология. Москва-Ижевск, РХД 2002.

37. Долбинин Н.П., Штанько М.А., Шторгин М.И. Кубические многообразия в решётках//Изв. РАН. Сер.матем., 1994, 58, 2, С. 93-107.

38. Понтрягин JI.C. Основы комбинаторной топологии. М.: Наука, 1986. 120 с.

39. Рябов Г.Г. Марковские процессы в динамике примитивных триангуляций в пространствах R3 и R4. II Вычислительные методы и программирование. 2009. 10, №1. С*. 1-8.

40. Мартинсон JI. К. Смирнов Е.В. Квантовая физика.М.:МГТУ им. Баумана, 2009. 580с.

41. Alliez P., Cohen-Steiner D., Yvinec М., Desbrun М. Variational Tetrahedral Meshing. // ACM Trans, on Graphics (SIGGRAPH '05), 2005. 24(3), P. 617625.

42. Ruppert J. A New and Simple Algorithm for Quality 2-Dimensional Mesh Generation. // In Proc. of the 4th ACM/SIAM Symp. on Disc. Algo. (SODA), 1993 .P.83-92.

43. Teng S.H., Wong C.W., Lee D.T. Unstructured Mesh Generation: Theory, Practice, and Perspectives. // International Journal Computational Geometry and Applications.2000.10, 3 (June), P.227-266.

44. Shewchuk J. What Is a Good Linear Element? Interpolation, Conditioning, and Quality Measure. // In Proc. of 11th Int. Meshing Roundtable.2002.P.l 15126.

45. Cohen-Steiner D., De Verdiere E. C., Yvinec M. Conforming Delaunay triangulations in 3D. // In Proc. of Symp. on Сотр. Geom. 2002.P.237-246.

46. Frey J. L., George P. L. Mesh Generation: Applications to Finite Elements. Paris. :Hermes, 2000. 817p.

47. Cheng, S.W., Poon S.H. Graded conforming Delaunay tetrahedralization with bounded radius-edge ratio. // In Proc. of the 14th ACM-SIAM Symposium on Discrete algorithms (SODA). 2003.P.295-304.

48. Li X.Y., Teng S.H., Ungor A. Biting: Advancing Front Meets Sphere Packing. // Int. J. on Num. Methods in Eng.2000. 49, 1, P.61-81.

49. Li X.Y., Teng. S.H., UNGOR. A. .Biting: Advancing Front Meets Sphere Packing // Int. J. on Num. Methods in Eng. 2000.49, 1, P. 61-81.

50. Molino N., Bridson R., Teeran J., Fedkiw R. A Crystalline, Red Green Strategy for Meshing Highly Deformable Objects with Tetrahedra // In Proceedings of the 12th International Meshing Roundtable, 2003. P: 103-114.

51. Mitchell1 Si, Vavasis S. Quality Mesh Generation in Higher Dimensions« // SIAM J. Sci. Comput. 29,- 2000. P. 1334-1370.

52. Shewchuk J. R. Tetrahedral mesh generation by Delaunay refinement // In Proc. 14th Annu. ACM Sympos. Comput. Geom., 1998, P. 86-95.

53. Borouchaki H., George P., Hecht F. Delaunay mesh generation governed by metric specifications. Part 1 : Algorithms. // Finite Elements in Analysis and Design 25 /Laug P., Saltel E., 1997P. 61-83.

54. Du Q., Wang D. Tetrahedral mesh generation- and- optimization- based, on* centroidalVoronoi tessellations. // International Journal on Numerical Methods in Engineering 56(9).2003.P.1355-1373.

55. SliverExudation /Cheng'S.W., Dey Т. K., Edelsbrunner H., Facello-M. A., Teng S.H. //InProc. 15thACMSymp. Comput. Geom. 1999. P. 1-13.

56. Brentzen J. A. Robust generation of signed distance fields from triangle meshes. // Volume Graphics. 2005, P. 167-175.

57. Nooruddin F. S., Turk G. Simplification and repair of polygonal models using volumetric techniques// In IEEE Trans, on Visualization and Computer Graphics. 2003, P. 191-205.

58. Галанин М.П., Щеглов И.А. Разработка и реализация алгоритмов трехмерной триангуляции сложных пространственных областей: прямые методы. М., 2006. 32 с. (Препринт ИПМ1 им. М.В. Келдыша РАН, № 10).

59. Cohen-Steiner, D., Alliez P., Desbrun M. Variational Shape Approximation. // ACM Trans, on Graphics (SIGGRAPH).2004. P. 905-914.

60. Lloyd S. P. Least Squares Quantization in PCM's. Tech. rep., Bell Telephone Laboratories, Murray Hill, NJ. 1957.

61. Chen L., Xu, J. Optimal Delaunay triangulations.// Journal of Computational Mathematics 22, 2004.2.P.299-308.

62. Long C. Optimal Delaunay Triangulations. // Tenth SIAM Conference on Geometric Design and Computing. 2007. P. 1-121.

63. Рябов Г.Г. О четверичном кодировании кубических структур // Вычислительные методы и программирование. 2009. 10, №2. С. 340-347.

64. Рябов Г.Г. О путевом кодировании к-гранешв п-кубе // Вычислительные методы и«программирование. 2008. 9, №1. С. 16-18.

65. Якобовский М.В. Вычислительная среда для моделирования задач механики сплошной среды на высокопроизводительных системах:

66. Hendrickson В, Kolda Т. G. Graph partitioning models for parallel computing. //Parallel'Computing, 26, 2000, P. 1519-1534.

67. Karypis G., Kumar V. A Parallel Algorithm for Multilevel Graph Partitioning andJ Sparse Matrix Ordering. // Journal of Parallel and Distributed Computing, 48, 1998, P. 71-95.

68. Walshaw C., Cross M. Parallel optimization algorithms for multilevel mesh partitioning. // Parallel Computing 26,2000, P. 1635-1660.

69. Якобовский М.В. Инкрементный алгоритм декомпозиции графов. Вестник Нижегородского университета им. Н.И.Лобачевского. Серия «Математическое моделирование и оптимальное управление», Вып. 1(28). Нижний Новгород: Издательство ННГУ, 2005, С. 243-250.

70. Bruce Hendrickson, Robert Leland. A Multilevel Algorithm for Partitioning Graphs. SAND93-1301, 1993.

71. Moulitsas I. Karypis G. Architecture Aware Partitioning Algorithms // 8th Intl. Conference on, Algorithms and1 Architectures for Parallel Processing (ICA3PP), 2008,P. 42-53.

72. Кормен, Т., Лейзерсон, Ч., Ривест, Р.,. Штайн, К.// Алгоритмы: построение и анализ = IntroductiontoAlgorithms / Под ред. И. В. Красикова. 2-е изд. М.: Вильяме, 2005. 1296 с.

73. Spillmann J.M., Teschner. W. M. Robust Tetrahedral Meshing of Triangle Soups./Лп Proc., Vision, Modeling, Visualization. 2006. P. 1-8.

74. Cohen-SteinerD., D'Verdiere E. C., Yvinec M. Conforming Delaunay . triangulations in 3D: // In Proc. of Symp: on Сотр. Geom., 2002. P. 237-246.

75. Krysl P., Ortiz M. Variational Delaunay Approach to the Generation of Finite Element Meshes. Int. J. for Num. Meth. in Eng. 50(7), 2001. P. 1681-1700.

76. Cheng S.W., Poon S.H. Graded'conforming Delaunay tetrahedralizationwith bounded radius-edge ratio. // In Proc, of the Î4th ACM-SIAM Symposium on Discrete algorithms (SODA), 2003. P. 295-304.

77. Collet P., Eckmann J. Dynamics of triangulations // arXiv: math-ph/0412085vl. 23 Dec., 2004.

78. Ambjorn J:, Jurkiewicz J., Loll R., Emergence of a 4D'world fromcausal quantum gravity, Phys. Rev. Lett. 93 (2004) 131301 arXiv:hep-th/0404156.

79. Kaibel V., Ziegler G. Counting lattice triangulations // arXiv: math/0211268v2math.CO. 13 Dec., 2002.

80. Семин В.В. Исследование поведения триангуляции на симплициальных комплексах. // Дискретная математика. Том 23. Выпуск 1. 2011. С. 119131.

81. Семин В.В. Алгоритмы построения и анализа симплициальных комплексов на квазистационарных решётках. // Информационные технологии. №5. 2011.С. 52-57.

82. Семин В.В. Моделирование поведения стохастической триангуляции на квазистационарных решетках. // Информационные технологии. №6. 2011.С. 45-50.

83. Семин В.В. Симплициальные комплексы на квазистационарных решётках. // Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ: Тез.докл. конф.- М.:МИЭМ, 2010. С. 8485.

84. Семин В.В. Алгоритмическое и математическое обеспечение программно-аппаратного комплекса «Топологический процессор». // Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ: Тез.докл. конф. М.:МИЭМ, 2011. С.82-83.