Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 38
Текст из файла (страница 38)
Теорема 7.3.2. Пусть х. ы У» и 5 = У,() ... () У» ь Тогда 1с = ппп (в! х, ~ У,, х, ен Йеастс (х„5) с) (х )). Доказательство. Если принять во внимание лемму 7.3,'с, то остается показать, что х,ее Кеасст (х>,5) для хген У» н г(сс. яб4 Гл. 7. Методы параллельных сечений Предположим, напротив, что можно найти х, ен У», для которого г 1; и х; ен Кеасп (х„5). Так как 5 с= (хо ..., х, 1), то х» ~ Кеасп (х„(хь ..., х, 1)). Поэтому (хь х,) ~ Е" (У»), что противоречит определению )ь Следствие 7.3.3.
Пусть х~ и 5 — те жг, что и в теореме 7.3.2. Тогда 1» —— гп)п (з ~х, еи Кеасй(хн 5) О(хг)). Доказательство, Это утверждение вытекает из теоремы 7.3,2 и симметрии оператора «Кеасп». Интересно сравнить полученный результат с тем, что дает (7.3А). Для иллюстрации рассмотрим блочную матрицу на рис. 7.3.1. Возьмем Уе = (хм хе, хт, хе). Соответствующее множество 5 есть (хь хь хз, х4).
Имеем Кеас)т(хы 5) =(хм, хп), Кеасп(хе, 5) =(х„хв хъ хм), КеасЬ(хт, 5) = (х„хе), Кеасн(хе, 5)=(х„хт, хм, хп). Согласно следствию 7,3.3, (е(вб(аа(Р)) =б, Хе(ВЙай (Р)) = гет (Вйад (Р)) = ~е (Вйад (Р)) = 6. 7.8Х Алгоритм и подпрограммы вычисления оболочки диагональных блоков Из следствия 7.3.3 несложно получить метод вычисления чи- сел 1, (ВЙад(Р)), которые определяют структуру оболочки мат- рицы ВЙад(Р). Однако при фактической реализации проще применять лемму 7.3.1. Соответствующий алгоритм можно опи- сать так, Пусть $= (Уь ..., Уе) — заданное разбиение.
Для каждого блока У» из разбиения выполнить следующее: Шаг 1 (инициализация). 5 = У~() ... () У» ь Т = 5() У». Шаг 2 (основной цикл). Для каждого узла х, из У» вы- полнит»п 2.1. Определить множество КеасЬ(х„5) в подграфе 0(Т). 2.2. Для каждого узла х» еи Кеасй(х„5) положить 2.3. Переопределить Т: Т е-ч Т вЂ” (КеасЬ(хт» 5)() (х,)), й 7.3. Об определении структуры оболочки диагональных блоков 2бб Этот алгоритм реализован двумя подпрограммами, обсуждаемыми ниже, КЕАСН(Впб КЕАСНаЬ)е зе(з) В графе заданы множество 5 и узел хф5. Для изучения достижимого множества КеасЬ(х,5) полезно ввести родственное понятие окрестности.
Формально окрестность узла х в мноясестве 5 определяется так: ЫьгЬб(х, 5) = (в~5 ~а достижимо из х через подмножество множества 5). Достижимые множества и окрестности связаны следующей леммой. Лемма 7.3.4. КеасЬ(х, 5) Аб)(ЫЬгЬб(х, 5)()(х)). Подпрограмма КЕАСН использует зто простое соотношение для вычисления достижимого множества в заданном лодгрофе. Подграф задается входными параметрами ХАР.), АР)Ь)С'т' и МАККЕК. Узел принадлежит подграфу, если в массиве МАККЕК ему соответствует нулевое значение. Подмножество 5 задается вектором маски АМАЯК: узел принадлежит 5, если соответствующее ему значение в массиве БМАВК не равно нулю. Переменная КРОТ вЂ” зто входной узел, чье достижимое множество нужно определить.
Вычисленное достижимое множество содержится в (КСНБХЕ, КСНЗЕТ). В качестве побочного продукта вычисляется также и окрестность, помещаемая в (ЫНРВЕЕ, Ь)ВКНР). Для узлов достижимого множества и окрестности в массиве МАККЕК устанавливается значение, равное КРОТ. После присвоения начальных значений подпрограмма циклом обходит соседей зйданного узла КОРТ. Соседи, не принадлежащие подмножеству 5, включаются в достижимое множество, а соседи из подмножества 5 — в окрестность.
Далее исследуется каждый сосед в подмножестве 5, в результате чего находятся новые достижимые узлы. Этот процесс повторяется до тех пор, пока не будут исчерпаны все соседи из 5, С ° ° ° С- ° ° ° С ° ° ° »»»»» ° ° ЙЕАСН ..... ДОСТИЖИМОЕ МНОЖЕСТВО ° '' С» ° » % С ° ° ° » ° ° ° ° ° ° »м ° С » ° ° ° ° ° ° »» ° * 1 С С» ° ° ° ° С ° ° ° ° ° ° ° Э 1 1 С С ° С ° ° ° ° 100 С С С С С В С С С С 'С С С С 'С С С С С С С С С С С С С С С С ИСПОЛЬЗУЕТСЯ ДЛЯ ОПРЕДЕЛЕНИЯ ДОСТИЖИМОГО У(НОЖЕСТВА УЗЛА У ЧЕРЕЗ ПОДМНОЖЕСТВО 3(Т,Е.
ИН-ВА ИЕАСН(У,З)) В ЗАДАННОМ ПОД(РАФЕ. ТАКЖЕ ВЫЧИСЛЯЕТ ОКРЕСТНОСТЬ У В Б, Т.Е. ИВИНО(У В), МН-ВО УЗЛОВ ИЗ В, КОТОРЫЕ МОГУТ БЫТЬ ДОСТИГН*Ы ИЗ У ЧЕРЕЗ ПОД)(Н-ВО ))Н-ВА В. ВХОДНЫЕ ПАРА)ЧЕТРЫКООТ - ЗАДАННЫЙ УЗЕЛ» НЕ ПРИНАДЛЕЖАЩИЙ В» (ХАО1, АО)МСУ) - СТРУКТУРА СМЕЖНОСТИ ГРАЧ»А, Ямазк - ВектОР ИАски для Я. кОмпОнЕнТА ЕСЛИ УЗЕЛ НЕ ПРИНАДЛЕЖИТ В, > О. ЕСЛИ УЗЕЛ ПРИНАДЛЕЖИТ Я. ВЫХОД((ЫЕ ПАРА)ЧЕТРЫ(МНОБХЕ, ИВИНО) - ОКРЕСТНОСТЬ.
(КСНЯЕЕ, йСНЯЕТ) - ДОСТИЖНУ(ОЕ (ЧНОЖЕСТВО, изненяеный ЛАРАнетР- майкей - иСПОльЗуЕтСЯ дЛЯ ЗАдАНия ЛОдГРАФА. УЗЛА)( ПОДГРАФА СООТВЕТСТВУЕТ О. ДО ВЫХОДА ЗНАЧЕНИЯ КОМПОНЕНТ ДЛЯ УЗЛОВ ДОСТИЖИМОГО Г(НОЖЕСТВА И ОКРЕСТНОСТИ ПЕРЕОПРЕДЕЛЯЮТСЯ НА ЛООТ. ЯОВИООТ1МЕ ИЕАСН ( ИООТ. ХАО), АО)МСУ, ЯМАЯК, МАККЕЙ. йСНЯХЕ, ИСНБЕТ. МН0$2$, ИВИНО ) 1МТЕОЕИ АО)МСУ(!), МАККЕЙ(1), МЯЙНО((), ЙСН$ЕТ(1). ЯМАЯК(1) 1МТЕОЕЙ ХАО1(1), 1, 1$тОР, 1$тйт, 1, 1$ТОР, ЗБТИТ, МАЙОЙ, МВИ.
МКОВЕО, МШ)РТЙ. МНО$7Е, МОРЕ, ИСН$2Е, ИООТ ИНИЦИАЛИЗАЦИЯ... МНОЯЕЕ 0 ИСНЯХЕ 0 1Р ( МАККЕЙ(ИООТ) .ОТ. 0 ) СО ТО 100 ИСН$7$ 1 ИСНЯЕТ(1) ИООТ МАККЕЙ(ИООТ) ИОСТ 1$ТИТ ХАЮ(ИОСТ) 1$ТОР ХАОЗ(ИОСТ+1) 1 1Р ( 1$ТОР .ЬТ. 1$ТИТ ) ИЕТОИМ ЦИКЛ ПО СОСЕДЯУ( УЗЛА ЯООТ.. °...... 00 600 1 1$ТЙТ, 1$ТОР НАВОИ АО)МСУ(1) 1Р ( МАККЕЙ(МАЙОЙ) МЕ, 0 ) 00 ТО 600 1Р ( ЯмАЯк(маВОИ) .От.
0 ) 00 тО 200 НАВОй НЕ ВХОДИТ В 3 ВКЛЮЧИТЬ 6 ДОСТ-МОЕ НН ВО, з 7.8. Об определении структуры оболочки диагональные блоков Ж7 НСНЗЕЕ КСНБЕЕ + нснзет(кснзхе> - мквой микка«млвок > - аоот во то воо с с с с с 200 МАВой ВХОДИТ В В И ПРЕЖДЕ МЕ РАССМАТРИВАЛСЯ, ВКЛЮЧИТЬ В ОКРЕСТНОСТЬ. НАЙТИ УЗЛЫ 1 ДОСТИЖИМЫЕ ИЗ ЙООТ ЧЕРЕЗ МАВОй. МНОБЕЕ МНОБЕЕ + 1 МВКЬО(МНОБХЕ) МАВОК МАНКЕН(МАВОй) йООТ МНОВЕО МНО52Е МНОРТй МНОБ2Е МООЕ МВЙНО(МНОРТН) ЗБТйТ ХАОЗ(МООЕ) 3БТОР ХАОЗ(МООЕ+1) - 1 ОО 500 1 лзтйт, ЗБТОР МВК АОЗМСТ(1) 1Р ( МАККЕЙ(МВй) .МЕ.
0 ) 00 ТО 500 ТР ( Бмпзк(мвй> .ео. о ) во то чоо МНОБХЕ МНОБ2Е + ! МВННО(МНОБЕЕ) МВН МАККЕЙ(МВН) НООТ 00 ТО 500 ЙСНБХЕ КСНБЕЕ е 1 КСНБЕТ(КСНБЕЕ) МВК МАККЕЙ(МВй) йООТ СОМТ1МПЕ мноРтй мнойтн + ХР ( МНОРТй ЬЕ. МНОБЕЕ ) 60 ТО 300 срмт1мпе НЕТОНМ ЕМО 300 БОО 600 Г)1)ВЕ)ч'>г (Г1(ч)(! ()!арона! В!ос)( Е)к))Ге1оре) Эта подпрограмма имеет то же назначение, что и Г)ЧТЕ1ч">7 из раздела б.4.3. Обе используются для определения структуры оболочки диагональнь>х блоков факторизованной матрицы. В отличие от Г)ч)ТЕ!ч) >> подпрограмма Г)ч)ВЕХУ находит точную структуру оболочки. Хотя она работает для произвольных блочных матриц, ее использование обходится дороже, чем Г1ч)ТЕ)ч'(7; в то же время для упорядочений, производимых алгоритмом ЩТ, структура, которую определяет Р)к)ТЕ(ч"1>, вполне удовлетворительна. Однако для алгоритма параллельных сечений применение более сложной подпрограммы Р!к>ВЕ(ЧЪ' является весьма важным.
Входные данные Р(ч(ВЕ(к))>; структура смежности (ХАШ, АШ1ЧС'1'), упорядочение (РЕКМ, 1)ч)>Р) и разбиение ()ч)В1КВ, ХВ1К) Информацию о структуре оболочки подпрограмма помещает в индексный вектор ХЕ)1))г; переменная МАХЕ)чР)Г указывает размер оболочки. Требуются три рабочих вектора. Вектор ВМАВК используется для задания узлов подмножества 5 (см. описание предыдущей 288 Гл 7 Методы нараллельнык сечений подпрограммы). С другой стороны, узлам миожес)ва Г отвечают нулевые значения в массиве МАККЕЙ Последний ис. пользуется также для временного хранения первого соседа каждой строки обрабатываемого блока. Третий рабочий вектор КСНоЕТ содержит достижимое множество и окрестность.
Так как эти два множества ие пересекаются, то вектору КСНоЕТ можно придать организацию, указанную иа рисунке. (ЧНОБЕЕ ПСНБЕЕ ВЬКВЕО С ° С ° ° ° ° ° ° РМВЕМУ ... ПОСТРОЕНИЕ ОБОЛОЧКИ ДИАГ. БЛОКОВ ° С ° С ° с с с с С С С с с с С с с с $ С Пох(ПРОГРАГ)НЫ с Я ВАСИ. НАХОДИТ ТОЧНУЮ СТРУКТУРУ ОБОЛОЧКИ ДИАГОНАЛЬНЫХ БЛОКОВ МНОЖИТЕЛЯ ХОПЕССКОГО ЛЛЯ ЛЕРЕУПОРЯДОЧЕИНОЙ БЛОЧНОЛ ПАтрицы . Входные ЛАРАметры(ХАО), АП)МСТ) - СТРУКТУРА СМЕЖНОСТИ ГРАФА.
(РЕЯМ, !МУР) - ВЕКТОРЫ ПЕРЕС!'-КИ Н ОБРАТНОЙ ВЕРЕИ-КН„ (МВЬКЗ, ХВЬК) - РАЗБИЕНИЕ. ВЫХОДНЫЕ ПАРАМЕТРЫХЕМУ - ИНДЕКСНЫЙ ВЕКТОР ОБОЛОЧКИ, ЕМУБЕЕ - РАЗМЕР ОБОЛОЧКИ. РАБОЧИЕ ПАРАМЕТРЫ БНАЯ( - МАРКИРУЕТ РАССМОТРЕННЫЙ УЗЛЫ. МАЯКЕЯ - ИСПОЛЬЗУЕТСЯ В ПЕАСН. Яснает - использУетси в ЯЙАсн. Ян)ннт доотижиный МНОЖЕСТВА И ОКРЕСТНОСТИ. Сч! ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ь ° ч ° ь ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° $ ° С' ° ° ° ° т ° ° ° О ВПВЯОПТ1МЕ 1 С ° ° ° ° ° ь ° С 1МТЕОЕВ 1 1МТЕОЕВ 1 ! С РМВЕМУ ( Х(ф) ° АО)МСТ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
