Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 39
Текст из файла (страница 39)
РЕЯМ. 1МУР. МВ( КБ ХВ! Кч ХЕМУ, ЮЧУЗ2Е, БМАЗК, МАЯКЕЯ, ВСИБЕТ ) АО5МСУ( ! ), !МУР ( ! ), МАЯКЕЯ( ! ) . РЕВИ(1), ЯСНЕЕТ(!). ЗМАБК(!). ХВ!.К(!) ХАО)(!), ХЕ)(У(!), В! КВЕО. ВЬКЕМО. 1, 1Р1ЯЗТ. 1МНО, К, ЕМУЗЕЕ, МВ(КЗ. НЕСМБ, мюачнп, миоаае, мове, яснзае Е 78 Об окределении етруктурм оболонки диагональнмк блоков 259 С с с с 1ОО с С с 200 с с с ЗОО С С С 400 С С С С 500 600 700 ИНИЦИАЛИЗАЦИЯ... МЕ()мя .
ХВЕК<МВЕКЯ+1) 1 ЕМУ52Е ° 1 ОО 100 1 1, МОЯ ЯМАЯК<1) . О МАЙКЕЙ<1) ° 1 СОМТ1%3Е ЦИКЛ ПО БЛОКАМ...... РО ТОО К - 1, МВСКЯ Мноягя - О ВЕКВЕО . ХВЕК<К) ВЕКЕМР - ХВЕК<К+1) - 1 РО 200 1 ВЕКВЕО, ВЕКЕ%3 МОРЕ РЕЕМ(1) МАЙКЕй(МОРЕ) 0 СОМТ1МОЕ ЦИКЛ ПО УЗЛАМ ТЕКУЩЕГО БЛОКА..... ОО 300 1 ВЕКВЕО, ВЕКЕМО МОРЕ РЕЕМ(1) САЕЕ ЙЕАСН ( МОРЕ, ХАО1, АОЗМСТ, ЯМАЯК, МАЙКЕЙ, йСНЯЕЕ, ЙСНЯЕТ(В1ХВЕО), МЕНМНР, ЙСНЯЕТ(мйоягв+1) ) МНРЯЕЕ МН052Е + МЕИЧНО 1Р1й5Т МАЙКЕЙ(МОРЕ) 1Р1Й5Т 1МУР(1Р1ЙЯТ) ХЕМУ(1) ЕЬ)У52Е ЕМУЯЕЕ ЕМУЯЕЕ + 1 — 1Р)ЙЯТ С01ЧТ1%3Е ДЛН УЗЛОВ ИЗ ОКР-СТИ ИЗМЕНИТЬ МАЙКЕИ. 1Р ( МНРЯЕЕ .ЕЕ 0 ) 60 ТО 500 РО 400 1МНР 1, МНРЯЕЕ МОРЕ ЙСНЯЕТ(1МНР) МАЙКЕй(МОРЕ) 0 СОМТ1%3Е ДЛЯ УЗЛОВ ТЕКУЩЕГО БЛОКА ИЗМЕНИТЬ ЗНАЧЕНИЯ В ИАйКЕЙ И ЯМАЯК. РО 600 1 ВЕКВЕО, ВЕКЕ)30 МОРЕ РЕЕМ(1) МАЙКЕЙ(МОРЕ) 0 5МАЯХ(МОРЕ) 1 СОМТ1%3Е О:НЧТ1МОЕ ХЕМУ( МЕ<гмя+ 1 ) ЕМУЯЕЕ ЕЬ)У52Е ЕМУЯЕЕ - 1 ЙЕТОЙМ БМ) 250 Гл. 7.
Методы параллельных сечений Работа подпрограммы начинается с установления исходных состояний для рабочих векторов ВМАБК и МАККЕК. В основном цикле последовательно обрабатываются все блоки. Узлы очередного блока добавляются к подграфу путем присвоения нулевых значений соответствующим компонентам массива МАККЕК. Для каждого узла г данного блока вызывается подпрограмма КЕАСН; узлы найденного достижимого множества будут иметь узел 1 своим первым соседом. Прежде чем перейти к обработке следующего блока, восстанавливаются прежние значения в массиве МАККЕК и узлы текущего блока добавляются к подмножеству 5.
1.3.4. Анализ временной сложности алгоритма Для произвольных блочных матриц сложность алгоритма вычисления оболочки диагональных блоков зависит от блочного порядка р, разреженности матрицы и характера связей между блоками, Однако для разбиений, полученных посредством параллельных сечений, имеется следующий результат. Теорема 1.3.5. Пусть 6 = (Х, Е), и пусть й) = (У!, ..., Уэ) — разбиение, полученное посредством параллельных сечений. Сложность алгоритма РР)ВЕ))У есть 0(!Е!).
Доказательство, Для узла х, из первых р — 1 блоков подпрограмма КЕАСН прн вызове всего лишь просматривает список смежности этого узла. С другой стороны, при обработке узлов последнего блока Уэ просматриваются не более чем по разу списки смежности всех узлов графа. Следовательно, в алгоритме в целом структура смежности проходится не более чем два раза. Упражнения 7.3.!.
Постройте пример блочной матрицы А с фактор-структурой дерева, для которой' посредством подпрограммы ГИТЕ)Ч'т' не удветси определить точную структуру оболочки блочно-диэгонзльной матрицы Вб)эд!Р), где и— матрица заполнения для А. 7.3.2. Приведите пример, доказывающий, что теорема 7.3.5 справедлива не для л1обого древовидного разбиения 3). 7.3.3. Это упражнение предполагает решение нескольких конечиоэлемент. ных матричных задач Ах = Ь порядка т! и типа, рассмотренного в й 7.!.
При этом т последовательно принимает значения 5, !О, !5, 20, з ! = 2аь Положите диагональные элементы А равными 8, внедизгоивльные') рзвнымн †! н выберите правую часть Ь таким обрвзом, чтобы все компоненты решения были рввиы единице. С помоп[ью программ главы 4 решите указанные сн- ~) Имеются в виду внедивгонвльные элементы, принздлежвшие опнсэнврй я й 7,! структуре ненулевых элементов Ыопх(А). †Пр. перев.
6 7лй Дополнительные замечания 261 стемы, записывая количество необходимой памяти и время исполнении каждой фазы решения каждой системы. Проделайте то же самое, используя приведенные в этой главе подпрограммы метода параллельных сечений вместе с соотзетствуюшими подпрограммами иэ главы. 6. Сравните оба метода решения этих коиечяоэяемеитных задач с точки зрения критериев, обсуждавшихся в 5 3 главы. 2. $7.4. Дополнительные замечания Интересно было бы испытать более сложные способы выбора параллельных сечений, Например, вместо фиксированного б МажНО бЫЛО бЫ ИСПОЛЬЗОВатЬ ПОСЛЕдОВатЕЛЬНОСтЬ бо 1= 1, 2,..., где б, определяется на основе локальной информации отой части (пз бхз 1 (ба+1) ~ (Š— бз) (ей+1) Рис.
7.4.!. Двухуровневое упорядочение посредством параллельных сечений. Здесь о~ = 2 сечений 1-го уровня, оа =- 3 сечений 2-го уровня н (о~ + 1) (от+ + 1) = 12 независимых блоков. Узлы каждого нз них нумеруютси в соответствии с их расположением на сетке, столбец за столбцом. структуры уровней, которую остается обработать после выборг первых 1 — 1 сечений. Исследования такого рода, нацеленные на получение робастного эвристического алгоритма, являются хорошей темой для курсовых н дипломных работ. Основная идея, придающая эффективность методу параллельный сечений, — зто использование приема «отбрасывания» (см. $ 6.2), Этот прием можно применять рекурснвно, как опнсано в разделе дополнительных заме ганий главы б.
Отсюда следует, что н схему параллельных сечений данной главы можно обобщить аналогичным образом. В простейшей форме идея состоит в том, чтобы использовать технику параллельных сечений н для о+1 независимых блоков вместо того, чтобы упорядочивать нх посредством алгоритма КСМ. 1знс. 7,4.1 нллюстри. рует суть этой двухуровневой схемы. 262 Гл.
и Методы нараллельныл сечений Разумеется, эту идею можно обобщить на случай большего числа уровней, Однако на практике использование более чем двух уровней, по-внднмому, не дает существенного выигрыша. Можно показать, что для сеточной и Х и задачи (тп =(= п) при оптимальном выборе п~ и пт память и число операций для двухуровневого упорядочения будут величинами порядка 0(пт~з) и 0(п'о~з) соответственно. Аналогичные цифры для обсуждавшейся в этой главе обычной (одноуровневой) схемы параллель. ных сечений — 0(пмз) и 0(нмт) (Ий!979). 8. Методы вложенных сечений $8.0 Введение В главе 7 мы познакомились с так называемым методом параллельных сечений, Мы видели, что этот метод легко приспосабливается к неявной схеме древовидного разбиения нз главы 6.
В этой главе мы рассмотрим другой метод сечений, который, так же как н алгоритм минимальной степени из главы 5, пытается минимизировать заполнение. Метод вложенных сечений этой главы предназначен главнык образом для матричных задач, возникающих в конечноразностных н конечноэлементных приложениях. Главные преимущества алгоритма нз $ 8.2 в сравнении с алгоритмом минимальной степени — это его скорость и его скромные н заранее предсказуемые требования к памяти.
Получаемые упорядочения по характеру схожи с теми, какие дает алгоритм минимальной степени. По этой причине в данной главе мы не касаемся вопросов схемы хранения, процедуры распределения памяти нли организации численных подпрограмм. Для метода вложенных сечений го. дятся соответствующие решения из главы 6 Разделители, введенные нами в $ 3.1, играют центральную роль при исследовании разреженной матричной факторизации. Пусть А — симметричная матрица, 6' — ассоциированный с ней неориентированный граф Рассмотрим разделитель 5, удаление которого разбивает граф 6" на две части, множества узлов которых суть С| и Сь Если узлы 5 нумеровать после нумерации узлов С~ и Сь то это индуцирует разбиение соответствующим образом упорядоченной матрицы, форма которогь показана на рнс. 8.0.1 Сделаем теперь ключевое замечание: нулевой блок матрицы остается нулевым н после разложения Поскольку одной нз главных целей при исследовании разреженных матричных вычислений является сохранение по возможности большего числа нулевых элементов, то использование разделителей указанным способом приобретает важное значение, При подходящем их выборе можно надеяться на получение большой подматрицы, которая гарантированно остается нулевой.
Ту же идею можно применять рекурсивно, сохраняя аналогичным образом нули в подматрицах. 284 Гл В Методы вложенных сечений Рекурсивное применение этой основной идеи приводит к методу, за которым закрепилось название метода вложенных сечений 'з, В 1973 г. Джордж использовал эту технику для рааре. женных систем, ассоциированных с регулярными (и Х и)-сетка- .4ч 0 Уч 0 47 еа ут уг Рис.
8.0Л. Использование разделителя для разбиении матрицы. мн, состоящими из (и — !)а малых элементов. В следующем параграфе мы проведем подробный анализ метода для этого специального случая. $8.1. Вложенные сечения регулярной сетки 8.!.!. Упорядочение Пусть Х вЂ” множество вершин регулярной (п Х п)-сетки, Через 5е обозначим множество узлов сеточной линии, которая делит Х на две по возможности равные части !ч' и )!з. Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
