Параллельные технологии решения краевых задач

Оглавление
Введение 5
Глава 1 Блочные параллельные методы для решения неструктурированных систем 34
1.1 Последовательные технологии решения неструктурированных систем ... 35
1.1.1 Методы факторизации ............................................. 35
1.1.2 Методы неполной факторизации..................................... 38
1.1.3 Алгебраические многосеточные методы.............................. 40
1.1.4 Структурированные переобуславливатели для неструктурированных сеток ............................................................. 41
1.2 Решение неструктурированных систем с матрицами тензорного ранга 2 . . 43
1.3 Блочные переобуславливатели и переупорядочивание для задач с анизотропными коэффициентами ................................................... 46
1.4 Параллельный метод агрегирования и его применения..................... 52
1.4.1 Метод агрегирования.............................................. 53
1.4.2 Параллелизация метода агрегирования.............................. 61
1.4.3 Диффузионные задачи с гетерогенными коэффициентами и/или
большим числом подобластей ...................................... 63
1.4.4 Параллелизация на адаптивных неструктурированных сетках ... 65
Выводы главы 1.............................................................. 68
Глава 2 Параллельные адаптивные технологии на симнлициальных анизотропных сетках 69
2.1 Оптимальные и квази-онгимальные сетки и их свойства................... 70
2.1.1 Оптимальные сетки................................................ 70
2.1.2 Квази-оптимальные сетки ......................................... 78
2.2 Последовательный адаптивный алгоритм построения квази-оптимальных сеток...................................................................... 84
2
2.2.1 Восполнение сеточного гессиана.................................... 84
2.2.2 Генерация сеток, квази-равномерных в заданной метрике .......... 92
2.2.3 Адаптивный алгоритм............................................... 95
2.3 Управление адаптацией.................................................... 98
2.4 Особенности адаптации для областей с дискретной границей.................106
2.5 Параллельный адаптивный алгоритм для приближенного решения краевых задач ......................................................................113
2.5.1 Параллельная генерация сеток, квази-равномерных в заданной метрике ...................................................................113
2.5.2 Параллельное адаптивное решение трехмерных краевых задач . . . 116
2.5.3 Влияние управления адаптацией ....................................124
Выводы главы 2...............................................................128
Глава 3 Блочные параллельные методы решения неконформных конечноэлементных систем 129
3.1 Макро-гибридная постановка на песты кующихся сетках......................130
3.2 Интерфейсные переобуславливатели ........................................137
3.2.1 Переобуславливатели с внутренним итерационным процессом для
множителей Лагранжа...............................................138
3.2.2 Дирихле-Дирихле переобуелавливатель...............................143
3.2.3 Численные эксперименты с параллельными решателями.................146
3.3 Параллельные адаптивные технологии на нестыкующихся сетках 151
3.4 Мозаично-скслетонные переобуславливатели для множителей Лагранжа . 156
3.5 Параллельный многосеточный метод для неконформных конечных элементов 165 Выводы главы 3...........................................................172
Глава 4 Блочные параллельные технологии на трехмерных прямоугольных сетках 173
4.1 Параллельный двухуровневый метод Шварца для сингулярно возмущенного уравнения конвекции-
диффузии ...............................................................174
4.1.1 Двухуровневый метод Шварца для постоянного вектора переноса . 175
4.1.2 Двухуровневый метод Шварца для переменного вектора переноса . 182
4.1.3 Адаптивный алгоритм разбиения для случая переменного вектора
переноса..........................................................192
4.2 Некоторые приложения параллельного двухуровневого метода Шварца . . 193
4.2.1 Трехмерное уравнение конвекции-диффузии..........................193
4.2.2 Трехмерное уравнение конвекции-диффузии-реакции ...................196
4.2.3 Проекционный алгоритм для нестационарных уравнений Навье-Стокса196
4.2.4 Проекционный алгоритм для уравнения тепло-массопереноса в простейшем химическом реакторе...............................................201
4.3 Адаптивные итерационные технологии для последовательности систем . . 204
4.3.1 Последовательность систем с одной матрицей и разными правыми
частями............................................................204
4.3.2 Последовательность систем с разными матрицами и правыми частями207
4.3.3 Последовательность нелинейных систем...............................210
4.4 Блочные параллельные методы для систем уравнений многофазной фильтрации ..................................................................219
4.4.1 Уравнения многофазной фильтрации, их дискретизация и линеаризация ....................................................................219
4.4.2 Многосеточный метод с ускоренным разгрублением ....................221
4.4.3 Алгебраическое выделение уравнения для давления....................225
Выводы главы 4................................................................230
Заключение....................................................................232
П
4
Введение
Настоящая диссертация посвящена рассмотрению некоторых современных вычислительных технологий нахождения приближенного решения краевых задач с эллиптическими операторами второго порядка. Под вычислительными технологиями здесь понимается совокупность алгоритмов, структур данных, расчетных методик и программных реализаций для решения вычислительных задач на вычислительных системах. Главной целью вычислительных технологий является получение ответа в нужной форме, к заданному сроку и при известных ограничениях на доступ к машинным и человеческим ресурсам [8| . Основные черты рассматриваемых здесь технологий — параллельность и эффективность.
Параллельность вычислительных технологий вызвана необходимостью решать задачи настолько большой размерности, что даже новейшие однопроцессорные компьютеры не в состоянии обеспечить требуемый расчет. Помимо практических ограничений на быстродействие процессора и размеры компьютерной памяти, немаловажно учитывать и экономический аспект вычислений: очевидна нелинейная зависимость цены компьютера от объема памяти и реального быстродействия процессора. В силу этого параллелизация вычислений, во-первых, позволяет решать гораздо большие задачи, и во-вторых, обеспечивает примерно линейную зависимость цены параллельного компьютера с распределенной памятью от его быстродействия и объема памяти. Именно последнее обстоятельство объясняет широкую распространенность параллельных компьютеров с распределенной памятью и естественный запрос на параллельные технологии, позволяющие использовать такие компьютеры. Распределенная память подразумевает разбиение данных на блоки, обрабатываемые каждым процессором, поэтому блочность алгоритмов характерна для большинства параллельных методов и технологий [18].
Эффективность вычислительных технологий связана с разумным распределением и использованием вычислительных ресурсов, для достижения заданной точности расчетов минимальными вычислительными затратами, или, что равнозначно, для повышения точности расчетов на заданной вычислительной системе. Одним из самых мощных средств повышения эффективности технологии является ее адаптация к конкретной зада-
5
че. Адаптивность технологии может пониматься в очень широком смысле: от возможности подстраивать выполнение базовых арифметических операций к конкретной архитектуре ЭВМ, до адаптации самого вычислительного алгоритма к особенностям конкретной задачи. В данной работе рассматриваются два вида адаптивности: адаптивное построение расчетной сетки, и адаптация алгоритма решения дискретных задач.
Таким образом, ключевыми инструментами при разработке параллельных и эффективных вычислительных технологий являются блочность и адаптивность, которые проявляются на двух основных этапах решения краевых задач — построении расчетных сеток и дискретизаций, и решении порожденных ими систем.
Общепринятым подходом при разработке современных технологий решений краевых задач математической физики является их замена сеточными уравнениями, обеспечивающая приближенное решение этих задач. Одной из основных составляющих технологии построения систем сеточных уравнений является генерация расчетной сетки. Адаптивно построенные сетки позволяют достигать желаемой точности при приближении исходной краевой задачи на меньшем количестве узлов и элементов сетки. Наиболее широкое освещение вопросов адаптивного приближенного решения краевых задач можно найти в книгах Р.Ферфурта [2G0], И.Бабушки и Т.Струболиса [59), хотя некоторые ключевые моменты технологии были рассмотрены уже в монографии J1.А.Оганесяна и Л.А.Руховца [33). Вопросы генерации адаптивных сеток рассматривались в монографиях П.Джорджа и Х.Буручаки [143], В.Д.Лизейкина (193|, Г.Кэри [94|, а также в сборнике [274|. Системы сеточных уравнений могут решаться как прямыми, так и итерационными методами, однако применение прямых методов ограничено лишь линейными системами с матрицами умеренных порядков или специального вида. Хорошее представление о состоянии теории и практики итерационных методов решения сеточных уравнений можно получить из книг Д.Янга [272], Г.И.Марчука [32], Г.И.Марчука и В.И.Лсбедева [30], A.A.Самарского и Е.С.Николаева |37|, Е.Г.Дьяконова |22), В.Хакбуша [157], И.Саада [234], Дж.Деммеля |20|.
Перейдем к общему обоснованию предлагаемых в диссертационной работе технологических решений.
Использование адаптивных сеток для построения сеточных уравнений зачастую подразумевает решение неструктурированных систем, графы матриц которых не обладают никакой структурой. Аппроксимации на структурированных сетках позволяют использовать эффективные методы решения линейных систем. Так, дискретизации на прямоугольных сетках предполагают лексикографическое упорядочивание узлов и связанных с ними неизвестных в уравнении, что позволяет использовать быстрые прямые методы для решения соответствующих систем [93, 62, 259, 28, 180, 231]. Если сетка представляет
G
собой подмножество ячеек прямоугольной сетки (как в методе фиктивных компонент), то возможно такое упорядочивание узлов, что быстрые прямые методы применимы в качестве переобуславливателей [197, б]. Использование иерархических локально сгущающихся сеток позволяет использовать многосеточные технологии [40, 34, 158), основанные на интерполяции данных между сетками разных уровней. Отметим усиленные многосеточные методы [159, 183], обеспечивающие высокую скорость сходимости на частично неструктурированных сетках, получаемых двух-, трех-уровневым равномерным измельчением достатачно мелкой неструктурированной сетки. Во всех упомянутых случаях, по крайней мере для модельных задач, удается построить и обосновать либо прямой, либо быстро сходящийся итерационный метод, в котором арифметическая работа одной итерации (или всего метода) пропорциональна числу неизвестных, умноженному на полилогарифмический множитель (в случае прямых методов), что является хорошим асимптотическим результатом.
В случае полностью неструктурированных сеток использование напрямую вышеупомянутых технологий невозможно. Более того, эффективное использование этих технологий невозможно и в случае подходящих сеток, но гетерогенных (т.е. сильно меняющихся от ячейки сетки к ячейке) коэффициентов в операторе уравнения. Назовем системы уравнений, порожденные неструктурированными сетками и/или гетерогенными коэффициентами, неструктурированными. Решение неструктурированных систем -- важная составная часть вычислительных технологий, поскольку оно обеспечивает их алгебраическую компоненту, применимую для наиболее широкого класса сеток и сеточных дискретизаций. В первой главе диссертации делается обзор известных технологий и рассматриваются некоторые новые блочные параллельные технологии решения неструктурированных систем.
Неструктурированные сетки как симплициальные разбиения областей привлекательны в инженерных приложениях но разным причинам. Сложность расчетной области является одной из ключевых: ни прямоугольная, ни симплициальная грубая сетка, порождающая иерархическую последовательность сеток, зачастую не в состоянии аппроксимировать все характерные особенности границы, обладая приемлемым количеством сеточных узлов. Именно этим объясняется широкое использование генераторов неструктурированных триангуляций в двумерном случае, и тетраэдризаций в трехмерном случае. Второй причиной привлекательности неструктурированных сеток является их гибкость в адаптации. Так, например, возможности адаптации прямоугольных сеток в рамках метода фиктивных областей/компонент исчерпываются сгущением узлов вдоль координатных осей и адаптацией криволинейной границы со вторым порядком точности. Адаптивное построение анизотропных сеток па основе преобразования координат узлов пря-
7
моугольной сетки [23, 193, 274| с сохранением связности между узлами также является востребованной технологией построения анизотропных сеток, которая, однако, обладает рядом практических ограничений, особенно в трехмерном случае. Возможности адаптации локально сгущающихся иерархических триангуляций и тетраэдризаций [143], [94], [260] ограничены регулярной формой симплексов: единственная возможность управлять формой элементов — поддерживать регулярность их формы на уровне, заданном начальной неструктурированной сеткой, поэтому подстраивание сеток под особенности решения имеет смысл для решений с изотропными особенностями. Управление вытянутостью ячеек, или анизотропностью сетки, представляется возможным только для полностью нестру кту ри рова н 11 ы х сего к.
Важность анизотропной адаптивности проявляется в краевых задачах с анизотропным решением, например, благодаря наличию погранслоя или входящего двугранного угла [57, 41]. Неструктурированные симплициальпые (треугольные и тетраэдральные) конформные (с ячейками, соседствующими по целой общей грани, ребру, или узлу) сетки являются, на наш взгляд, простейшими сетками, способными обеспечить адекватную адаптацию к наиболее широкому классу решений краевых задач. Дальнейшие расширения класса сеток (неконформность, ячейки-полиэдры) не приведут к более тонким оценкам ошибок, хотя и обеспечат ббльшую технологичность аппроксимаций. Адаптивные свойства класса неструктурированных симплициальных конформных сеток рассматриваются во второй главе диссертации. Для этого вводится и исследуется оптимальная сетка как сетка, минимизирующая норму ошибки заданного оператора проектирования среди всех сеток класса с ограниченным сверху количеством элементов. Там же рассмотрены свойства и технологии (в том числе параллельные) построения аппроксимаций оптимальных сеток и некоторые сопутствующие вопросы адаптивной ^нерации подобных аппроксимаций.
Возможное расширение класса используемых сеток связано с разбиением области на подобласти, в каждой из которых сетка является конформной, а на границе между подобластями (интерфейсе) — разрывной. Такие сетки назовем нестыкующимися. Технологические преимущества использования нестыкующихся сеток проявляются в следующем: в подобластях можно использовать разные формы сеточных ячеек; можно использовать “скользящие” сетки, когда аппроксимация задачи с движущимися границами осуществляется сдвигом одних подобластей относительно других; можно использовать сетки с сильным скачком шага при переходе через границу между подобластями; можно генерировать сетку в подобластях независимо от генерации сеток в соседних подобластях; можно строить легко параллелизуемые методы решения возникающих систем уравнений, поскольку они не содержат уравнений в точках ветвления границы между подобластями,
8
что минимизирует обмен между процессорами.
Аппроксимации эллиптических уравнений на нестыкующихся сетках порождают линейные системы с седловыми матрицами. Эффективное параллельное итерационное решение подобных систем является самым сложным элементом технологии приближенного адаптивного решения краевых задач на нестыкующихся сетках [9]. В третьей главе разработаны и обоснованы два типа подобных решателей и предложен и протестирован прообраз соответствующей паралельной технологии. С математической точки зрения, ключевыми для использования нестыкующихся сеток являются условия сшивки на границе между подобластями. Использование упрощенных аналогов этих условий для стыкующихся сеток позволяет сформулировать и обосновать новый декомпозиционный алгоритм для конформных сеток и добавить в предлагаемую параллельную технологию дополнительный метод итерационного решения возникающих сеточных систем.
За последнее десятилетие смешанный метод конечных элементов приобрел большое прикладное значение, поскольку он обеспечивает консервативные аппроксимации эллиптических уравнений и одновременное приближение скалярного решения и его потоков |88]. Матрица сеточного оператора является ссдловой, однако система может быть эффективно и параллельно преобразована статической конденсацией к системе с симметричной (в случае диффузионного оператора) и положительно определенной матрицей, которая для смешанных конечных элементов Равиара-Тома наименьшего порядка [225| аналогична неконформной конечно-элементной аппроксимации Крузэ-Равиара [108]. Параллельная реализация [102] многосеточного метода для конечно-элементных аппроксимаций Крузэ-Равиара на локально сгущающихся иерархических симплициальиых сетках позволила построить эффективную параллельную адаптивную технологию [103] решения смешанных конечно-элементных систем. Таким образом, параллельные адаптивные технологии, изложенные в третьей главе, позволяют эффективно применять некоторые практически значимые аппроксимации с использованием нестыкующихся сеток или консервативных смешанных конечных элементов.
Несмотря на гибкость в адаптации и общность аппроксимаций, предоставляемые неструктурированными сетками, многие приложения до сих пор базируются на использовании прямоугольных сеток. Помимо исторических причин, доя этою существуют и технологические причины. Действительно, простота реализации, простота аппроксимаций повышенного порядка точности, наличие свойства суперсходимости при аппроксимации гладких решений, минимизация отношения числа сеточных ячеек и числа сеточных узлов, безусловно, могут обеспечить некоторые технологические преимущества прямоугольным сеткам. В четвертой главе рассматривается ряд приложений в решении краевых задач с использованием прямоугольных сеток. Все технологии, предлагаемые в этой главе, не
9
ограничены классом прямоугольных сеток, их изложение в этой главе диктуется либо простотой изложения и анализа на прямоугольных сетках, либо органичностью их представления в рамках определенных приложений. Так, параллельный двухуровневый метод Шварца для сингулярно возмущенного уравнения конвекции-диффузии с переменным конвективным полем проанализирован для конечно-разностных аппроксимаций [137|, однако его реализация возможна и для конечно-элементных аппроксимаций на неструктурированных сетках и даже песты кующихся сетках [162]. Естественным приложением этого метода является параллельное решение нестационарных уравнений Навьс-Стокса [140] с помощью проекционного метода [101, 242, 42, 198, 154], в котором необходимо решать сеточный аналог уравнения Пуассона на каждом временном шаге. Это, в свою очередь, приводит к необходимости эффективного решения последовательности больших жестких систем с разными правыми частями. Помимо использования параллельного метода фиктивных компонент, наиболее эффективного на прямоугольных сетках, предлагается использовать адаптивные механизмы выбора начального приближения для итерационных методов. Будучи вычислительно недорогими, технологически простыми и легко па-раллелезуемыми, эти механизмы позволяют существенно сократить число итераций и, следовательно, вычислительную работу. В диссертации рассматриваются три адаптивных метода выбора начального приближения в рамках приложений на прямоугольных сетках, хотя они являются не зависимыми от типа используемых сеток и аппроксимаций.
Аналогично уравнениям Навье-Стокса, рассмотренные приложения технологии параллельного решения уравнений многофазной фильтрации ограничены прямоугольными сетками, однако один из предлагаемых методов опирается не на структуру сетки, а только на физические свойства сеточных уравнений. Второй метод, используя оператор агрегирования по вертикальным столбцам сетки, использует ее прямоугольную структуру, хотя и может быть обобщен на призматические сетки. Таким образом, практически все технологии параллельного решения некоторых прикладных краевых задач, изложенные для прямоугольных сеток в четвертой главе, применимы либо для неструктурированных, либо для частично неструктурированных сеток.
Резюмируя изложенные выше соображения, сформулируем основные технологические направления, рассмотренные в работе. Это, во-первых, обзор доступных технологий решения неструктурированных систем и предложение нескольких новых блочных параллельных технологий решения этих систем; во-втпорых, введение и анализ оптимальных сеток и адаптивные параллельные технологии построения квази-оптимальных сеток, аппроксимирующих оптимальные сетки; в-третьих, рассмотрение параллельных технологий для практически значимых аппроксимаций с использованием нестыкующих-ся сеток и консервативных смешанных конечных элементов; в-четвертых, исследование
10
блочных параллельных алгоритмов для решения сингулярно-возмущенного уравнения конвекции-диффузии, трехмерных уравнений Навье-Стокса и уравнений многофазной фильтрации; в-пятых, рассмотрение параллельных адаптивных технологий эффективного выбора начального приближения для итерационного решения последовательности сеточных систем.
Перейдем к описанию излагаемых в диссертационной работе алгоритмов и теоретических результатов и обзору связанных с ними существующих методик.
Решение неструктурированных систем имеет многолетнюю историю в инженерных приложениях. Используемые технологии можно подразделить па две группы: технологии “черного ящика”, и технологии “серого ящика”.
Методы первой группы используют минимальную информацию об элементах матрицы и правой части. К ним относятся прежде всего прямые методы факторизации разреженных матриц, современные реализации которых обсуждаются п [55, 109, 155, 113], итерационные методы неполной факторизации [24],[58],[234], и итерационные алгебраические многосеточные методы [106, 240). Каждый из методов обладает рядом достоинств и недостатков: методы факторизации фактически не зависят от значений матричных элементов, однако имеют неудовлетворительную асимптотику арифметической работы на этапе инициализации, особенно для матриц, порожденных трехмерными сетками, и большие требования на компьютерную память, налагающие ограничения на порядок матриц; методы неполной факторизации не обеспечивают высокой скорости сходимости, не зависящей от порядка матриц, однако быстро инициализируются; алгебраические многосеточные методы, показывая высокую скорость сходимости и линейную арифметическую сложность как инициализации, так и решения, опираются на определенные свойства исходных матриц, которые не всегда выполняются.
Методы второй группы (“серый ящик”) используют дополнительную информацию для построения переобуславливателя. Так, метод фиктивного пространства [205, 206] нуждается в данных о сетке, порождающей сеточный оператор, и соответствующих краевых условиях, при этом порождает спектрально эквивалентные переобуславливатели с временами инициализации и решения, пропорциональными порядку матриц [121].
Можно отметить следующие тенденции, проявляющиеся в последние годы: методы неполной факторизации строят более аккуратное разложение на верхний и нижний треугольные множители [172] за счет более дорогой процедуры инициализации, однако лучшей скорости сходимости; в то же время алгебраические многосеточные методы могут нуждаться в дополнительной информации, например, предоставление матрицы в дисассемблированном виде [87, 96].
Результаты экспериментальных исследований автора [14, 121|, проведенных для раз-
11
личных последовательностей матриц увеличивающегося порядка, дали ответы на некоторые практические вопросы по перечисленным выше классам методов. Для нескольких реализаций методов точной факторизации экспериментально выведены асимптотические оценки сложности процедуры факторизации и последующего решения, а также практические ограничения на компьютерную память, для матриц с наиболее популярными структурами разреженности. Это дает возможность оценить целесообразность применения той или другой реализации метода для конкретной задачи. Показано (см. раздел 1.1), что даже наиболее точные процедуры неполной факторизации [172] чувствительны к измельчению и структуре сетки, в то время как метод фиктивного пространства в сочетании с многоуровневой технологией обеспечивает линейную арифмеческую сложность как процедуры инициализации, так и последующего решения.
В настоящей работе предложено три новых технологии “серого ящика”, опирающиеся на различные свойства решаемых сеточных эллиптических уравнений и преследующих различные цели. Это метод для аппроксимаций на неструктурированных призматических сетках, метод для сеточных задач с анизотропным тензором диффузии, и декомпозиционный метод для конечно-элементной аппроксимации диффузионного оператора с гетерогенными коэффициентами на неструктурированных сетках.
Матрицы неструктурированных систем, порождаемых призматическими сетками, обладают тензорным рангом 2, т.е. представимы в виде А\ 0Л/23 + Л/х ® . Здесь А^, Л/23
(Лх, Л/х) — матрицы жесткости и масс (лампированная) на двумерном (соотв.,одномерном) сечении призматической сетки. Для решения таких систем автором предлагается новый метод, обладающий почти линейной арифметической сложностью решения и невысокой сложностью инициализации. Метод представляет собой обобщение быстрого прямого метода [175, 259, 28, 43, 180, 232, 231] на случай неструктурированных матриц Л23 с двумерным графом и использует явный вид матриц А\, Лгз> А/х, А/23 ■ Смысл обобщения — замена прямого решения двумерных систем с матрицами Л23 + АЛ/23 с произвольным параметром А на приближенное итерационное решение с иереобуславливатслем, базирующемся на факторизации одной из трех матриц Л23+ЮА/23, Лгз+1о(Ш2з> Л2з+1500А/2з. При этом результирующий переобуславливающий оператор будет нелинейным, и метод из прямого становится быстро сходящимся итерационным (FGMR.ES [235]) с нелинейным переобуславливателем, арифметическая цена применения которого (на практике) пропорциональна порядку матрицы с полилогарифмическим множителем.
Для решения неструктурированных анизотропных систем, порождаемых симплици-альными сетками и анизотропным коэффициентом диффузии, предлагается метод пере-упорядочиваиия неизвестных и разбиения матрицы на блоки, с помощью которого простейшие блочные переобуславливатели (блочные методы Якоби, Гаусса-Зсйделя) стано-
12
вятся весьма эффективными. Алгоритм, разработанный и реализованный С.А.Горейновым с частичным участием автора, является вариантом жадного алгоритма с ограничениями, перекликающегося с алгоритмами блочного персупорядочивания PABLO [210| и TPABLO [100]. Дополнительные данные, требуемые алгоритмом переуиорядочивания и формирования блоков, — матрица весов, соответствующая ненаправленному графу матрицы системы и задающая анизотропию системы. В случае оператора диффузии в качестве матрицы весов можно взять модули внедиагональных элементов матрицы жесткости. Обладая линейной арифметической сложностью, предлагаемый алгоритм обеспечивает приемлемые скорости сходимости для матриц, порождаемых как сильной, так и слабой анизотропией диффузионного тензора, на сильно сгущающихся неструктурированных двумерных и трехмерных сетках.
Для параллельного решения неструктурированных систем, порождаемых эллиптическим оператором с гетерогенным коэффициентом диффузии на неструктурированных сетках, автором предложен декомпозиционный метод агрегирования [255, 258]. Одной из основных целей декомпозиционных алгоритмов [31, 220, 238, 275] является следующая: при заданном разбиении расчетной области на подобласти и заданных в подобластях решателях или преобуславливателях, решить общую задачу быстросходящимся итерационным методом, легко реализуемым, легко параллелезуемым, и с низкими накладными арифметическими расходами. Желательно, чтобы скорость сходимости итераций не зависела от шага сетки (Л), диаметра подобластей (Я), и других параметров задачи, например, скачков коэффициента диффузии (р).
Существуют методы [208], удовлетворяющие почти всем требованиям, однако они сложны в реализации и имеют определенные ограничения (например, на прохождение границы между подобластями и линиями скачка коэффициента). В силу этого, разумным представляется поиск методов, удовлетворяющих не всем условиям, но желаемым. Например, методы [119,120,195, 196, 221| демонстрируют слабую полилогарифмическую зависимость числа обусловленности переобусловленной матрицы жесткости от шага сетки, однако требуют точного решения подзадач, что повышает арифметические затраты, а метод [82] легко параллслезуем, использует в подобластях лишь переобуславливате-ли, однако порождает более сильную зависимость от шага сетки (H/h). Вышеупомянутые методы базируются на разбиении на непересекающиеся подобласти, причем границы раздела подобластей (интерфейсы) предполагаются гладкими и совпадающими с линиями или поверхностями скачка коэффициентов эллиптического оператора. Это означает априорное разбиение с гладкими границами, что практически не реализуемо на неструктурированных сетках для параллельных технологий типа “черный ящик”.
Второй класс методов декомпозиции использует перекрывающиеся подобласти. Со-
13
ображения параллельной эффективности требуют минимального перекрывания (/г), которое позволяет использовать простые технологии автоматического разбиения неструктурированных сеток, минимальные межпроцессорные обмены и избежать дублирования вычислений. Другое преимущество наличия перекрывания в том, что границы подобластей не обязаны совпадать со скачком коэффициента диффузии (р).
Отправной точкой при построении декомпозиционного переобуславливателя является легко параллелезуемый аддитивный метод Шварца [199], представляющий собой просто блочио-диагональную матрицу' в случае минимального перекрывания подобластей. Диагональные блоки в ней — переобуславливатели к соответствующим диагональным блокам матрицы жесткости. Для оператора диффузии число обусловленности к таким образом переобусловленной матрицы жесткости зависит от диаметра подобластей ( Г'-' 1/Я2), ширины перекрывания (~ 1/<5) и скачка коэффициента диффузии (~ шахр/шіпр). Если снабдить блочно-диагональный иереобуславливатель коррекцией на каркасном подпространстве, оценка числа обусловленности улучшится то С(р) (1 + у) [92], а в случае гладкого коэффициента р ее можно довести до С (1 + у) [118, 238].
Здесь и далее С (г) обозначает константу, зависящую от г, но не зависящую от остальных параметров. Кроме этого, в дальнейшем с, С (с индексами и без индексов) будут обозначать некоторые положительные константы, не зависящие от параметров задачи, а выражение А ~ В будет обозначать спектральную эквивалентность матриц А и В с константами, не зависящими от размеров матриц, или приближенное равенство или пропорциональность величин Л и Б.
Отметим, что зависимость к от р не является критической, если коэффициент р(х) гладкий в больших подобластях и применяется метод сопряженных градиентов (СГ). Как показано в [150], при сильных скачках число итераций СГ лишь незначительно возрастает на величину, зависящую от геометрической структуры скачков р[х). Однако этот результат не применим для других итерационных методов, а также для гетерогенного коэффициента р{х).
В настоящей работе предлагается метод на основе аддитивного метода Шварца, впервые обеспечивающий теоретическую независимость к от гетерогенного коэффициента диффузии р{х) в зоне перекрывания и оценку к < С(1 + у) (Теорема 1.3). В доказательстве теоремы используется гладкость р(х) в подобластях вне зоны перекрывания, хотя это не нужно на практике. Важным практическим достоинством метода является его независимость от гетерогенности р(х) в зоне перекрывания, что позволяет не координировать разрезание на подобласти с линией скачка. Суть метода — специфическое каркасное подпространство, получаемое агрегированием неизвестных внутри подобластей. Агрегирование неизвестных — весьма востребованная технология при разработке числен-
14
ных методов [86, 164, 253]. Предлагаемый метод, как и метод [164], использует негладкие базисные функции каркасного простраснтва, что отличает его от работ [86, 253). В отличие от [164], наше каркасное пространство является гораздо большим, поскольку оно включает в себя базисные функции на мелкой сетке, которые не равны нулю в зоне перекрывания. С одной стороны, это делает каркасную (агрегированную) задачу более сложной для решения, с другой стороны, эго позволяет исключить зависимость к, от р(х).
Параллелизация решения агрегированной задачи зависит от конкретного приложения. В случае двумерных сеток, уменьшение размерности агрегированной матрицы по отношению к исходной размерности настолько существенно (Лг —» JV1/2), что позволяет использовать прямой метод (факторизации) на каждом процессоре [78, 79). В случае трехмерных сеток каркасная задача остается достаточно большой (понижение размерности N —* Лг2/3), поэтому ее приближенное решение осуществляется с помощью блочного метода верхней последовательной релаксации BSOR или его симметризованного аналога. Эффективность подобного решения мотивируется тем, что арифметическая цена одной итерации BSOR существенно ниже умножения на исходную матрицу жесткости, а жесткость агрегированной матрицы существенно ниже жесткости исходной матрицы, что порождает высокую скорость сходимости BSOR. Легкая параллелезуемость метода является его привлекательной чертой, также как простота его реализации на неструктурированных сетках [187,188, 184). По сути дела, метод является методом “серого ящика”, поскольку помимо элементов исходной матрицы жесткости, требует только разбиение степеней свободы на неиересекающиеся подмножества, обеспечиваемые, например, любым алгоритмом разбиения графа. Отметим, что по формальным признакам предлагаемый алгоритм относится к гибридным методам [194, 238], поскольку его аддитивная структура на уровне подобластей сочетается с мультипликативной процедурой коррекции в каркасном пространстве.
Доступные методы решения неструктурированных систем позволяют использовать полностью неструктурированные симплициальные сетки в адаптивных технологиях приближенного решения краевых задач, которые, в свою очередь, открывают путь к анизотропной адаптации, рассмотренной в главе второй. Как уже отмечалось выше, именно возможность анизотропной адаптации расширяет границы современных адаптивных технологий, поскольку позволяет эффективно аппроксимировать анизотропные решения. В ряде работ [111, 110, 112, 226], появившихся на рубеже 90-х годов, было показано, что треугольники с тупыми и острыми углами, вытянутые вдоль направления минимальной второй производной некоторой функции, могут быть наилучшими элементами для минимизации ошибки интерполяции. При этом степень вытянутости треугольников и
15
их малости зависит от матрицы вторых производных (гессиана) функции. На практике управление вытянутостыо элементов задавалось метрикой на основе гессиана функции или его приближения |90, 117, 77, 213, 134]. Предпринимались попытки обобщений на адаптацию к вектор-функциям [116]. Однако первое теоретическое обоснование анизотропной адаптации появилось в работах [11, 53], где были доказаны асимптотические аннроксимационные свойства оптимальных симплициальных сеток и их приближений, квази-оптимальных сеток, которые можно строить на практике.
Технология адаптивного приближенного решения на основе восстановления гессиана сеточного решения породила ряд теоретических вопросов. На некоторые из них даны ответы во второй главе в виде теоретических результатов автора. Так, доказано существование оптимальных сеток при разумных предположениях на непрерывность ошибки интерполирования от координат сеточных узлов и не увеличении этой ошибки при иерархическом измельчении треугольников [12] (Теорема 2.3). Выведены асимптотические оценки ошибки в норме L0с для оптимальных сеток, в двумерном [11] и трехмерном [53] случаях, предложен их объединенный анализ [10] (Теорема 2.4), а в Теореме 2.7 приведены обобщения (совместно с А.Агузалом) на случай норм Lp, 0 < р < -foc [10]. Рассмотрены свойства приближений оптимальных сеток, которые являются квазиравномерными в метрике, порожденной гессианом функции, и доказана Теорема 2.8 о том, что такие приближения являются квази-оитимальными сетками, ошибка интерполяции на которых асимптотически имеет такую же зависимость от числа симплексов сетки, что и на оптимальных сетках [11, 53].
Восстановление гессиана сеточной функции — важная часть адаптивной технологии. По сути дела, необходимо вычислить матрицу вторых производных у сеточного решения, что на практике осуществляется в рамках конечно-элементных аппроксимаций (за счет перебрасывания одной производной на пробную функцию в формуле Грина). Подобное восстановление не обеспечивает поточечную сходимость восстановленного гессиана к дифференциальному для функций с особенностями, поэтому предположение о поточечной аппроксимации, используемое в излагаемой теории, может не выполняться. С учетом этого автором был предчожен новый метод восстановления [54] гессиана у функций с особенностями, который обеспечивает локальную аппроксимацию компонент дифференциального гессиана в L\ норме, что имеет смысл для функций из Wf. Здесь и далее W* обозначает соболевское пространство вещественных функций, у которых р-е степени производных порядка не выше q интегрируемы в рассматриваемой области. Отметим, что решения большинства эллиптических краевых задач принадлежат пространству W? в подобластях, где коэффициенты дифференциального оператора — гладкие функции [151]. Это открывает путь к локальной аппроксимации гессиана сеточных функций с
16
особенностями. Доказанная автором Теорема 2.15 о локальной сходимости восстановленного гессиана к дифференциальному — первый теоретический результат для функций с особенностями и анизотропных сеток.
Генерация квази-равномерных сеток в заданной непрерывной метрике — ключевой элемент рассматриваемой адаптивной технологии [90, 117, 77, 213,134]. В работе предлагается совместный алгоритм автора и К.Н.Липникова генерации тетраэдральных сеток, являющийся обобщением двумерного алгоритма [90] и представляющий собой последовательность локальных модификаций сетки для достижения ее квази-равномерности.
Нужно отметить, что теоретического обоснования, почему сходится адаптивный алгоритм построения квази-оптимальиых сеток для функций с особенностями, нет. Однако в Теореме 2.18 автору удалось построить оценки, показывающие возможность уменьшения нормы ошибки при интерполяции гладких функций [11, 53|. Вопрос теоретического обоснования в общем случае не решен, так же как и вопрос апостериорных оценок ошибки в рамках данной технологии, хотя для случая изотропного сгущения предложен конструктивный метод построения таких оценок [63], а для некоторых краевых задач и некоторых типов анизотропных сеток предложены оценки [174]. Альтернативная адаптивная технология [260, 59, 161], основанная на локальном измельчении/огрублении сетки на основе выравнивания аиостериорно оцененной ошибки, естественным образом интегрирует оценку ошибки, однако использует иерахические локально измельчающиеся сетки, элементы которых наследуют форму начальной сетки.
Общий адаптивный алгоритм весьма технологичен, поскольку его структура предполагает выполнение четырех совершенно независящих друг от друга шагов:
1. шаг инициализации: построение начальной сетки;
2. нахождение сеточного решения (непрерывной кусочно-линейной функции);
3. восстановление сеточного гессиана;
4. генерация сеток, квази-равномерных в заданной метрике.
Ключевым свойством алгоритма является полная автономность от пользователя шагов 3 и 4, реализуемых по принципу “черных ящиков”, а также минимизация обмена данными между сетками (используются только данные о сетке и сеточном решении). Удобство использования метрики заключается в том, что ее легко модифицировать, тем самым управляя процессом адаптации и свойствами симплициальной сетки. Например, можно фокусировать измельчение сетки в зонах повышенного интереса и ослаблять концентрацию узлов сетки в зонах пониженного интереса. Аналогичные цели типичны для целевых
17
адаптивных технологий |219]. Кроме того, можно управлять степенью вытянутости симплексов, если используемый метод аппроксимации не может использовать анизотропные сетки. В Теореме 2.19 автором показано, как влияет модификация метрики на ошибку интерполяции, через сравнение ошибок на квази-оптимальных сетках и сеток с управляемой адаптацией [13, 190] ; там же рассмотрено несколько примеров управления.
Восстановление гессиана сеточной функции нашло свое применение и в построении поверхности более высокого порядка на основе кусочно-линейных поверхностей. Актуальность этой проблемы вызвана тем, что современные системы САПР порождают границы расчетной области в виде треугольных сеток в пространстве. Недостаточное разрешение поверхности границы зачастую ухудшает работу адаптивных методов, поскольку дискретная граница сама по себе порождает дополнительную ошибку аппроксимации, не уменьшаемую за счет адаптации внутри области. Точность аппроксимации кусочногладкой поверхности можно существенно повысить за счет восстановления поверхности более высокого порядка, чем заданная кусочно-линейная дискретизация. Существует несколько методов такого восстановления [142, 200, 203, 204|: в одних [200, 204) параметризация поверхности (а также другие характеристики поверхности) вычисляется из производных функций, задающих параметризацию; в других [142. 200) дискретная кусочно-линейная поверхность аппроксимируется кусочно-квадратичной поверхностью методом наименьших квадратов. Предлагаемый в диссертации метод использует технологию вычисления приближенного гессиана кусочно-квадратичной функции, задающей восстанавливаемую поверхность. Гессиан вычисляется на основе обобщенной формулировки, но аналогии с методом конечных элементов. Предлагаемый метод точен для квадратичных поверхностей и позволяет повысить порядок аппроксимации кусочно-гладкой границы, если ее куски представимы функциями с непрерывными третьими производными. В Теореме 2.22 доказаны оценки аппроксимации для кусочно-гладких границ общего вида.
Приближенное решение трехмерных краевых задач даже на адаптивных сетках требует весьма большою числа симплексов, поэтому вопросы параллельной адаптации наиболее актуальны для трехмерных задач. Генерация трехмерной сетки, квази-равномерной в заданной метрике, является весьма трудоемкой процедурой, и может занимать больше времени, чем получение сеточною решения. Поэтому ускорение приближенного адаптивною решения требует лараллелизации как решения сеточных систем, рассмотренной в главе первой, так и генерации трехмерных сеток. Предлагаемый метод параллельной генерации основан на разрезании сетки на подобласти-слои с чередующимися направлениями нарезки, независимой генерации сеток в слоях с замороженными границами, и склейке подсеток в глобальную сетку [187, 189, 191). Численные расчеты для некото-
18
рых модельных задач математической физики и гидродинамики [187, 188] показали параллельную эффективность предлагаемой технологии адаптивного решения, выявив при этом интересную особенность параллельной генерации: если сетки почти установились в ходе адаптации, а число локальных модификаций сетки достаточно велико, то наблюдается сверхлинейное параллельное ускорение процесса генерации сетки [187, 189, 191].
Разбиение расчетной области на подобласти и использование в них конформных сеток, не согласованных друг с другом на границах подобластей, порождает нестыкую-щиеся сетки, впервые проанализированные в [70]. Технологические преимущества таких сеток были перечислены выше. Анализ аинроксимациопиых свойств нестыкующихся сеток в рамках метода мортарных конечных элементов и/или макро-гибридных постановок представлен в работах [52, 67, 68, 70,169, 73] и сводится к утверждению, что при корректной трактовке условий сшивки на интерфейсе асимптотические свойства энергетической нормы ошибки аналогичны результатам для конформных сеток.
В этой связи уместно подчеркнуть исключительную важность корректности условий сшивки решения на интерфейсе между подобластями, которые неразрывно связаны со свойствами операторов Пуанкаре-Стеклова. На функциональном уровне условия сшивки и свойства операторов Пуанкаре-Стеклова в приложении к методам декомпозиции области были впервые рассмотрены в монографиях [1, 31], а также в работах [2, 50, 51]. Общность полученных результатов породила ряд композиционных методов для задач с различными операторами в ненерекрывающихся подобластях [31, 220]. Однако эта методология не переносится на случай несты кующихся сеток и на случай многих подобластей с произвольными скачками коэффициентов. Эффективные для этих случаев алгоритмы базируются на специальных интерфейсных переобуславливателях, строящихся на сеточном, а не дифференциальном уровне.
Системы сеточных уравнений, порождаемые аппроксимациями на нестыкующихся сетках, являются седловыми. Начиная с середины девяностых годов, эффективному решению этих систем было посвящено много работ [39, 69, 44, 47, 46, 178, 179, 239, 160, 128, 127, 122, 181, 256, 80, 148, 271, 268]. Эти методы можно условно разделить на три группы: многосеточпыс методы, использующие иерархию сеток как в подобластях, так и на интерфейсах между подобластями [80, 148, 271, 268], декомпозиционные методы, строящие интерфейсные переобуславливатели на основе приближенного обращения дополнения Шура на разрежающихся сетках [44, 46, 178, 179, 163, 160, 128, 127, 122], а также декомпозиционные интерфейсные переобуславливатели [47, 239, 181, 256]. Достоинством методов первой группы является независимость скорости сходимости от шага сетки и асимптотическая оптимальность арифметической работы, а недостатком — требование иерархичности сеток; достоинством второй группы также является незави-
19
симость скорости сходимости от шага сетки, причем технология может как опираться [44, 46, 178, 179, 160, 128, 127, 49], так и не опираться [122] на иерархичность сетки, а недостатком - зависимость арифметической работы от структуры сгущения исходной сетки и достаточно трудоемкое применение интерфейсного иереобуславливателя; достоинством третьей группы [239, 181, 256] является удобство реализации (технологичность) и параллелизации, а недостатком — возможная незначительная зависимость скорости сходимости от шага сетки. В третьей главе автором рассмотрены методы второй и третьей группы с точки зрения их применения в адаптивном решении краевых задач. В Лемме 3.5 и Теореме 3.7 обоснована независимость скорости сходимости итерационных алгоритмов от шага сетки (методы второй группы), а также числа подобластей и величины коэффициентов диффузии и реакции для уравнений реакции-диффузии (методы обеих групп). Построены параллельные адаптивные алгоритмы и на численных примерах проиллюстрированы их основные свойства.
Аппроксимации на нестыкующихся сетках являются неконформными, поскольку используемые конечно-элементные пространства порождают разрывные на интерфейсах решения, которые не принадлежат стандартному пространству обобщенных решений Wl(Q). Специфические варианты подобных аппроксимаций удобно применять для декомпозиционных алгоритмов и на стыкующихся на интерфейсе сетках. Действительно, в качестве условий сшивки на интерфейсе между стыкующимися сетками можно потребовать поузловую непрерывность сеточного решения и его потока на интерфейсе [131] и сформулировать и обосновать эффективные алгоритмы итерационного решения получаемых седловых систем [252]. С учетом конформности сетки можно показать, что полученное решение удовлетворяет стандартной конечно-элементной системе на стыкующихся сетках. Для некоторых случаев разбиения области на подобласти удается использовать нормировку сеточных функций в пространстве следов [205, 207] на интерфейсах в качестве спектрально эквивалентного переобуславливателя, при этом эффективность его применения достигается технологией мозаично-скелетонной аппроксимации [249, 251]. Основная идея состоит в аппроксимации плотной матрицы, возникающей из нормализации следа, некоторой разреженной матрицей, которую легко умножать на вектор. Дня двумерного метода подструктур такая попытка предпринималась в [171]. В работе [252] рассматривается интерфейсное переобуславливание дуального дополнения но Шуру для множителей Лагранжа, что оказывается гораздо проще даже в трехмерном случае. Предлагаемый нереобуславливатель может быть реализован как “серый ящик”, требующий на входе коэффициенты задачи и интерфейсную сетку, поэтому напоминает быстрые муль-типольные методы [66].
Другим источником неконформности метода даже на конформных сетках я пл я ют-
20
ся конечно-элементные пространства, базисные функции которых не принадлежат пространству У/\ (П). Практическая значимость простейшего из них, Крузэ-Равиара [108], определяется тем обстоятельством, что порождаемые конечно-элементные матрицы имеют тот же вид, что и статически конденсированные матрицы смешанных конечных элементов Равиара-Тома наименьшего порядка [225]. обеспечивающие локально консервативные аппроксимации эллиптических уравнений на неструктурированных сетках и одновременное вычисление скалярного решения и его потока. Параллельная реализация [102] многосеточного метода для конечно-элементных аппроксимаций Крузэ-Равиара на локально сгущающихся иерархических симплициальных сетках позволила построить эффективную параллельную технологию [103] решения смешанных конечно-элементных систем:
1. на входе дается линейная смешанная конечно-элементная система в дисассемблированном (по ячейкам сетки) виде, а также координаты вершин симплексов и граф связности вершин;
2. с использованием геометрических данных система преобразуется локально по ячейкам в гибридную систему за счет добавления множителей Лагранжа на грани симплексов;
3. в расширенной системе локально по ячейкам исключаются скалярные неизвестные внутри симплексов и потоки на гранях симплексов, порождая симметричную положительно определенную разреженную матрицу;
4. итерационно решается разреженная конденсированная система для множителей Лагранжа;
5. восстанавливаются локально по ячейкам скалярные неизвестные внутри симплексов и потоки на гранях симплексов.
Ключевым наблюдением является то, что все этапы, кроме четвертого, арифметически дешевы и легко параллелезуемы, в силу локальности действий. Параллельное решение линейной системы, как наиболее трудоемкий этап всей цепочки, осуществляется быстрос-ходящимся многосеточным методом [102, 103, 16], реализация которого позволила сформировать всю технологическую цепочку.
^ Таким образом, алгоритмы, изложенные в третьей главе, открывают путь к исиоль-
г зованию параллельных адаптивных технологий для некоторых практически значимых неконформных аппроксимаций.
21
Алгоритмы четвертой главы объединяет применение и тестирование в приложениях на прямоугольных сетках, хотя использование ни одного из методов не ограничено классом прямоугольных сеток. Рассматриваются две основные задачи гидродинамики: уравнения Навье-Стокса и задача многофазной фильтрации. Являясь нелинейными нестационарными уравнениями, они допускают ряд технологий получения решения [216, 132, 156, 243, 198, 145, 3, 26, 4]. Здесь мы ограничимся двумя наиболее востребованными методами. Во-первых, это полностью неявные аппроксимации по времени, обеспечивающие абсолютную устойчивость к шагу по времени и порождающие на каждом временном шаге систему нелинейных уравнений, которую необходимо решить. Во-вторых, это проекционный алгоритм для уравнений Навье-Стокса, сводящийся к решению одной или нескольких линейных систем, с нежесткими ограничениями на шаг по времени [198, 154, 248]. Преимуществом первого метода является возможность управлять шагом по времени на основе внешних данных (правой части, граничных условий), а не внутренней динамики системы, что весьма привлекательно в инженерных приложениях. Преимущества второго метода — в упрощении решаемых систем уравнений и существенном ускорении их решения на каждом шаге, что обеспечивает этим методам наибольшую скорость расчетов [248].
Проекционные алгоритмы были предложены в работах [101, 242, 42] и их смысл сводился к двухшаговой процедуре: с помощью уравнения моментов предсказать поле скоростей на очередном шаге по времени и спроектировать это поле в пространство соле-ноидальных функций. Предсказание возможно за счет явной аппроксимации но времени уравнения моментов [101] (при этом налагаются существенные ограничения на временной шаг), за счет метода характеристик [216] (параллельная реализация которого очень сложна [45]), за счет полунеявной аппроксимации по времени уравнения моментов [198, 170], чье единственное отличие от неявной аппроксимации — линеаризация нелинейного конвективного члена вида (ufc+1 • V)ufc+1 —♦ (ufc • V)ufc+1. Последний подход предполагает решение линеаризованного уравнения моментов, представляющего собой в трехмерном случае три сингулярно возмущенных уравнения реакции-конвекции-диффузии для каждой из компонент скорости. Именно это приложение потребовало разработки эффективною параллельною метода решения сингулярно возмущенного уравнения конвекции-диффузии.
Сингулярно возмущенные операторы предоставляют дополнительные возможности для эффективной параллелизации решателей на основе методов декомпозиции с перекрывающимися подобластями. В применении к параболическим уравнениям наличие сингулярно возмущенного члена нулевого порядка привело к ряду родственных методов [176, 177, 74], основанных на экспоненциальном убывании сеточной функции Грина.
22
Предлагаемый алгоритм базируется на важном свойстве сингулярно возмущенного уравнения конвекции-диффузии: возмущения решения, вызванные локальным возмущением краевого условия, распространяются анизотропно. В случае постоянного вектора переноса точечное возмущение распространяется только вниз по потоку, быстро убывая в поперечном направлении и вверх по потоку. Это свойство может быть переформулировано в терминах анизотропного поведения сеточной функции Грина |165, 211,137), которое может быть использовано при построении как декомпозиционных [222, 137], так и многосеточных методов [35, 212|.
На основе этих свойств оператора конвекции-диффузии конструируется параллельный двухуровневый метод Шварца [137, 141], быстро сходящийся даже для малых налеганий между подобластями. На первом уровне область разбивается на налегающие полосы (слои), перпендикулярные доминирующему направлению переноса, и определяются итерации Шварца в направлении вниз но потоку. На втором уровне каждая подобласть-полоса разбивается на налегающие подобласти-квадраты и задаются несколько итераций Шварца между квадратами с четными и нечетными индексами. Естественный параллелизм методу дает именно второй уровень, поскольку каждая подобласть-квадрат может обрабатываться своим процессором. Если вектор переноса сильно отклоняется от заданного направления (например, вследствие завихрений), разбиение первого уровня должно быть адаптировано к поведению вектора.
Рассмотренный метод является первым итерационным методом для оператора конвекции диффузии с плоско-параллельным нолем переноса, чья скорость сходимости теоретически ограничена сверху константой, не зависящей от малости коэффициента диффузии е и шага сетки к} если е < к, см. Теорему 4.1, впервые доказанную в [136]. Метод обобщен автором на случай нолей переноса с локальными завихренностями, при этом в Теореме
4.6 автором доказано, что итерационная скорость сходимости остается не зависящей от малости е и к при разумных предположениях на разбиение на подобласти. Арифметическая цена одной итерации этого метода (как и его инициализации) пропорциональна числу неизвестных в системе, поскольку представляет собой набор линейных систем с матрицами ограниченного порядка (в двумерном случае) или ленточными матрицами с малой шириной ленты (в трехмерном случае). Более того, метод легко иараллелезуем. Отметим, что предложенный метод, будучи первым проанализированным декомпозиционным алгоритмом, универсальным по отношению к сеточному числу Пекле, получил обобщения на нелинейные задачи [75, 76]. Добавление в уравнение сингулярно возмущенного члена нулевого порядка (реакции) только улучшает свойства метода, поскольку позволяет избегать адаптивного разбиения для поля переноса с завихрениями, сохраняя высокую скорость сходимости |138). Среди методов декомпозиции на неперскрывающи-
23