Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 27
Текст из файла (страница 27)
6.2.2 иллюстрирует сказанное. Если явно не оговорено противоположное, то всякий раз, когда мы упоминаем об упорядочении блочного графа, мы подразумеваем, что упорядочение совместимо с разбиением — ведь интерес для нас представляет упорядочение блочных матриц. В общем случае при выполнении для блочной матрицы (блочного) гауссова исключения нулевые блоки могут стать ненулевыми. Таким образом, может происходить «блочное заполнение» точно так же, как заполнение происходит в скалярном случае. Например, в блочной матрице на рис, 6 2.1 имеются !74 Гл б Методы факгор-дерееьее два нулевых внедиагональных блока, которые после разложения станут ненулевыми. Структура треугольного множителя показана на рис.
6.2.3. Ш Т П Рнс. 6.2.2. Пример индуцированных упорядочений для графа на рис 62!. (а) Упорядочение ОЯ, индуцированное исходным упорядочением графа на рис. 62Л. (6) Другое упорядочение, совместимое с 2), Однако при заданном разбиении симметричной матрицы характер появления блочного заполнения не обязательно в точности соответствует скалярной ситуации. Другими словами, мы Рис. 6.2.2. Структура треугольного множителя для матрицы на рис.
6 2.1. не можем просто выполнить символическое исключение на фактор-графе и получить тем самым блочную структуру множителя Е Таким путем мы найдем лишь наихудшее возможное заполнение, которое, конечно, никогда нельзя исключить, так б б.х Фактор-графы, деревья и древовидные разбиения 17б как любой ненулевой блок может быть заполнен. Иллюстрация сказанного приведена на рис. 6.2.4. Итак, символическое разложение фактор-графа блочной матрицы может указать ббльшую величину блочного заполнения, чем имеет место в действительности.
Интуитивно причина этого ясна: модель исключения предполагает, что произведение Граф зааалгненол Зля улур с'+"'ур Пл лр Рис. В.2.4. Пример, показывающий, что символическое исключение иа фактор- графе Орй может переоценить величину блочного заполнении двух ненулевых величин всегда будет ненулевым, что верно для чисел. Однако две ненулевые матрицы вполне могут иметь произведение, логически ') равное нулю. 6.2.2 Деревья, фактор-деревья и древовидные разбиения Деревом Т =(Х, Е) называется связный граф без циклов. Легко проверить, что для дерева Т выполняется соотношение ) Х) =)Е)+1 и что каждая пара различных узлов связана ровно одним путем.
Корневое дерево есть упорядоченная пара ') То есть независимо от числовых значений ненулевых злечентов перемножаем ах матриц — Прим перев. 176 Гл б Метода фактор-деревьев (г, Т), где г — выделенный узел Т, называемый корнем Так как каждая пара узлов Т связана только одним путем, то путь от г к произвольному узлу х~Х единствен. Если этот путь проходит через у, то х называется потомком у, а у — предком х. Если к тому же (х, у) ~ Е, то х — сын у, а у — отец х Если У состоит из узла у н всех потомков этого узла, то подграф Т(У) называется поддеревом дерева Т.
Заметим, что отношение предок-потомок определено только для корневых деревьев. Рис. 6.2.5 иллюстрирует введенные определения. оретто Пвдвврввв стврвва Т Дврввв т Рнс. 6,Х.Б. Корневое дерево н его поддерева Упорядочение а корневого дерева (г, Т) называется монотонным упорядочением, если каждый узел нумеруется раньше своего отца. Ясно, что корень должен быть помечен последним.
Если дерево Т не имеет корня, то упорядочение а будет монотонным, если оно монотонно для корневого дерева (а(~Х~), Т). Важность монотонно упорядоченных деревьев объясняется тем, что соответствующие им матрицы не испытывают заполнения при разложении Следующая лемма принадлежит Партеру (Раг1ег 1961). Лемма 6.2.1.
Пусть А — симметричная матрица порядка Ф, помеченный граф которой является монотонно упорядоченным деревом. Если А ЕГ, гдг .б — множитель Холгсского матрицы А, то из ач = О следцет 1„= О, 1 ) 1. Доказательство предоставляется читателю в качестве упражнения. Лемма 6.2.2. Пусть А и Š— тг жг, что и в лемме 62 ! Тогда 1ч — — ач/1п, ь ) б 178 Гл б. Методы фактор-деревьев Предположим, что А, как и прежде, разбита на р» подмат- Риц Ан, 1 ~ 61(Р, и пУсть х,о — соответствУющие подмат- рицы ее множителя Холесского»,. Предположим далее, что по- меченный фактор-граф блочной матрицы А является монотонно упорядоченным деревом (иллюстрация приведена на рис.
6.2.6). Тогда без труда проверяется аналог леммы 6.2.2 для такой блочной матрицы, именно й,д = АоС,," = (Е~~'Ан) для каждой ненулевой подматрицы Ан нижнего треугольника А. Если разбиение ф графа 6 таково, что 6/$ есть дерево, то мы называем $ древовидным разбиением 6. Мы достигли теперь той цели, какую намечали, а именно: определить, какие характеристики должна иметь блочная мат- рица, чтобы к ней были применимы идеи раздела 6.1, Ответ таков; мы хотим, чтобы ее помеченный фактор-граф был мо- нотонно упорядоченным деревом. Если это свойство имеется, то мы можем отказаться от хранения внедиагональных бло- ков Е, храня лишь ее диагональные блоки и внедиагональные блоки нижнего треугольника А.
6.2.3. Асимметричное блочное разлозсение и неявное блочное решение систем с древовидным разбиением Пусть А — матрица блочного порядка р с блоками Ан, 1 «= 61 - Р, и пУсть»,ч (ь ) !) — соответствУющие блоки Е, Если фактор-граф А является монотонно упорядоченным дере- вом, то под каждым диагональным блоком А и Е (кроме по- следнего) будет расположен ровно один ненулевой блок (по- чему?); пусть этим блоком будет Аи», ! (Й(р — 1. Алго- ритм асимметричного блочного разложения для таких задач формулируется следующим образом.
Шаг й Для й = 1, 2, ..., р — 1 выполнить следующее: 1.1) Разложить Аьь 1.2) Для каждого столбца и блока Ак и» реши ~ ь т систему А»»о = и, вычислить векгор те =А»,и»о и вычесть его из соответствующего столбца блока Аи», „. Шаг 2. Разложить А„, Процесс модификации блока А„»,и» показан на рис. 6.2,7. Заметим„что вся дополнительная память, какая нужна в алго- ритме,— это место для хранения векторов и и те, длина кото- рых равна порядку наибольшего блока.
(Вектор о можно запи- сать на место вектора и.) Конечно, можно использовать сим. метрию диагональных блоков. Неявная схема решения для таких блочных систем тоже вполне очевидна. В нашем описании 1 и 1 — промежуточные векторы, которым можно отвести одно и то же место в памяти. 6 6.2 Фактор-графы, деревья и древовидные разбаекия 176 Прямой ход неявной блочной схемы (Еу = Ь): Шаг Е Для Ь = 1,..., р — ! выполнить следуюшее: 1,1) Решить систему ЕааУь = Ьь г 1.2) Решить систему Еы1= уа. 1,3) Положить Ь -܄— Аа „1.
Шаг 2. Решить систему Еееуе = Ь.. Рис. 6.2Л. Иллюстрация к процессу асимметричного блочного разложении. Обратный ход неявной блочной схемы (Е"х = (г): т Шаг Е Решить систему Е хе=у . Шаг 2. Для Ь = р — 1, р — 2, ..., 1 выполнить следующеез 2.!) Вычислить 1=Аз «,хи„. 2,2) Решить систему Еаа1 = 1. 2.3) Положить «а — уа — 1. 2.4) Решить систему Е", х, = (г». Рис. 8.2.8 показывает этапы прямого хода блочного решения для системы блочного порядка 4. Упражнения 6.2.!. Доказать лемму 621 6.2.2. Пусть стггв = ($, д'г) — фактор-граф относительно разбиения ф дЛя Графа Занаписпня, ПОЛУЧЕННОГО НЗ 6, Н агата (й(6)т = (6), 6') — Граф !80 Гл д Методы фактор-деревьев ечвтлайнив П ~:'3 юериргилаиил Рнс.
6.2.6. Прямой ход неявной блочной схемы для системы блочного порядка 4 б б 2 Фактор-графы, деревья и древовидные разбиения 181 заполнения для 6/И Прнмер на рпс 6 2 4 показывает, что часло элементов д' может быть меньше, чем у Ю' Другими словами, блочная структура множителя Ь блочной матрицы А может быть более разреженной, чем показывает граф заполнения для фактор-графа 61ч) Показать, что если диагональные блоки ь имеют свойство распространения (см упр 2 2 3), то граф заполнения для 6(й правильно отражает блочную структуру Е То есть показать, что в атом случае д' = д' 6.2.3. Пусть д' и Л' — те же, что и в упр 622, причем граф 6 помечен, а $ = (Уь Уь, Уе) а) Доказать, что если подграфы 6(Уг), з = 1, 2,, р, связин, то я с — д*г б) Привести пример, поназывающий, что обратное утверждение может быть неверным >ь""-'"- "-"йь" е(()н) '=~ у" ~-' -- т,г-! то Ю' = д'" 6.2А.
Древовидное разбиение $ = (Уь Уз, ° °, Уь) графа 6 = (Х, Е) называется максимальным, если не существует древовидного разбиения 17 = (Еь Яз Ъ) такого, что Р «1 и длЯ каждого з спРаведливо Я, <: Уь пРи некотором й, 1 «й «р Другими словами, разбиение чз максимально, если мы не можем разбить панне-нибудь из множеств У, на части и все еще сохранить структуру фактор-дерева Предположим, что для каждой пары х, у различных узлов любого У, существуют два различных пути от х я у Х, Х!, Хз,..., Х, У и х У! Ух .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
