Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 10
Текст из файла (страница 10)
(заполненная оболочка) Доказать, что матрица А + с.г имеет заполненную оболочку, если А!А) ( С для 2 ( С( Ас Похазатсн что о+ьг имеет заполненную оболочиу, если А — матрица с монотонныч профилем. 4.2А Пусть ь — й')с дс нижняя треугольная матрица с шириной ленты р ~ Ас, н пусть У вЂ” с)()г Р (псевдо) нижняя треугольная матрица, определенная в упр. 2 2 3 Указать приблизительное число операций, необходимых для вычисления ь-сУ. 4.2.6, Пусть (хь ..., хн) — узлы графа О", ассоциированного с симметричной матрнцей А.
Показать, что следующие условия зививалентны: а) оболочка Епч(А) заполнена; б) АсЦ((хь ..., х!)) ~ АсЦ(х!) для ! < ! (» АЦ в) О(АсЦ((хь, .., хй) ()(х!)) для 1 ~ С» Су является клииой 4.2.7. Доказать„что для связного графа О' справедливо ы,(А) ~ О для 1 ~ С ~ !У вЂ” 1. й 4.8. Профильные улорлдоченил 66 $4.3. Профильные упорядочения 4.3.1. Обратный алгоритм Катхилла — Макки Вероятно, наиболее широко используемым алгоритмом ущ. рядочення, имеющим целью уменьшение профиля, является опнсываемый виже вариант метода Катхнлла — Макки.
Опубликованный этими авторами в 1969 г. (Сп()т1П 1969) алгоритм первоначально предназначался для уменьшения ширины ленты разреженной симметричной матрицы. В основе метода — следующее замечание. Пусть у — помем ченный узел, а г — непомеченный соседу. Понятно, что, для торо Рис, 4.ЗЛ. Влияние не ширину ленты относительной нумерации смежных уе.
ловли у. чтобы уменьшить ширину ленты в строке, соответствующей х, нужно присвоить г номер, как можно менее отлнчающнйся от номера у. Рнс. 4.3.1 поясняет это замечание. Схему Катхнлла — Макки можно рассматривать как метод уменьшения ширины ленты матрицы посредством локальной минимизации чисел бь Это приводит к предположению, что схему можно использовать н для уменьшения профиля Х~~ матрнпы. Исследуя профильные методы, Джордж обнаружил (Оеогпе 1971), что упорядочение, получаемое обращением упорядочения Катхнлла — Макки, часто гораздо сильнее уменьшает профиль, чем первоначальное упорядочение, хотя ширина ленты остается нензменной.
Это упорядочение было названо обратным упорядочением Катхилла — Макки ((чСМ)'). Позднее было доказано, что обратная схема всегда не хуже прямой в отношении хранения н обработки оболочки (1ш 1975). ') От английского словосочетания — Цечегве Сцгнй — МсКее. — Прим. нерее. 66 Гл 4. Ленточные и ирофнльные методы Для связного графа алгоритм КСМ можно описать следуюИЬнм образом. (Вопрос о выборе начального узла на шаге ! разбирается в следуюшем разделе.) Шаг 1. Определить начальный узел г и выполнить присваива* нме х~ +-г.
Шаг 2 (осногной цикл). Для 1= 1, ..., )ч' найти всех ненумерованных соседей узла х, и занумеровать их в порядке возраегвния степеней. Шаг 8 (обратное упорядочение). Обратное упорядочение Катхилла — Макки есть уь уа, ..., у», где ут = хн т+1 для 1= 1, ..., У. В случае если граф бл иесвязен, описанный выше алгоритм можно применять к каждой связной компоненте графа по очереди. Если начальный узел задан, алгоритм относительно прост. Рнс.
4.3.2. Граф, к которому пряменяется алгоритм йСМ. Ненч уаданныа йггоря~кв ааараааганил оагаггалгатг й,е,Ь,У а,д Рнс. 4.3.3. Таблица, покааынаюшая нумерацию иа шаге 2 алгоритма йСМ. Рассмотрим его применение к примеру, изображенному на рис. 4.3.2. Предположим, что в качестве начального взят узел «и», т. в. хт я. На рис.-4.3,3 показано, как нумеруются узлы на 1 2 3 4 $ 6 7 $ 9 10 8 й Ь У 'л а Ы я 4.8. Про4пльвые упорядочения зт шаге 2 алгоритма. Обратное упорядочение Катхилла — Макки приведено на рис. 4.3.4; размер оболочки равен 22. Эффективность алгоритма упорядочения критическим образом зависит от выбора начального узла.
Если в нашем примере Рнс 4,3.4. Окончательное упорядочение н структура соответствующе6 мат. рицы. Рнс. 4,3.6. ДОМ-упорядоченне для графа на рнс 4.3.2 прн другом начальнпм узле. в качестве начального взять узел «а», то получим меньший профиль, равный 18. В разделе 4.3.2 будет описан алгоритм, который, как показала практика, дает хорошие начальные узлы для алгоритма Катхилла — Макки. Установим теперь грубую оценку сложности (времени исполнения) алгоритма гсСМ, считая, что начальный узел задан. 68 Гл. е. Ленточные и профильные методы В основе будет предположение, что время исполнения используемого алгоритма сортировки пропорционально числу операций. Под операцией понимается сравнение либо выборка элемента информации из структуры смежности, применяемой для хранения графа. Рис, 4.3.6. Диаграмма, показывающая эффект обращения упорядочения по сравнению с рис.
4.3.1. Теорема 4.3.1. Если для сортировки используется метод пузырька' ), то временнйя сложность алгоритма ггСМ ограничена величиной 0(т~Е)), где т — максимальная степень узла. Доказательство. Основной вклад в стоимость вносит, очевидно, шаг 2 алгоритма, поскольку шаг 3 может быть выполнен за время 0(Ф). Сортировка 1 элементов посредством метода пузырька требует сР операций, где с — некоторая константа (Апо 1974). Таким образом, общее время, затрачиваемое на сортировку, меньше, чем с 2 (Пеп(х) ~а(ст~ !Ред(х) ~=2ст~Е~.
лых л х Для каждого индекса 1 мы должны обследовать на шаге 2 соседей узла 1, выделить среди них ненумерованных и сортировать их по возрастанию степеней. Проход по структуре смежности требует 21Е( операций. Вычисление степеней узлов требует еще 2)Е~ операций. Итак, алгоритм КСМ требует не более чем 4 ~Е!+ 2сгп~(Е(+ Ф операций, где последний член отображает время, необходимое для обращения упорядочения.
') В оригинале — бпеаг!паег1юп. — Прим. перев, Э 4.8. 1Урофилзныв упорядочения 69 4,3.2. Определение начальносо узла Обратимся теперь к задаче отыскания начального узла для алгоритма КСМ. Мы выделяем эту задачу, поскольку ее решение используется еще в нескольких алгоритмах, описываемых в книге. Во всех случаях цель состоит в том, чтобы найти пару узлов, удаленных друг от друга на максимальное или почти максимальное «расстояние» (определяемое ниже). Значительный практический опыт свидетельствует, что такие узлы хороши в качестве начальных для нескольких алгоритмов упорядоче. ния, в том числе для алгоритма КСМ.
Ряс. 4.8.7. Граф О с 8 узлами, дяя которого Ь(б) 8. Напомним (см. $3.1), что путем длины й из узла хо в узел х, называется упорядоченное множество различных вершин (хо, хь ..., хя), где хз ~Аг(1(х~+~) для О =1~ а — 1. Расстояние г((х, у) между двумя узлами х и у связного графа 0 = =(Х, Е) есть просто длина кратчайшего пути, соединяющего эти узлы. Следуя Бержу (Ветре 1962), определим эхсцентриситет узла х как величину 1(х) гпах (с((х„у) ~ у е=- Х). Теперь можно ввести понятие диалзетра графа 0: б(0) шах(1(х) )х енХ), (4.3.1) или эквивалентно б(0) шах(а(х, у)1х, уевХ). Узел х~Х называется периферийным, если его эксцентрнситет равен диаметру графа, т. е.
если 1(х) = 6(0). На рис. 4.3.7 показан граф с восемью узлами, диаметр которого равен 5. При этом узлы х,, хз и хт периферийные. Теперь, когда терминология установлена, можно сформулировать цель данного раздела. Она состоит в описании эффективного эвристического алгоритма для определения узлов с большим эксцентриситетом. Подчеркнем, что алгоритм не дает гарантии, что будет найден периферийный узел или хотя бы узел, близкий к периферийному. Тем не менее получаемые узлы, как правило, имеют большой эксцентриситет и являются хорошими начальными значениями для использующих их алгоритмов. 70 Г*.
4. Ленточные и профильные методы Кроме того, исключая некоторые весьма тривиальные ситуации, нет оснований думать, что периферийные узлы сколько. нибудь лучше в качестве начальных, чем те, которые определяют данный алгоритм. Наконец, во многих случаях отыскание периферийных узлов, даже если оно желательно, представляет собой дорогостоящее предприятие, так как наилучший известный алгоритм для этой задачи имеет в качестве оценки временной сложности величину 0()Х((Е!). В большинстве разреженных матричных приложений оценку можно заменить на 0((Х(з), Ео(хз) (хе) Ез(хе) = (х»ха) (-а(хе) = (хьхз хе) Ет(хе) (хз,хт) Рнс. 4.3.8.
Структура уровней с корнем в хз для графа рнс. 4.3.7. В последующем изложении узлы, определяемые данным алгоритмом, будут называться псевдопериферийноиии. Введем теперь некоторые обозначения и терминологию, нуж. ные для описания алгоритма. Читателю, возможно, будет полезно вспомнить определения смежного множества, степени, подграфа и связной компоненты (см, 5 3.1). Основной конструкцией алгоритма является корневая структура уровней ') (Агапу 1972)з), При заданном узле х структура уровней с корнем в х есть разбиение сс (х) множества Х: Ы(х)=(Ео(х), Е,(х), ..., Еггз)(х)), (4.3.2) такое, что 1 о (х) = (х), 1.
~ (х) = Аб) (Ео (х)) Е,(х) = Аб)(Е, ,(х)) — Л, з(х), 1 = 2, 3, ..., 1(х). (4,3,3) ') В оригинале — (не гоо(еб !ече! з(гнсьнге. — Прим. нерее з) Общая структура уровней есть разбиение Я'= Е» Е» ..., ЕД, где Ад)(Ее) ~.Е» Ад)(Е!) еЕ-1 н Аб)(Е1) с=Ег-~()Ег+» г=2, 3.." ! — ! й е 8. Профильные упорядочения 11 Эксцентриситет 1(х) узла х по отношению к структуре уровней называется длиной Ы(х); ширина гс(х) структуры Ы(х) определяется как гв(х) = гпах (11., (х) 1/О (1( Е (х)). (43.4) На рис. 4.3.8 показана корневая структура уровней для графа рис.
4.3.7; корень находится в узле ха Заметим, что 1(хе) = 3 и го (ха) = 3. Рис. 4.3.9. Пример применения алгоритма поиска псеиаоперифериаиого узла, Теперь можно приступить к описанию алгоритма отыскания псевдопериферийного узла; с точностью до модификаций зто алгорктм, принадлежащий Гиббсу и соавторам (ОЕЬЬз е1 а1. 1976Ь). Объяснение, почему были введены зтн модификации, дано в работе (Оеогде, Еш 1979Ь). Если привлечь только что определенное понятие структуры уровней, то алгоритм описывается следующим образом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
