Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 16
Текст из файла (страница 16)
Тем самым (чопг(Р) не зависит от числовых значений элементов А Из предположения о неуничтожении немедленно следует, что (х)опг (А) с: Мопг (Р). Заполнение матрицы А можно теперь определить как Р11! (А) = )чопг (Р) — (х(опг (А). б ДП Симметринное риаеожение 99 ф «с «с ф «с (й) с!с ое воз*ее Ф®Е«с :и ее®е «с «Е*Е®9 «с ® Рнс. «.1.1. Пример множеств !йоис и г!!!. 5.1.1. Модель графов исключения Установим теперь связь между применением к А симметричного гауссова исключения и соответствующими изменениями в ее графе. Напомним (см. главу 2), что первый шаг алгоритма в форме внешних произведений, примененного к ст'Х Ю симметричной положительно определенной матрице А = Ае, можно описать уравнением: А ~Аоее Но рт с(, ес (5.1.1) се/Ы", ег'1' о мс 1 О щ е ~А1т ес — 1ес-! н,/4~ 9 Н, Рассмотрим, например, матрицу на рис.
5,1.1, где элементы заполнения указаны звездочкой в кружочке. Соответствующие множества здесь таковы: Хопа(А) =((1, 5), (1, 8), (2, 4), (2, 5), (3, 8), (4, 7), (5, 6), (6, 8), (8, 9)). РП1(А) =((4, 5), (5, 7), (5, 8), (6, 7), (7, 8)). В следующем разделе мы рассмотрим методы получения Р(П(А) нз 5)опх(А). ИО Гл 3 унааерсальнме раэреженнаэе метода где Н~ = Н| — 'о~п~7А, (5.1,2) 3 сновной шаг затем рекурсивно применяется к Нь На и т. д. ри обычном предположении, что точное взаимное уничтожение не имеет места, из уравнения (5.1.2) следует, что элемент (1,)г) матрицы Н1 не равен нулю, если соответствующий злемент в Н| уже отличен от нуля или если одновременно (аэ,)~чвО рве.
бпзк Графическая иллюстрация эацолвеввя в варваяте внешних врояаввцевяб и (п1)а чв О. Конечно, может выполняться и то и другое; однако, если справедливо лишь последнее, происходит заполнение. Ситуацию наглядно изображает рис. 5.1.2. После завершения первого шага разложения предстоит разложить матрицу Нь Вслед за Партером (Раг1ег 1961) и Роузом (козе 1972а) установим соответствие между преобразованием На в Н, и соответствующими изменениями в ассоциированных с ними графах. Как обычно, графы Но(= А) и Н, обозначаем через 6~' и 6~' соответственно; для удобства узел са(1), где сс — помечивание 6", индуцнрованное матрицей А, записываем как хь Теперь, как показывает пример на рис. 5.1.3, граф матрицы Н, получается из графа матрицы На.
1) удалением узла х1 и инцидентных ему ребер; 2) добавлением к графу ребер с таким расчетом, чтобы узлы из Ас(1(х,) были в 0Я' попа1эно смежными. Этот рецепт принадлежит Партеру (Раг1ег 1961). Таким образом (как отмечено Роузом), симметричное гауссово исключение можно интерпретировать как построение последовательности графов исключения 6';=6"' =(Х~,Е,"), 1=1, 2, ..., М вЂ” 1, где 0э получается из 6~ ~ а соответствии с описанной выше процедурой. Когда а известно из контекста, мы будем писать 6, вместо 6э.
Пример иа рис. 5.1.3 иллюстрирует зту операцию З од. Симметричное разложение 101 исключения вершины. Жирные линии изображают ребра, добавленные цри разложении. Например, исключение узла хз ио И2 Оф О~ члз 06 — -® О о, Де Ио Рис. 5,1.3. Последовательность грифов всключенвя в графе сгг порождает в сгз три ребра заполнения (хз,хД, (хохот и (хз,хе1, так как смежное множество хз в йг есть (хз, хо хе1. 1ОЗ Гл Д Униеерсельнне рпзреженлме методы Пусть Š— треугольный множитель матрицы А. Определим граф заполнения для 6' как симметричный граф 6" = (Хе, Е'), где Е = Е+Е'. Здесь множество ребер Е' состоит из всех ребер Е' плюс ребра, добавленные при разложении.
Очевиднд, Хе = Х". Связь между множествами ребер Ет и Е" устанавливается следующей леммой, принадлежащей Партеру (Раг1ег 1961). Ее доказательство предоставляется читателю в качестве упражнения. Лемма 5.1.1. Неупорядоченная пара (хих ) ~Е' тогда и только тогда, когда (хн х,) ~ Е" либо для некоторого й (х„хе) аи Ет и (хм х1) енЕе, причем й < ш!и (Е)). 4е чь чь 4е О + ~0+' О 'О+"" ®О "О+~ ~ О+О+О Е+ Ет 6е Рнс, 5.1.4. Граф заполнения н матрица заполнения для прнмера на рнс.
5.1.3. Понятие графа исключения позволяет интерпретировать шаги процесса исключения как последовательность преобразований графа. Кроме того, множество ребер, добавленных к графам исключения, соответствует множеству элементов заполнения. Так, для примера на рис. 5.!.3 структура соответствую. щей матрицы Р = Е+ Е' и графа заполнения 6' показана на рис. 5.!.4. Итак, мы видим, что граф заполнения 6~ легко построить по последовательности графов исключения. Построение 6" важно, поскольку им определяется структура Е. 5(ы должны знать этот граф, если намерены применить схему хранения, использующую все нули Е. 5.Е2.
Моделирование исключения посредством достижимых ланожеств В разделе 5.!.1 определена последовательность графов исключения 60- 61- " — 6н- 0 Зд. Симметричное разложение 103 и дано рекурсивное описание множества ребер Е'.
Часто бывает полезно как в теоретическом, так и вычислительном плане иметь описание 6, и Е" непосредственно через исходный граф 6", Наша пель в этом разделе — дать такое описание с помощью понятия о достижимых множествах. Прежде всего установим причину, почему в примере на рис. 8,1.3 было образовано ребро заполнения (х,, хе). В 6~ имеется путь (хю хя, хе), поэтому, когда исключается хя, возникает ребро (хь хе).
Однако в исходном графе нет ребра (хя, хе); оно образовалось из пути (х„хь х,) при исключении х~ нз 6о. Объединяя эти два замечания, видим, что за ребро заполнения (хь хе) в действительности ответствен путь (хь хм хь х,) в исходном графе. Это мотивирует Рис. ВЛ.В. Пример, иллюстрируюигиа иоиятие достижимого ииожествв. использование достижимых множеств, которые сейчас будут определены (Оеогде 1980). Пусть 5 — подмножество множества узлов, и пусть х~ 5, Говорят, что узел х достижим из узла у через 5, если существует путь (д, оь ..., ою х) из у в х такой, что р, ен5 для 1 (1 ~ й. Заметим, что й может быть нулем, так что каждый смежный с у узел, не принадлежащий 5, достижим из у через 5. Теперь можно определить достижимое множество у через 5; будем обозначать его Гхеас11 (у, 5) (х Ф 5 ~ х достижимо из у через 5).
(6.1.3) Чтобы проиллюстрировать понятие достижимого множества, рассмотрим пример на рис. 8.1.5. Если 5 =(зь ля, зв, зе), то Гхеасй(у, 5) =(а, Ь, с), !04 Гл. б. Универсальные разренгенные нетоЮм поскольку имеются следующие пути через йч (у, з„зы о), (у, 5), (у, вь с). Следующая теорема характеризует граф заполнения посредством достижимых множеств. 'Теорема 5.1.2. ЕР=((хо х!))х!~Кеас!!(х„(хо ха, ..., х, ))). доказательство. Пусть х! ~ Кеас!!(хн (х!, ..., хь !)). По определению в Ол имеется путь (х„уь ..., уь х!), такой, что Рнс.
б.!.б. Помечннанне графа, наображанного на рнс. б.!.б. уа~ (хь, х, !) для 1 (Й (!. Если 1=0 или 1=1, иуж. ный результат немедленно следует из леммы 5.1.1. Если ! ) 1, простая индукция по ! с использованием леммы 5.1.1 показывает, что (х„х,) ~ Ее. Обратно, предположим (х„х,) ~ Ее и ! = !'. Доказательство проводится иидукцией по !.
Утверждение верно при ! = 1, так как из (х„х,) еи Е" следует (х„х ) ен Е". Пусть утверждение верно для значений индекса, меньших чем ь. Если (х„ х ) еи еи Е", то доказывать нечего. В противном случае по лемме 5.1.1 найдется и, й «с ш!и(1,!), такое, что (х„хь) еюЕ" и (хь хь) ~ Е'. По индуктивному предположению в подграфе бл((хь ..., х,) ц (х„х,)) можно найти путь из х, в х„проходящий через хь. Отсюда и следует, что х! ~ Кеас!!(х,, (хо ..., х, Д). На матричном языке множество Кеас!!(х„(х!, ..., х, !)) .еоть попросту множество строчных индексов, отвечающих ненулевым компонентам столбца Ь„.
Пусть, например, граф на рис. 5.1.5 помечен так, как указано на рис. 5.1.6. Если В о1. Симметричное разложение 1ОЬ положить Я, =(хь ..., ХД, то из жества легко следует: тсеаси (х „Яи) тзеаса (х,5 ~) тчеасл (Х5,55) тсеасн (хь,о 5) тсеаси (хз.оь) тсеасй (хь 55) Аеас (хт5ь) тчеас» (хв,оз) Кемей (хч ов) определения достижимого мно- = (Хь,Х5) = (хв) = (хз,х,) = (хь.хьхв) = (хьхв) = (хв) = (хз) =Ф 6 02 0з ® О~ 05 Ф 06 ~ 0~0~07 О~ ~ О~О8 Ф О9 Рис. зл 7. более важно, что имеется удобный способ для описания (вве денных в разделе 5.1.1) графов исключения посредством достижимых тлножеств, Пусть 6о, 6ь ..., 6н — 5 — последовательность графов исключения, определяемая узлами хь хв, ..., х». Рассмотрим граф 6, = (Х„Е,).
Имеем Согласно теореме 5.1.2, структура соответствующей матрицы ( такова, как изображено иа рис. 5.1.7. Таким образом, и и описали структуру Ь непосредственно через свруктуру А. Евце 106 Гл. Б, Универсальные разреженные методы Теорема 5.1.3. Пусть у — узел в графе исключения 6; = (Хь Ет). Множество узлов, смежных с у в 6ь есть КеасЛ(у, (хи ..., хт)), еде оператор 1(еасЛ применяется к исходному графу 6о. Доказательство. Доказательство можно провести индукпией по й Обратимся снова к примеру на рис. 5.1.3. Рассмотрим графы 69 и 6з Пусть Ез = (хь хз). Ясно, что КеасЛ(хз Ез) =(хо хм хв), КеасЛ(х„Яз) =(хз хв), КеасЛ(хз, Яз) =(хз, хв) И зсеасЛ(хв оз)=(хз, хл хз), поскольку в графе'6о имеются пути (хз, хз, хз), (хз, хз, хп хз) (хз хз хт хв)' Эти достижимые множества суть в точности смежные множества графа 6з.
Теорема 5.1.3 объясняет важность той роли, какую дости. жимые множества играют в разреженном исключении, Прн за. данном графе 6 = (Х, Е) и заданной последовательности узлов хь х,, ..., хв весь пропесс исключения можно описать неявно с помопгью этой последовательности и оператора КеасЛ, Такое описание можно рассматривать как неявную модель нсклточения в противоположность явной модели, основанной на графах исключения (раздел 5.1.1). б 6.2. Машинное лргдсгазлеыиг графов исключения 107 'г?проз?ен ения 6.1.1. Пусть Ыопг(А) — пронзвольнзя зздзннзя структурз ненулевых элементов. Всегда лн можно найти матрицу А" '), такую, что соответствующая мзтрнцз ззполнення Р" имеет ндентнчные логическую н численную структуры ненулевых элементов? Объясннте евой ответ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
