Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 13
Текст из файла (страница 13)
Подпрограмма начинает работу с того, что присваивает значение 1 всем компонентам массива МАЯК (цикл 00 100 1 =...). Затем выполняется цикл, в котором МАЯК просматривается до тех пор, пока не будет найдено 1, для которого МАЯК(!) = 1. Узел !' вместе с МАЯК, ХАШ и АШХС1' определяет связный подграф исходного графа О.
Далее происходит обращение к подпрограммам РХ)(ООТ и ЙСМ для упорядочения узлов этого подграфа. (Вспомним, что )ТСМ устанавливает нулевые значения в МАЯК для пронумерованных узлов.) Отмети!1, что переменная КОМ указывает первую свободную позицию массива РЕ)1М; ее значение изменяется после каждого обращения к 1(СМ.
Формальному параметру РЕЯМ в ЯСМ соответствует фактический параметр РЕ)ХМ()Ч()М) в ОЕХ)(СМ, тем самым массиву РЕЯМ в 1(СМ соответствуют последние ХЕ(4)ЧЯ вЂ” 1(1()М+ 1 элементов массива РЕЯМ в ОЕ)Х)КСЖ, Отметим еще, что те же элементы РЕЯМ используются в подпрограмме РМКООТ для хранения структуры уровней. Оин соответствуют массиву (.Я в списке формальных параметров этой подпрограммы. После того как очередная компонента упорядочена, возобновляется поиск следующего значения 1, для которого д 4.8. Проб»пленив упорядочения 33 МАЗК(!)Ф О.
Работа программы заканчивается, когда таких значений ! больше нет либо оказалось, что пронумерованы ХЕ(4)ч)$ узлов. Упражнения 4.3.!. Пусть граф, соответствующий заданной матрице, является н)4л сеточным графом. Йа рисунке показан случай и 5. а) Показать, что если работа обратного алгоритма Катхилла — Макки 8 начинается с углового узла, то профиль равен — пэ+ 0(пэ).
3 б) Каков будет профиль, если алгоритм начинает работу с центрального узлар 4.3.2. Привести пример, в котором узел, найденный алгоритмом раздела 4.3.2, не будет периферийным. Йайти пример большого порядка, для которого ответ х, полученный алгоритмом, будет особенно плох, например эксцентрнситет х будет меньше диаметра 0 нз значительную долю 1ХЬ Авторам не известен нн один большой пример, где время работы алгоритма было бы больше, чем 0(1Е1). Сможете ли вы найти такой пример? 4.3.3. Первоначальный алгоритм Гиббса и соавторов (01ЬЬз ег а!.
1975Ь) для отыскания псевдопериферийного узла не имел «стягивающего шага», Шаги 3 и 4 были таковы; Шаг д (сортировка последнего уровня). Упорядочить узлы в Ецо(г) по возрастанию степеней. Шаг 4 (ггсг на окончание работы). Для х ен Ецю(г) в порядке возрастания степеней построить структуры Ы'(х)=(ьэ(х), Е,(х),..., ЕИ (х)). Если !(х) ) !(г), положить г «- х и перейти к шагу 3.
Привести пример, показывающий, что время работы этого алгоритма мо. жег быть больше, чем 0()Е!). Ответьте на первые два вопроса упр. 432 по отношению к этому алгоритму. 4,3.4. Предположим, что в алгоритме раздела 4.3.1 опущен шаг 3, Угюрядочение кь хз, ..., к» называется упорядочением Кагхилла — Макки Пусть А, — матрица, упорядоченная этим алгоритмом Показать, что: а) матрица А, имеет монотонный профиль (см. упр.
4.2.2); б) в графе 6 г для 1 С!с й Аб) Дхг " кн)) ~ (хг,(А,) " кг-!) 4.3.5. Показать, что Епч(А,) = Епч(А,) тогда и только тогда, когда матрица А, имеет монотонный профиль. здесь А,— матрица, упорядоченная алгоритмом раздела 4.3 1, а А, описана в упр 434 4.3.6. Что вынуждает окончание работы алгоритма поиска псевдопериферийного узла из раздела 4.3.2? 54 Г*.
4. Ленточные и профильные методы 4.3.7. Рассмотрим симметричную положительно определенную систему уравнениИ Ал = Ь порядка Л', полученную из коиечиоэлементной сетки л Х и следующим образом. Сетка состоит из (и — 1)' малых квадратов, как показано на рис. 4.3.10 для и = 5. Узлы расположены в вершинах и на серединах сторон квадратов; с каждым узлом связана переменная хз Если каким-либо образом пометить зУ = Зп' — йп узлов графа, то соответствующая матрица А имеет такое свойство; он чь 0 тогда и только тогда, когда ассоциированные переменные х, и х, отвечают одному и тому же квадрату сетки. Пусть имеется выбор из двух упорядочений а| и аь показанных иа рис. 4 3.10. Упорядочения схожи в том отношении, что в обоих линии сетки нумеруются последовательно, одна за другой.
Различие состоит в том, что в случае а, нумеруются одновременно узлы каждой горизонтальной линии и зз зз зт зт 3 4з за 7з зз Рнс, 4.3АО. Два упорядочения а, и аз конечноэлементной сетки 5Х 5 узлы вертикальных линий, лежащие как раз нлд данной горизонталью. При упорядочении пз нумеруются одновременно узлы горизонтальной линии и лежащие прямо под ней узлы вертикальных линий Это указано на диаграммах прерывистыми линиями. а) Какова ширина ленты А для упорядочений а, и аз7 б) Предположим, что для решения системы Ах Ь при упорядочениях сз, и а, соответственно используется профильный метод.
Пусть О, и Оз — число арифметических операций в том н другом случае, П, и з)з — соответственные запросы к памяти. Показать, что для больших и О, = бп' + 0 (пз), О, - 135пз+ 0 (пз), тп -Опз+ 0 (и'), цз = 9пз + 0 (пз). Упорядочения и, и аз сходны с упорядочениями, которые порождают соответственно алгоритм КСМ и стандартный алгоритм Катхилла — Макки, Приведенные результаты иллюстрируют существенное различие в памяти н числе операпий, которое может наблюдаться для этих двух алгоритмов. Детали см.
в работе (Е1п !975). 4.3.8. (Упорядочение Кинга ] Кингом предложен (К1пп 1970) алгоритм уменьшения профиля симметричной матрицы, который в случае связного графа можно описать следующим образом. р 4.4. Реализация профильного метода дз Шаг 1 (инициализация). Определить псевдоперифервйный узел г и поло' жить х,~-г. Шаг 2 (основной цикл). Для( 1, ..., Аз — ! найти узел убмАд)((хь" ..., хй), для которого величяиа ! Ай! ((хз, ..., хг, у)) ) минимальна. Пометить узел у как хз+ь Шог 8 (выход). Упорядочение Книга есть хь х,, , хг. Этот алгоритм уменьшает профиль путем локальной минимизации ширины фронта. Реализуйте этот алгоритм для случая произвольного несвязного графа.
Проверьте свою программу на матрицах тестового множества цр! нэ главы 9. Сравните результаты этого алгоритма с результатамя алгоритма ВСМ. $4.4. Реализация профильного метода 4.4Л. Профильная схема хранения Наиболее употребительной схемой хранения в профильном методе является схема Дженнингса (Зепи(паз )966). В каждой строке матрицы хранятся все элементы от первого ненулевого до ,аы Синмвтричнэ ам аз1 азз а» ам аэз азз абз Втдп ам а з ам аы ам абб Хай зг Рнс, 4.4.1. Пример профильной схемы хранения. диагонального.
Этн отрезки строк размещены в последовательных позициях одномерного массива. Однако мы будем пользоваться модификацией этой схемы, в которой диагональные элементы хранятся отдельным вектором. Преимущесгво такого варианта в том, что ои легко приспосабливается к случаю несимметричной матрицы А; это соображение развивается в упражнении, приведенном в конце главы.
86 Гл. е. етентонные и профильные методы В схеме имеется основной массив ЕХЧ, содержащий эле. менты оболочки из всех строк матрицы. Для указания начала отрезка каждой строки используется вспомогательный индексный вектор ХЕХЧ длины Ф+ 1. Чтобы добиться единообразия при индексировании, полагаем ХЕХЧ(Ж+ 1) равным (Епч(А);+ 1. Индексный вектор ХЕХУ дает возможность удобного доступа к любому ненулевому элементу. Отображение Епч(А) на множество (1, 2, ..., (Епч(А) !) задается таким образом: ((', !) -лХЕХЧ(1+ 1) — (4 — 1). Другими словами, значение элемента аи, принадлежащего профильной области А, находится в ЕХЧ (ХЕХЧ((+1) — (( — ))).
Рис. 4.4.! иллюстрирует эту схему хранения. Пусть, например, ну)кно найти значение элемента ае4. Имеем ХЕХЧ (7) — (6 — 4) = 8, поэтому ае4 хранится в 8-м элементе вектора ЕХЧ. Чаще всего используемой операцией являемое)~ выделение профильного отрезка какой-либо строки, Это удобно делать, пользуясь следующим фрагментом: затят хенч(тном) 35ТОР ХЕЛЧ((коне)) ТР (25ТОР Ьт.батат) 00 ТО 200 по 100 ) 25тат. 35ТОР ЕЬЕИМТ ЕМЧ()) )оо самттмсе 200 Основная память в данной схеме равна 1Епч(А) (+ )Ч а накладная — У+ 1.
Структура данных для схемы хранения может быть сформирована за время 0((Е1). Эту функцию выполняет подпрограмма РХЕХЧ, обсуждаемая в следующем разделе. 4.4,2. Подпрограмма распределения памяти ГХЕХЧ (Р)Хб — ЕХЧе!оре) В этом разделе мы описываем подпрограмму ГХЕХУ. Входными данными этой подпрограммы являются граф матрицы А, хранимый парой массивов (ХАРЗ, АР3ХС')'), вектор перестановки РЕЯМ и вектор обратной перестановки 1ХЧР (см. $3.3).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
