Методы декомпозиции области для решения нестационарных задач увлажнения грунта тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Захаров, Петр Егорович

• Захаров, Петр Егорович
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Захаров, Петр Егорович

Содержание

Введение

1 Методы декомпозиции без налегания подобластей

1.1 Модельная задача

1.1.1 Постановка задачи

1.1.2 Аппроксимация по пространству

1.1.3 Схема с весами

1.1.4 Декомпозиция области

1.2 Декомпозиция явной схемы

1.2.1 Параллельный алгоритм

1.2.2 Сложность алгоритма

1.2.3 Эффективность параллельного алгоритма

1.3 Явно-неявные схемы

1.3.1 Явно-неявная схема с коррекцией

1.3.2 Факторизованная схема

1.3.3 Сходимость

1.3.4 Численные эксперименты

2 Методы декомпозиции с налеганием подобластей

2.1 Модельная задача

2.1.1 Постановка задачи

2.1.2 Аппроксимация по пространству

2.1.3 Схема с весами

2.1.4 Операторы декомпозиции

2.2 Двухкомпонентная декомпозиция

2.2.1 Схема Дугласа-Рэкфорда

2.2.2 Факторизованные схемы

2.2.3 Сходимость факторизованных схем

2.2.4 Точность факторизованных схем

2.2.5 Симметричная схема покомпонентного расщепления

2.2.6 Факторизованная схема с другими операторами

2.3 Многокомпонентная декомпозиция

2.3.1 Схема покомпонентного расщепления

2.3.2 Аддитивно-усредненные схемы

2.3.3 Векторные аддитивные схемы

2.3.4 Асинхронные векторные схемы

3 Моделирование увлажнения грунта

3.1 Двумерная задача увлажнения плотины

3.1.1 Математическая модель

3.1.2 Дискретизация

3.1.3 Вычислительная реализация

3.1.4 Численное сравнение

3.2 Трехмерная задача увлажнения плотины

3.2.1 Математическая модель

3.2.2 Дискретизация

3.2.3 Вычислительная реализация

3.2.4 Численные результаты

3.3 Схема декомпозиции области для задачи увлажнения

3.3.1 Схема декомпозиции

3.3.2 Вариационная постановка

3.3.3 Численное сравнение

Заключение

Литература

Введение диссертации (часть автореферата) на тему «Методы декомпозиции области для решения нестационарных задач увлажнения грунта»

Введение

В настоящее время сложилась новая технология научных исследований, которая базируется на исследовании прикладных математических моделей с помощью вычислительных средств (компьютеры и численные методы) [9, 17,32, 42,49,50,71,92]. Численное моделирование позволяет описать свойств исследуемого объекта с необходимой полнотой и детальностью на основе адекватных математических моделей.

Содержательные математические модели включают системы связанных друг с другом нестационарных нелинейных уравнений с частными производными, системы обыкновенных дифференциальных и алгебраических уравнений. Разработка вычислительных алгоритмов для прикладного математического моделирования базируется на глубокой теоретической и методической проработкой численных методов для базовых задач [23,51,61,68,75]. Для аппроксимации по пространству используются все основные технологии, связанные с разностной, конечно-объемной и конечно-элементной аппроксимацией [40,77,108]. Необходимо только иметь в виду, что, обычно, приходится решать задачи в многомерных областях со сложной геометрией. При приближенном решении нестационарных задач основное внимание должно уделяться разностным методам [24,36,46,52,54,57,62,72,78,84,93,95]. Проблемы применения конечно-элементных аппроксимаций при решении нестационарных задач обсуждаются в [47,96].

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

• построение дискретных аналогов, наследующих основные свойства дифференциальной задачи;

• исследование устойчивости (корректности) разностной задачи;

• эффективная вычислительная реализация на современной вычислительной технике.

Исследование разностных схем для нестационарных задач базируется на использовании общей теории устойчивости (корректности) операторно-разностных

схем [10,24,29,80]. Основные результаты связаны с точными (совпадающие необходимые и достаточные) условиями устойчивости для широкого класса двух- и трехслойных разностных схем в конечномерных гильбертовых пространствах. Конструктивность теории обеспечивается тем, что эти условия формулируются в виде легко проверяемых неравенств для операторов.

Расчетно-теоретическое исследование прикладных проблем требует решения задач в сложных многомерных областях, использования достаточно подробных расчетных сеток. Для нахождения приближенного решения приходится решать большие системы линейных или нелинейных алгебраических уравнений. С этой целью используются итерационные методы сеточных уравнений [24,30,79]. Особое внимание уделяется методам решения задач с несамосопряженными операторами.

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

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

мы ориентируемся на использование стандартных неявных аппроксимаций по времени и решение соответствующих сеточных задач на новом временном слое с использованием тех или иных вариантов методов декомпозиции области для стационарных задач. Учет особенностей нестационарных задач (смотри, например, реализацию на основе метода Шварца [38,39,48]) приводит к оптимальным итерационным методам декомпозиции области, когда число итераций не зависит от шагов дискретизации по времени и пространству.

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

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

• способу декомпозиции области,

• по выбору операторов декомпозиции (обменных граничных условий),

• используемой схеме расщепления.

При решении краевых задач для дифференциальных уравнений с частными

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

р

па = паидпа, а = 1,2 (1)

а=1

с налеганием подобластей = 0,а П Пр ф 0) и методы без налегания подобластей (ПаР = 0) [76,97].

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

С декомпозицией области (1) мы можем сопоставить соответствующее аддитивное представление оператора задачи

р а=1

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

При декомпозиции (1) с отдельной подобластью £1а свяжем функцию г}а(х), а = 1,2, ...,р такую, что

| > 0, х <Е С1а,

Г)а(х) = < а = 1,2 ,...,р, (3)

^ 0, х ф

причем

р

Х>а(®) = 1, хеП. (4)

а=1

Рассмотрим характерный пример. Пусть, например, оператор задачи А есть оператор диффузии:

Л = — сНу к(х) grad, х £ О,. (5)

Тогда для операторов декомпозиции можно задать следующим три основные конструкции:

Аа = 77« Л, (6)

А* = - к{х)г]а(х) grad, (7)

Лп=Лг](у, а = 1,2,...,р. (8)

Эта общая технология используется начиная с работ [20,22,66] (декомпозиция (7)), [7] (декомпозиция (6)-(8)), результаты более поздних работ суммированы в книгах [31,80]. Различные варианты операторов декомпозиции соответствуют использованию различных обменных граничных условий и обеспечивают сходимость приближенного решения в разных пространствах сеточных функций. Отдельного внимания заслуживают вопросы построения операторов декомпозиции при решении нестационарных задач с несамосопряженными операторами [6,27,82].

При построении регионально-аддитивных схем (схем декомпозиции области) для решения нестационарных задач на основе расщепления (2) используются различные схемы расщепления. В теории аддитивных операторно-разностных схем, схем расщепления [24,31,35,69] необходимо выделить случай простейшего двухкомпонентного расщепления. В этом простейшем случае строятся безусловно устойчивые факторизованные схемы расщепления, к которым, в частности, относятся классические схемы переменных направлений, схемы предиктор-корректор. Двухкомпонентные регионально-аддитивные схемы построены и исследованы в работах [7,8,66,67], а также в отмеченных выше работах [6,27,82] для задач конвекции-диффузии.

Для вычислительной практики, в том числе и при применении методов декомпозиции области, большой интерес представляет расщепление оператора задачи на сумму трех и более попарно некоммутативных операторов (р > 2 в (2)). Классические [24,35,69] схемы многокомпонентного расщепления строятся на основе понятия суммарной аппроксимации. Аддитивно-усредненные схемы суммарной аппроксимации [18,31] более явно ориентированы на параллельную организа-

цию вычислений. Регионально-аддитивные схемы покомпонентного расщепления исследуются в работе [12]. Вариант двухкомпонентного расщепления при использовании схемы Кранка-Николсона для отдельных подзадач при минимальном наложении и операторах декомпозиции (7) рассмотрен в статье [41].

В настоящее время получили распространение схемы полной аппроксимации для общего многокомпонентного расщепления. В этой связи отметим регуляри-зованные аддитивные схемы [28], в которых условия устойчивости достигаются за счет возмущений операторов разностной схемы. В векторных аддитивных схемах [1,5]. вместо одного уравнения решается система однотипных уравнений. Такие схемы строятся также для эволюционных уравнений второго порядка [2,81]. Векторные регионально-аддитивные схемы исследуются в работах [11,26]. Отметим также работу [99], в которой предложены более общие регуляризованные схемы декомпозиции области с различными конструкциями для операторов расщепления и для операторов сеточной задачи на новом временном слое.

Отдельного упоминания заслуживают явные схемы для нестационарных задач математической физики. Явные схемы имеют несомненные преимущества перед неявными в плане вычислительной реализации. Особенно это достоинство сильно проявляется при построении вычислительных алгоритмов, которые ориентированы на вычислительные системы параллельной архитектуры. Хорошо также известен основной недостаток явных схем, который связан с жесткими ограничениями на допустимый шаг по времени. Для параболических уравнений условие устойчивости [24,29] имеет вид г < то = 0(к2), где т — шаг сетки по времени, а к — шаг сетки по пространству.

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

ся проблемы с аппроксимацией. Дополнительный член погрешности для таких условно сходящимися схем есть 0(т2/гГ2).

Впервые явные схемы бегущего счета для параболических уравнений второго порядка предложены в книге [33]. С учетом организации явно-неявной неоднородности аппроксимаций по времени эти схемы названы автором asymmetric schemes. Следующий принципиальный результат получен A.A. Самарским в работе [25], где эти схемы рассматриваются как факторизованные операторно-разностные схемы с аддитивным расщеплением оператора задачи (матрицы) на сопряженные друг другу слагаемые. Применительно к системам обыкновенных дифференциальных уравнений мы имеем расщепление матрицы на нижнюю и верхнюю треугольные матрицы — ПТМ (попеременно-треугольный метод). При решении стационарных задач на основе таких расщеплений мы имеем попеременно-треугольный итерационный метод [30].

Более поздний этап использования явных схем бегущего счета при решении параболических краевых задач можно связать с работами [43,44]. С учетом возможностей организации вычислений выделяются явные схемы Group Explicit (Alternating Group Explicit) method. Активно (смотри, например, [105,106]) обсуждаются возможности рассматриваемых явных схем при построении вычислительных алгоритмов решения краевых задач для параболических уравнений на параллельных компьютерах. Отметим также работы по использованию явных схем бегущего счета для нестационарных задач конвекции-диффузии [45,102].

Среди других методов декомпозиции области при решении краевой задачи для параболических уравнений отметим явно-неявные методы, которые с небольшими вариациями рассматриваются во многих работах (смотри, например, [21,58-60,94,98,104,107]). Декомпозиция области проводится без наложения подобластей, и переход на новый временной слой организуется следующим образом. Сначала с использованием явной схемы делается прогноз приближенного решения на общих границах подобластей, после этого с этими граничными условиями находится приближенное решение внутри отдельных подобластей, на

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

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

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

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

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

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

Автор выражает глубокую благодарность научному руководителю, доктору физико-математических наук, профессору Вабищевичу Петру Николаевичу за помощь, оказанную при работе над диссертацией и коллегам из Центра вычислительных технологий СВФУ за полезные советы и предоставленные информационные материалы.

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

Глава 1

Методы декомпозиции без налегания подобластей

Рассматриваются алгоритмы декомпозиции области без налегания подобластей для решения нестационарных задач. На примере декомпозиции явной схемы исследуется вычислительная и коммуникационная сложность алгоритма. Сравниваются различные алгоритмы для схем декомпозиции области без налегания. Также аналитически и численно исследуется точность класса явно-неявных схем [19].

1.1 Модельная задача

Формулируется модельная задача Коши для параболического уравнения второго порядка. Определяется разностная аппроксимация по пространству и времени. Строится стандартная двухслойная схема с весами как отправная точка для рассматриваемой задачи.

1.1.1 Постановка задачи

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

хеп, 0 < £ < Т, (1.1)

а=\ 01

где к{х) > к > 0,х е П. Уравнение (1.1) дополняется однородным граничным условием Дирихле

и{х, = О, хедп, О <КТ. (1.2)

Также задается начальное условие

и(х,0) = и°(х), хеП. 13

(1.3)

Итак, рассматривается нестационарная задача диффузии (1.1)-(1.3). Вместо (1.1) и (1.2) будем использовать дифференциально-операторную запись

(111

— + Ли = /(*), 0 < ;£ < Т, (1.4)

где оператор

«=1 4 '

определен на множестве функций и{х>€), удовлетворяющих граничным условиям (1.2). Рассматривается задача Коши для эволюционного уравнения (1.4) с начальным условием

■и(О) = и0. (1.5)

Для множества функций, удовлетворяющих (1.2), определим Гильбертово пространство % = £2^) со скалярным произведением и нормой

(и:у) = / и(х)у(х)с1х, ||м|| = (и,и)1^2.

В % оператор диффузионного переноса Л самосопряжен и положительно определен:

Л = Л* > к6£, 5 = 6(0.) > О, (1.6)

где £ единичный оператор в %.

Для решения задачи (1.4)—(1.6) определим простейшую априорную оценку, которая будет отправной точкой для рассматриваемых сеточных задач. Самосопряженный положительно определенный оператор Т> может быть связан с Гильбертовым пространством "Нр, имеющим скалярное произведение и норму

(и, у)т> = (Ли, у), ||гг||х> = (и,

соответственно. В Н уравнение (1.4) скалярно умножаем на Ли. С учетом (1.6) получаем уравнение

~Ыл + \\М\2 = (1,Ли). (1.7)

Принимая во внимание

из (1.7) получаем

d

1

Используя лемму Гронуолла, получаем желаемую оценку

и\\2Л<\\и°\\2А + и* \\m\\2de,

(1.8)

которая выражает устойчивость решения задачи (1.4)—(1.6) относительно начального значения и правой части.

1.1.2 Аппроксимация по пространству

Детальное изучение аппроксимаций по пространству и времени будем проводить на примере начально-краевой задачи в прямоугольной области

Приближенное решение задается в узлах равномерной прямоугольной сетки области П

а через со и ди обозначим множество внутренних и граничных узлов соответственно (й = и и ди). Для сеточных функций у(х) = 0, х е ди определим Гильбертово пространство Н = Ь2 (си) со скалярным произведением и нормой

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

Ау — — -h(Тл -Х- h-, /9 1"гЛ (и(Т-, -I- h-, ТгЛ — ii(Ti т-гЛ^ -J-

Q = {x | x = (.Ti, ж2), 0 < xa < la: а = 1, 2} .

ш = {x I x = (xi, rc2), xa = iaha, ia = 0,1,..., Nat Naha = la, a = 1,2} ,

(y, = y{x)w{x)hih2, IMI = (y, y)l/2.

l

(1.9)

- T2k(xi, x2 + h2/2) (y(x i,x2 + h2) - y(xux2)) +

Щ 1

+ -^k(xi,x2 - h2/2) (y(xux2) - y(xi,x2 - h2)).

h\

В пространстве Н оператор А самосопряжен и положительно определен

A = A*>k(Ó1 + S2)E, = а = 1,2. (1.10)

fii ¿La

После аппроксимации по пространству из уравнений (1.1), (1.2) переходим к дифференциально-разностному уравнению

^ + Ay = f(x,t), х euj, 0 <t<T. (1.11)

С учетом (1.3) дополним уравнение (1.11) начальным условием

у(х,0) =и°(х), хесо. (1.12)

Для решения дифференциально-разностной задачи Коши (1.11), (1-12) выполняется следующая априорная оценка (см. (1.8)):

Ы1<\\пЧа + \ J\\m\\2de. 0-13)

1.1.3 Схема с весами

Теперь особое внимание уделим аппроксимации по времени. При построении схемы декомпозиции области для задачи (1.11), (1.12) в качестве отправной точки используется стандартная двухслойная схема. Пусть т — шаг по времени и уп = y(tn), tn = пт, п = 0,1 Мт = Т. Уравнение (1.11) аппроксимируем

двухслойной схемой с весами

„ .72+1 _ П

2-У- + A(ayn+l + (1 - а)уп) = <рп, п = 0,1,..., N- 1, (1.14)

т

где срп = f(tn + ат). Дополняем (1.14) начальным условием

У° = и°. (1.15)

Для достаточно гладких решений задачи разностная схема (1.14), (1.15) имеет ошибку аппроксимации 0(т2 + (сг — 1/2)т + |/г|2), где \h\2 = h\ + h\.

Теорема 1. Разностная схема (1.14), (1.15) безусловно устойчива при а > 0.5 и для численного решения выполняется оценка

\\уп+Ч1 < \\уп\\в + п = о, 1,N- 1, (1.16)

где

Доказательство. Перепишем разностную схему (1.14) следующим образом

и скалярно умножим на гА(уп+1 + уп). Так как а > 1/2, следовательно D > А и получаем

112/п+1||Ь - \\уп\\1 + ^1И(уп+1 +2/п)Ц2 = т(<рп,А(уп+1 + уп)). Учитывая, что

(¥>», А(уп+г + у»)) < + у»)||2 + ^||<Л|2,

получаем требуемую оценку (1.16). □

Априорная оценка (1.16) для решения задачи (1.14), (1.15) является дискретным аналогом априорной оценки (1.13) для решения дифференциально-разностной задачи (1.11), (1.12) (D = A + О(т)).

1.1.4 Декомпозиция области

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

h

\h

Сетка си разделена грубой сеткой на прямоугольные подобласти размером h. Границы подобластей (интерфейсные линии) содержат узлы мелкой вычислительной сетки. Обозначим это множество внутренних граничных узлов через си. Фрагмент сетки показан на рис. 1.1. Такая декомпозиция вычислительной сетки соответствует декомпозиции области изображенной на рис. 1.2: ii = f^ U П2, fii П 0,2 = 0- Подобласть 0,2 является каркасом, и ширина отдельного ребра решетки равна h. Область состоит из несвязных отдельных подобластей.

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

р

J2x* = E, Ха> 0, а=1,2,..,р. (1.17)

ot=1

Операторы декомпозиции могут быть записаны в форме

Аа = ХаА, а = 1,2,...,р. (1.18)

О о о о о о о < > о о о о о о о

о о о О о о о < > о о о о о о о

о о о о о о О < > о о о о о о о

о о о О о о о < > о о о о о о о

О о о о о о О i > о о о о о о о

о о о о о о о < > о о о о о о о

О о о о о о О < > о о о О о О о

о о о о о о о < > о о о о о о о

о О о О О о О < > о О о О о о О

о о о о о о о < 1 о о о о О о о

о о о о о о о < i о о о о о о о

О о о о о о о < > о о о о о о о

о о о о о о о < i о о о о о о о

о о о о о о о < > о о о о о о о

Рисунок 1.1: Декомпозиция сетки

к

Рисунок 1.2: Декомпозиция области

Учитывая (1.17), в данном расщеплении мы получаем для оператора задачи следующее аддитивное представление

А = ^Аа. (1.19)

а=1

Расщепление (1.19) позволяет перейти от уравнения (1.11) к уравнению , р

+ = жеы, 0<£<Т. (1.20)

а=1

Прямое построение различных схем расщепления для задачи (1.12), (1.20) усложняется тем фактом, что отдельные операторные члены Аа, а ~ 1,2, ...,р не наследуют основные свойства оператора А, т.е., самосопряженность и неотрицательность. Однако, используя операторы декомпозиции (1.19), уравнение (1.20) легко может быть приведено к симметричной форме. Умножая уравнение (1.20)

на самосопряженный оператор А, мы получаем уравнение

B^ + J2Aay = Af(x,t), хеси, 0< ¿< Г, (1.21)

а=1

где операторы

В = А, Аа = АХаА, <* = 1,2,...,р (1.22)

являются самосопряженные и неотрицательные. Более того, мы можем ввести новую неизвестную v = А1/2у и вместо (1.21) рассматривать уравнение

jt+^2Aav = A1/2f(x,t): хеш, 0 < t <Т, (1.23)

а=1

с самосопряженным и неотрицательным оператором

Аа = А1/\аА1!2, =1,2,..., р.

Стандартные оценки для решения уравнения (1.23) в норме Н (для ||г>[|) соответствуют использованию оценок в На (для ||у|Ц)- Это объясняет наш в некотором смысле необычный выбор априорной оценки (1.13) для задачи (1.11), (1.12) и оценки (1.16) для задачи (1.14), (1.15).

Определенные характеристики операторов декомпозиции типов (1.17), (1.19) обеспечиваются с помощью выбора членов Ха,а = 2, ...,р. Некоторые дополнительные свойства обсуждаются ниже, но мы начнем с самого простого варианта. Если мы используем декомпозицию без налегания, то, естественно, брать

J 1, х Е ы,

Х2{х) = < XI(ю) = 1 - Х2(х), хеш. (1.24)

I 0, х ^ и,

Оператор А2 связан с интерфейсными узлами а А\ с внутренними узлами в подобластях.

1.2 Декомпозиция явной схемы

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

1.2.1 Параллельный алгоритм

Список литературы диссертационного исследования кандидат наук Захаров, Петр Егорович, 2013 год

Литература

1. Абрашин В. Н. Об одном варианте метода переменных направлений решения многомерных задач математической физики. 1 // Дифференциальные уравнения. - 1990,- Т. 26.- С. 314-323.

2. Абрашин В. Н., Вабищевич П. Н. Векторные адитивные схемы для эволюционных уравнений второго порядка // Дифференциальные уравнения. — 1998,- Т. 34, № 12.- С. 1666-1674.

3. Афанасьева Н.М., Васильева М.В., Захаров П. Е. Параллельное численное моделирование процесса заводнения нефтяного месторождения // Мат. заметки ЯГУ.-2011,-Т. 18, № 1.-С. 159-172.

4. Баландин МЮ, Шурина ЭП. Некоторые оценки эффективности параллельных алгоритмов решения СЛАУ на подпространствах Крылова // Вычислительные технологии. — 1998. — Т. 3, № 1. — С. 23-30.

5. Вабищевич П. Н. Векторные аддитивные разностные схемы для эволюционных уравнений первого порядка // Журнал вычислительной математики и математической физики. — 1996. — Т. 36(3). — С. 44-51.

6. Вабищевич П. Н. Разностные схемы декомпозиции области для нестационарных задач конвекции/диффузии // Дифференциальные уравнения. — 1996. - Т. 32, № 7. - С. 923-927.

7. Вабищевич П. Н. Разностные схемы декомпозиции расчетной области при решении нестационарных задач // Журнал вычислительной математики и математической физики, - 1989.- Т. 29, № 12.- С. 1822-1829.

8. Вабищевич П. Н. Регионально-аддитивные разностные схемы стабилихиру-ющей поправки для параболических задач // Журнал вычислительной математики и математической физики, — 1994.— Т. 34, № 12.— С. 1832-1842.

9. Вабищевич П. Н. Численное моделирование.— М. : Изд-во Московского университета, 1993.

10. Вабищевич П. Н. Вычислительные методы математической физики. Нестационарные задачи. — М. : Вузовская книга, 2009.

11. Вабищевич П. Н., Вераховский В. А. Векторные схемы декомпозиции области для эволюционных уравнений второго порядка // Вестн. Моск. ун-та. Вычислит, матем. и киберн. — 1998. — № 2. — С. 3-9.

12. Вабищевич П. Н., Вераховский В. А. Разностные схемы покомпонентного расщепления - декомпозиции обрасти // Вестн. Моск. ун-та. Вычислит, матем. и киберн. — 1994.— № 3.— С. 17-22.

13. Вабищевич П. Н., Данияров А. О. Математическое моделирование прома-чивания зоны аэрации в условиях близкого залегания грунтовых вод // Математическое моделирование. — 1994. — Т. 6, № 11. — С. 11-24.

14. Вабищевич П. Н., Данияров А. О., Пулатов П. А. Численное моделирование увлажнения грунта // Математическое моделирование. — 1991. — Т. 3, № 6. — С. 3-9.

15. Васильева М.В., Григорьев A.B., Захаров П. Е. Параллельное программирование на основе библиотек: учебное пособие.— Якутск: Издательско-полиграфический комплекс СВФУ, 2011.

16. Васильева М. В., Захаров П. Е. Библиотека SCore для численного моделирования на высокопроизводительных вычислительных системах // Труды международных конференций по математическому моделированию.— 2012.-С. 295-307.

17. Введение в математическое моделирование / В. Н. Ашихмин, М. Б. Гитман, И. Э. Келлер и др. — М. : Логос, 2005.

18. Гордезиани Д. Г., Меладзе Г. В. О моделировании третьей краевой задачи для многомерных параболических уравнений в произвольной области одномерными уравнениями // Журнал вычислительной математики и математической физики. — 1974. — Т. 14. — С. 246-250.

19. Захаров П. Е. Параллельные алгоритмы разделения области для параболической задачи // Мат. заметки ЯГУ. — 2013. — Т. 20, № 2. — С. 256-270.

20. Лаевский Ю. М. Об одном алгоритме декомпозиции области без налегания подобластей решения параболических уравнений // Журнал вычислительной математики и математической физики.— 1992.— Т. 32, № П.— С. 1744-1755.

21. Лаевский Ю. М., Гололобов С. В. Явно-неявные методы декомпозиции области решения параболических уравнений // Сибирский математический журнал, - 1995.- Т. 36, № 3.- С. 590-601.

22. Лаевский Ю. М., Мацокин А. М. Методы декомпозиции решения эллиптических и параболических краевых задач // Сибирский журнал вычислительной математики. - 1999. - Т. 2, № 4. - С. 361-372.

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

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

25. Самарский А. А. Экономичные разностные схемы для систем уравнений параболического типа // Ж. вычисл. матем. и матем. физ. — 1964. — Т. 4, № 5. - С. 927-930.

26. Самарский А. А., Вабищевич П. Н. Векторные аддитивные схемы декомпозиции области для параболических задач // Дифференциальные уравнения.- 1995.-Т. 31.- С. 1563-1569.

27. Самарский А. А., Вабищевич П. Н. Факторизованные разностные схемы декомпозиции области для задач конвекции-диффузии // Дифференциальные уравнения. - 1997. - Т. 33. - С. 967-974.

28. Самарский А. А., Вабищевич П. Н. Регуляризованные аддитивные схемы полной аппроксимации // ДАН. - 1998. - Т. 358. - С. 461-464.

29. Самарский А. А., Гулин А. В. Устойчивость разностных схем. — М. : Наука, 1973.

30. Самарский А. А., Николаев Е. С. Методы решения сеточных уравнений. — М. : Наука, 1978.

31. Самарский А. А., Вабищевич П. Н. Аддитивные схемы для задач математической физики. — М. : Наука, 1999.

32. Самарский А. А., Михайлов А. П. Математическое моделирование. Идеи. Методы. Примеры. — М. : Физматлит, 2005.

33. Саульев В. К. Интегрирование уравнений параболического типа методом сеток. — М. : Физматгиз, 1960.

34. Разработка пакета SCore для численного моделирования на вычислительных кластерах / В. С. Борисов, П. Н. Вабищевич, В. И. Васильев и др. // естник ЦКР Роснедра. - 2012. - Т. 2. - С. 36-39.

35. Яненко Н. Н. Метод дробных шагов решения многомерных задач математической физики. — Новосибирск : Наука, 1967.

36. Ascher U. М. Numerical methods for evolutionary differential equations.— Society for Industrial Mathematics, 2008.

37. С++ Programming Language.— http://www. stroustrup.com/C++. html.

38. Cai Xiao-Chuan. Additive Schwarz Algorithms for Parabolic Convection-Diffusion Equations // Numer. Math. — 1991. — Vol. 60, no. 1. — P. 41-61.

39. Cai Xiao-Chuan. Multiplicative Schwarz Methods for Parabolic Problems // SIAM J. Sci Comput. — 1994. — Vol. 15, no. 3. — P. 587-603.

40. Ciarlet Philippe G. The finite element method for elliptic problems. — Access Online via Elsevier, 1978.

41. Dryja Maksymilian, Tu Xuemin. A domain decomposition discretization of parabolic problems // Numerische Mathematik. — 2007.— Vol. 107.— P. 625640.

42. Dym C. L. Principles of mathematical modeling. — Academic Press, 2004.

43. Evans D. J. Alternating group explicit method for the diffusion equation // Applied mathematical modelling. — 1985. — Vol. 9, no. 3, — P. 201-206.

44. Evans D. J., Abdullah A. R. B. Group explicit methods for parabolic equations // International journal of computer mathematics.— 1983.— Vol. 14, no. 1.— P. 73-105.

45. Feng Qinghua, Zheng Bin. Parallel Alternating Group Explicit Iterative Method for Convection-Diffusion Equations // WSEAS International Conference. Proceedings. Mathematics and Computers in Science and Engineering / World Scientific and Engineering Academy and Society. — No. 8.— 2009.— P. 383387.

46. Forsythe G. E., Wasow W. R. Finite Difference Methods for Partial Differential Equations. — New York : Wiley, 1960.

47. Fujita H., Suzuki T. Evolution problems // Handbook of numerical analysis. — 1991. — Vol. 2. - P. 789-928.

48. Gander Martin J. Overlapping Schwarz for parabolic problems // Ninth International Conference on Domain Decomposition Methods (Petter E. Bj0rstad, Magne Espedal, and David Keyes, eds.), ddm. org. — 1997.— P. 97-104.

49. Gershenfeld N. A. The nature of mathematical modeling. — Cambridge University Press, 1999.

50. Golub G. H., Ortega J. M. Scientific computing and differential equations: an introduction to numerical methods. — Academic Press, Inc. Orlando, FL, USA, 1991.

51. Grossmann C., Roos H. G., Stynes M. Numerical treatment of partial differential equations. — Springer Verlag, 2007.

52. Gustafsson B. High order difference methods for time dependent PDE.— Springer Verlag, 2008.

53. Hockney Roger W. The communication challenge for MPP: Intel Paragon and Meiko CS-2 // Parallel computing. — 1994. — Vol. 20, no. 3. — P. 389-398.

54. Hundsdorfer W. H., Verwer J. G. Numerical solution of time-dependent advection-diffusion-reaction equations. — Springer Verlag, 2003.

55. Ippisch O, Vogel H-J, Bastian P. Validity limits for the van Genuchten-Mualem model and implications for parameter estimation and numerical simulation // Advances in water resources. — 2006. — Vol. 29, no. 12. — P. 1780-1789.

56. Jame Yih-Wu, Norum Donald I. Heat and mass transfer in a freezing unsaturated porous medium // Water Resources Research.— 1980.— Vol. 16, no. 4.— P. 811-819.

57. Johnson G. M. Numerical Solution of Partial Differential Equations by the Finite Element Method. — Cambridge : Cambridge University Press, 1987.

58. Jun Younbae, Mai Tsun-Zee. ADI method - domain decomposition. // Appl. Numer. Math. — 2006. — Vol. 56, no. 8. —P. 1092-1107.

59. Jun Younbae, Mai Tsun-Zee. IPIC domain decomposition algorithm for parabolic problems. // Appl. Math. Comput. — 2006.— Vol. 177, no. 1.— P. 352-364.

60. Jun Younbae, Mai Tsun-Zee. Numerical analysis of the rectangular domain decomposition method. // Commun. Numer. Methods Eng. — 2009. — Vol. 25, no. 7.-P. 810-826.

61. Knabner P., Angermann L. Numerical methods for elliptic and parabolic partial differential equations. — Springer Verlag, 2003.

62. Kreiss H. O., Lorenz J. Initial-Boundary Value Problems and the Navier-Stokes Equations. — San Diego : Academic Press, 1989.

63. Kruskal Clyde P, Rudolph Larry, Snir Marc. A complexity theory of efficient parallel algorithms // Theoretical Computer Science. — 1990. — Vol. 71, no. 1. — P. 95-132.

64. Kuznetsov Yu. A. New algorithms for approximate realization of implicit difference schemes // Sov. J. Numer. Anal. Math. Model. — 1988. — Vol. 3, no. 2.— P. 99-114.

65. Kuznetsov Yu. A. Overlapping domain decomposition methods for FE-problems with elliptic singular perturbed operators. — Fourth international symposium on domain decomposition methods for partial differential equations, Proc. Symp., Moscow/Russ. 1990,223-241 (1991). — 1991.

66. Laevsky Yu. M. Domain decomposition methods for the solution of two-dimensional parabolic equations // Variational-difference methods in problems of numerical analysis. — No. 2.— Novosibirsk : Comp. Cent. Sib. Branch, USSR Acad. Sci., 1987. —P. 112-128.—in russian.

67. Laevsky Yu. M. Quadratic elements in splitting methods // So v. J. Numer. Anal. Math. Model. — 1990. — Vol. 5. — P. 244-249.

68. Larsson S., Thomee V. Partial differential equations with numerical methods. — Springer Verlag, 2003.

69. Marchuk Gurii I. Splitting and alternating direction methods // Handbook of Numerical Analysis, Vol. I / Ed. by Philip G. Ciarlet, Jacques-Louis Lions. — North-Holland, 1990.-P. 197-462.

70. Mathew T. Domain decomposition methods for the numerical solution of partial differential equations. — Lecture Notes in Computational Science and Engineering 61. Berlin: Springer, xiii, 764 p., 2008.

71. Meyer W. J. Concepts of mathematical modeling. — Dover Publications, Inc., 2004.

72. Mitchell A. R., Griffiths D. F. The Finite Difference Method in Partial Differential Equations. — Chichester : Wiley, 1980.

73. Performance analysis of MPI collective operations / Jelena Pjesivac-Grbovic, Thara Angskun, George Bosilca et al. // Cluster Computing. — 2007. — Vol. 10, no. 2.-P. 127-143.

74. Python Programming Language. — http: //www.python. org/.

75. Quarteroni A., Valli A. Numerical Approximation of Partial Differential Equations. — Berlin : Springer-Verlag, 1994.

76. Quarteroni Alfio, Valli Alberto. Domain decomposition methods for partial differential equations.— Numerical Mathematics and Scientific Computation. Oxford: Clarendon Press, xv, 360 p., 1999.

77. Reddy Junuthula Narasimha. An introduction to the finite element method. — McGraw-Hill New York, 2006. — Vol. 2.

78. Richtmyer R. D., Morton K. W. Difference Methods for Initial-Value Problems.—New York : Wiley, 1967.

79. Saad Y. Iterative methods for sparse linear systems.— Society for Industrial Mathematics, 2003.

80. Samarskii A. A., Matus P. P., Vabishchevich P. N. Difference schemes with operator factors. — Kluwer Academic Pub, 2002.

81. Samarskii A. A., Vabishchevich P. N. Regularized difference schemes for evolutionary second order equations // Math. Mod. Meth. Appl. Sciences. — 1992. — Vol. 3.-P. 295-315.

82. Samarskii A. A., Vabishchevich P. N. Domain decomposition methods for parabolic problems // Eleventh International Conference on Domain Decomposition Methods / Ed. by C.-H. Lai, P. Bjorstad, M. Gross, O. Widlund.— DDM.org, 1999.- P. 341-347.

83. Smith B. Domain decomposition. Parallel multilevel methods for elliptic partial differential equations. — Cambridge: Cambridge University Press, xii, 224 p., 1996.

84. Smith G. D. Numerical Solution of Partial Differential Equations. Finite Difference Method. — Oxford : Clarendon Press, 1992.

85. Software Gmsh. — http: //geuz .org/gmsh/.

86. Software VTK. — http: //www.vtk.org/.

87. Software package DOLFIN. — https://bitbucket.org/ fenics-project/dolfin.

88. Software package FEniCS. — http://fenicsproject. org/.

89. Software package MPI. — http://www.mcs.anl.gov/research/ projects/mpi/.

90. Software package Paraview. — http: //www.paraview.org/.

91. Software package UFL. — https://bitbucket.org/ fenics-project/uf1.

92. Strang G. Introduction to applied mathematics.— Wellesley-Cambridge Press Wellesley, MA, 1986.

93. Strikwerda J. C. Finite difference schemes and partial differential equations.— Society for Industrial Mathematics, 2004.

94. Sun Tong. Stability and error analysis on partially implicit schemes. // Numer. Methods Partial Differ. Equations. — 2005. — Vol. 21, no. 4. — P. 843-858.

95. Thomas J. W. Numerical Partial Differential Equations. Finite Difference Methods.—Berlin: Springer-Verlag, 1995.

96. Thomee V. Galerkin finite element methods for parabolic problems. — Springer Verlag, 2006.

97. Toselli Andrea, Widlund Olof. Domain decomposition methods - algorithms and theory.— Springer Series in Computational Mathematics 34. Berlin: Springer, xv, 450 p., 2005.

98. Vabishchevich Petr. A Substructuring Domain Decomposition Scheme for Unsteady Problems // Comput. Methods Appl. Math. — 2011.— Vol. 11, no. 2.— P. 241-268.

99. Vabishchevich P. N. Domain decomposition methods with overlapping subdomains for the time-dependent problems of mathematical physics. // Computational Methods in Applied Mathematics. — 2008. — Vol. 8, no. 4. — P. 393-405.

100. Vabishchevich P. N., Zakharov P. E. Domain Decomposition Scheme for FirstOrder Evolution Equations with Nonselfadjoint Operators // Numerical Solution of Partial Differential Equations: Theory, Algorithms, and Their Applications.

Springer Proceedings in Mathematics & Statistics. — 2013. — Vol. 45. — P. 279302.

101. Van Dam Jos C, Feddes Reinder A. Numerical simulation of infiltration, evaporation and shallow groundwater levels with the Richards equation // Journal of Hydrology. - 2000. - Vol. 233, no. 1. - P. 72-85.

102. Wang Wen-qia. The alternating segment Crank-Nicolson method for solving convection-diffusion equation with variable coefficient // Applied Mathematics and Mechanics. — 2003. — Vol. 24. — P. 32^12.

103. Water Flow and Heat Transport in Frozen Soil / Klas Hansson, Jirka Simunek, Masaru Mizoguchi et al. // Vadose Zone Journal. — 2004. — Vol. 3, no. 2. — P. 693-704.

104. Yu Zhuang. An alternating explicit-implicit domain decomposition method for the parallel solution of parabolic equations. // J. Comput. Appl. Math.— 2007. — Vol. 206, no. 1. — P. 549-566.

105. Zhang Baolin, Li Wenzhi. AGE method with variable coefficients for parallel computing // Parallel Algorithms and Applications. — 1995. — Vol. 5, no. 3-4. — P. 219-228.

106. Zhuang Yu. An alternating explicit-implicit domain decomposition method for the parallel solution of parabolic equations // Journal of computational and applied mathematics. — 2007. — Vol. 206, no. 1. — P. 549-566.

107. Zhuang Yu, Sun Xian-He. Stabilized explicit-implicit domain decomposition methods for the numerical solution of parabolic equations. // SIAM J. Sci. Comput. — 2002. — Vol. 24, no. 1. — P. 335-358.