Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 30
Текст из файла (страница 30)
верее. с Се С С С С С С С С«л ° С БСВЯООТ1МЕ РМБРАМ ( ХАОЛ, АОЛМСТ, МООЕЧЕ, МБРЛМ, 5ЕТ, г 1.ЕЧЕ1., МАОЛБ, ЛРЗБ, 1.ЕАР ) С С С 100 МОСЕ БЕ)(БЕТРТЯ) ЗБТВ) ХАОЛ(МОСЕ) С С С С С С С С С С С С Р бд Алгоритм вычисления древовидного рвзбиенил 197 РМБРЛМ ПОСТРОЕНИЕ ОБОЛОЧКИ ИСПОЛЬЗУЕТСЯ ЛИШЬ ПОДПРОГРАММОЙ ПЦТЛЕЕ . ОСНОВНАЯ ЗАДАЧА НАЙТИ ОБОЛОЧКУ ДАННОГО ПОДМНОЖЕСТВА В ПОДГРАвРЕ ЗАДАННОГО УРОВНЯ . ОПРЕДЕЛЯЕТСЯ ТАКЖЕ ПЕРЕСЕЧЕНИЕ СМЕЖНОГО МНОЖЕСТВА ОБОЛОЧКИ С НИЖНИМ УРОВНЕМ . ЕСЛИ ОБОЛОЧКА ИМЕЕТ НЕНУМЕРОВАННОГО СОСЕДА В ВЕРХНЕМ УРОВНЕЛ ТО БУДЕТ НАЙДЕН НЕНУМЕРОВАННЫЙ ЛИСТОВОЙ УЗЕЛ, ВХОДНЫЕ ПАРАМЕТРЫ " (ХАОЗ . АОЗМСУ) - СТРУКТУРА СМЕЖНОСТИ ° ).ЕЧЕ1.
- НОМЕР УРОВНЯ ТЕКУЩЕГО МНОЖЕСТВА . изттеняемые пАРАметРы " (М5РАМ, БЕТ) - ВХОДНОЕ МНОЖЕСТВО. НА ВЫХОДЕ СОДЕРЖИТ ПОЛУЧЕННУЮ ОБОЛОЧКУ, МОО1.ЧЕ - ВЕКТОР НОМЕРОВ УРОВНЕЙ. ДЛЯ ИССЛЕД-ЫХ УЗЛОВ В МООЕЧй ЗАНОСИТСЯ О. ВЫХОДНЫЕ ПАРАМЕТРЫ— (МАОЗБ, АОЛБ) - ПЕРЕСЕЧЕНИЕ СМЕЖНОГО МНОЖЕСТВА ОБОЛОЧКИ С НИЖНИМ УРОВНЕМ. БЕАР - ЕСЛИ ОБОЛОЧКА ИМЕЕТ НЕНУМЕРОВАННОГО СОСЕДА В ВЕРХНЕМ УРОВНЕ, ТО ЕЕАР— НЕНУМЕРОВАННЫЙ ЛИСТОВОЙ УЗЕЛ ' ИНАЧЕ т ЕЕАЕ = О. 1МТЕ6ЕЯ АОЛМСЧ(1), АОЛБ(1), МООРУ).(1), БЕТ(1) 1МТЕОЕЯ ХАОЗ(1), 1, Л, Л5ТОР. ЛБТЯТ, БЕАР, 1.ЕЧЕЕ, 1 ЕЧ)., ).ЧЕИ1, МАОЛБ, МВЯ, МБЯЕЧЕ, МОСЕ, 1 МБРАМ, БЕТРТЯ в лл ле ° Флле ° л е ° ° л ° Ф л * ФВ ИНИЦИАЛИЗАЦИЯ... ).ЕА1 О МАОЛ Б О БЕТРТЯ О БЕТРТЯ 5ЕТРТЯ и ) 1Р 5ЕТРТЯ ОТ М5РАМ ) ЯЕТ)ЖМ для клждоро ЧБЛА члстичной оболочки., 198 Гл б Методы фактор-деревьев 15ТОР ХА01(ЫООЕ + !) - 1 1Р ( 15ТОР .1.Т. 15ТЙТ ) 00 ТО 100 ДЛЯ КАХ(ЛОГО СОСЕДА ПРОВЕРИТЬ ЗНАЧЕНИЕ В Н001М..
ОО 500 1 15ТВТ, ЗЗТОР Ннй АОЛ4СТ(1) ННЙЬЧЬ НОР(АЧ. ( НВЙ ) 1Р (НВЙЬЧЬ !.Е 0) 00 ТО 500 1Р (НВВЬЧЬ - ЬЕЧЕЬ) 200, 300, 500 С С С 200 СОСЕД В УРОВНЕ 1ЕЧЕЬ -1 е ЗАНЕСТИ ЕГО В АОЮЗ. НАВЯЗ НА015 ь ! АО15(НА015) НВК 00 ТО 400 С С С 300 СОСЕД 8 ДАННОЕЕ УРОВНЕ, ДОЕАВИТЬ ЕГО К ОЕОЛОЧКЕ ° НЗРАЫ КЗРАН + 1 5ЕТ(НЗРАЫ) Нвй НООЬЧЬ(НВВ) 0 СОНТТНОЕ ОО ТО 100 400 500 С С С С С 500 СОСЕД В УРОВНЕ ЬЕЧЕЬ+ 1. НАЙТИ НЕНУНЕРОВАННЬИЙ ЛИСГОВОН УЗЕЛ! ПОДНИМАЯСЬ ПО СТРУКТУРЕ УРОВНЕЙ т И ДЛЯ УЗЛОВ ИЗ АОТ5 ВОССТАНОВИТЬ ИСХОДНЫЕ ЗНАЧЕНИЯ В ИООЬЧЬ.
ЬЕАР НВК $.ЧЬ ЬЕЧЕЬ + 1 15ТКТ ХАО1(1.ЕАР) 15ТОР ХА(К)(ЬЕАР41) - 1 00 800 1 15ТКТ, 15ТОР НВЙ АОЗНСТ(1) 1Р ( НООЬЧ$.(ННЙ) !.Е. ЬЧЬ ) 00 ТО 800 (.ЕАР ННЙ ЬЧЬ ЬЧЬ + 1 00 ТО 700 СОНТ1НОЕ ТР (НАШЗ ЬЕ. О) КЕТОйы ЬЧЬМ! ЬЕЧЕЬ - 1 ОО 900 1 1, НА015 НОЛЕ АО)5(1) НООЬЧЬ(НООЕ) ЬЧ(М! СОНТ1НОЕ КЕТОВН ЕНО 700 600 900 Упражнение 6.3Д. Пусть (3 (Уь Уе, ..., У,) — разбиение графа (), полученное алгоритмом нз раздела 63.!. а) Показать, что 6) — фактор.
дерево б) Доказать, что это фактор дерево максимально в смысле упр. 6 2 4 (еказание. пусть У щ $ и У ~ (ь(т); (ь(т) определено в разделе 6.3 1. Показать. что для любых двух узлов х и у из У существуют два соединяющих их е'1-1 пути — один в () ~ () Е, (т)), другой в В ~ ( ) Е((т) ), После этого исполь- 1 Е ( ВОВЗть результат упр. 6.2.4ф 4 бе Схема хранения и праяедура распределения памяти !99 9 6.4. Схема хранения и процедура распределения памяти В этом параграфе мы опишем схему хранения, специально предназначенную для блочных матричных задач, чьи фактор- графы являются монотонно упорядоченными деревьями.
Вместо внедиагональных блоков треугольного множителя Е хранятся блоки исходной матрицы А. Другими словами, используется неявная схема, описанная в конце раздела 6 2 3 6.4.1. Схема хранения Снова будем считать, что А разбита на ри подматрнц Ап, 1 ~ 1, 1( р, и пусть Ьн — соответствующие подматрицы Й, где А= Ест. Так как заранее не известно, будет ли А иметь одну из указанных ниже форм (отвечающих весьма различным фактор-деревьям) или что-то среднее между ними, то наша схема хранения должна быть очень гибкой. Определим матрицы Ам 4ы (6.4.1) 2<1с <р.
Тогда А можно представить в следующем виде, где р взято равным б. 200 ГА б, Методы дтаетор-деревьев Наша вычислительная схема требует хранения диагональных блоков (,ьь, 1 ( й ( р, и ненулевых внедиагональных блоков А. Схему хранения иллюстрирует рис. б.4.!. Диагональные блоки 1, считаются образующими блочно-диагональную матрицу, которая хранится по профильной схеме, уже описанной в разделе 4.4.1. Это значит, что диагональ хранится в массиве 1)1АО, а строки нижней оболочки — посредством пары массивов (ХЕ)чЧ, ЕЫЧ). Кроме того, для запоминания разбиения $ используется массив ХВЕК длины р+1; прн этом ХВ1К(й) указывает номер первой строки й-го диагонального блока. Для удобства мы полагаем ХВ1.К(р+1) =У+ 1.
НенУлевые элементы матРиц )те, 1 < й ( Р, хРанЯтсЯ по столбцам в едином одномерном массиве ЫО!чА, начиная с элементов е'т Для хранения строчных индексов элементов из ХОЧЕ используется параллельный целый массив МХЗПВЗ, а вектор ХИОСЕ длины А(+1 указывает начало каждого столбца в НОЯХ. Для удобства программирования полагаем ХИОСЕ(У+!)=(>+1, где т> обозначает число элементов в 1чО(чс.
Заметим, что равенство ХАРОНУ (1+ 1) = Х14ОХХ (1) означает, что соответствующий столбец Р'ь нулевой. Предположим, что ХВ1.К,(й) (1( ХВ(.К(й+ 1), и мы хотим вывести на печать столбец с номером 1 — ХВЕК(й)+ ! блока А)е, где 1'(й. Следующий фрагмент программы показывает, как это можно сделать. Предполагается, что элементы каждого столбца хранятся в ИОНЕ в порядке возрастания строчных индексов. мзткт - имаев(1> МБТОР ХИОМЕ(1ь1)-! ТР (мзтоР (.т.мзткт> со то зоо ПО 100 М - МБТКТ, МБТОР КОИ - ЬМБОВБ'(М> 1Р(кои.ьт хвьк(1» со то >оо и (кои ст хвьк(3+1» со то зоо УА(НЕ ЮЧЕ(М) ИК1ТЕ (6,3000) КОИ, ЧАЬОЕ 3000 РОКМАТ (1Х,1БИ КОИ 50ВБСК1РТ ,13,7Н РОЛЗЕ ,Р12.6) >оо сомттипе 200 СОНТТИОВ Ф 64.
Схема хранения и проиедура распределения памяти 301 Память, требуемая для векторов ХЕ)чЧ, ХВ).К, ХВОЯХ и ИЕВОВВ, должна рассматриваться как накладная (вспомните ЕНМ 1 3 3 О 3 0 0 4 ХЕНЧ Хий1с НЕЯОВЗ МОМЕ О 7 8 9 10 11 12 13 14 1 1 1 3 4 4 4 4 4 О О 9 10 Рнс. Оав!. Пример, показывающий массивы, используемые в схеме хранения фактор-дерева. наши замечания в разделе 2.3.)), так как она используется не для хранения числовых значений коэффициентов. Кроме того, для реализации процедур разложения и решения нужны некоторые рабочие массивы.
Этот аспект обсуждается в 3 6.5, где 202 Гл 6 Методье фактор-деревьев рассматриваются подпрограммы численных процедур ТЯРСТ (Тгее Яупппе1г1с гаСТогиа)1оп) и ТЬБ).'т/ (Тгее Ьушп1е1г!с Ьо).Че) . б.4.2. Внутреннее нереупорядочение блоков Описанный в $63 алгоритм упорядочения определяет древовидное разбиение связного графа. До сих пор мы предпо- / Ъ2 / / е2 / Упорядочение оет Упорядочение св2 Рис. 6.4,2.
Припер, покаэывавщий эффект внутриолочного переупорндоченин. лагали, что узлы внутри блока (или члена разбиения) помечены произвольным образом. Это, разумеется, не влияет на число ненулевых элементов исходной матрицы, расположенных вне диагональных блоков, Однако поскольку в нашей схеме хранения используется профильная структура диагональных блоков, то от способа 4 64 Схема храпения и процедура раепредеяеяия памяти 203 упорядочения узлов внутри блока может зависеть основная память для диагональной оболочки. Наша цель в этом разделе — обсудить стратегию внутреннего упорядочения и описать ее реализацию. Эта стратегия должна использовать в каждом блоке некоторую схему уменьшения оболочки/профиля. Простой и очень эффективный обратный алгоритм Катхилла — Макки (см.
раздел 4.3.1) кажется подходящим выбором. Пусть й) =(Уь Уя, ..., Уя) — заданное разбиение, определяющее монотонно упорядоченное фактор-дерево, Метод описывается следующим образом. Для каждого блока У» из $ выполнить; Шаг 1. Определить подмножество (1 = (у ~ У» )Ап) (у) () (У~ () . () У» ~) = З). Шаг 2. Переупорядочить узлы 6((1) посредством обратного алгоритма Катхилла — Макки. Шаг 3. Произвольным образом присвоить узлам У» — 0 номера, следующие за номерами 1/ Пример на рис. 6.4.2 демонстрирует эффект этого переупорядочиваюшего шага Оболочка диагональных блоков для упорядочения а~ состоит из 24 элементов, в то время как для а»вЂ” только из 1! элементов. Таким образом, переупорядочение действительно может дать существенное сокращение необходимой памяти.
Реализация этой внутриблочной схемы переупорядочения вполне очевидна. Ее выполняют две новые подпрограммы ВЯН()РЕ и 51)ВЛКСМ вместе с тремя другими, уже рассмотренными в предыдущих главах. Новые подпрограммы ниже обсуждаются подробно. Гл б А(етодм Фактор-деревьев 204 С ''''' ' ВБНОРО ....ВНУТРИБЛОЧНОЕ ПЕРЕУПОРЯДОЧЕНИЕ ° ° ° ° ИСПОЛЬЗУЕМАЯ ПОДПРОГРаММАБОВНСМ. С БОВВ01Л'1МЕ ВБНОРО ( ХАО1, АОЗМСУ, РЕНМ, МВОКБ, ХВОЕ, 1 ОМОМ, МАЕК, БОВО, ХОБ ) С С1 ° ° ° 1 ° ° 1 С С С 1Р ( МВОКБ .ОЕ.
0 ) НЕТОВН С С С С ОО 200 К 1. МВОКБ 1БТВТ ХВОЕ(К) 1БТОР ХВОЕ(К+1) - 1 ОО 100 1 15ТВТ,15ТОР МОРЕ РЕВИ(1) ОМОМ(МОВЕ) К маБК(мООе) 0 СОМТ1МОЕ СОМТ1МОЕ 100 200 С С С С С С С С С С С С С С С С С С С С С С С С С ПЕРЕУПОРЯДОЧИТЬ УЗЛЫ КАЖДОГО БЛОКА ЧТОБЫ УМЕНЬШИТЬ его ОБОлочку. узлы Блока, у кото(тых нет 00с~дей В ПРЕДЫДУЩИХ БЛОКАХ! НУМЕРУЮТСЯ ПОДПРОГРАММОЙ БОВВСМ РАНЬШЕ ОСТАЛЬЙЫХ УЗЛОВ. ВХОДНЫЕ ПАРАМЕТРЫ(ХАО1, АОЗмсх) - стРуктуРА смежнОСТи ГРАФА. (МВОКБ, ХЕ1.К ) - ДРЕВОВИДНОЕ РАЗБИЕНИЕ. ИЗМЕНЯЕМЫЙ ПАРАМЕТР— РЕВМ - ВЕКТОР ПЕРЕСТАНОВКИ.
НА ВЫХОДЕ СОДЕРЖИТ НОВУЮ ПЕРЕСТАНОВКУ. РАБОЧИЕ ВЕКТОРЫ ВММ - ХРАНИТ БЛОЧНЫЙ НОМЕР КАЖДОЙ ПЕРЕМЕННОЙ. МАЕК - ВЕКТОР ДЛЯ МАРКИРОВКИ ПОДГРАФА, НОВО - ВЕКТОР ДЛЯ НАКОПЛЕНИЯ ПОДГРАФА. ХОБ - ИНДЕКСНЫЙ ВЕКТОР ДЛЯ СТРУКТУРЫ УРОВНЕЙ. ° 11 11 ° ° ° ° ° ° 1 1МТЕОЕВ ВОЗМОГ(1), ВМОМ(1), МАЕК(1), РЕЯМ(1), 1 5ОЕО( 1), ХВОЕ(1), ХОБ(1) 1МТЕОЕН ХАО1(1), 1, 1Р, 15ТОР, 15ТВТ, 3, 1 15ТНТ, 15ТОР, К, МАЗОВ, МВ(.КБ, МВНВОК, ! МОРЕ, МБОВО ИНИКИАЛИЗАКИЯ..... НАЙТИ БЛОЧНЫЙ НОМЕР КАЖДОЙ ПЕРЕМЕННОЙ И ЙНИЦЙАЛИЗИРОВАТЬ МАЕК.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
