Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 36
Текст из файла (страница 36)
раздел 6.1.1). Покажите, что теперь число операций при разложении будет 0(г«»1), а ие 0(глзт«1). Какая рабочая память потребуется для проведения вычислений? 7.1.4. На протяжении всего $?П мы предполагали, что ш < 1, хоти нигде явно этот факт не использовался. Применимы ли наши результаты и при т ) 1? Зачем мы сделали предположение гл < Р 7.1.5. Пусть М вЂ” л Х «симметричная положительно определенная ленточная матрица с шириной ленты 3 Ф л и разложением Холесского Ет.г. Пусть У вЂ « Х г (г < и) «псевдотрехдиагональная» матрица, у которой веду.
щий ненулевой элемент столбца 1 стоит в позиции (1 — 1)(л — 1) Рг и пусть Ф = ь-г(Е-'У). Покажите, что число операций при вычислении«311, 1 < 1 < г, ~ц < 1 < «, равно приблизительно «(3+ 1) (г — 1), (Заметим, что этн элементы приближенно составлиют псевдонижннй треугольник Йг, описанный в упр. 2.2.8.) 73.6. Пусть аг минимизирует функцию 8>(п) из формулы (7.1.8). Покажите, что нижнюю границу для ог дает число йр —— 1( — ) ', причем 7 ь'/« В (др)= — оР1+21 ) 'шз?Я1. 24 чЗУ 7.1.7. В описании упорядочения (ш Х 1)-сетки посредством параллельных сечений, которое было дано в этом параграфе, разделительные блоки нумеро- вались монотонно Оказывается, что порядок нумерации этих разделительных блоков важен.
Например, блоки рнс. 7.1.2 могли бы быть пронумерованы, как указано на диаграмме. а) На рисунке, аналогичном рис. 7.1.3, покажите структуру Е, соответствующую этому упорядочению. Возрастет илн уменьшится число блоков заполнения по сравнению с рис. 7.1.2? б) Для упорядочении (шХ1)-сачки посредством параллельных сечениИ, показанного иа рис. 7.!.2, число блоков заполнения равно а — 1. Покажите, что для некоторых нумераций разделителей число блоков заполнения может достигать 2п — 3. 242 Гл.
т. Методы плреллелыеых се«гний й 7.2. Алгоритм построения параллельных сечений для задач на нерегулярных сетках 7.2.1. Алгоритм Описание и анализ предыдущего параграфа подсказывают, что и в общем случае нам следовало бы искать набор «параллельных» разделителей, состоящих из относительно немногих узлов.
Эти разделители должны разбивать граф или сетку на компоненты, которые можно было бы переупорядочить к форме с малой оболочкой. По существу, это и пытается делать излагаемый ниже эвристический алгоритм. Алгоритм оперирует с заданным графом 6 = (Х, Е), который, мы будем считать связным. Обобщение на несвязные графы очевидно. Напомним (глава 3), что множество У ~ Х называется разделителем связного графа 6, если подграф 6(Х вЂ” У) несвязен. Приведем теперь пошаговое описание алгоритма, вслед за которым даны пояснения к важным его шагам.
В этом описании У= ~Х~, а аг и 1 примерно соответствуют числам пт и 1 — 1 из $7.1. Значение о в алгоритме выбирается из условия приближенной минимизации памяти, но несложная модификация позволяет минимизировать число операций при разложении или ре. шенин. Шаг 1 (построить структуру уровней). Найти псевдопериферийный узел х посредством алгоритма раздела 4.3.2 и построить структуру уровней с корнем в х: Ю(х)(Е„Е, „... Е,). Шаг 2 (ог(гнить б).
Вычислить пе АГ/(1+1) н положить ( зм+ гз уь Шаг 3 (предельный случай). Если б(1/2 и )Х( ) бО, пе- рейти к шагу 4. В противном случае положить р = 1, Уе =Х и перейти к шагу 5. Шаг 4 (найти разделитель), Положить (=1,1= ьб+ 05~ и Т= 8. До тех пор пока 1' = 1, выполнять следующее: 4.1) Выбрать Т, = (х е= 1л ! А<Ц (х) П Тл+, чь 8). 4.2) Положить Т « — < Т и Ть 4.3) Положить 1«-е(+ 1 и 1 = ).1б + 0.5,), Шаг б (определить блоки), Взять в качестве Уе, й =1, ..., р — 1, связные компоненты подграфа 6(Х вЂ” Т); положить У Т.
Э 7.2 Алеоритм нараллельнык сечений на нерегулярных сетках 24З Шаг б (внутреннее переунорядочение). Последовательно пронумеровать узлы каждого множества У», й = 1, ,-, р, пользуясь методом раздела 6.4.2. Шаг ! алгоритма порождает (можно надеяться) длинную и узкую структуру уровней. Структура с такими свойствами желательна, поскольку разделители выбираются как подмножества некоторых уровней Ьь Вычисление чисел и и ! на шаге 2 непосредственно мотивировано анализом (нт Х 1)-сетки из $ 7.1. Так как нт †средн число узлов на уровне, оно служит мерой ширины структуры уровней.
Формула (7.!.3) для ое была получена путем весьма грубых выкладок — нашей целью в 2 7.1 было просто изложить основные идеи. Более тщательный анализ и некоторый экспериментальный опыт подсказывают, что значение лучше подходит для н'. Соответствующее значение 6* дает формула, используемая на шаге 2. Назначение шага 3 — опознавать аномальные ситуации, когда и «! или М попросту слишком мало для того, чтобы использование метода параллельных сечений имело смысл. Эксперименты показывают, что для малых конечноэлементных задач и/или задач типа «!опп з!епдег»н методы главы 4 более эффективны независимо от того, что берется за основу для сравнения В таких случаях весь граф обрабатывается как один блок (р = = 1).
Тем самым получается обычное профильное упорядочение графа, обсуждавшееся в главе 4. Действительный выбор разделителей происходит на шаге 4. Это делается по существу так же, как если бы граф соответст. вовал (нт Х 1)-сетке (см. 2 7!). Как уже отмечалось, каждый уровень т'., из Ы является разделителем тл.
На шаге 4 из Ы выбираются приблизительно равноудаленные уровни, а затем находятся подмножества этих уровней (Т,), которые все еще будут разделителями. Наконец, на шаге 6 узлы р() и+!) независимых блоков, полученных удалением разделителей из графа, нумеруются посредством (описанной в разделе 6.4.2) схемы внутреннего пере. упо ядочения. отя значение для о и метод выбора разделителей могут показаться довольно грубыми, мы обнаружили, что переход к более сложным решениям часто не дает сколько-нибудь существенного выигрыша (исключая некоторые нереалистические, специально сконструированные примеры). Как и в случае регулярной '1 То есть длинных и тонких. — Прим нерее.
244 Гк у. Методы параллельных сечений прямоугольной сетки, характер функции запросов к памяти в окрестности точки минимума мало отличается от константы. Даже сравнительно большие возмущения в значении и и выборе разделителей обычно ведут к довольно малым изменениям в количестве памяти. (а) Рис.
7.й.1. Диаграмма нерегулярной сетки, показыааьоньаа разделители, амбранные алгоритмом На рис. 7.2.! приведен пример задачи на нерегулярной сетке вместе с некоторыми указаниями шагов, выполняемых алгоритмом. (Для этой иллюстрации мы будем считать, что из алгорит. ма удален тест 1Х~) 50 на шаге 3,) Рис. 72.1(а) показывает номера уровней в исходной структуре уровней, а рис.
7.2.! (б)— узлы, выбранные для разделителей. Здесь т = 6Ь/(1+ 1) = =25/11 — 2.27, 6 =~/9.91 ж 3.12. Поэтому разделители выбираются из уровней с номерами 4 и 8. 7.2.2. Подпрограммы для аььчисления разбиения льегодом параллельных сечений Набор подпрограмм, реализующих алгоритм параллельных сечений, показан на диаграмме управления рис.
7,2.2. Подпро б 7.2. Алгоритм лараллельиых сечений иа иерееуллриык сетках 24б граммы Г1чКООТ и гсООТЬБ вместе определяют псевдопериферийный узел связной компоненты заданного графа. Они были детально разобраны в разделе 4.3.3. ВЕУКЗŠ— это служебная Рмс. 7.2.2, Огиошеииа упраалеиии между иодирограммамь а алгоритме г.арал. лсльиых сечений. подпрограмма, используемая для обращения порядка в целом массиве. Выполнение оператора вызова САЬЬ ЙЕУЙЗЕ (ИЧ, Ч) приведет к следующей перестановке компонент целого вектора Ч длины ЖЧ: У(г) ~ Ч (МЧ вЂ” г+ 1), 1 < г < 1 ИЧ/2 3.
Остальные две подпрограммы ОЕ(ч)1ЖР и Р1ч)1ьУР ниже описаны подробно. ОЕ1ч1ьУР (ОЕ11ега! 1-%ау Р(ззес11оп) Это главная подпрограмма при применении к произвольному несвязному графу метода параллельных сечений. Входные и выходные параметры в ОЕХ1'ьЧР следуют тем же обозначениям. что и в реализациях других алгоритмов упорядочения. Параметры ХЕБИБ, ХАР3 и АРЗЫС'г' описывают структуру смеж. ности заданного графа.
Выходными данными подпрограммы являются упорядочение посредством параллельных сечений, содержащееся в векторе РЕгчМ, и информация о разбиении в (1чВЬКЯ, З46 Гл. 7. Методы параллельных сечений ХВ).К). Подпрограмма ОЕМ1%0 использует три рабочих вектора: МАЕК, Х1.5 и 1 3. Пара массивов (Х18, 1.$) нужна подпрограмме Гчч!%0 для хранения структуры уровней с корнем в псевдопериферийном узле, а вектор МАЯК используется для маркировки уже пронумерованных узлов. Работа подпрограммы начинается с установления исходного состояния для массива МАЕК, при котором все узлы считаются ненумерованными, Затем просматривается граф, пока не будет найден еще не нумерованный узел й Этот узел определяет неупо. рядоченную связную компоненту графа, параллельные сечения которой вычисляет вызываемая подпрограмма Р)ч)1%0.
Множество узлов сечений образует блок разбиения. Каждая компонента в остатке рассеченного подграфа также составляет блок; этн компоненты определяются вызовом подпрограммы БООТ(,8. После того как все связные компоненты графа обработаны, подпрограмма обращает порядок в векторе перестановки РЕНМ и векторе блочного разбиения ХВ).К. Причина та, что хотя узлы параллельных сечений определяются раньше прочих узлов компоненты, они должны иметь большие номера.
с ° ° С ° ° ° ° ° ° ° СЕН)ХО ... МЕТОД ПАРАЛЛЕЛЬНЫХ СЕЧЕНИЙ ДЛЯ ее С" * "" ° "" ° ° ° ° ° ° °" П~ОИЗВОЛЬНОГО ГРАФА ° ° "»" ° ° "° ° ИСПОЛЬЗУЕМЫЕ ПОДПРОГРАММЫРм)ТЕО, ЯЕЧЯВЕ НООТЬВ. Г)ч)1%0 (Н)ч)() 1-%ау 01ззес1)оп ог()ег)пд) Эта подпрограмма применяет алгоритм параллельных сечений из раздела 7.2.1 к связной компоненте графа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
