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

РГ6 од

2'3-МАЯ 1994

РОССИЙСКАЯ АКАДЕМИЯ НАУК ИНСТИТУТ ПРИКЛАДНОЙ МАТЕМАТИКИ

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

УДК 681.3.06

СУПАЛОВ Александр Валерьевич

РАЗРАБОТКА АЛГОРИТМОВ ПОСТРОЕНИЯ ТРЕХМЕРНЫХ ЛОКАЛЬНО АДАПТИРОВАННЫХ СЕТОК И ИХ ПРОГРАММНАЯ РЕАЛИЗАЦИЯ

Спегшальность 05.13.16 — применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (в отрасли физико-математических паук)

АВТОРЕФЕРАТ

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

МОСКВА 1394

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

Научный руководитель — доктор физико-математических наук, профессор КУЗНЕЦОВ Ю. А.

Официальные оппоненты: доктор физико-математических наук ГАСИЛОВ В. А. доктор физико-математических наук, профессор КЛИМЕНКО С. В.

Ведущая организация — Вычислительный центр Сибирского отделения РАН

Защита состоится " _"__ 1994 г. в_часов на

заседании специализированного совета Д 002.40.03 в Институте прикладной математики РАН по адресу: 125047, г. Москва, Миусская пл., Д. 4.

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

Автореферат разослан " _ 1994 г.

Ученый секретарь й/^/л!«.

специализированного совета кандидат физико-математических наук М. II. ГАЛАНИН

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

2. Исследование дополнительных возможностей метода локальной адаптации.

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

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

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

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

Практическая значимость. Разработана система ВсМ, применяемая для построения сеток, используемых при решении модельных и реальных задач гидродинамики и акустики в двумерных областях с кусочно-гладкой границей. В сотрудничестве с С.А. Финогеновым и С.П. Чеботаревым создан комплекс программ ПСот/ЗБ, предназначенный для численного решения задач с эллиптическими дифференциальными операторами в трехмерных областях сложной формы. На основании модульного генератора локально адаптированных сеток, являющегося компонентой системы ПСогп/ЗБ, разработано несколько специализированных программ, нацеленных на построение декартовых, цилиндрических и сферических локально адаптированных сеток, используемых для решения задач электростатики, гидродинамики и дифракции радиоволн.

Апробация работы. Основные результаты диссертации докладывались на:

• семинарах лаборатории вычислительной математики ИВМ РАН,

• семинаре Института основ информационных технологий Германского общенационального исследовательского центра компьютерных наук (г. Санкт Аугустин, Германия),

• Десятом франко-итало-российском совместном симпозиуме по вычислительной математике и приложениям (г. Москва, 1993 г.).

Публикации. По теме диссертации опубликовано четыре работы, список которых приведен в конце автореферата.

Структура диссертации. Диссертация состоит из введения, четырех глав, заключения, приложения и списка литературы из 92 наименований. Общий объем работы 100 страниц, из них 34 страницы с таблицами и рисунками.

СОДЕРЖАНИЕ РАБОТЫ

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

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

В параграфе 1.1 содержится постановка задачи построения двумерной локально адаптированной сетки для ограниченной односвязной области О с кусочно-гладкой границей ЗП, составленной из конечного числа простых незамкнутых гладких кривых 7/, сопрягающихся попарно в различных точках пространства тц с образованием невырожденных углов. В качестве исходной сетки в рассматриваемом простейшем случае применяется сетка с квадратными ячейками, вписанная в объемлющий область П прямоугольник II со сторонами, параллельными осям декартовой системы координат.

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

Для исследования влияния негладкости границы на процесс локальной адаптации и характеристики локально адаптированных сеток вводятся несколько определений. Сеточным расстоянием между вершинами 7"1 — (х1,у{) и т% = (х'2,1/2) называется выражение

^г(тЫ2) = тах(|х1 - 12|, \У1 - УгОЛ- (1)

Сеточным расстоянием между точкой г и кривой 7 называется выражение ^(г,7)=ппп1>;т(т,р) (2)

(легко заметить, что сеточное расстояние между вершиной и исходящей из нее кривой равно нулю). Наконец, сеточным расстоянием между кривыми 71 и 72 называется выражение

1^(71,72) = тщ С^(р,72) (3)

На основании введенных определений, расстояние между двумя областями П] и О2 определяется как минимум расстояний и £>77 между ограничивающими данные области границами д£1\ и

Пусть, вдобавок к введенным в предыдущем параграфе ограничениям на конфигурацию области Г2, соотношения границы 80, и исходной сетки ЕЛ с шагом к таковы, что:

1. Область Л не только лежит внутри прямоугольника П, но и удалена от границ И3 \ П не менее чем на Г^л > 1.

2. Каждая отдельная кривая границы <9П удовлетворяет ограничению кривизны

тш(Д7,1/Ку) П< 4^2 ' где круги радиуса Щ > 0, касательные к любой кривой 7 внешним или внутренним образом, не имеют с ней иных общих точек.

3. Минимальное расстояние между отдельными вершинами, вершинами и не относящимися к ним кривыми, и несвязанными друг с другом кривыми ограничено константами тт^ > 2, тт^ > 2 и ттп > 2 соответственно.

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

Этап 1 предназначен для нахождения множества г''-узлов. При действующих ограничениях эта задача решается очень просто: с данной вершиной т ассоциируется ближайший к ней узел исходной сетки

Этап 2 посвящен поиску множества 7Л-узлов исходной сетки. Поскольку тл-узлы уже найдены, они исключаются из дальнейшего анализа. Для каждого из оставшихся узлов, перенос осуществляется практически тем же способом, что и в алгоритме для гладкой границы. Именно, для каждого узла исходной сетки находится минимальное сеточное расстояние до точек пересечения проходящих через данный узел линий исходной сетки с границей области. Если это расстояние меньше 1/2, то узел перемещается в соответствующую точку, иначе он остается в исходном положении. В случае равноудаленности двух узлов от точки пересечения, переносу подлежит тот из них, что находится выше или правее ее. При неоднозначности сдвига узла, перенос осуществляется в любую из найденных точек. Отличие от случая гладкой границы заключается в том,

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

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

Этап 3 предназначен для разбора конфликтов, если таковые возникли в ходе выполнения предыдущего этапа. Разбор конфликтов заключается в последовательной обработке групп конфликтных узлов, которые могут относиться к одному (изолированный конфликт) или нескольким соседним (обширный конфликт) узлам исходной сетки. Число кривых, претендующих на данный узел (узлы), называется кратностью конфликта. Поскольку в данном случае все узлы должны быть перенесены на кривые, то все конфликты являются однородными. Для разрешения конфликтов предлагается эвристический метод, минимизирующий число перемещаемых узлов и максимум модуля их отклонения от исходного положения. Приводятся также достаточные условия отсутствия конфликтов указанных классов.

Этап 4 алгоритма предназначен для построения согласованной триангуляции полученной ранее искаженной сетки. Для этого все ячейки делятся на три группы:

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

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

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

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

е

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

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

(йо^ЛЛ) + (Л1Л1)(а2а2) [аха-^АхАг]

найденный по всем треугольникам сетки. Здесь символами а\ и

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

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

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

ю

В параграфе 2.1 приводится постановка задачи построения трехмерной локально адаптированной сетки для ограниченной односвязной области с кусочно-гладкой границей, состоящей из конечного числа попарно различных простых гладких поверхностей 7Г ограниченной кривизны (называемых далее поверхностями границы), конечного числа попарно различных простых гладких кривых '/ ограниченной кривизны (называемых, как и ранее, кривыми границы), и конечного числа попарно различных точек г, являющихся вершинами границы. Предполагается, что кривые 7 образуются путем сопряжения ровно двух различных поверхностей границы, а вершины получаются только в результате схождения в одной точке минимум трех различных кривых. Кривые 7 могут быть замкнутыми и незамкнутыми, причем последние могут объединяться в замкнутые кусочно-гладкие кривые, сопрягаясь в вершинах границы. Как и в двумерном случае, не рассматриваются замкнутые кривые, имеющие одну точку разрыва гладкости: такие кривые полагаются представленными в виде двух сопряженных кривых. Кроме того, считается, что все плоские, двугранные и телесные углы (как внутренние, так и внешние по отношению к области) не являются вырожденными.

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

1

2

3

. Область П не только лежит внутрй параллелепипеда П, но и удалена от границ 1!13 \ П не менее чем на > 1.

. Каждая отдельная поверхность границы 9П удовлетворяет ограничению кривизны

Л < ^, (6)

где шары радиуса Их > 0, касательные к любой поверхности п внешним или внутренним образом, не имеют с ней иных общих точек.

. Каждая отдельная кривая границы 8И удовлетворяет ограничению кривизны и кручения

(7>

где шары радиуса Щ > О, касательные к любой кривой 7 внешним или внутренним образом, не имеют с ней иных общих точек.

4. Минимальное расстояние между несвязанными друг с другом элементами границы области ограничено

mmDhTT>2, minn DhTy > 2, min Я?, > 2, (8)

miuD^ > 2, minn -D^ > 2, nüuDjr > 2,

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

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

Этая 1 предназначен для построения множества тЛ-узлов, аппроксимирующих соответствующие вершины границы области 8Q. Этот процесс ничем, кроме размерности, не отличается от соответствующего этапа двумерного алгоритма.

Этап 2 имеет целью построение сеточных кривых yh, аппроксимирующих соответствующие исходные хризые j границы области DQ. Выбор и перенос узлов на замкнутые гладкие кривые происходит следующим образом: для каждого узла исходной сетки определяется минимальное сеточное расстояние до точек пересечения проходящих через данный узел плоскостей исходной сетки с кривыми границы. Еслп это расстояние больше 1 /2, то узел не смещается. Если, напротив, это расстояние меньше 1/2, то узел смещается в соответствующую точку. При неоднозначности выбора узла, предпочтение отдается тому, что имеет большие сеточные координаты. При неоднозначности сдвига данного узла, он перемещается в любую из подходящих точек. Легко показать, что при введенном ограничении на кривизну и взаимную удаленность кривых границы, подобный способ аппроксимации линий гарантированно приводит к образованию корректных сеточных кривых, смежные, узлы которых не сближаются менее чем на

Dhrr > 1/2.

Перенос узлов на незамкнутые кривые отличается от описанного только что процесса предварительным исключением из числа рассматриваемых всех гл-узлов и исходящих из них гранен исходной сетки. Это гарантирует удаленность гА-узлов и "/'-узлов на > 1/2. Естественно, прн недостаточной разделенностн кривых возможно возникновение однородных конфликтов кратности два и более, которые запоминаются л:?;; дальнейшего разбора.

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

Этап 4 имеет целью построение сеточных поверхностей тг'1, аппроксимирующих поверхности тг границы области. Способ переноса узлов практически не отличается от описанного ранее для случая гладких границ. Однако из рассмотрения, как и в двумерном случае, исключатея тн-узлы и ^-узлы, а также исходящие из них ребра исходной сетки." Тем самым гарантируется, что 7Л-узлы и 7гл-узлы не сближаются менее чем на > 1/2. Выполнение этого условия для внутренних узлов поверхностей обеспечивается введенным ограничением на кривизну последних.

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

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

Пусть требуется построить согласованное тетраэдальное разбиение всех ячеек искаженной сетки. Известно, что существует 74 различных варианта разбиения куба (кубоида) на пять (2 случая) или шесть взаимно непересекающихся тетраэдров. Эти разбиения образуют шесть классов, и многообразие разрешенных положений внешних диагоналей ячеек весьма ограничено. Для построения согласованного разбиения, все ячейки делятся на три группы:

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

2. Вторую группу образуют прочие приграничные ячейки.

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

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

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

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

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

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

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

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

3. Сформированный таким образом список перебирается от начала к концу, и при этом для каждой ячейки:

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

€ В противном случае:

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

— Иначе, происходит отступление по списку на одну ячейку назад, что вызывает выбор нового способа разбиения предыдущей ячейки или переупорядочивание списка, и так далее.

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

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

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

1. по наибольшей величине синуса угла между любыми двумя обобщенно смежными ребрами,

2. по наибольшему минимальному объему получающихся тетраэдров,

3. по наименьшему максимальному отношению объема тетраэдра к произведению длин трех его самых коротких ребер,

4. по наименьшей максимальной величине отношения радиусов описанной и вписанной сфер,

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

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

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

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

Пусть в пространстве Я2 задана ограниченная односвязная область П с гладкой границей <9П'1 ограниченной кривизны. Исходная сетка является результатом аффинного отображения Т исходной сетки с шагом /г, вписанной в некий прямоугольник П' такой, что его образ — параллелограмм П = Т(П'), величина острого угла при вершине которого равна тг/З — полностью заключает в себя рассматриваемую область При этом преобразовании не происходит изменения длин сторон четырехугольников П'иП.

Построенная таким образом исходная сетка обладает рядом полезных свойств. Во-первых, она наследует сетке £' в смысле простоты структуры связности узлов. Во-вторых, она может быть разбита на правильные треугольники, качество которых является эталоном с точки зрения соотношения длин ребер, величины минимального угла, площади элементов и отношения радиусов вписанной и описанной окружностей. В-третьих, полученная таким образом симплексная сетка является триангуляцией Делоне для данного множества точек (впрочем, и прообраз — сетка с прямоугольными ячейками — является вырожденным разбиением Делоне).

Процесс построения локально адаптированной сетки имеет следующий вид. В результате обратного преобразования Т-1, переводящего параллелограмм П в прямоугольник П', область Q переходит в ограниченную односвязную область П' с гладкой границей dfi' ограниченной кривизны. Если эта кривизна удовлетворяет известным ограничениям, то перенос узлов исходной сетки на границу области описанным ранее способом приводит к образованию корректной искаженной сетки. После триангуляции длины сторон и площади треугольников лежат соответственно в пределах [ч/ЗЛ/4, Зл/ЗЬ/2] и [Зл/ЗЛ2/16, 9\/ЗА2/16], а углы треугольников лежат в пределах от 10,89 до 158,21 градуса.

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

Пусть в пространстве R3 задана ограниченная односвязная область Î! с гладкой границей dfth ограниченной кривизны. Исходная сетка £Л является результатом аффинного отображения Т исходной сетки с шагом h, вписанной в некий прямоугольный параллелепипед П' такой, что его образ —• параллелепипед П — Г(П'), пропорции которого описываются далее — полностью заключает в себя рассматриваемую область П.

Преобразование Т строится следующим образом. Оно переводит единичный куб в параллелепипед, такой, что каждая грань параллелепипеда является единичным ромбом, длина меньшей диагонали которого равна 2/у/З. Легко убедиться, что при этом длина меньшей внутренней диагонали параллелепипеда равна длине его стороны, то есть единице. Построенная в результате такого преобразования сетка обладает рядом положительных свойств. Во-первых, она очевидным образом сохраняет связность узлов, присущую сетке с кубическими ячейками. Во-вторых, существует такое тетраэдальное разбиение сетки £' , которое переводится в результате преобразования в набор конгруэнтных тетраэдров. Форма такого базового тетраэдра соответствует локальному максимуму отношения радиусов вписанной и описанной сфер, а также минимуму абсолютного и относительного квадратичных отклонений длин ребер и величин плоских углов сетки. Более того, разбитая указанным образом сетка является триангуляцией Делоне.

Искажение узлов производится на сетке Е' аналогично двумерному случаю. Если область iî' = T-1(ft) удовлетворяет известным ограниче-

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

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

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

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

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

Нетрудно показать, что при поддержании соответствующего соотно-

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

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

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

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

1. сеточной, или топологической, наиболее естественно соответствующей структуре связности исходной сетки;

2. параметрической, или модельной, в которой может задаваться модель;

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

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

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

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

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

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

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

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

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

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

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

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

Параграф 4.3 представляет созданный автором в сотрудничестве с С.А. Финогеновым и С.П. Чеботаревым программный комплекс ПСот/ЗБ,

■4Г-'

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

Описание программ иллюстрируете» с помощью некоторых результатов, достигнутых при практическом применении систем ВсМ, ПСот/ЗБ и их производных для построения плоских и пространственных сеток в областях сложной формы. При этом указывается, что время построения всех приводимых сеток не превышает нескольких секунд в двумерном случае, и нескольких десятков секунд — в трехмерном случае, несмотря на наличие в сетках десятков и сотен тысяч узлов соответственно.

В заключении формулируются основные результаты данной работы. Детальное описание формата файлов, используемых в системе Г1Сот/ЗБ для обмена данными между компонентами, выделено в особое приложение.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

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

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

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

. Создан комплекс программ РЮот/ЗБ, предназначенный для построения трехмерных локально адаптированных сеток в областях с кусочно-гладкой границей и численного решения задач с эллиптическими дифференциальными операторами в этих областях при помощи метода

фиктивных компонент на многопроцессорных ЭВМ с локальной памятью.

6. На основании модульного генератора локально адаптированных сеток, являющегося компонентой системы FiCom/3D, создано несколько специализированных программ, нацеленных на построение декартовых, цилиндрических и сферических локально адаптированных сеток для задач электростатики, гидродинамики и дифракции радиоволн.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Построение двумерных локально-адаптированных сеток: алгоритмы и реализация. - В сб.: Численный анализ и математическое моделирование. - М., ОВМ АН СССР, 1990. - С.98-130.

2. О локальной адаптации произвольных сеток. - В сб.: Численные методы и математическое моделирование. - М., ОВМ АН СССР, 1992. - С.80-102.

3. Fictitious domain methods for 3D elliptic problems: algorithms and software within a parallel environment. - 1993. - 48 p. - (Arbeitspapiere der GMD; 726), совместно с Кузнецовым Ю.А. и Финогеновым С.А.

4. Generation of three-dimensional locally fitted meshes. Algorithms and software. - 1993. - 60 p. - (Tech. Rep./Jyvaskyla Univ., Finland), совместно с Беспаловым A.H., Кузнецовым Ю.А., Липниковым К.Н и Финогеновым С.А.