Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 35
Текст из файла (страница 35)
Однако мы увидим позднее, что этн аберрации не имеют большого практического значения. Во всяком случае, наша цель в этом разделе — наложить некоторые основные идеи, а не исследовать во всех подробностях данную сеточную задачу, Нам будет удобно считать о н б целыми числами, а т и ! — настолько большими, что т~тви 1~!в В 71 Пример — задача на (тУ(П-сстне йзб Как мы уже отметили, полезность этого упорядочения зависит от использования развитой в главе 6 техники блочных матриц. В самом деле, если не привлекать эту технику, то нетрудно проверить, что наше упорядочение не лучше и даже хуже, чем стандартное ленточное упорядочение (см. упр.
7.1.2 и 7.1.3). Наиболее важное соображение, позволяющее нам применить описанную в главе 6 методику фактор-деревьев, состоит в следующем: если считать, что и блоков, соответствующих разделителям, образуют единый член разбиения, то результирующее разбиение, теперь уже с р = о+ 2 членами, имеет Рнс. 7.!.4. Фактор-дерево, соответствуюп»ее упорядочению посредством параллельных сечений н объеднненню разделителей в однн член раебнення. структуру монотонно упорядоченного фактор-дерева, Рис. 7ЛА иллюстрирует ситуацию для примера на рис.
7.!.2. Таким образом, можно использовать схему хранения, обсуждавшуюся в $6.4, и хранить лишь диагональные блоки Ь и внедиагональные блоки А При обсуждении удобно продолжать рассматривать А и Т как матрицы блочного порядка о, где»7=2о+ 1. Однако читатель должен понимать, что при вычислении последние и членов разбиения объединяются, так что в действительности остается р = а + 2 членов. 7.7.3. Требования к памяти Обозначим через 7.н подматрнцы (, соответствующие подматрицам А„, 1 ~ 1,/ < 2о+ 1. Мы получим сейчас оценку для памяти, необходимой в алгоритме параллельных сечений, при условии, что используется неявная схема хранения нз раздела 6.4.1, Основная память подсчитывается таким образом: !) Е»», 1 ~ й ~ о + 1.
Ширина ленты у этих ленточных матриц равна (1 + 1)/(о + 1). В целом для всех Ь»» требуется ячеек тл (1 — о) (1 + 1),„(т (о+ 1) 226 Гл. 7. Методм аараллельнеи сечений 2) Ечь о+ ! (1, й ( 2о+1, ! (й Всего здесь и — 1 заполненных блоков и о нижних треугольных блоков; все имеют порядок т, В целом требуется ячеек (о — !) т'+ аас (ас + !) Засач 2 Ж вЂ”. 2 3) Аеь й ~ о+ 1, !' ) о+ 1. Каждый узел разделителя связан с шестью узлами ведущих о+ ! блоков; исключение составляют только граничные узлы. Таким образом, основная память для этих матриц равна приблизительно бат ячеек.
Накладная память для матриц из 1) н 2) равна 1т+ о + 3 (для массивов ХЕ!ч!Ч и ХВЕК) и примерно 6от+ 1т для Х!ч!ОМЕ и )ч!Е3!ЗВЬ. Тем самым если пренебречь младшими членами, то общие запросы к памяти для нашего упорядочения (при использовании неявной схемы хранения из раздела 6.4.1) выражаются такой приближенной формулой; гт + Заест (7.1,2) Если наша цель состоит в минимизации памяти, то и нужно выбрать так, чтобы минимизировать функцию 8(о). Дифференцируя по и, получим Л3 са!а Зиса — = — — + —.
на ае 2 Отсюда заключаем, что 8 приближенно мннимизнруется выбором о=в', где и'=1(з'„)". (7.1.3) что дает Я(н') =л,76 т'а1+ 0(т1). (7.1.4) Отметим, что соответствующее оптимальное значение б* равно '-( — ")" Интересно сравнить полученный результат с памятью, необходимой при использовании стандартной ленточной или профильной схемы. Так как тп ( 1, то мы нумеровали бы узлы сетки столбец за столбцом, что приводит к матрице с шириной ленты т+ 1.
При больших т и 1 память, необходимая для л', была бы равна тт1+ 0(т1). Таким образом, асимптотически схема параллельных сечений сокращает запросы к памяти по сравнению со стандартными схемами главы 4. Коэффициент сокращения равен т/67т. 4 7П. Пример — задача на ~т Х 1)-сетке 237 7.7 3.
Число операций при разложении Теперь оценим вычислительную работу в алгоритме парал'лельных сечений. По существу, нам нужно просто сосчитать число операций в алгоритмах разложения и решения из $6.2. Однако внедиагональные блоки Ае, для й ~ о+ 1 и ! ) о+ 1 имеют довольно специальную «псевдотрехдиагональную структуру», которая используется подпрограммами ТЬГСТ и ТББ(.7. Поэтому получение достоверной приближенной оценки числа операций далеко не тривиально. В данном разделе мы рассмотрим разложение, Подсчет приближенного числа операций при решении приведен в разделе 7.1А. При выводе оценки полезно разбить все операции на три указанные виже категории и игнорировать в суммах младшие члены. !. Разложение о+ 1 ведущих диагональных блоков, (В нашем примере на рис. 7.1.1 — 7.1.3, где и = 4, это вычисление матриц Е»е, 1 =.
й (5.) Замечая, что ширина ленты у этих матриц равна (1+ 1)/(о+ 1), н используя теорему 4.1.1, заключаем, что число операций этой категории — приблизительно 1з 2. Вычисление Ее~ для Й ) 1 и 1 ) о + !. Это соответствует разложению матрицы порядка пто, имеющей блочную трехдиагональную структуру с блоками порядка т. Используя результаты $ 2.! и 2.2, находим, что число операций равно приблизительно тоат в 3. Поправки к Аи, Ат+ь~ и Атн,~+~ для !» о-1-1 посредством внедиагональных блоков Аы и вычисленных матриц Еек, к ( о+1. Рис. 7.1.5 показывает, как вычисляются такие поправки. Ниже приводится подсчет числа операций третьей категории.
При вычислении матричной поправки по асимметричной схеме мы должны вычислять произведения Еак (Ьае'Аа!) (7.1.5) для 1.» о+ 1 и й ~ о+ 1. Результаты $ 6.5 показывьют, что в каждом столбце матрицы Еке (Ее»АМ) нет необходимости вычислять ту часть, которая находится выше первого ненулевого элемента соответствующего столбца матрицы Акь Поэтому 238 Гл 7, Методы чароллельиых сечений при вычислении Ф'=л.ааАат мы используем верхние нули в т столбцах Аан а при вычислении мГ=Еьь мт останавливаем счет, как только получен последний требуемый элемент йр, Рнс.
7.1.6 иллюстрирует сказанное. Рис. 7.1ль Матрицы, которые взаимодействуют с л.ьл, Ал~ и А,,ы и модифицируются ими; й = 3, 1' 7. т' Р Рис. 7.1.8. Структура Ам и той части Ф, которую нужно вычислять. Несложно проверить, что число операций для вычисления указанной части )е приближенно выражается формулой л(6+!)(г — 1), (7.1.6) т где Ато — (и Х г)-матрица, а Еаа+Ььа — ленточная матрица порядка а с шириной ленты 1) а; а (см. упр. 7.1.5).
Здесь п ж ж т1/о, р ж 1/о и г=-т; поэтому выражение (7.1.6) преврашается в е 7,!. Лример — задача ка (из Х !1-сегке 239 Заметим, что всего имеется 2о таких внедиагональных блоков; тем самым работа по вычислению всех произведений азьь (ЬьзАз!) !' > о+ 1, й(о+ 1, равна приблизительно 2езз! а (7.1.7) опе аций. ценим теперь стоимость вычисления поправок к матрицам Аз1, й ) о + 1, ! ) о + 1.
Замечаем, что если произведения (7.1.5) вычислены, то модификация каждого элемента диагональных блоков Азз, 7е ) о + 1, может быть получена за шесть операций, а модификация элемента внедиагонального блока Ае, з ! требует трех операций. Следовательно, стоимость всего процесса модификации есть 0(олзз), Итак, оценка полного числа операций, нужных для разложения в схеме параллельных сечений, дается формулой «з!з таазз 2езз!з 0р(п) = — + — + —.
2а' 6 а (7,1.8) Если в алгоритме параллельных сечений мы ставим целью минимизировать число операций при разложении, то нужно выбрать !те, которое бы минимизировало йе(ст). Можно показать, что при больших тл и !выбор приближенно минимизирует (7.1.8), давая значение (см. упр, 7.1.6) йр (ое) = ( ) тлз!Ч + О (тпЧ). (7.1.9) Соответствующее бе равно 4 1!'7/(8тп). Снова интересно сравнить полученный результат с числом операций, необходимых в стандартной ленточной или профильной схеме (глава 4). Для данной сеточной задачи число опе- 1 раций в разложении было бы -"* — т~!.
Таким образом„асимптотически схема параллельных сечений сокращает число операций в разложении; коэффициент равен приблизительно 240 Гл. 7. Методы параллельных сечений 7./.4. Число операций при решении Выведем теперь оценку числа операций, необходимых для решения.системы Ал = Ь. Предполагается, что «разложение», описанное в предыдущем разделе, уже вычислено.
Заметим прежде всего, что каждый из а+ 1 ведущих дяагоиальных блоков юзз, ! ~ й:6; а+ 1, используется четырежды: два раза при решении нижней треугольной системы и еще два — при решении верхней. Это требует приблизительно 4ш(а операций. Все ненулевые блоки / зь й ) а + 1, ! ) а + 1, используются дважды при обшей оценке числа операций Затя+ + 0(ат). Дважды используется и каждая из матриц Ам, /г ) а+ 1, / ~ а+ 1, что обходится примерно в 12ат операций. Таким образом, в качестве оценки числа операций при решении системы посредством алгоритма параллельных сечений можно принять Вз (а) 4 -1- Зат'. (7.1.10) Если мы желаем минимизировать Вз, то соответствующее приближенное значение а равно 21 аз д*= ~ откуда В (а ) — 4,(/З тз1з/+ 0(т1).
(7.1.1 1) И опять интересно сопоставить (?.1.1!) с соответствующей оценкой числа операций, равной примерно 2тз!, при использовании стандартной ленточной или профильной схемы. Видим, что асимптотически упорядочение посредством параллельных сечений сокращает число операций при решении системы; коэффициент равен приблизительно 2 т/З/т. Разумеется, мы не можем посредством одного значения а минимизировать сразу и память„и работу при разложении, и работу при решении.
Так как низкие запросы к памяти являются наиболео привлекательной чертой описанного метода, то в алгоритме следующего параграфа а выбираетса из условия минимизации памяти. Уиражнения 7.1.1. Каковы будут коэффициенты при старших членах в (7.1.8) н (7,1,11), если для и взято значение и' из формулы (7.1.3)? 7.1.2.
Предположим, что применено упорядочение посредством параллельных сечений, дая о взято значение О (1/З/лт), но ие используется техника ие. явного хранения, т.е. вычисляются н хранятси внедиагональные блоки Сп, й 7,1, Лример — зпбпча ла ('тХ1)-сетке 241 ! > а+ 1, 1 < и+ 1. Каковы теперь булут требования я памяти? Каково бу дет число операций Оз, если использовать этн блоки в схеме решения? 7.1.3, Предположим, что применено упоридочепне посредством параллельных сечений, для а взято значение 1/ Ч«ь но вместо асимметричного используется симметричный вариант схемы разложения (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
