Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 28
Текст из файла (страница 28)
Уы У причем множества б= ()(2 =2))», =2, 1«г«зу, У= ()(Хема)(у, еп Е, 1«»1«»1) не пересекаются Показать, что разбиение В максимально 6.2.5. Пусть А — блочно-трехдиагональная матрица УЗ' АЗЗ 1'3 АЗ! У,' А„, 1йй Гл б Методы Фактор-деревьев где каждая Аз — заполненная квалратная матрица порядка ят, а каждая У~ — диагональная матрица а) Канава будет арифметическая работа при выполнении асимметричного блочного разложенияр Сравнить ее с работой для симметричного варианта. б) Что, если каждая подматрица Уг имеет такую форму разреженности. (') Считайте, что гл велико, и игнорируйте при подсчете числа операций младшие члены 9 6.3. Алгоритм вычисления древовидного разбиения 6.8.1.
Эвристический алгоритм з,-з()) ь,); (6.3.1) тогда Е) разбивается на подмножества У такие, что У=С,ПС, (6.3.2) где 6(С) — связная компонента Вь Рис, 6.3.2 иллюстрирует на примере простого графа эту процедуру подразбиення. Результаты $ 6.2 подсказывают, что было бы желательно найти разбиение й) = (Уь Уз,, Уз), содержащее по возможности больше членов и согласованное с требованием, чтобы 6/$ было деревом.
В этом разделе мы представим алгоритм, определяющий древовидное разбиение графа. Предлагаемый алгоритм тесно связан с понятием структуры уровней (см. $ 4.3). Поэтому мы начнем с описания соотношения между структурой уровней графа н разбиением, которое она индуцирует на соответствующей матрице. Пусть бл — непомеченный граф, ассоциированный с А, н пусть У = = (1с, 1.ь ..., 1л) — структура уровней на бл Из определения структуры уровней легко следует, что фактор-граф Ст/2' является цепью; поэтому если мы пронумеруем узлы каждого уровня 1., последовательными целыми числами, начиная с 1о и кончая (.и то уровни 2' индуцируют блочно-трехдиагональную структуру на соответствующим образом упорядоченной мат ице.
Пример показан на рис. 6.3.1. лгоритм, который будет описан в конце этого раздела, начинает работу с корневой структуры уровней и пытается затем получить более мелкое разбиение, исследуя уровни исходной структуры. Пусть 2' = (Ео, 4, ..., 1л) — корневая структура уровней, и пусть $ = (Уь Угь ..., У,) — разбиение, получаемое подразделением каждого 1.) следующим образом. Обозначим через В, подграф, определяемый формулой У б.З. Алгоритм вычисления древовидного равбиеиия !33 Рассмотрим разбиение уровня г а = (гг, е). Заметим, что Вг=0((гел, е, г, у гг, й)), и В, состоит из двух связных компонент с множествами узлов (д, г,д) и (е,(,Ь) соответственно.
Согласно (6.3.2), уровень г'.а можно разбить на (4 и (е). 1 г.б ) ь1 Рнс. 6.3Л. Блочно-трехдиагоиальное раабиение, нидуцироаанное структурой уровней, йо (а) г.1 (ь,с) ! г '. (д.е) ьг (г',Хд,г) 6/еч Рис. 6.3.2. Пример вычисления более мелкого разбиения сРпо структуре уров. ней .У. Теперь можно перейти к описанию алгоритма, находящего древовидное разбиение. В нашем описании используется определение множества ЯРА)ч)(У), где У вЂ” подмножество Х: 6 РАЯ ( У) = (х а: Х ~ существует путь от у к х для не которого у еи У.) (6.3.3) Если )' состонт из единственного узла у, то ЗРА)ч)(У) — это просто связная компонента, содержащая у.
~84 Гл. б. Методы тйактор-деревьев В алгоритме используется стек; тем самым устраняется необходимость в явном вычислении связных компонент подграфа Нрестоооразныйераф Корнебая структура уроонейй~т ) Рнс. 8.3.3. Граф, корневая структура уровней н вычисленное фактор-дерева Вь которые входят в описание (6.3.2) процедуры подразбиеиня уровней Мы считаем, что коре)сь г для исходной корневой структуры задан, Выбор г мы обсудим в этом же разделе не.
сколько позже. з б.з. Алгоритм оычаслгная древовидного разбиения !З Шаг 0 (инициализация), Очистить стек. Построить структу. ру уровней Ы'(г) = (1-о, г'.и Гм, Ь~о) с корнем в г и выбрать произвольный узел уев Ько. Положить 1=!(г) и 5== -Ф аг 7 (продвинуть стек), Если множество узлов Т на вершине стека принадлежит г.ь то вытолкнуть Т и положить 5 -5()Т.
Шаг 2 (сформировать возможный член разбиения). Определить множество У = ЯРА!ч (5) в подграфе 0((.,). Если ! ( !(г) и некоторый узел из Ай!(У)П).»»а еше не принадлежит никакому члену разбиения, то перейти к шагу 5. Шаг 3 (новый член разбиения). Поместить У в й). Шаг 4 (новый уровень). Определить множество 5 = = Ай)(У) П 1.»» и положить )ч — ! — 1. Если ! ) О, перейти к шагу 1, в противном случае — останов. Шаг б (часгично сформированный член разбиения), Поместить 5 в стек.
Выбрать у»+~ ~ Ай)(У)П»'.»+~ и найти путь у»+и у,+и, у»».г такой, что у»ы ен Ь+» и Ай)(уьы) Д г.»+»+» = И. Положить 5 = (уьы) и 1-» — (+ А затем перейти к шагу 2. Пример на рис. 6.3.3, 6.3.4, взятый из работы (Оеогде, !.!и 1978с), показывает работу алгоритма. Первоначальнаи структура уровней с корнем в узле 1 превращена в фактор-дерево с десятью узлами. При этом У» — — (20), Уз — — (18, 19), Уз = = (16), У» = (10, 15), Уз = (9, 14, 17) и Уг = (5, 11); Е,» —— = У, Ц 'У, 5, = У,'() У,'и 7.. = У', Ц У,. Чтобы закончить описание алгоритма, вычисляющего древовидное разбиение, нужно указать способ выбора корневого узла г для структуры уровней.
Мы находим г и 2'(г) посредством подпрограммы Г)»)БООТ, обсуждавшейся в разделе 4.3.3. Так как мы заинтересованы в получении разбиения с возможно большим числом членов, то, по-видимому, выбор этого способа разумен, поскольку обычно приводит к структуре, имеющей относительно много уровней. б.З 2. Подпрограммы для вычисления древовидного разбиения В этом разделе обсуждается набор подпрограмм, реализующих алгоритм вычисления фактор-дерева. Параметры 5)ЕЯЫ5, ХАР3 и АШ1)СУ, как и прежде, используются для задания структуры смежности графа, Вектор РЕЯМ на выходе содержит вычисленное древовидное упорядочение. Кроме упорядочения нужна' еше информапия о разбиении; ее дают переменная НВ) К5 и вектор ХВ).К.
При этом 5)В) К5 указывает число блоков разбиения; номера узлов конкретного блока, скажем й-го, указывают компоненты (РЕЯМ()) !ХВ).К(й)(! < ХВ).К(Й+ 1)). ~86 Гл б ~Иетоды фактор-деревьев Рве диенае Слтвл Рис. 6.3.4, Нумерация в алгоритме еычислеиия фактор дерева. О Яа (20) (18,19) (1 6) (10 15) (9,14,17) (5,11) 8,13,12, 6) Снвинов нноиваидо (18,19) (14,17) (10,15) (9,14) (6,12) (14,17) (14,17) (8,13) !66 Гл б Методы фактор-деревьев Рис. 6.3.5 демонстрирует представление древовидного упорядо.
чения для примера на рис. 6.3.3. Как видно нз этого примера, вектор ХВ).К имеет длину (ь(В).КЯ + 1. Последний, дополнительный указатель включен в РЕйм: хвше МВ$-Квс 10 Рнс. 6.3.6. Пример структуры данных для разбиения. вектор для того, чтобы блоки можно было обрабатывать единообразно, Для нашего примера, чтобы получить пятый блок, замечаем, что ХВ1.К(5) = 7, ХВ1 К(6) = 10, Следовательно, Рнс. 6.3.6. Отношения управления между подпрограммами в алгоритме вычисления фактор-дерева.
узлы этого блока задаются переменными РЕ11М(7), РЕЕМ(8) и РЕЯМ (9) . В пашем наборе семь подпрограмм, две пз которых были подробно рассмотрены в главе 4. Остановимся вначале на отношениях управления между ними, показанных на рис, 6.3.6, Подпрограммы РИКООТ и РООТ15 используются для определения псевдопериферийного узла связной компоненты заданного графа, За деталями этих двух подпрограмм мы отсылаем читателя к разделу 4.4.3. Подпрограмма СОРт81 — служебная, она попросту переносит содержимое одного целого массива в другой.
(Листинг этой подпрограммы приводится вслед за листингом КОТКЕЕ.) Теперь мы подробно опишем остальные подпрограммы этой группы. ОЕ)ч)КОТ (ОЕ)чега! Кейпеб ' Опо((еп! Тгее) Эта подпрограмма — управляю)цая при определении древовидного упорядочения для произвольного несвязного графа. Она исследует граф и вызывает подпрограмму КОТКЕЕ для нумерации узлов каждой его связной компоненты. Требуются три рабочих массива Х).о, ) 3 и )ч)ОР!.'3)!.. Пара массивов (Х) 5, ) Е) используется подпрограммой Зт)ч(!.')г).Е, чтобы получить с с. « ° » ° с"" ° ° с ° ° ° ° ° с ° ° ° ° «*« ° « ИСПОЛЬЗУЕМЫЕ ПОДПРОГРАММЫРз)ьуьз, яотяее. С» ° ° « «« ° ° ° «««« ° «« « ° « ° «* ° «« »«« « ° ° ° ° ° « ° ° ° «ььа С БОВКО)ЗГ)не вичяот ( нщчз, хлвз.
Аолчст, нвькв, хВ1.к, ) РЕЯМ, ХЬБ, ЬБ, НОВЬЧЬ ) С ° ° ° ° ««' ° ' ° ° ° ° ««« ° « ° ° ° ° ° ° »« ° ° ° ° ° ° ° ° ° ° ° ««« С ПЧТЕОЕЯ АОЛЧСТ()), ЬБ(1), НООЬ9Ь(1), РЕЯМ(1), 1 ХВЗ К(1), Х)Л(1) ТНТЕВЕЯ ХАОЗ(1), 1. ЗХЬБ, З.ЕАР, НВЗ.КБ, НЕОНБ, НЬЧЬ, 1 ЯООТ С« « ° ° ° ° ° «« ° » «« «" « « ° ° ««««« ° ° ' ° ° ° ° « ° «««« ° ° ° ') Определенне гсбпеб в названнн алгоритма указывает на то, что он почучает, вообще говоря, более мелкое разбиение, чем непь, соответствующая структуре уровней Название алгоритма мы в дальнекщем переводим как «алгоритм вычнслення рафнннрованного фактор-дерева».
— Прим, перев. с С с с с С с С С С С С с С С С с с С с с Й блс Алгоритм вычисления древовидного разбиения 1БЬ веняот .... Вычисление РАФиниРОВАннОГО ЯЧЗКТОР- ДЕРЕВА ДЛЯ ПРОНЗВОЛЬНОГО ГРАФА УПРАВЛЯЮЩАЯ ПОДПРОГРАММА ПРИ ОПРЕДЕЛЕНИИ БЛОЧНОГО упорядочения для произвольного, Быть может, НЕСВЯЗНОГО ГРАФА . ВХОДНЫЕ ПАРАМЕТРЫЗЧЩ4Б - ЧИСЛО ПЕРЕМЕННЫХ.
(хдоз, Аолчст) - стРуктуРА смежности ° ВЫХОДНЬЗЕ ПАРАМЕТРЫ(НВЗ.КБ, ХВЗ.КЗ - ДРЕВОВИДНОЕ РАЗБИЕНИЕ, РЕЯ)и " ВЕКТОР ПЕРЕСТАНОВКИ. РАБОЧИЕ ЛАРАМЕТРЫ— (ХЗ.Б, З.Б) - МАССИВЫ ДЛЯ СТРУКТУРЫ УРОВНЕЙ» Их ИСПОЛЬЗУЕТ РМНООТ, НООЬУЬ вЂ” РАБОЧИЙ ВЕКТОР ДЛЯ НОМЕРОВ УРОВНЕЙ« СООТВЕТСТВУЮЩИХ УЗЛАМ. ЕВО Гл б Методы фактор-деревьее ИНИЦИАЛИЗАЦИЙ... ОО !00 1 1, МЕОМБ мооече( 1) - 1 СОМТ1МОЕ МВЕКБ 0 ХВЕК(1) 1 100 для хлхьдОЙ связнОЙ кот1понеиты Определить кОРнеВую СТРУКТУРУ УРОВНЕЙ И ВЫЗВАТЬ ЯОГЯЕЕ ДЛЯ БЛОЧН. УПОРЯДОЧ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
