Введение к работе
Актуальность работы
В настоящее время исследование и разработка методов формального синтеза, машинного представления и алгоритмической обработки геометрико-топологической информации в классе симплициальных моделей представляет значительный практический интерес. Часто поиск решения актуальных прикладных задач анализа, моделирования и оптимизации структурно сложных систем большой размерности приводит необходимости применения формального аппарата симплициальных комплексов. Так трехмерные симплици-альные комплексы нашли широкое применение в многочисленных методиках моделирования физических процессов, в моделировании процессов химического и биологического синтеза на молекулярном уровне, в решении задач гидро-и газо-динамики, в автоматизированном проектировании транспортных средств, в реалистичном моделировании деформации объектов в компьютерной графике, а также в решении большинства основных разностных дифференциальных уравнений на основе методов конечных элементов или конечных объемов. Значительные результаты получены в области создания инструментальных средств решения задач автоматизированного моделирования транспортных систем в различных физических средах. Анализ областей применения исследуемых методов представления геометрико-топлогических данных указывает на устойчивую тенденцию повышения необходимой размерности геомет-рико-топологического представления объектов. Например, размерности модели глобальной циркуляции океан-атмосфера (MITgcm) - Ю9"" узлов, перколяцион-ных задач - 109"12 узлов, научно-технической визуализации - 108-1010 узлов, модели динамической гравитации (Space-Time models)-10 .
В исследуемой области геометрико-топологического моделирования наиболее существенные научные результаты получены в работах Рябова Г.Г., П. Коллета, М. Десбруна, Д. Кохен-Штейнера, А. Эдкрофта. Однако вопросы, связанные с унифицированным представлением и аппаратной поддержкой обработки требуют дальнейшего исследования.
Таким образом, задача построения единого унифицированного подхода к созданию математического и алгоритмического обеспечений для анализа и обработки симплициальных структур данных, является необходимым условием реализации эффективных программно- аппаратных методов поддержки процесса решения широкого круга прикладных и научных задач.
Отличительной особенностью постановки задачи данной диссертационной работы является исследование и разработка общего формального подхода к созданию математического и алгоритмического обеспечений программно-аппаратной системы обработки геометрико-топологической информации, инвариантной по отношению к физической природе многомерных геометрико-топологических входных данных. Необходимо отметить, что эффективное решение поставленной задачи обуславливает необходимость применения средств вычислительной техники, обеспечивающих возможности параллельной обработки больших объемов данных, реального масштаба времени обработки. Таким образом, тема диссертационной работы, посвященной решению задачи построения единой формальной системы обработки геометрико-топологической информации в классе симплициальных моделей, и базовых операций с последующей аппаратной поддержкой, является актуальной.
Предлагаемые в диссертационной работе подходы реализованы на примере программно-аппаратного комплекса «Топологический процессор». Цели работы и задачи исследования
Целью исследования является разработка математического и алгоритмического обеспечения программно-аппаратных комплексов обработки многомерных геометрико-топологических данных большой размерности в широком спектре практических задач.
Для достижения данной цели потребовалось решение следующих основных задач:
анализа и разработки классификации по типам и видам многомерных триангулированных данных (решётки, многообразия, комплек-
сы и т.д.) с целью выявления общих характеристик для формирования унифицированного метода представления данных;
разработки статистической модели анализа геометрико-топологических моделей на основе унифицированного представления данных;
разработки и обоснования критериев качества геометрико-топологических моделей, синтезируемых на основе предложенного типа данных;
разработки математического обеспечения для универсального представления данных и анализа исследуемого класса моделей;
разработки набора базовых операций обработки данных;
разработки базового алгоритмического обеспечения процесса обработки геометрико-топологических данных.
Объект исследования
Объектом исследования являются математические модели и программные комплексы, направленные на обработку больших объёмов многомерных триангулированных и решётчатых типов данных представления геометрико-топологической информации.
Предмет исследования
Предметом исследования является математическое и алгоритмическое обеспечение программно-аппаратных комплексов, а также перспективные методы аппаратной поддержки вычислений в подобных комплексах.
Методологическая и теоретическая основа исследования
При решении данных задач использовались методы математической статистики, алгебраический аппарат, элементы теории вычислений, элементы топологического аппарата, методы представления и оптимизации триангулированных решеток, математический аппарат оптимизации и в частности принцип максимума, элементы теории сложности вычислений.
Научная новизна работы заключается в следующем:
разработан подход к унифицированному способу представления многомерных геометрико-тологических данных, сформулированы критерии применимости данного подхода;
разработан статистический метод анализа на основе статистических распределений интегральных характеристик многомерных триангулированных решёток;
предложены критерии оценки качества многомерных триангулированных решёток;
разработан метод оптимизации качества триангулированной решётки;
разработаны методы формального представления решёточных структур на основе целочисленного кодирования. Приведены табличные определения различных элементарных операций над кодами, позволяющими проводить анализ и преобразования решётки;
предложены методы машинного представления решёточных структур;
разработаны алгоритмы и методы, реализующие предложенные подходы в инструментальной среде программной системы «Топологический процессор».
Практическая ценность и реализация
Результаты, полученные в данной работе, могут быть использованы при построении программно-аппаратных комплексов, ориентированных на решение задач обработки больших объёмов многомерных решётчатых и триангулированных данных (гидрометеорологические исследования, задачи гидродинамики, газодинамики, моделирование поведения высокоэнергетических пучков сверхмалых частиц и т.д.).
Апробация результатов исследования
Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах:
Научная конференция «Ломоносовские чтения», Москва, Россия, апрель 2008;
Научно-практическая конференция «Инновации в условиях развития информационно-коммуникационных технологий» ИНФО-2009, Сочи, Россия, октябрь 2009;
Ежегодная научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ, Москва, Россия, февраль 2010;
Научно-практическая конференция «Инновации в условиях развития информационно-коммуникационных технологий» ИНФО-2010, Сочи, Россия, октябрь 2010;
Ежегодная научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ, Москва, Россия, февраль 2011;
Также результаты проделанной работы (работа Программно-аппаратный комплекс «Топологический процессор» Семин В.В. МГУ, МИЭМ) были представлены на ежегодном международном конкурсе научных проектов «Максимальная масштабируемость» 2009г. проводимым корпорацией РОСНАНО и компанией Intel, где получили высокую оценку экспертов (13 место из 41 участника).
Публикации
По теме диссертации опубликовано 7 печатных работ из них 3 из перечня ВАК.
Основные положения, выносимые на защиту
Система формального представления, анализа и оптимизации многомерных решётчатых и триангулированных структур композитного типа.
Структура и объём работы
Диссертационная работа содержит введение, четыре главы, заключение, приложение, библиографию работ по теме диссертации. Диссертация содержит 38 рисунков и 10 таблиц. Общий объём диссертации 138 страниц.
