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

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

Чернышснко Алексей Юрьевич

Технология построения адаптируемых многогранных сеток и численное решение эллиптических уравнений 2-го порядка в трехмерных областях и на поверхностях

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

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

г 8 НОЯ 2013

005540162

Москва - 2013

005540162

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте вычислительной математики Российской

академии паук.

Научный руководитель: Официальные оппоненты:

Василевский Юрий Викторович, доктор физико-математических наук, доцент. Гасилов Владимир Анатольевич, доктор физико-математических наук, профессор, Федеральное государственное бюджетное учреждение науки Институт прикладной математики им. М. В. Келдыша Российской академии паук,

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

Федеральное государственное бюджетное учреждение науки Вычислительный центр им. А. А. Дородницына Российской академии наук.

Защита состоится «18» декабря 2013 г. в 15 часов на заседании диссертационного совета Д 002.045.01 при Федеральном государственном бюджетном учреждении науки Институте вычислительной математики Российской академии паук (ИВМ РАН), расположенном по адресу: 119333, г. Москва, ул. Губкина, д. 8, ауд. 121.

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

Автореферат разослан <•< ноября 2013 г. Ученый секретарь

Ведущая организация:

диссертационного совета,

доктор физико-математических наук

Бочаров Г. А.

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

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

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

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

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

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

04201 451 482

Чернышенко Алексей Юрьевич

Технология построения адаптируемых многогранных сеток и численное решение эллиптических уравнений 2-го порядка в трехмерных областях и на поверхностях

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

ДИССЕРТАЦИЯ

на соискание учёной степени кандидата физико-математических наук

Научный руководитель д. ф.-м. н.

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

Содержание

Введение ......................................................................4

Обзор используемой терминологии ..................19

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

дерево со сколотыми ячейками в составных областях .... 22

1.1. Построение сколотых ячеек ....................24

1.2. Случай составной области .....................34

1.3. Общий алгоритм построения сетки ................48

1.4. Анализ алгоритма..........................51

1.5. Дополнительные операции с сеткой ................56

1.6. Сетки для слоистых областей ...................60

1.7. Примеры сеток............................64

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

Глава 2. Монотонный метод конечных объемов для трехмерной задачи диффузии.........................72

2.1. Стационарное уравнение диффузии................72

2.2. Нелинейный метод конечных объемов на сетках с многогранными ячейками .............................73

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

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

Глава 3. Метод приближенного решения эллиптических уравнений 2-го порядка на поверхностях ...............89

3.1. Предварительные сведения и обозначения ............89

3.2. Расширение уравнения на поверхности ..............91

3.3. Численные методы .........................100

3.4. Численные эксперименты......................103

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

Заключение .................................114

Литература .................................115

Введение

Процесс решения задач математической физики с использованием ЭВМ можно разделить на три основных этапа: построение расчетной сетки, дискретизация дифференциальных или интегральных уравнений и решение системы алгебраических уравнений. В настоящей работе центральную часть занимает проблема построения качественных расчетных сеток. Кроме этого, будут рассмотрены дискретизации эллиптических уравнений в трехмерных областях и на поверхностях. Различные методы дискретизаций представлены в работах [4, 5, 7]. Методы решения алгебраических уравнений рассматриваются в работах [6, 8, 9, 82].

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

Так, например, сетки должны приближать границу области с достаточным порядком точности. В настоящее время при расчетах приемлемым является второй порядок точности. В консервативных дискретизациях, популярных у инженеров, степени свободы находятся в центрах ячеек, поэтому генераторы сеток должны стремиться минимизировать число ячеек для заданной плотности распределения узлов сетки. При фиксированном количестве вершин ЛГу сетки известны следующие оценки количества ячеек Ыс и граней Ы? в сетках разных типов. Для неструктурированных тетраэдральных сеток А~ 5.5АГу, А^ ~ ПАГу, для треугольных призматических сеток Ис ~ 2А^у, А^ « 5Д^у, для гексаэдральных А/с ~ А^у, И? « ЗА/у. С этой точки зрения, гексаэдральные сетки являются наиболее выгодными. Получающиеся при дискретизации на гексаэдральных сетках шаблоны являются самыми компактными, а, значит, соответствующие матрицы имеют меньшее

количество ненулевых элементов. Такие матрицы являются более экономичными с точки зрения требуемого объема памяти и вычислительной сложности решения системы уравнений. С другой стороны, с точки зрения автоматического построения сеток для сложных областей, гексаэдральные сетки являются самыми трудными и неудобными. Существующие на сегодняшний день методы построения гексаэдральных сеток чаще всего применимы для узкого класса областей (блочно-структурированные сетки). Кроме этого остается открытым вопрос качественной аппроксимации границы подобными сетками. Однако, можно отметить некоторые коммерческие генераторы, позволяющие строить качественные гексаэдральные сетки в сложных областях: генератор HEXPRESS компании Numeca [15], а также генератор Hexotic [20], являющийся частью комплекса MeshGems [21].

Тетраэдральные сетки содержат большое количество ячеек и граней, что увеличивает количество ненулевых значений в матрице системы уравнений. Другим недостатком является то, что для анизотропных областей получаемые неструктурированные сетки могут иметь ячейки с очень большими двугранными углами, что значительно ухудшает качество дискретизации. Однако, с помощью тетраэдральных сеток можно строить расчётные сетки в сколь угодно сложных областях [2, 39]. Существует ряд комплексов программ, позволяющих строить тетраэдральные сетки: открытые Ani3D [17], TetGen [24], NETGEN [23], а также коммерческие TetMesh [25], CUBIT [18] и другие.

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

числительной математики РАН генератор треугольных призматических сеток разработан В.Н.Чугуновым [14]. Известны также коммерческие пакеты FEFLOW [19], MODFLOW-USG [22], а также разрабатываемый расчетный комплекс GeRa 1 [1], позволяющие строить такие сетки.

Перспективным направлением в развитии сеточных генераторов является создание надёжной технологии построения гибридных сеток для сложных областей, состоящих преимущественно из гексаэдров, а также из приграничных многогранных ячеек. В настоящее время можно выделить несколько пакетов программ, которые позволяют строить сетки с преимущественно гек-саэдральными ячейками. Закрытый программный пакет ЛОГОС.ПреПост, разрабатываемый в ВНИИЭФ г.Сарова, позволяет строить сетки с шестигранными и многогранными ячейками. Кроме этого, известен коммерческий пакет HEXPRESS/Hybrid компании Numeca [15], позволяющий строить подобные сетки.

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

1 Geomigration of Radionuclides - совместный проект ИВМ РАН и ИБРАЭ РАН в рамках проекта "Прорыв" ГК Росатом

Сколотая ячейка представляет собой часть кубической ячейки, полученную в результате ее среза поверхностной сеткой. Скалывание кубической ячейки может осуществляться различными способами. Так, например, Бре-тоннет и др. [34] применяют алгоритм полигональных сечений (Polygon clipping algorithm) [87], который используется в коммерческом генераторе HEXPRESS [15]. В настоящей работе в алгоритме скалывания используются поверхностные триангуляции. Существует ряд методов построения поверхностной триангуляции, использующих кубические сетки.

Широко известен метод марширующих кубов [71] (Marching cubes, МС). Однако, при всей своей популярности, известны также проблемы этого метода. Во-первых, в силу неоднозначности выбора триангуляции в кубической ячейке, алгоритм может порождать топологически несвязные сетки. Существует ряд работ, посвященных решению этой проблемы, [36, 53, 64, 73] и др. Во-вторых, классический метод марширующих кубов не может воспроизводить резкие искривления и особенности границы. В своей работе [60] Коб-бельт и др. предлагают расширенный метод марширующих кубов (Extended marching cubes), который отслеживает сложную геометрию границы, используя дополнительную информацию о нормалях к поверхности. В-третьих, алгоритм МС может быть применён только к равномерным кубическим сеткам. В случае, если размеры двух соседних ячеек отличаются, получаемая триангуляция становится топологически несвязной и может содержать дырки и пустоты. В работах [54, 56, 70, 91] предложены методы для восстановления топологической связности такой триангуляции на сетках типа восьмеричное дерево. Однако, данные алгоритмы также имеют существенные недостатки и сложности реализации, описанные в работе [55]. Там же предложен элегантный алгоритм кубических марширующих квадратов (Cubical marching squares, CMS), который лишен всех описанных недостатков. Данный алгоритм позволяет строить конформную триангуляцию поверхности для сеток

типа восьмеричное дерево.

Также известен метод марширующих тетраэдров (Marching tetrahedra) для построения поверхностной триангуляции на кубических сетках. В отличие от метода МС, он лишен проблемы неоднозначности, однако порождает значительно большее количество треугольников в поверхностной триангуляции.

Во многих прикладных задачах, таких как построение сеток для численных моделей подземной гидродинамики или построение трехмерных сеток по данным MPT или KT, область разбита на непересекающиеся подобласти с различными физическими свойствами, которые граничат между собой произвольным образом. Построенная сетка должна правильно отражать наличие различных подобластей. Для построения подобных сеток в настоящей работе предложена модификация метода марширующих кубов для областей с нескольким материалами (Multiple material marching cubes, M3C [93]) с более точным приближением границы. Эта модификация обобщает преимущества методов CMS и М3С, а, значит, может быть использована для построения сколотых ячеек на сетках типа восьмеричное дерево в областях с несколькими материалами. В результате получается многогранная сетка типа восьмеричное дерево со сколотыми ячейками, которая состоит преимущественно из гексаэдров.

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

тыми ячейками для приближенного решения краевых задач, во второй главе предлагается трехмерный аналог нелинейной-многоточечной схемы, удовлетворяющей дискретному принципу максимума (ДПМ). Двумерная версия этого метода была предложена в работе [68].

Принцип максимума (или минимума) является важным свойством решений линейных и нелинейных уравнений в частных производных. Выполнение дискретного аналога принципа максимума является желаемым свойством для численных схем. К сожалению, общепринятые схемы, удовлетворяющие дискретному принципу максимума, накладывают существенные ограничения на регулярность тетраэдральной сетки [61] и коэффициенты задачи. Нарушение ДПМ может привести к различным численным артефактам, таким как тепловой поток из холодного материала к горячему и др.

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

Классический метод конечных объёмов со степенями свободы в центрах ячеек и линейной двухточечной аппроксимацией диффузионного потока удовлетворяет ДПМ [31, 86]. Однако, главные направления тензора диффузии должны быть ортогональны граням сетки, в противном случае метод не имеет даже первого порядка точности для анизотропных диффузионных задач или на неструктурированных сетках. Тем не менее именно этот метод является наиболее распространённым в моделировании течений в пористых средах в силу своей технологической простоты и монотонности. Многоточечная аппроксимации потока (MPFA - Multipoint flux approximation) имеет второй порядок точности благодаря использованию большего числа точек в шаблоне, однако является условно устойчивой и условно монотонной. Ограничения на устойчивость и монотонность конечно-объёмных схем MPFA рассмотрены в

[26, 59, 75].

Другой класс монотонных схем для произвольных многогранных сеток состоит из нелинейных методов. Первоначальная идея принадлежит ЛеПотье [62], который предложил монотонную двухточечную схему дискретизации потока с коэффициентами, зависящими от концентраций в соседних ячейках. Этот подход развивался в работах [40, 66, 67, 74, 95] (см. также ссылки в этих работах), в которых доказывается неотрицательность решения на произвольных многогранных сетках и тензорах общего вида. Некоторые из подобных схем вводят дополнительные неизвестные на вершинах, ребрах или гранях сетки, значения в которые интерполируются из концентраций в соседних ячейках. Выбор схемы интерполяции оказывает большое влияние на точность нелинейной схемы [65, 95]. Определённый метод интерполяции может оказаться эффективным для одних задач и неэффективным для других. В работах [66, 67] предлагаются и исследуются схемы для уравнений диффузии и конвекции-диффузии, не требующие интерполяции решения в узлы сетки.

Нелинейные многоточечные схемы, удовлетворяющие ДПМ, были предложены в работах [63, 96] для двумерных диффузионных задач. Эти схемы также используют интерполяцию решения в дополнительных неизвестных. В работе [68] предлагается многоточечная нелинейная схема для диффузионного потока, не требующая интерполяции данных. В результате получается схема с минимальным шаблоном (в шаблоне используются только соседи по ребрам двумерной сетки), которая на ортогональных сетках и с диагональным тензором становится классической пятиточечной (для полного тензора шаблон также пятиточечный). В настоящей работе предлагается трехмерный аналог этой схемы для произвольных многогранных сеток с ячейками звездного типа.

Предложенная схема может потребовать интерполяции для некоторых

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

В одно время с данной работой независимо от нас была опубликована работа [49], в которой также предлагается нелинейная многоточечная схема дискретизации диффузионного потока на многогранных сетках, удовлетворяющая ДПМ. В настоящей работе не стоит задачи сравнения качества данных схем, однако отметим отличия схем. В работе [49] для аппроксимации диффузионного потока через грань используются точки гармонического осреднения [27]. В предлагаемой же схеме такие точки используются только на гранях, в которых происходит разрыв тензора, поэтому в ней гораздо меньше интерполяции данных.

Помимо дифференциальных уравнений в трехмерных областях, во многих прикладных задачах возникают уравнения в частных производных на поверхностях. Такие уравнения возникают в математических моделях различных природных явлений: диффузия вдоль межкристаллических границ [72], перенос поверхностно активных веществ на интерфейсах многофазных течений [81], липидные взаимодействия в биомембранах [47], а также во многих инженерных и биомедицинских приложениях: визуализация векторного поля [43], синтез текстур [89], построение развертки мозга [88], моделирование жидкости в легких [52] и многих других. Таким образом, в настоящее время большой интерес представляет развитие методов численного решения уравнений на поверхностях.

Можно выделить несколько основных подходов к численному решению

уравнений на поверхностях. Один из них требует построения явных триан