Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 37
Текст из файла (страница 37)
Она оперирует со связной компонентой, заданной входными параметрами НООТ, с с с с с с с с с с с с с с с с с с с с ОПРЕДЕЛЯЕТ РАЗБИЕНИЕ ПРОИЗВОЛЬНОГО ГРАФА МЕТОДОМ ПАРАЛЛЕЛЬНЫХ СЕЧЕНИЙ. ДЛЯ УПОРЯДОЧЕНИЯ КАЖДОЙ СВЯЗНОЙ КОМПОНЕНТЫ ИСПОЛЬЗУЕТСЯ РМ(ЧЕО. ВХОДНЫЕ ПАРАМЕТРЫ- неона - число уРАвнениЙ. (ХАО), АО)НСТ) - СТРУКТУРА СМЕЖНОСТИ ГРАФА.
ВЫХОДНЫЕ ПАРАМЕТРЫ- (нвькз, хвьк) — нАЙденнОе РАВБиение . Реям -'упорядочение посредством ЛАРАллельных СЕЧЕНИЙ. РАБОЧИЕ ВЕКТОРЫ- мнвк - используется для мхикировки переменных, УЖЕ ПРОНУМЕРОВАННЫХ ПРИ УПОРЯДОЧЕНИИ. (ХЬЗ, ЬЗ) - СТРУКТУРА УРОВНЕЙ, ИСПОЛЬЗУЕМАЯ ЯООТЬБ. 1МТЕСЕй АОЛМСУ(!), 1.5(1) МАЯК(1) РЕЕМ(1) ХВ1.К(1). Х1.5(!) 1МТЕСЕК ХА03(1), СС512Е, 1 3, Я, ЬМОМ МВЬКЯ. МЕТЧЕ, МЬУЕ МООЕ МЕЕР МОМ, йООТ 1 1 С С С ° 1~* ° ~1 ° 1~* ° Ф ° ° Ф ° ° ° ~1 ° 00 100 1 1 МЕ(ЧМЯ МАЯК(1) 1 СОМТ1МОЕ МВЬКЯ 0 М13М 0 ОО 400 1 1, МЕОМЯ 1Р ( МАЯК(1) ЕО 0 ) СО ТО 400 ПАРАЛЛЕЛЬН.
СЕЧЕНИЯ ДЛЯ КАЖДОЙ КОМПОНЕНТЬ(, 100 йООТ 1 СА1.3. ЕМ!КО ( ВОСТ ХА01, АОЛМСУ МАЯК МЕЕР РЕВИ(М(Ы+3) МЕУС ХЬЯ ЬЯ М(ЗМ МСМ + МЯЕР МВЕКЯ МВЬКЯ + 1 ХВЬК(МВЬКЯ) МЕОМБ МСМ СС512Е ХЬЯ(МЬУЬ+3) ! С С С С С ПРОНУМЕРОВАТЬ ОСТАЛЬНЫЕ УЗЛЫ КО)ЧПОНЕНТЬ>. КАЖДАЯ КОМПОНЕНТА ОСТАВВЗЕГОСЯ ПОДГРАфА ОБРАЗУЕТ НОВЫЙ БЛОК РАЗБИЕНИЯ. ОО 200 1 1 СС512Е МОВЕ 3.5(3) 1Р ( МАЯК(МООЕ> Е(> 0 > СО ТО 500 СА>.1 ВООТЬБ ( МОВЕ ХА01 АОЛМСУ МА5К, М! 01 ХЬЯ РЕЙН(МСМч1) ) ЬМСМ МОЧ + 3 МОЧ МСМ + Х3.5(МЬУЬ~З ) 1 МВЬКЯ МВЬКЯ + 1 ХВ1.К(МВ1.КБ) МЕ()МЯ МСМ + 1 ОО 200 К ЬМСМ, МСМ МОВЕ РЕКМ(К) МАЯК(МОСЕ) 0 СОМТ1МСЕ 1Р ( МОЧ СТ МЕ(ЧМЯ > СО ТО 500 СОМТ1МОЕ СОМТ1МСЕ хотя узлы сечениЙ Опйеделяются РАМЬ>яе ЛРОчих УЗЛОВ! ИН НУЖНО ПРИСВОИТЬ Б()ЛЬ(МИЕ НОГ>ЕРА.
ВЬ)ЗОВ йеУЯБе ОБРАЩАЮВ(ей пОРЯдОк В Рейн и хВЬк, САЬ1 йЕУКЯЕ ( МЕОМЯ РЕЯМ > САЬЬ КЕУйБЕ ( МВЬКЯ ХВЬК ! ХВ1.К(МВ1.КЯ+1) МЕОМЯ ° ! ВЕТВЯМ ЕМО 200 500 400 С С С С 500 ° ° ФФФ ° Ф ° ~ ° ° ° ° ° ° ° ° ° ° ° ° ~$ ° ° ° ° ° ° ° ° ° ° 1$1$ ° ° ~~1 ° ° ° ° 14~$ ° Ф ° ° ° ° ° 3 ЯСВВООТ1МЕ СЕЛ>ХО ( МЕ!)МЯ ХАОЗ АОЛЧСУ МАЯК, 1 МВЬКЯ ХВЬК РЕЯМ. ХЬЯ Ь5 ] 1~~1 ° ~Ф 1* ° ° ° ° 1 ~ ° ° ~ ~1 1 *~ ° ° С 948 Гл.
7, Методы нараллельных сечений с- с С ° ° ° ч РМ1МО .. ПОСТРОЕНИЕ ПАИЧЛЛЕЛЬИЫХ СЕЧЕНИЙ *ч ° с ° с с с с С ВХОДНЫЕ ПАРАМЕТРЫ— С ВООТ вЂ” УЗЕЛ ЗАДАЮЩИЙ ЕВМЕСТЕ С МАВК) Ф КОМП()НЕНТУ ДЛЯ ОВРАВОГКИ. С (ХАО), АО)МСХ) — СТРУКТУРА СМЕЖНОСТИ. С С с с с с с с с С РАБОЧИЕ ПАРАМЕТРЫ— С (х(.Б, ся) — структуРА уровней, используемАЯ Рнноот. с С ПОДПРОГРАММЫ- с Рнйоот. с С ° НАХОДИТ ПАХАЛЛЕЛЬНЫЕ СЕЧЕНИЯ ДЛЯ СВЯЗНОЙ КОМПОНЕНТЫ ЗАДАННОИ МАЗК И ЛООТ.
ВЫХОДНЫЕ ПАРАМЕТРЫМБЕР - ЧИСЛО УЗЛОВ В ПАРАЛЛЕЛЬНЫХ СЕЧЕНИЯХ. ЯЕР - ВЕКТОРт СОДЕРЛ(АКЦИЙ УЗЛЫ СЕЧЕНИЙ. изменяемый пАРАметР- МАЯК - ДЛЯ УЗЛОВ СЕЧЕНИИ В МАЗК УСТАНАВЛИВАЕТСЯ ЗНАЧЕНИЕ О. с яовйопттме Ршмо ( аоот, хАО1, АО)мех, млзк, МБЕР, БЕР, МЕЧЕ, ХЕБ. ЕБ ) с с 1МТЕОЕВ АО1МСХ(1), ЕЯ(1), МАЯК(1), БЕР(1), Х1.Я(1) 1МТЕОЕй ХАО1(1), 1, 1, К, КЯТОР, КЯТВТ, 1.Р1ВЕО, ЕР1ЕМО, 1 1.че, ечевео, ечеет(О, НВВ, мече, мОРе, 1 МБЕР, ВООТ ВЕАЕ ОЕЕТР1, РМЕЧЕ, И1ОТИ МАВК, ХАР,) и АР.)МС'1'. Выходная информация подпрограммы — набор узлов сечений, описываемый парой (МВЕР, $ЕР).
Первым шагом подпрограммы является построение структуры уровней с корнем в псевдоперифернйном узле, что достигается обращением к подпрограмме ЕМКООТ. В зависимости от характеристик структуры уровней (числа уровней МЕЧЕ и средней ширины %1РТН) подпрограмма определяет нужное приращение номера уровня РЕЕТА. Если число уровней МЕЧЕ или размер компоненты слишком малы, то вся компонента передается на выход в качестве «сечения». Когда РЕ1ТА найдено, подпрограмма обходит структуру уровней, выбирая те уровни, подмножества которых образуют набор параллельных сечений. Сее ° е ° ° ° е ° е ° * САУЛ.
РМЯООТ ( ЯСОТ, ХАО), АО/МСХ. ИАВК. МЕУ(„Х$.5, 15 ) РМЕУЬ Р(Л)АТ(МЬУЬ) ИВЕР ХЕВ(МИ. + 1) - 1 М10ТЯ Р(Л)АТ(ИВЕР) / РНЕР. ОЕЕТР! ! 0 + 5!)ЯТ((3 0 Х1ОТН+13.0)/2.0) 1Р (ИБЕР .СЕ. 50 .АМО ОЕЕТР! .ЕЕ, 0.5 ОПЛЯ.) СО ТО 300 С С С С КОМ-НТА СЛИШКОМ МАЛА, ЛИБО СТР-РА УР-НЕЙ ОЧЕНЬ ДЛИННАЯ И УЗКАЯ. ПЕРЕДАТЬ НА ВЫХОД ВСЮ КОМ-НТУ. ОО 200 1 1, М5ЕР МООЕ 15(1) ВЕР(1) МОЛЕ ИАВК(МООЕ) 0 СОМТ1МСЕ ВЕТВЯМ НАЙТИ ПАРАЛЛЕЛЬНЫЕ СЕЧЕНИЯ. С 300 ИВЕР 0 1 0 1 1+ 1 АЛО. 1Р1Х (И.ОАТ(1)еОЕЕТР! + 0.6) 1Р ( ЕУЬ .СЕ.
МЕУ7 ) ЯЕТСЕМ ЕУЕВЕС ХЕВ((М.) ЕР1ВЕС ХЬВ(ЬМ. е 1) ЕУЕЕМО ЕР1ВЕС - 1 1Р!ЕМО ХЕБ(ЬУЕ + 2) - 1 ОО 500 1 ЕР!ВЕС, ЕР!ЕМО МООЕ !.5(1) ХАО)(МОСЕ) - ХАО1(МОЛЕ) ССМТ1 МОЕ 400 600 С С С С С ДЛЯ СЕЧЕНИЯ БЕРЕМ УЗЛЫ УРОВНЯ 1УЕ. В РАВД-ЛЬ ВКЛЮЧАЕМ ТОЛЬКО УЗЛЫ, ИМЕЮП(ИЕ СОСЕДЕЙ В УРОВНЕ ЕУЕ+!. ХАВУ ИСПОЛЬЗУЕМ ДЛЯ МАРК КИ УЗЛОВ УРОВНЯ Ц/(.+1 ОО 700 1 » ЕУ(ВЕС, ЕУЕЕМО МОЛЕ ЕВ()) КВТХТ ХАО1(МООЕ) КБТСР 1АВВ(ХАО)(МООЕ+1)) - 1 ВО 500 К КВТЯТ, КВТОР ИВЯ АО/МСХ(К) 1Р ( ХАО)(МВЯ) .СТ. 0 ) СО ТО 500 ИВЕР МЕЕР + 1 ВЕР(ИБЕР) МОСЕ ИАВК(МООЕ) 0 СО ТО 700 СОМТ1МОЕ СОМТ1ИОЕ 00 ВОС 1 !.Р!ВЕС, ЕР!ЕМО МООЕ ЬВ (1 ) ХАО/(ИООЕ) - ХАО)(МОСЕ) ССМТ1МСЕ СО ТО 400 ЕИО 5 72 Алгоритм параллельных сечений на нерегулярнык сеткак 249 2бо Гл, 7. Методы параллельных сечений $7.3.
Об определении структуры оболочки диагональных блоков В главе 4 изучалась структура оболочки симметричной матрицы А. Было показано, что эта структура сохраняется при симметричном разложении. Другими словами, если р' — матрица заполнения для А, то Епч(А) = Епч()т). 7.3.1 Постановка задачи Пусть разреженная симметричная матрица А разбита на блоки: Ан Аг ° ° А, А!2 '422. '42р т (7.3А) г т Ар Агр Арр Все Алл — квадратные подматрицы.
Блочной диагональю мат- рицы А при заданном разбиении называется матрица Ам (7.3,2) ЙйаК (А ) В этом параграфе мы исследуем структуру оболочки для диагональных блоков матрицы заполнения при заданном разбиении, Это важно при формировании структуры данных для схем хрднення из раздела 6.4А. б 7.8.
Об определении структура оболонки дноеональнак блокоа гб! Пусть треугольный множитель Е матрицы А разбит на блоки таким же образом: ) Еп Ерр Ер! Ер2 Тогда блочной диагональю соответствующей матрицы заполне- ния 1т будет матрица Вгг Вд!ае (Г) где Етьь=йьь+Еьь, 1(~й=.р. т Наша цель — определить структуру оболочки матрицы Вд!ад (Г). Хотя Епч(А)= Епч(Р), это равенство, .вообще говоря, не переносится на матрицы Вд!ад(А) и Вб!ад()о) вследствие того, что прн разложении вне множества Епч(Вб!ая(А)) могли появиться ненулевые элементы. 7.8,2. Характеризация оболочки блочной диагонали посредством достижимых множеств Напомним (глава 4), что структура оболочки матрицы А определяется столбцовыми индексами 1, (А) = гп!и (1! а, ~ О), 1» 1( М.
С точки зрения ассоциированного графа бл = (Хл,Ел), где Х" = (хь ..., хн), эти числа описываются формулами ~1(А)=пг!п(в)х,еиА61(х,) () (х,Ц. (7.3.3) 262 Гл. 7. Метода параллельных сечений В этом разделе мы исследуем структуру оболочки матрицы Вб»ад (Р), для чего установим связь столбцового индекса первого ненулевого элемента н со структурой соответствующего графа. Пусть 6" = (Х',Ел) и 6" = (Хе, Ее) — ненаправленные графы, ассоциированные с симметричными матрицами е» и Р соответственно. Пусть $ = (Уь Уе, ... Ур) — разбиение множества Х", отвечающее блочному разбиению е1.
Полезно отметить, что 6льь 6л (у ) 6'ее 6"'(У„) 6вжеа ж (Хл Евй е<к>) Евмее< ()(Е (У )~»~й~р) где В нижеследующем тексте мы пишем ), вместо ), (Вб»ай(Р)). Пусть строка 1 принадлежит й-му блоку разбиения. Другими словами, пусть х, ен Уе. С точки зрения графа заполнения числа(~ выражается формулой ), =ппп(з ~в=( иля (х„х1) енЕе (Уь)). Таким образом, Е содержит все узлы первых й — 1 блоков, Тогда х, е= аеас'и (хм, 5) () (хи). Доказательство, Из определения1, следует, что (х„х1,) гн Е, поэтому, по теореме 5.1.2,х ен Квас»11'х1, (х„..., х )1 Тогда 4 можно найти путь х„х,, ..., х,, х, где (х,, ..., х ) ч 1 6 Ю ~(х„..., х 1).
'1и,веьщ.— пр . р . Свяжем теперь это число с исходным графом 6", используя введенные в разделе 5.1,2 достижимые множества. Согласно теореме 5.1,2, которая характеризует заполнение в терминах достижимых множеств, имеем (, =ш»п(з ~х,ен Уь, х, ен Йеасй((х„(хо ..., х,,))()(х )), (7.3.4) В теореме 7.3.2 мы установим более сильный результат. Лемма 7.3.1.
Пусть х, ен Ум и пусть Е=у10... () 1'» н б т.д Об определении структуры оболочки диагональных блоков абй Теперь мы покажем, что х, можно достигнуть из хс также н с через 5, являюшееся подмножеством множества (х„..., хс с). Если 1=0, то ясно, что х,енсчеас)т(хс, 5). С другой стороны, Рис.
7.3.1. Б»очиая матрица А порядка 11. если 1чьО, то пусть х будет узлом с наибольшим номером г среди х, ..., х . Тогда х„х, ..., х,, х, есть путь от 'с х, к х через (х„х„..., х, с), так что ге т» > с (х„х„) ~ Е". Но г, (1ь поэтомУ„согласно опРеделению Сс ° х, чм У» или, дРУ- гимн словами, х ен 5. Из выбора г, следует (х,, ..., х,,)с5, и поточу х, ен Кеас11(хс, 5).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
