Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 40
Текст из файла (страница 40)
8.1.1 показывает случай и =!О. Если вначале пронумеровать строка за строкой узлы компонент !!' и !гз, а затем узлы 5е, то получим матричную структуру, изображенную на рис, 8.1,2. Такое упорядочение будем называть одноуровневым упорядочением посредством сечений. Чтобы получить упорядочение, соответствующее методу вложенных сечений, перейдем к сечению двух оставшихся компонент. Выберем множества вершин 5!с)с~, 1=1, 2, состоящие нз узлов сеточных линий, которые делят )с! (по возможности) на равные части. Если переменные, ассоциированные с вершинами из Й' — 5', пронумеровать прежде, чем переменные, ассоциированные с вершинами 5ч, то мы индуцируем на двух ведуших главных подматрицах в точности ту же структуру, что и иа всей матрице.
') В оригинале — !пе пса!ей й!наес!!оп гпейоб.— Прим. перев. 266 Гл В Методы вложенных сечений Процесс можно продолжать, пока не останутся уже неделимые компоненты. Это и дает упорядочение посредством влоатепяьи сечений. Рис. 8.1.3 показывает такое упорядочение для Рис. 3Л.З. Упоркдочение сетки 10Х 1О посредством вложенных сечений. сеточной задачи 10Х10, а рис. 8.1.4 — структуру соответственно упорядоченной матрицы.
Отметьте повторение в этой структуре основного шаблона. 8.1,2. Требования к памяти Метод вложенных сечений использует стратегию, обычно называемую «разделяй и властвуй». Эта стратегия разделяет задачу на меньшие подзадачи; их индивидуальные решения можно скомбинировать и получить решение исходной задачи, Кроме того, подзадачи имеют и структуру, аналогичную первоначальной; поэтому процесс можно повторять рекурсивно, пока решения подзадач не станут тривиальны. При исследовании таких стратегий обычно приходится решать те или иные разностные уравнения. Мы сформулируем сейчас некоторые результаты, которые понадобятся при ана. лизе требоваяий к памяти для метода вложенных сечений.
Их доказательство оставляется читателю, Лемма 8.1.1. Пусть 1(п)=41(п/2)+ йпх+0(п). Тогда '1 (и) = йп' 1опхп + О (пв). В В! Вложенные сечения регулярной сетки 2ЕУ Лемма 8.1.2. Пусть д(п) =д(п/2)+йпг(ойг и-1- О (п'). Тогда д(п) = — Ипг)оагп+ О(п'). Лемма 8.1.3. Пусть Ь(п) =26(п/2)+Ипг(паап+О (пг). Тогда й (п) 2йпг1оигп + О (пг) Чтобы провести анализ метода вложенных сечений, мы введем окаймленные (пХп)-сетки.
Окаймленная (пгчп)-сетка— Рнс ВЛ.4. Структура матрицы, соответствующая упорядочению посредством вложенных сечений это обычная (пр,'п)-сетка плюс окаймление одной илн нескольких сторон границы посредством дополнительных сеточных линий. На рис. 8.!.5 приведены некоторые примеры окаймленных (ЗХЗ) -сеток. 268 Гл 8 Метода~ вложвнныл сечений Теперь мы можем приступить к подсчету объема пймяти, необходимого для метода вложенных сечений. Пусть о(и, г) (г) Рис. 8й,б.
Примеры онаймлеиных сетон 3 Х 3. обозначает число ненулевых элементов треугольного множителя для матрицы, ассоциированной с (пХп)-сеткой, окаймленной вдоль г' сторон. Предполагается, что сетка упорядо- Рис. 8д.а. Сечение сетха л Х и чена по методу вложенных сечений. Ясно, что нужная нам величина — это 5(п,О). Впредь в случае г=2 мы всегда имеем, в виду сетку, показанную на рис. 8.1.5 (в), а не такую сетку: 4 8 Л Вложеннь~е сечения регулярной сетки 269 В последующем тексте мы установим соотношения между величинами 5(п, !), О ( с' ( 4. Рассмотрим вначале 5(п, 0).
На рис. 8.1.6 сетка пХп разделена на 4 меньшие подсеткн посредством крестообразного разделителя. Переменные нз областей 1, 2, 3 и 4 должны быть пронумерованы прежде, чем переменные из области 5. Тогда будет нндуцирована матричная структура, показанная на рис. 8.1.7 Рнс, 8.).7. Струнтура матрицы для сеченняз показанного на рнс. 8.1.6. Ненулевые элементы треугольного множителя сосредоточены в блоках Еи, 1 < ! < 4, и Езн ! < ! < 5.
Поскольку та же стратегия применяется к меньшим подсеткам, имеем т)(Е; )+ т)(Еа,) ж5(п72, 2), !к г~(4. Так как Езз соответствует узлам крестообразного разделителя, то число ненулевых элементов можно определить, пользуясь теоремой 5.!.2. Оно равно зи/3 г) (Ез ) = 2 ~, "! + п~)2 + 0 (п) = 7п~/4 + 0 (и). и Тем самым получено первое разностное уравнение.
5(п, 0) =45 ( —,2) + — + 0(п). (8.1.1) Х(и,г) Ю(и,з) й(и,я) 270 Гл. д. Методы елонсенных сечений Остальные уравнения могут быть установлены таким же образом. Все онн выражают равенство: 5(л,!) = стоимость хранения четырех окаймленных подсеток л/2 Х а/2 + стоимость хранения крестообразного разделителя.
Предоставляем читателю проверку следующих результатов: 5 (л, 2) = 5 (п/2, 2) + 25 (л/2, 3) + 5 (л/2, 4) + 19ае/4 + + О (л), (8.1.2) 5 (л, 3) = 25 (а/2, 3) + 25 (а/2, 4) + 25п /4+ 0 (и), (8.1.3) 5(а, 4) =45(а/2, 4)+ 3!п'/4+ 0 (и). (8.1.4) Теорема 8,1.4. Число ненулевых элементов треугольного множителя е. матрицы, ассоциированной с регулярной (пКа)-сеткой, которая упорядочена посредством вложенных сечений, выражается е/тормулой т1(Ь) =3! (лт!од,а)/4+ 0(лт).
Доказательство. Нужный результат следует нз разностных уравнений (8.1.1) — (8.1.4). Применяя лемму 8.1.1 к уравнению (8.1.4), получаем 5 (п,4) = 31 (лт1опгп)/4+ О (ае) После подстановки в (8.1.3) имеем 5(а, 3) = 25(л/2, 3) + 31(п'1ойоп)/8+ 0(ае). Согласно лемме 8,1.3, решением этого уравнения будет 5(п, 3) =31(а'!одел)/4+ 0(лг) Подставляя выражения для 5(л,3) и 5(п,4) в уравнение (8.1.2), получим 5(п, 2) =5(л/2, 2)+ 93(п'!оп,л)/16+ 0(а).
Решение этого уравнения— 5(а, 2) = 31(п'1ойтп)/4+ 0(пг), а тогда т1(Ь) = 5 (а, О) 3! (пе)одел)/4+ 0(пт). В доказательстве теоремы 8.!.4 интересно отметить тот факт, что асимптотические оценки для всех 5(л,1), 1=0, 2, 3, 4, совпадают и равны 3! (лг!оие л)/4 (а прн 1= 1?) 8.1.3. Число операций Пусть А — матрица, ассоциированная с (аХл)-сеткой, упорядоченной методом вложенных сечений, При оценке числа операций в разложении А мы можем следовать тем же путем, З 8 д Вложенные сечения регулярной сетки ег1 что и в предыдущем разделе. Вначале сформулируем некоторые дополнительные результаты о разностных уравнениях Лемма 8.1 6.
Пусть /(п) = /(и/2)+ /газ+ 0(аг!одзи). Тогда /(п) = Вяпз/7 + О (аг)опгп). Лемма 8.1.6. Пусть д(а) =2й(п/2)+ йпз+ 0(аг1оВгп). Тогда й (п) = 4/гп'/3 + 0 (пг!одзи). Лемма 8.1.7. Пусть й(и)=4й(п/2)+ йпз+ 0(аг). Тогда й (а) 2/газ + О (аг)оргп). По аналогии с 5(а,г) введем число О(п,г) операций, необходимых при разложении матрицы, ассоциированной с (и)( Хп)-сеткой, которая окаймлена вдоль 1' сторон.
Предполагается, что сетка упорядочена методом вложенных сечений. Для вычисления 0(п, 0) снова рассмотрим рнс. 8!.6. Ясно, что 0(п,О) есть стоимость исключения в четырех окаймленных (и/2Ха/2) -подсетках плюс стоимость исключения узлов в крестообразном сечении. Применяя теорему 2.1.2, имеем Зк12 к В(и, 0)ж40(а/2, 2)+~~ Р+ — / /2 1-н 1-1 = 40(п/2 2) + 19аз/24+ пз/6+ 0(пг) 40(п/2 2)+ 23аз/24+ 0(пг) (8.!.5) Предоставляем читателю проверку следующих равенств: 0(п, 2)=0(п/2, 2)+20(п/2, 3)+8(п/2, 4)+35п'/6+О (п'), (8.1.6) О(п, 3)=28(п/2, 3) + 20(а/2, 4) + 239из/24+ 0(пг), (8.1.7) В(п, 4)=40(п/2, 4) + 371аз/24+ 0 (и ). (8.1.8) Теорема 8.1 8.
Число операций, необходимых дяя разложения магрицьй ассоциирово 1ной с (п Х п)-сеткой, в методе вложенных сечений авно Р 829и'/84 + 0 (пг!оугп) Доказательство. Нужно определить число 8(а,О). Применяя лемму 8.!.7 к уравнению (8.1.8) получаем В (п,4) = 37!и /12 + 0 (а'!ойгп). Теперь уравнение (8.1.7) можно переписать в виде В(п, 3) = 20(а/2, 3) + 849из/48 + 0 (пг!одгп), рте Гл 3 Методы еложенных сечений Согласно лемме 8.1.6, 0(п, 3) =283пе/12+ 0 !и'1од,п). Подставляя выражения для 0(п,3) и 0(п,4) в (8.1.6), получим 0(п, 2) =0(п/2, 2)+ 1497пз/96+ 0(п'1оп,п), откуда по лемме 8.1.5 0(п, 2) = 499пе/28+ 0 (пе!опеп), Наконец, из уравнения (8.1.5) следует 0(п, О) = 829пз/84+ 0 (и'1ой,п), В.1.4.
Оптимальность упорядочения В этом разделе мы установим нижние оценки для числа ненулевых элементов треугольного множителя (т. е. объема основной памяти) и числа операций при выполнении симметричного разложения для произвольного упорядочения матрицы, ассоциированной с регулярной (и Х и)-сеткой. Мы покажем, что для разложения требуется не менее 0(пе) операций, а соответствующий нижний треугольный множитель должен иметь по меньшей мере 0(п'!оде п) ненулевых элементов. Метод вложенных сечений из раздела 8.1.1 достигает этих нижних границ и, следовательно, может рассматриваться как оптимальный по порядку.
Выведем вначале нижнюю оценку для числа операций. Лемма 8,1.9, Пусть 0 = (Х, Е) — граф, ассоциированный с (пХ и)-сеткой. Пусть х1мхь ..., хв — произвольное упорядочение О. Тогда найдется узел х, такой, что ! Кеаси(х„(хь ..., х, 1)) !>и — 1. Доказательство. Пусть х, — первый узел, исключение которого завершает исключение какой-либо строки или столбца сетки. Пусть для определенности это будет столбец (строка). На этом этапе еще остаются по крайней мере и — 1 сеточных строк (столбцов), не все узлы которых исключены.
В каждой из этих строк (столбцов) имеется хотя бы один узел, которого можно достигнуть из хе через подмножество (хь ..., х, 1), Это доказывает лемму. Теорема 8.!,1О. Разложение матрицы, ассоциированной с (и р,', п)-свткой, требует нв менее 0(п') операций. у 8 1 Влоясеяяие сечения регулярное сетки 27З Доказательство. Согласно лемме 8.1.9, найдется узел х, такой, что подграф, определяемый множеством Йеасй(хс (х„..., хс-Д)() (хс) является кликой в графе заполнения 6Я<л> (см. упр, 5.1,4) и при этом имеет по меньшей мере и узлов. Он соответствует заполненной (иХи)-подматрице в матрице заполнения Р, поэтому симметричное разложение требует не менее ие/б+ 0(пз) операций.
Вывод нижней оценки для основной памяти следует иной линии. Для произвольной (йХй)-подсетки в нижеследующей лемме указывается специальное ребро в результирующем графе заполнения. Лемма 8 1.11. Рассмотрим произвольную (й Х я)-подсетку заданной сетки и Х и. В графе 0" найдется ребро, соединяющее пару параллельньсх граничньсх линий подсетки. Доказательство. В (й Х я)-подсетке — четыре граничные сеточные линии. Пусть х, — первый граничный узел подсетки, после исключения которого будет полностью исключена какая- либо граничная линия (в которую не включаются угловые вершины). Всегда найдутся два узла в остающихся параллельных граничных линиях, которые связаны через множество (х„х„..., хс ь хс). (См.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
