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

Данилов Александр Анатольевич

Технология построения неструктурированных сеток и монотонная дискретизация уравнения диффузии

05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

1 6 СЕН 2010

Москва - 2010

004608064

Работа выполнена в Учреждении Российской академии наук Институт вычислительной математики РАН.

Научный руководитель: доктор физико-математических наук,

доцент,

Василевский Юрий Викторович

Официальные оппоненты: доктор физико-математических наук,

профессор,

Агошков Валерий Иванович

кандидат физико-математических наук, Гаранжа Владимир Анатольевич

Ведущая организация: Институт прикладной математики им.

М. В. Келдыша РАН

Защита состоится сентября 2010 г. в часов на заседании диссер-

тационного совета Д 002.045.01 при Учреждении Российской академии наук Институт вычислительной математики РАН, расположенном но адресу: 119333, г. Москва, ул. Губкина, д. 8, ауд. 121.

С диссертацией можно ознакомиться в библиотеке Учреждения Российской академии наук Институт вычислительной математики РАН.

Автореферат разослан « "2-1 » августа 2010 г.

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

а //

доктор физико-математических наук Бочаров Г. А.

Общая характеристика работы

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

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

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

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

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

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

На защиту выносятся следующие основные результаты:

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

2. Предложена и исследована новая монотонная нелинейная схема дискретизации уравнения диффузии на основе метода конечных объёмов на сетках с многогранными ячейками.

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

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

числительного центра РАН, Механико-математического факультета МГУ им. М.В.Ломоносова, в Институте прикладной математики и информационных технологий, г. Павия (Италия), в Лос-Аламосской национальной лаборатории, г. Лос-Аламос (США) и па следующих научных конференциях: конференции "Тихоновские чтения" (МГУ, Москва, ноябрь 2007, октябрь 2009); конференции "Ломоносов" (МГУ, Москва, апрель 2008, апрель 2010); конференции "Ломоносовские чтения" (МГУ, Москва, апрель 2009, апрель 2010); конференция молодых учёных "Технологии высокопроизводительных вычислений и компьютерного моделирования" (СПбГУ ИТМО, С.-Петербург, апрель 2009); конференция "Лобачевские чтения" (КГУ, Казань, ноябрь 2009); международные конференции "NUMGRID-2006" и "NUMGRID-2008" (ВЦ РАН, Москва, июнь 2006, июнь 2008); международная конференция "SIAM Geosciences 2009" (Лейпциг, Германия, июнь 2009); международный научный семинар "Computational Mathematics and Applications" (Технологический университет Тампере, Тампере, Финляндия, сентябрь 2009).

Публикации. Основные материалы диссертации опубликованы в 6 печатных работах, из них 3 статьи в рецензируемых журналах, входящих в перечень ВАК, [1-3].

Личный вклад автора. В совместной работе [1] вклад автора заключался в разработке нелинейной схемы дискретизации уравнения диффузии в трёхмерном пространстве, в программной реализации метода и в постановке численных экспериментов.

В совместной работе [4] вклад автора заключался в разработке методов построения треугольных и тетраэдральных неструктурированных сеток.

В совместной работе [5] вклад автора заключался в разработке методов взаимодействия с САПР при построении сеток, в программной реализации алгоритмов и проведении численных экспериментов.

Структура и объём диссертации. Диссертационная работа, состоит

из введения, обзора методов построения сеток и комплексов программ, четырёх глав, заключения и списка литературы из 73 наименований. Диссертационная работа содержит 32 рисунка и 15 таблиц. Общий объём диссертационной работы - 148 страниц.

Содержание работы

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

В обзоре методов построения сеток и комплексов программ проведён краткий анализ широко распространённых методов построения треугольных и тетраэдральных неструктурированных сеток, сделан обзор наиболее известных комплексов программ для построения неструктурированных сеток: Triangle, TetGen, TetMesli, NETGEN и CUBIT. Автор диссертационной работы является основным разработчиком библиотек для построения неструктурированных треугольных и тетраэдральных сеток, входящих в свободно распространяемые пакеты библиотек Ani2D1 и Ani3D2. В обзор включено описание особенностей разработанной библиотеки и её сравнение с остальными комплексами программ. Отметим, что в пакете Ani3D предусмотрен богатый выбор способов построения поверхностных сеток [3, 4].

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

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

1 http ://sourceforge.net/proj ects/ani2d/

2 http ://sourceforge.net/proj ects/ani3d/

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

В разделе 1.3 проведено исследование устойчивости алгоритма к вычислительным погрешностям, возникающим при реализации алгоритма на современных ЭВМ, предлагается устойчивый алгоритм проверки пересечения треугольника и отрезка на плоскости, основанный на вычислении знака определителя матрицы 2x2. Отметим, что при использовании в реализации на ЭВМ типов вещественных чисел с двойной точностью знак определителя может быть вычислен точно.

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

7ГСГ ТГО

где Л^г - количество треугольников, 5 - площадь многоугольной области, р -

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

В разделе 1.5 проведён анализ вычислительной сложности Алгоритма 1.1, выделены критические участки алгоритма, предложены способы ускорения работы этих участков с использованием структур данных на основе четверичных деревьев поиска.. В результате анализа сложности были получены оценки в среднем и в худшем случае для количества операций Алгоритма 1.1. В упрощённом виде эти оценки записываются следующим образом: в среднем количество операций пропорционально NxlogNx, и в худшем случае пропорционально N^,. Предложены две модификации Алгоритма 1.1 с улучшенными оценками количества операций в худшем случае. Первая модификация основана на результатах, полученных в разделе 1.4 при доказательстве существования подходящего треугольника, и в худшем случае требует количество операций пропорциональное Во второй предложенной модификации накладываются дополнительные ограничения на равномерность дискретизации начального фронта: отношение минимальной и максимальной длин отрезков не должно превышать двух. В этом случае количество операций в худшем случае будет пропорционально A'rlogA^r. Отметим, что все предложенные алгоритмы имеют среднюю сложность пропорциональную iV^ log Nt, и на практике применяется исходный вариант Алгоритма 1.1, описанный в разделе 1.2.

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

В разделе 1.7 проведены эксперименты, подтверждающие на практи-

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

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

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

В разделе 2.2 описаны возможности взаимодействия с геометрическим ядром системы автоматизации проектных работ (САПР). В работе [5] детально рассмотрен способ организации взаимодействия с промежуточной библиотекой Common Geometry Module (CGM), предоставляющей универсальный способ доступа к данным разных САПР. В пакет Ani3D была добавлена возможность подключения библиотек CGM и свободно распространяемой САПР Open CASCADE, для этого автором диссертационной работы была реализована базовая поддержка САПР Open CASCADE в библиотеке CGM.

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

В разделе 2.4 проведены эксперименты, подтверждающие на практике среднюю оценку количества операций алгоритма продвигаемого фронта на криволинейных поверхностях: количество операций в среднем пропорционально Nt log Nt, где Nt - количество построенных треугольников. В качестве демонстрации взаимодействия с геометрическим ядром САПР на Рис. 1

Рис. 1. Модель, заданная в САПР: а) геометрическая модель, б) дискретизация криволинейных рёбер, в) поверхностная квазиравномерная треугольная сетка.

приведён пример построения поверхностной сетки для модели, заданной в САПР.

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

В разделе 3.1 рассмотрены особенности построения тетраэдральных сеток с помощью алгоритма продвигаемого фронта, проведён анализ конечности числа операций и устойчивости алгоритма к вычислительным погрешностям, предложен устойчивый алгоритм проверки пересечения тетраэдра и треугольника, основанный на вычислении знака определителя матрицы 3x3. Рассмотренный алгоритм не всегда строит сетку для всей области, иногда остаются лакуны - локальные несвязные части области, в которых алгоритм продвигаемого фронта не работает. На практике лакуны занимают менее 1% объёма области.

Для построения тетраэдральных сеток в лакунах в разделе 3.2 предложен второй метод, основанный на тетраэдризации Делоне [6]. Доказана конечность работы второго метода. Комбинация двух методов позволяет строить сетки в трёхмерных многоугольных многосвязных многокомпонентных областях с заданным следом дискретизации на границе.

В разделе 3.3 сделан краткий обзор доступных методов улучшения ка-

чества полученной тетраэдральной сетки.

В разделе 3.4 проведено экспериментальное подтверждение оценки количества операций алгоритма продвигаемого фронта, проведено исследование распределения объёмных частей области, для которых строится сетка с помощью алгоритма продвигаемого фронта и с помощью алгоритма на основе тетраэдризации Делоне. Проведено исследование качества элементов сеток, полученных на разных этапах построения, а также изучены возможности улучшения качества с помощью доступных алгоритмов и методов. На Рис. 2 продемонстрирован разрез тетраэдральной сетки, полученной с помощью методов, изложенных во второй и третьей главах, на основе модели, заданной в САПР.

Рис. 2. Модель, заданная в САПР: а) геометрическая модель, б) разрез тетраэдральной сетки.

Рассмотренные методы и технология построения тетраэдральных сеток опубликованы в работе [2].

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

В разделе 4.1 дана постановка задачи. Пусть П - трёхмерная многогранная область, граница которой состоит из двух частей, Г = IV и Гд, причём множество Гд замкнуто и непусто, Гд = Гр, Гд ^ 0. Рассматривается задача диффузии для неизвестной концентрации с:

-сКу(КУс) = д в П

с = до на Гд (1)

—п • КУс = дх на Гдг,

здесь Ж(х) = Кт(х) > 0 - полный анизотропный тензор диффузии, д -внешние источники, до и д^ - граничные условия Дирихле и Неймана, соответственно, п - вектор внешней нормали.

В разделе 4.2 предложена новая схема дискретизации на основе метода конечных объёмов с использованием нелинейного двухточечного шаблона для аппроксимации диффузионного потока на гранях расчётной сетки. Диффузионный поток qlj на грани / между двумя ячейками Т+ и Т- представляется в виде

ч) • П/ = м;сг+ - м;ст_,

где п/ - нормаль к грани, направленная из Т+ в Т_, Ст± - значения дискретных концентраций в Т±, М^ > 0 - коэффициенты, зависящие от значений концентрации в окружающих ячейках.

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

Теорема. Пусть д > 0, до > 0, дк < 0 и Гд Ф 0 в (1). Если начальное приближение С0 > 0 и линейные системы в м,етоде Пикара решаются точ-

12

по, то полученное решение Ск > 0 на каждой итерации метода Пикара, к > 1.

В разделе 4.4 проведены эксперименты, анализирующие сохранение неотрицательности решения и выполнение дискретного принципа максимума, проведено исследование количества итераций в методе Пикара и скорости сходимости метода при различных условиях. Полученные результаты демонстрируют второй порядок сходимости концентрации в дискретной ¿2-норме на тетраэдральных, призматических и гексаэдральных сетках, в том числе с разрывным тензором диффузии и на ячейках с неплоскими гранями. Порядок сходимости падает ниже второго при сильной анизотропии сетки. Дискретный принцип максимума может нарушаться, но неотрицательность решения всегда сохраняется (если д > 0, до > 0, д^ < 0 и Го 0 в (1), то решение с > 0). Наблюдается высокая скорость сходимости метода Пикара на первых итерациях, обратная зависимость количества итераций от шага сетки и слабая зависимость от типа сетки.

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

При моделировании стационарного распределения интерферона в лимфоузле была исследована зависимость распределения от количества источников интерферона - плазмацитоидных дендритных клеток (см. Рис. З.б), а также от скорости деградации интерферона. Важным полученным результатом является значительная неоднородность концентрации интерферона внутри лимфоузла.

а)

б)

Рис. 3. Стационарное распределение интерферона в лимфоузле, а) разрез построенной сетки, 6) распределение интерферона (пг./л), количество плазмацитоидных дендритных клеток 10 клеток, случайно распределённых в верхней части краевого синуса.

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

Разработана технология надёжного построения треугольных и тетраэдральных сеток. В работе проведён анализ влияния вычислительных погрешностей при реализации алгоритмов на ЭВМ, представлено теоретическое обоснование конечности числа операций предложенных алгоритмов. Программы для построения треугольных, поверхностных, и тетраэдральных сеток включены в пакет библиотек АшЗБ и находятся в свободном доступе.

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

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

Список публикаций

1. Danilov A., Vassilevski Y. A monotone nonlinear finite volume method for diffusion equations on conformai polyhedral meshes // Russ. J. Numer. Anal. Math. Modelling. 2009. V. 24, № 3. P. 207-227.

2. Danilov A. Unstructured tetrahedral mesh generation technology // Ж. Выч. Мат. и Мат. Физ. 2010. Т. 50, № 1. С. 146-163.

3. Данилов А. А. Способы построения трёхмерных поверхностных триангуляция и тетраэдральных сеток // Научно-технический вестник СПбГУ ИТМО. 2010. Т. 65, № 1. С. 87-92.

4. Василевский Ю. В., Вершинин А. В., Данилов А. А., Плёнкин А. В. Технология построения тетраэдральных сеток для областей, заданных в САПР // Матричные методы и технологии решения больших задач / Под ред. Е. Тыртышникова. М.: ИВМ РАН, 2005. С. 21-32.

5. Василевский Ю. В., Данилов А. А. Взаимодействие с САПР для построения расчётных сеток в сложных областях // Труды Математического центра им. Н.И. Лобачевского. 2009. Т. 39. С. 5-12.

6. Данилов А. А. Построение тетраэдральных сеток для областей с заданными поверхностными триангуляциями // Численные методы, параллельные вычисления и информационные технологии. М.: МГУ, 2008. С. 119-130.

Vjn

Заказ Jfe 52-a/08/10 Подписано в печать 18.08.2010 Тираж 80 экз. Усл. пл. 1

\ 000 "Цифровичок", тел. (495) 649-83-30

'П^у) www.cfr.ru; e-mail:info@cfr.ru

Введение

Обзор методов построения сеток и комплексов программ

Глава 1. Построение двумерных треугольных сеток.

1.1. Обозначения.

1.2. Алгоритм продвигаемого фронта

1.3. Влияние вычислительных погрешностей.

1.4. Конечность работы алгоритма.

1.5. Скорость работы алгоритма продвигаемого фронта.

1.6. Улучшение качества полученной сетки.

1.7. Результаты экспериментов.

1.8. Выводы к первой главе.

Глава 2. Построение поверхностных сеток.

2.1. Представление поверхности.

2.2. Взаимодействие с геометрическим ядром САПР.

2.3. Алгоритм продвигаемого фронта

2.4. Результаты экспериментов.

2.5. Выводы к второй главе.

Глава 3. Построение трёхмерных сеток.

3.1. Алгоритм продвигаемого фронта

3.2. Устойчивый метод на основе тетраэдризации Делоне.

3.3. Улучшение качества полученной сетки.

3.4. Результаты экспериментов.

3.5. Выводы к третьей главе.

Глава 4. Сетки с многогранными ячейками и монотонная дискретизация уравнения диффузии.

4.1. Уравнение диффузии.

4.2. Монотонная нелинейная схема на основе метода конечных объёмов

4.3. Схема дискретизации и анализ её монотонности.

4.4. Результаты экспериментов.

4.5. Моделирование стационарного распределения интерферона в лимфатическом узле

4.6. Выводы к четвёртой главе.

При решении современных научных и инженерных задач широко применяется математическое моделирование. Существуют готовые системы автоматизации инженерных расчётов (CAE - Computer-aided engineering) для анализа и моделирования физических процессов па ЭВМ. Как правило, это большие закрытые коммерческие проекты, разрабатывающиеся на протяжении десятков лет группами в несколько сотен специалистов. С точки зрения пользователя системы CAE предоставляют удобный графический интерфейс для задания параметров и условий задачи, проведения расчётов, отображения и анализа результатов. Алгоритмы и методы, используемые для решения конкретной задачи, зачастую скрыты от пользователя.

Как правило, процесс моделирования физических процессов с использованием ЭВМ сводится к трём основным операциям: построение расчётных сеток, дискретизация дифференциального уравнения, решение системы алгебраических уравнений. В диссертационной работе мы детально рассмотрим проблемы построения сеток. Различные методы дискретизаций представлены в работах [13, 14, 17]. Методы решения алгебраических уравнений рассматриваются в работах [12, 15, 19].

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

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

Автор диссертационной работы входит в коллектив исследователей, разрабатывающих пакет библиотек АшЗО с открытым исходным кодом - программный код библиотеки доступен для просмотра, изучения и изменения. В этот пакет входят библиотеки для построения и адаптации неструктурированных сеток, для построения дискретизаций на неструктурированных сетках, для решения систем линейных и нелинейных алгебраических уравнений. Также развивается и "двумерная" версия пакета - Аш2В. Программный код обеих библиотек распространяется свободно.

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

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

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

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

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

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

На защиту выносятся следующие основные результаты:

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

2. Предложена и исследована новая монотонная нелинейная схема дискретизации уравнения диффузии на основе метода конечных объёмов на сетках с многогранными ячейками.

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

Апробация работы. Результаты диссертационной работы докладывались автором и обсуждались на научных семинарах Института вычислительной математики РАН, Института математического моделирования РАН, Вычислительного центра РАН, Механико-математического факультета МГУ им. М. В. Ломоносова, в Институте прикладной математики и информационных технологий, г. Павия (Италия), в Лос-Аламосской национальной лаборатории, г. Лос-Аламос (США) и на следующих научных конференциях: конференции "Тихоновские чтения" (МГУ, Москва, ноябрь 2007, октябрь 2009); конференции "Ломоносов" (МГУ, Москва, апрель 2008, апрель 2010); конференции "Ломоносовские чтения" (МГУ, Москва, апрель 2009, апрель 2010); конференция молодых учёных "Технологии высокопроизводительных вычислений и компьютерного моделирования" (СПбГУ ИТМО, С.-Петербург, апрель 2009); конференция "Лобачевские чтения" (КГУ, Казань, ноябрь 2009); международные конференции "NUMGRID-2006" и "NUMGRID-2008" (ВЦ РАН, Москва, июнь 2006, июнь 2008); международная конференция "SIAM Geosciences 2009" (Лейпциг, Германия, июнь 2009); международный научный семинар "Computational Mathematics and Applications" (Технологический университет Тампере, Тампере, Финляндия, сентябрь 2009).

Публикации. Основные материалы, диссертации опубликованы в 6 печатных работах, из них 3 статьи в рецензируемых журналах, входящих в перечень ВАК, [8, 40, 41].

Личный вклад автора. В совместной работе [41] вклад автора заключался в разработке нелинейной схемы дискретизации уравнения диффузии в трёхмерном пространстве, в программной реализации метода и в постановке численных экспериментов.

В совместной работе [2] вклад автора заключался в разработке методов построения треугольных и тетраэдральных неструктурированных сеток.

В совместной работе [3] вклад автора заключался в разработке методов взаимодействия с САПР при построении сеток, в программной реализации алгоритмов и проведении численных экспериментов.

Структура и объём диссертации. Диссертационная работа состоит из введения, обзора методов построения сеток и комплексов программ, четырёх глав, заключения и списка литературы из 73 наименований. Диссертационная работа содержит 32 рисунка и 15 таблиц. Общий объём диссертационной работы - 148 страниц.

4.6. Выводы к четвёртой главе

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

Заключение

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

Разработана технология надёжного построения треугольных и тетраэдральных сеток. В работе проведён анализ влияния вычислительных погрешностей при реализации алгоритмов на ЭВМ, представлено теоретическое обоснование конечности числа операций предложенных алгоритмов. Программы для построения треугольных, поверхностных, и тетраэдральных сеток включены в пакет библиотек АшЗБ и находятся в свободном доступе.

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

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

1. Боровиков С. Н., Иванов И. Э., Крюков И. А. Построение тетраэдризацпи Делоне с ограничениями для тел с криволинейными границами // Ж. Выч. Мат. и Мат. Физ. 2005. Т. 45, № 8. С. 1407-1423.

2. Василевский Ю. В., Вершинин А. В., Данилов А. А., Плёнкин А. В. Технология построения тетраэдральных сеток для областей, заданных в САПР // Матричные методы и технологии решения больших задач / Под ред. Е. Тыртышнпкова. М.: ИВМ РАН, 2005. С. 21-32.

3. Василевский Ю. В., Данилов А. А. Взаимодействие с САПР для построения расчётных сеток в сложных областях // Труды Математического центра им. Н.И. Лобачевского. 2009. Т. 39. С. 5-12.

4. Василевский Ю. В., Капырин И. В. Две схемы расщепления для нестационарной задачи конвекции-диффузии на тетраэдральных сетках //Ж. Выч. Мат. и Мат. Физ. 2008. Т. 48, № 8. С. 1429-1447.

5. Воеводин В. В., Кузнецов Ю. А. Матрицы и вычисления. М.: Наука, 1984.

6. Гаранжа В. А., Капорин И. Е. Регуляризация барьерного вариационного метода построения разностных сеток // Ж. Выч. Мат. и Мат. Физ. 1999. Т. 39, № 9. С. 1489-1503.

7. Данилов А. А. Построение тетраэдральных сеток для областей с заданными поверхностными триангуляциями // Численные методы, параллельные вычисления и информационные технологии. М.: МГУ, 2008. С. 119-130.

8. Данилов А. А. Способы построения трёхмерных поверхностных триангуляций и тетраэдральных сеток // Научно-технический вестник СПбГУ ИТМО. 2010. Т. 65, № 1. С. 87-92.

9. Капырин И. В. Семейство монотонных методов численного решения трёхмерных задач диффузии на неструктурированных тетраэдральных сетках // Доклады Академии Наук. 2007. Т. 614, № 5. С. 588-593.

10. Колдоба А. В., Повещенко Ю. А., Попов Ю. П. Об одном алгоритме решения уравнения теплопроводности на неортогональных сетках // Дифференциальные уравнения. 1985. Т. 21, № 7. С. 1273-1276.

11. Ладыженская О. А. Краевые задачи математической физики. М.: Наука, 1973.

12. Лебедев В. И., Агошков В. И. Операторы Пуанкаре-Стеклова и их приложения в анализе. М.: ОВМ АН СССР, 1983.

13. Марчук Г. И. Методы вычислительной математики. М.: Наука, 1989.

14. Марчук Г. И., Агошков В. И. Введение в проекционно-сеточные методы. М.: Наука, 1981.

15. Марчук Г. И., Кузнецов Ю. А. Итерационные методы и квадратичные функционалы // Методы вычислительной математики. Новосибирск: Наука, 1975.

16. Никитин К. Д. Технология построения поверхностных регулярных триан-гуляций для областей, составленных из примитивов. Дипломная работа, Мех.-мат. ф-т. МГУ им. М.В.Ломоносова, Москва, 2007.

17. Самарский А. А. Теория разностных схем. М.: Наука, 1982.

18. Скворцов А. В. Триангуляция Делоне и её применение. Томск: Изд-во Том. ун-та, 2002.

19. Тыртыигаиков Е. Е. Методы численного анализа. М.: Издательский центр "Академия", 2007.

20. Харари Ф. Теория графов. М.: Мир, 1973.

21. Цинкернагель Р. Основы иммунологии. Пер. с нем. М.: Мир, 2008. С. 135.

22. Чугунов В. Н. Алгоритм построения конформной квази-иерархической треугольной сетки, слабо J-аппроксимируюгцей заданные ломаные //Ж. Выч. Мат. и Мат. Физ. 2009. Т. 49, № 5. С. 874-878.

23. Электронный ресурс: A Two-Dimensional Quality Mesh Generator and De-launay Triangulator. http://www.cs. emu. edu/~quake/triangle .html.

24. Электронный ресурс: Advanced Numerical Instruments 2D. http:// sourceforge.net/projects/ani2d/.

25. Электронный ресурс: Advanced Numerical Instruments 3D. http:// sourceforge.net/projects/ani3d/.

26. Электронный ресурс: CUBIT, http://cubit.sandia.gov/.

27. Электронный ресурс: Netgen Mesh Generator, http://sourceforge.net/ proj ects/netgen-mesher/.

28. Электронный ресурс: Open CASCADE Technology. http://www. opencascade.org/.

29. Электронный ресурс: TetGen: A Quality Tetrahedral Mesh Generator, http://tetgen.berlios.de/.

30. Электронный ресурс: TetMesh-GHS3D. http: //www. distene. com/build/ meshing.html.

31. Электронный ресурс: The Common Geometry Module, http: //cubit. sandia. gov/cgm. html.

32. Электронный ресурс: The Common Geometry Module, Argonne (CGMA). http://trac .mcs.anl.gov/proj ects/ITAPS/wiki/CGM.

33. Aavatsmark I., Eigestad G., Mallison В., Nordbotten J. A compact multipoint flux approximation method with improved robustness // Num. Meth. for Part. Diff. Eqs. 2008. Vol. 24, no. 5. Pp. 1329-1360.

34. Baker T. J. Shape Reconstruction and Volume Meshing for Complex Solids // Int. J. Numer. Meth. Engng. 1991. Vol. 32. Pp. 665-675.

35. Bocharov G., Ziist R., Cervantes-Вarragan L. et al. A Systems Immunology Approach to Plasmacytoid Dendritic Cell Function in Cytopathic Virus Infections // PLoS Pathogens. 2010.

36. Borouchaki H., Hecht F., Saltel E., George P.-L. Reasonably efficient De-launay based mesh generator in 3 dimensions // Proc. of 4th Int. Meshing Roundtable. 1995. Pp. 3-14.

37. Brezzi F., Fortin M. Mixed and Hybrid Finite Element Methods. New York: Springer-Verlag, 1991.

38. Burman E., Ern A. Discrete maximum principle for galerkin approximations of the laplace operator on arbitrary meshes // Comptes Rendus Mathematique. 2004. Vol. 338, no. 8. Pp. 641-646.

39. Ciarlet P. G., Raviart P.-A. Maximum principle and uniform convergence for the finite element method // Comput. Methods Appl. Mech. Engrg. 1973. Vol. 2. Pp. 17-31.

40. Danilov A. Unstructured tctrahedral mesh generation technology // Ж. Выч. Мат. и Мат. Физ. 2010. Т. 50, № 1. С. 146-163.

41. Danilov A., Vassilevski Y. A monotone nonlinear finite volume method for diffusion equations on conformai polyhedral meshes // Russ. J. Numer. Anal. Math. Modelling. 2009. Vol. 24, no. 3. Pp. 207-227.

42. Du Q., Wang D. Recent progress in robust and quality Delaunay mesh generation // J. of Сотр. and App. Math. 2006. Vol. 195. Pp. 8-23.

43. Escobar J., Rodríguez E., Montenegro R., González-Yuste J. Simultaneous untangling and smoothing of tetrahedral meshes // Сотр. Meth. in Appl. Mech. and Eng. 2003. Vol. 192. Pp. 2775-2787.

44. Gartner K., Si H., Fuhrmann J. Boundary conforming delaunay mesh generation // Ж. Выч. Мат. и Мат. Физ. 2010. Т. 50, № 1. С. 44-59.

45. George P.-L., Borouchaki H. Delaunay Triangulation and Meshing. Application to Finite Elements. Paris: Hermes, 1998.

46. George P.-L., Borouchaki H. Maillage simplicial d'un polyèdre arbitraire // C. R. Acad. Sci. Paris, 2004. Vol. 338. Pp. 735-740.

47. George P.-L., Borouchaki H., Saltel E. 'Ultimate' robustness in meshing an arbitrary polyhedron // Int. J. Numer. Meth. Eng. 2003. Vol. 58. Pp. 1061-1089.

48. Ito Y., Shih A., Soni B. Reliable isotropic tetrahedral mesh generation based on an advancing front method // Proc. of 13th Int. Meshing Roundtable. 2004. Pp. 95-106.

49. Joe B. Three-dimensional boundary-constrained triangulations // Proc. of 13th IMACS World Congress. 1992. Pp. 215-222.

50. Junt T., Scandella E., Ludewig B. Form follows function: lymphoid tissue microarchitecture in antimicrobial immune defence // Nature Reviews Immunology. 2008. Vol. 8. Pp. 764-775.

51. Kaporin I. E. High quality preconditioning of a general symmetric positive definite matrix based on its ulu + ufr + ^^-decomposition // Numer. Linear Algebra Appl. 1998. Vol. 5, no. 6. Pp. 483-509.

52. Keener J., Sneyd J. Mathematical Physiology. New York: Springer-Verlag. P. 766.

53. Korotov S., Krizek M., Neittaanmâki P. Weakened acute type condition for tetrahedral triangulations and the discrete maximum principle // Math. Gomp. 2001. Vol. 70, no. 233. Pp. 107-119.

54. Lammermann T., Sixt M. The microanatomy of T-cell responses // Immunological Reviews. 2008. Vol. 221. Pp. 26-43.

55. LePotier C. Schema volumes finis monotone pour des operateurs de diffusion fortement anisotropes sur des maillages de triangle non structures // G. C. Acad. Sci. Paris, 2005. Vol. 341. Pp. 787-792.

56. LePotier C. Finite volume scheme satisfying maxcimum and minimum principles for anisotropic diffusion operators // Finite Volumes for Complex Applications / Ed. by R. Eymard, J.-M. Hérard. 2008. Pp. 103-118.

57. Lipnikov K., Svyatskiy D., Shashkov M., Vassilevski Y. Monotone finite volume schemes for diffusion equations on unstructured triangular and shape-regular polygonal meshes // J. Comp. Phys. 2007. Vol. 227. Pp. 492-512.

58. Lipnikov K., Svyatskiy D., Vassilevski Y. Interpolation-free monotone finitevolume method for diffusion equations on polygonal meshes //J. Comp. Pliys. 2009. Vol. 228, no. 3. Pp. 703-716.

59. Lohner R., Parikh P. Generation of Three-Dimensional Unstructured Grids by the Advancing Front Method // Int. J. Numer. Meth. Fluids. 1988. Vol. 8. Pp. 1135-1149.

60. Lopez E., Nigro N., Storti M. Simultaneous untangling and smoothing of moving and fixed grids // Int. J. Numer. Meth. Engng. 2000. Vol. 10. Pp. 1-6.

61. Nordbotten J. M., Aavatsmark I., Eigestad G. T. Monotonicity of control volume methods // Numer. Math. 2007. Vol. 106, no. 2. Pp. 255-288.

62. Peraire J., Peiro J., Formaggia L. et al. Finite Element Euler Calculations in Three Dimensions // Int. J. Numer. Meth. Engng. 1988. Vol. 26. Pp. 2135-2159.

63. Santos V. R. On the strong maximum principle for some piecewise linear finite element approximate problems of nonpositive type //J. Fac. Sci. Univ. Tokyo Sect. IA Math. 1982. Vol. 29, no. 2. Pp. 473-491.

64. Schonhardt E. Uber die Zerlegung von Dreieckspolyedern in Tetraeder // Mathematische Annalen. 1928. Vol. 98. Pp. 309-312.

65. Shewchuk J. R. Triangle: Engineering a 2D Quality Mesh Generator and De-launay Triangulator // Applied Computational Geometry: Towards Geometric Engineering / Ed. by M. C. Lin, D. Manocha. Berlin: Springer-Verlag, 1996. Pp. 203-222.

66. Shewchuk J. R. Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates // Discrete & Comp. Geom. 1997. Vol. 18, no. 3. Pp. 305-363.

67. Shewchuk J. R. Constrained Delaunay tetrahedralizations and provably good boundary recovery // Proc. of 11th Int. Meshing Roundtable. 2002. Pp. 193-204.

68. Shewchuk J. R. Delaunay Refinement Algorithms for Triangular Mesh Generation // Comp. Geom.: Theory and Appl. 2002. Vol. 22, no. 1-3. Pp. 21-74.

69. Varga R. S. Matrix Iterative Analysis. Englewood Cliffs, NJ, USA: Prentice-Hall, 1962.

70. Yang Y., Yong J., Sun J. An algorithm for tetrahedral mesh generation based on conforming constrained Delaunay tetrahedralization // Computers & Graphics. 2005. Vol. 29. Pp. 606-615.

71. Yuan A., Shcng Z. Monotone finite volume schemes for diffusion equations on polygonal meshes //J. Comp. Phys. 2008. Vol. 227, no. 12. Pp. 6288-6312.