Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 41
Текст из файла (страница 41)
узлы, указанные на рисунке.) Другими словами, в 6" имеется соединяющее их ребро. Ещв не исключенные узлы Исключенные узлы Теорема 8.1.12. Треугольный множитель матрицы, ассоциированной с (пХ Х и)-сеткой, имеет не менее 0(ит!айги) ненулевьсх элементов. 274 Гл. 8. Методы вложенных сечений Доказательство. Рассмотрим произвольную подсетку размера й. Из леммы 8.1.11 следует, что в Он имеется ребро, соединяющее пару граничных линий подсетки.
Такое ребро может отвечать, самое большее, й различным подсеткам размера й. Число всех подсеток размера й равно (п — й + 1)з. Поэтому число различных ребер указанного типа ограничено снизу величиной (и — А+ 1)з А Кроме того, для подсеток разных размеров соответствующие ребра должны быть различны. Отсюда следует, что и 1Е ~)~ ( А+ ) х)од А ! Упражнения 8.1Л.
Пусть А — матрица, ассоциированная с (и Х п)-сеткой, которая упорядочена по одноуровневой схеме сечений. Показать, что: а) число операций при выполнении симметричного разложения равно (13/24)п' + 0 (пз) б) число ненулевых элементов множителя Е равно п'+ 0(п'). 8.1.2. Доказать формулы для решений разностных уравнений из лемм 8.1.! — 8,1.3 и 8,1.5 — 8.1.7. 8.1.3. При выводе уравнения (8.1.8) для О(п, 2) мы предполагалн, что крестообразный разделитель упорядочен в соответствии с рксунком (а).
Обо. значим через О'(и, 2) аналогичное число при использовании упорядочения (б). (а) Показать, что О'(и, 2) = О' (п/2, 2) + 28 (п/2, 3) + О (и/2, 4) + 125пз/24 -1- 0 (пз). Сравнить числа О(п, 2) и О'(и, 2). 8.1.4. Доказать утверждения, аналогичные теоремам ОЛ.4 н 8.1.8, для произвольной (гп Х !)-сетки, где гп велико и гп ( !. 8.1.5. Доказать, что любому упорядочению сетки и Х и отвечает матрица, ширина ленты которой не меньше и — 1. 8.1,8. Рассмотрим сетку п Х п.
Известно, что ассоциированный граф 0 (Х, Е) удовлетворяет изопарамегрическому неравенству: для произвольного подмножества 3 такого, что (В( ~ пз/2, справедливо 1 Аб) (Я) 1)~ 1 8 1 !'. Доказатзь что нри любом упорядочении 0 профиль не будет меззьше, чем 0 (п'), Э 8.2, Вложенные сечения для произвольных задач 27$ 8.!.7. Предположим, что для сеточной (» хс «)-задача выполняется «неполный алгоритм вложенных сечсннй» !Оеогяе е1 а). !9?8с). Эго значит, что производятся лишь сечения ! уровней, где ! «.!оя«л, а остающиеся нез«внснмые сеточные массивы упорядочиваются построчно. Поназать, что прн ! ~»)оях Ч/и число операпнй для гакого упорядочения остается величиной О(п»). Поназать, что число ненулевых элементов соответствующего множителя Ь равно О (лт ч/и). 8.1.8.
Используя метод, прнналлежащнй штрассену (5!газзеп !969) н обобщенный Банчем н Допкрофтом (Бппсь, Норсгон 1974), можно решать заполненные системы лнпейных ураввеннй н перемножать две заполненные матрнпы порядка гл за О (ш'~к' ) операннй. На основе этого результата н моди. !ояг г' фнпнруя леммы 8.1.5 — 8.1.7, показать, что сеточные (п )с л) -задачн можно решать, пользуясь методом вложенных сечений, за О(п'"к'т) операпнй (йозе 1976Ь) й 8.2. Вложенные сечения для произвольных задач 8.2.1, Эвристический алгоритм Оптимальность метода вложенных сечений для сеточной (и Х и)-задачи была установлена в предыдущем разделе, Очевидна важность основной идеи: деления сетки на две части приблизительно одинакового размера посредством малого разделителя.
В этом разделе мы опишем эвристический алгоритм, который применяет эту стратегию к упорядочению произвольного графа. Как найти малый разделитель, который разбивал бы заданный граф на компоненты примерно одинакового размера? Наш метод состоит в построении для графа длинной структуры уровней и выборе малого разделителя из «среднего» уровня. Пусть б = (Х, Е) — заданный граф.
Алгоритм упорядочения посредством сечений можно описать так. Шаг 1 (инициализация), Положить )? = Х, М = )Х!. Шаг 2 (построить структуру уровней). Найти в б(й) связную компоненту б(С) и построить для нее структуру уровней с корнем в псевдопернферийном узле г: оа(г) = Ро* Е! ° ° г Е!) Шаг 3 (найти разделитель). Если 1( 2, положить 5 = С и перейти к шагу 4. В противном случае положить ! = ((1+ + 1)/2) и определить множество 5 с: Е! такое, что 5=(у ен 1!) Ад) (у)() Е!») чь З). Шаг 4 (упорядочение разделителя и цикл) Пронумеровать узлы разделителя 5 числами от гт' — 15~ + 1 до ?т1, Положить )? — )? — 5 и Ф -Ж вЂ” !5 ~.
Если )? ~ 8, перейти к шагу 2. На шаге 3 алгоритма разделитель 5 можно получить простым отбрасыванием тех узлов из (н которые не смежны ни с лта Гл 8 Метода нложеннеех сеченой одним узлом из Е,+ь Во многих случаях это уменьшает размер разделителя и. 8.2.2. Машинная реализация Набор подпрограмм, реализующих алгоритм упорядочения посредством вложенных сечений, показан на рисунке. Подпрограммы Р!)ГРООТ и ГРООТ).Я описаны в разделе 4.3.3, а служебная подпрограмма цЕЧ)сЯŠ— в разделе 7.2.2.
Остальные две подпрограммы описываются ниже. ОЕХ)нР(ЙЕХега! )ч(ез(еб Огазес((оп огбег(пи) Это — ведущая подпрограмма набора. Она используется для упорядочения произвольного несвязного графа методом вложенных сечений, Входной граф задается посредством ЫЕЯ)ЦЯ и (ХА(лз, АВАНСУ); выходное упорядочение хранится вектором РЕКМ. Рабочий вектор МАЯК используется для маркировки узлов, которые уже пронумерованы в процессе упорядочения, Нужны еще два рабочих вектора (ХЕЯ, 1Я); оии используются вызываемой подпрограммой Р!)РЯЕР. Работа подпрограммы начинается с установления начального состояния для вектора МАЯК.
Затем обходится граф, пока не будет найден еще не нумерованный узел й Этот узел ( определяет компоненту в неупорядоченной части графа. Далее происходит обращение к подпрограмме Р(нРЯЕР, которая находит разделитель для компоненты. Заметим, что разделитель помещается в вектор РЕЕМ, начиная с позиции ИБМ+ !. Поэтому после нумерации всех узлов для получения окончательного упорядочения необходимо обратить порядок компонент в векторе РЕЕМ. И По сравнению с !еч!.— Прим нерее.
С ° С ° С ° ° ° Ф Ф ° 6ЕММО ... АЛГОРИТМ ВЛОЖЕННЫХ СЕЧЕНИЙ ДЛЯ ° ° С ° ° ° ° ° Ф ° ° ° ° Ф ° ° ° 1 ° 1 ° ПРОИЗВОЛЬНОГО ГРАИФА ° ° ° ° 11 ° 1111 С ° ° * ° ° Ф 11 ° Ф Ф1 ° ФФ ° ПОДПРОГРАННЫРМ))ЗЕР ЕЕУЕЗЕ С ° ° ° 1 ° ° 1 ° 111 ° 11 ° 1 ° 1 ° Ф ° 1 ° С ЗСВЕОСТ1МЕ ОЕММО ( МЕОМЗ, ХАО), Ао)МСУ, ИАЗК, 1 РЕЯМ, ХЬЗ, ЬЗ ) С С ° ° 1 ° ° ° ° ° Ф ° ° 11 ° ° Ф ° ° ° ° 11 ° 1 ° 1 ° Ф ° 1 ° ° С 1МТЕОЕЕ АО)МСУ(1), ИАЗК(1), 3.6(1), РЕКИ(1), 1 Х) З(1) 1МТЕОЕЕ ХАО)(1), 1, МЕОМЗ, МЕЕР, МОИ, ЕООТ С СФФФФ ° ° ° ° ° ° ° ° ° Ф ° ° Ф ° ° 1 ° ° 1 ° ° ° 1 ° 1 ° ° Ф ° ° ° ° ° Ф ° ° С 00 100 1 1, МЕ()МЗ ИАЗК(1) 1 СОМТ1 МОЕ Мои 0 00 200 1 1, МЕ3)МЗ 100 С С С 200 С С С 200 С С С С С 400 САЫ.
ЕЕУЕЗЕ ( МЕОМЗ, РЕЕМ ) ВЕП)ЕМ ЕМО С С С С С С С С С С С С С С С С С С С С С ° ° ° ° Ф ° 1* ° Ф ° ° *1 ° 11 ° 111 1 Ф ° 1 ° 11 ° ° Ф ° Ф ° 1 ° Ф ° ° ° 1 1 ° 1 111 ° ° ° ° Ф 1* ° ° 1 ° 11 ° ° Ф ° Ф 111 ° ° 11 НАХОДИТ УПОРЯДОЧЕНИЕ ПРОИЗВОЛЬНОГО ГРАФА МЕТОДОМ ВЛОЖЕННЫХ СЕЧЕННИ ° ВХОДНЫЕ ПАРАНЕТРЬ)- МЕ))МЕ - ЧИСЛО УРАВИЕНИй. (ХАО), АО)МСТ) - СТРУКТУРА СМЕЖНОСТИ ГРАФА. ВЫХОДНЫЕ ПАРАНЕТРЫРЕВМ - УПОРЯДОЧЕНИЕ ПОСРЕДСТВОМ ВЛОЖЕННЫХ СЕЧЕНИЙ.
РАБОЧИЕ ПАРАНЕТРЫ- ИАЗК вЂ” ИСПОЛЬЗУЕТСЯ ДЛЯ МАРКИРОВКИ ПЕРЕНЕННЫХФ ПРОНУМЕРОВАННЫХ ПРИ УПОРЯДОЧЕНИИ. (Х(.З, 1$) - ЗТА ПАРА ИСПОЛЬЗУЕТСЯ В РМЯООТ ДЛЯ ВРЕМЕННОГО ХРАНЕНИЯ СТРУКТУРЫ УРОВНЕЙ ДЛЯ КАЖДой НАРКИРОВАННОй КОМПОНЕНТЫ... 1г ( НАзк(1) .ХО. о ) оо то зоо ЕООТ 1 МАЛТИ РАЗЯ-ЛЬ.
ПРИСВ. УЗЛАМ ОЧЕРЕДИЬ(Е НОНа Л. САЬЬ РМГОЕР ( ВОЮТ, ХАО), АО)МСТ, ИАЗК, МЕЕР, РЕКИ(М(Б(Ф)), Х3.$, ЬЗ ) М(Б( Мои Ф МЕЕР 1Р ( М(3М .6Е. МЕОМЗ ) 60 ТО 400 60 ТО 200 СОМТ1 МОЕ Т.К. ПОРЯДОК ° В К-РОН ОПРЕДЕ)(ЯЮТСЯ РАЗДЕЛИТЕЛИ ОБРАТЕН ИХ ПОРЯДКУ В ИСКОНОЛ СТР-РЕФ ТО ВЫЗЫВАЕТСЯ ЙЕУЯЕЕ Ф ОБРИН,АЮШАЯ УПОРЯДОЧЕНИЕ РЕЯМ. ЗТВ Гл 8 Методы вложенных сеченов г(ч(лЬЕР (Рм (О ЬЕРага!ог) с ° с ° ° ° с ° НАИтн РАЗДЕЛИТЕЛЬ ° ° ° ЕМОЯЕР с с использтется для опяеделения мялого Ркзделителя С В СВЯЗНОЙ КОМПОНЕНТЕ ЗАДАННОГО ГРАФА ч с укАзыВАемоЙ посРедстВом НАзк.
с С ВХОДНЫЕ ПАРАМЕТРЫ- с йоот - узел ОпРеделяющий мАРкиРОВАнную с компоненту. с (хАО), Апзмст) - стРуктуРА сме)кности ГРАФА. с С ВЫХОДНЫЕ ПАРАМЕТРЫ- с маей - число пеяеменных В РАзделителе, с Яе - некто~, содеРЛ(Ащиа узлы РАзделителя. с с изменйемыЙ ЛАРАметР с МАЯК - ДЛЯ УЗЛОВ РАЗДЕЛИТЕЛЯ В МАВК с УСТАНАВЛИВАЕТСЯ О. с С РАБОЧИЕ ПАРАМЕТРЫ- с (ХЕЯ, ьз) - ПАРА ДЛЯ ХРАНЕНИЯ СТРУКТУРЫ УРОВНЕЙ» с нАЙденнОЙ Рняоот. с С ПОДПРОГРАМНЫ- с емйсот с с ° ° ° " * ° ° ° ° ° ° ° * ° ° ° ° ° ° ° ° ° * с ЯОВКООТ1ме емО5еР ( аоот, хАО1, АО)мсч, мл5к, 1 МЕЕР, 5ЕР, ХЬЯ , ЬЯ ) с С»» ° чч ч * ° * С 1мтесей АО)мст(1), ЕЯ(1), мАяк(1), 5еР(1), хьз(1) 1мтесей хАО1(1), 1.
1, )ятоР, 1ятйт, м!овес, 1 М1ОЕМО, М1ОЬЧШ МР!ВЕС, МР! ЕМО, 1 Мвй, МЕЧЕ, МОСЕ, М5ЕР, ЕООТ С С«чччч ° чч ч*ч ° ч *ч ч * Эта подпрограмма используется в ОЕИ)ч(Р для поиска разделителя в связном подграфе. Связная компонента задается входными параметрами )чООТ, ХАО), АРЛч)СУ и МАЬК. Найденный разделитель хранится парой ((ч(ЬЕР, ЬЕР). Пара массивов (ХЕЬ, ЕЬ) используется для хранения структуры уровней компоненты.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
