Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 19
Текст из файла (страница 19)
4.2.3. В идеале мы хотели бы найти перестановку Р*, которая бы минимизировала размер структуры ненулевых элементов матрицы заполнения: ( 5(опг (Р (Р'АР')) ~ = ш(п! 5!опг (Р (РАРт)) ~ До сих пор нет эффективного алгоритма для отыскания такой оптимальной Р* в случае произвольной симметричной матрицы. Рис. З.З.1. Мотивировка алгоритме минимальной степени. Аналогичная задача для случая несимметричной А, как было показано, очень трудна и принадлежит классу так называемых ХР-полных задач (Козе 1975). Поэтому приходится прибегать к эвристическим алгоритмам, которые бы давали упорядочение с приемлемо малой, хотя и не обязательно минимальной величиной ~Хопг(Р(РАРт)) ~.
Бесспорно, самой популярной схемой уменьшения заполнения среди используемых является алгоритм минимальной степени (Т!ппеу 1969), которому в случае несимметричных матриц соответствует схема Марковица (Маг(сото!!г 1957), В основе алгоритма — следующее наблюдение, иллюстрируемое рис.5.3.1. Пусть помечены узлы (хь ..., х, ). Число ненулевых элементов в этих столбцах графа заполнения в дальнейшем не меняется.
Ясно, что для уменьшения числа ненулевых элементов рго столбца') в еще не факторизованной подматрице иа место 1-го столбца нужно перевести столбец с наименьшим т) В графе заполнения. — Прим. нерее. й Д8. Алгоритм минимальной степени 121 числом ненулевых элементов. Другими словами, схему можно рассматривать как метод уменьшения заполненности путем локальной минимизации чисел т1(Е.,) для разлагаемойматрицы. 5.8.1.
Основной алгоритм Легче всего алгоритм минимальной степени описать в терминах упорядочения симметричного графа. Пусть 6,= (Х, Е)— непомеченный граф. Используя модель графов исключения, можно изложить основной алгоритм следующим образом. Рис. 5.3.2, упорядочение графа алгоритмом минимальной степени. Шаг 1 (инициализация). г — 1. Шаг 2 (выбор минимальной степени). В графе исключения 6; 1 =(Х, ь Е, 1) выбрать узел хь имеющий в 6,, минимальную степень. Шаг 3 (пргобразоааниг грагра), Построить мовый граф исключения 6; = (Хг, Е;), исключая из 6, 1 узел х,. Шаг 4 (цикл или остановка). 1н — 1+ 1.
Если 1) ~Х~)— остановка, В противном случае перейти к шагу 2. В качестве иллюстрации алгоритма рассмотрим граф на рис. 5.3,2. Рнс, 5.3.3 показывает шаг за шагом работу алгоритма минимальной степени. Отметим, что на отдельных шагах может быть несколько узлов с минимальной степенью.
В этом примере мы выбираем произвольный нз таких узлов. Однако различные стратегии выбора в подобной ситуации неоднозначности дают разные варианты алгоритма минимальной степени. 5.3.2. Описание алгоритма минимальной степени посредством достижимых множеств Использование графов исключения в алгоритме минимальной степени дает механизм, с помощью которого мы выбираем для нумерации следующий узел. Каждый шаг связан с преобразованием графа, что является с точки зрения реализации 122 Гл.
б. етнпаереолвные роаресеенные методы Рис. 3.3.3, Нумерация а алторитме мииималаиой степеии. Гррр исиаочвяия О; 1 атыбраттттые7 .сзв т Мини осадная свтвттвиь Э б.д Алгоритм минимальной степени 123 наиболее дорогостоящей частью алгоритма. Этих преобразований можно было бы избежать, если бы мы располагали другим способом вычисления степеней узлов ь графе исключения. Теорема 5.!.3 дает средство для этого, состоящее в использовании достижимых множеств.
С нх помощью алгоритм минимальной степени можно переформулировать следующим образом. Шаг 1 (инициализация), 5-к- И. Для х ~ Х положить Ред(х) — ) Аб) (х) ). Шаг 2 (выбор минимальной степени). Выбрать узел уев ~ Х вЂ” 5, такой, что Реп(у) = ш1п Реп(х), Присвоить узлу у к ох-3 следующий номер и положить Т -5 () (у1 Шаг 3 (пересчет степеней). Для и ~ Х вЂ” Т положить Рец(и) -(КеасЬ(и, Т) ). Шаг 4 (цикл или остановка).
Если Т = Х вЂ” остановка. В противном случае положить 5 — Т и перейти к шагу 2. При таком подходе на протяжении всего процесса используется структура исходного графа. Действительно, алгоритм можно реализовать, используя лишь структуру смежности бо =(Х, Е). Здесь уместно указать, что на шаге 3 алгоритма (пересчет степеней) нет необходимости перевычислять размеры достижимых множеств для каждого узла из Х вЂ” Т, так как для большинства из них эти множества не меняются.
Это замечание формализуется в следующей лемме, чье доказательство вытекает из определения достижимых множеств и предоставляется читателю. Лемма 5.3.1. Пусть у Ф 5 и Т = 5 () (у). Тогда Кеасй(х, 5) для х ~ Кеас)т(у, 5), Кеас(т(х, Т)= Кеас)х(х, 5) 0 Кеас)т(у, 5) — (х, у)н в противном случае. В примере на рис. 5.3.3 рассмотрим этап, соответствующий исключению узла й, ') Здесь (к, у) — обозначенне множества, состоящего нз двух узлов к н Е, а не ребра, нндндентного нм.
— Прим, перса 1З4»"л. о. универсальные па»ременные метод»и Имеем 5 = (а, с), так что цеас)т(а, 5) = (Ь, д). Следовательно, исключение а воздействует лишь на степени узлов Ь и д. Учитывая это замечание, шаг 3 алгоритма можно переформулировать так: Шаг 5 (пересчет степеней). Для и~ Гсеас(т(у,5) положить 1)ед(и) — 11(еас)т(и, Т) 1. $ ледствие 5.3.2. усть у, 5, Т вЂ” те же, что и е лемме 5.5.1.
Для хек Х вЂ” Т 1цеас)т(х, Т) ~=в ~цепс)т(х, 5) ~ — 1, Доказательство. Утверждение вытекает непосредственно из леммы 3.3.!. 5.8.5. Ускорение алгоритма Согласно приведенной формулировке алгоритма, при каждом выполнении цикла нумеруется ровно один узел. Однако при определении на шаге 2 узла у с минимальной степенью часто бывает возможно обнаружить такое подмножество узлов, которым следует присвоить дальнейшие номера автоматически без дополнительного поиска минимальной степени.
Начнем исследование этого вопроса с введения некоторого отношения эквивалентности. Рассмотрим этап процесса исключения, соответствующий множеству 5 исключенных узлов. Говорят, что два узла х, уен Х вЂ” 5 неразличимы по отношению к исключению '), если цеас(т(х, 5)()(х)=цеасп(у, 5) () (у). (5.3.1) Рассмотрим граф на рис. 5.3.4. Множество 5 состоит из 36 заштрихованных узлов. (Это реальная ситуация, имеющая место при применении к такому графу алгоритма минимальной степени.) Замечаем, что узлы а, 6 и с неразличимы по отношению к исключению, так как все множества (сеас)т (а,5)Д (а), цеас)т(6,5)() (Ь), цепс(т(с,5)1) (с) совпадают с (а, Ь, с, су, е, 1, д, Ь, 1, я).
Есть еще две группы неразличимых узлов. Это и, й) и (1, у). Изучим теперь следствия этого отношения эквивалентности и его роль в алгоритме минимальной степени. Как будет показано ниже, оно может быть использовано для ускорения работы алгоритма минимальной степени. ') В последующем тексте предполагаетск, что узлы, наааанные енераа. лнчнмымн», неразличимы по отношению к нсключенню. я о.а. Алгоритм минимальной степени 1И Теорема 3.3.3. Пусть х, уеиХ вЂ” 5.
Если Кеасп(х, 5) () (х) = Кеасп(у, 5) () (у), то длл любого Т такого, что Х вЂ” (х, у):з Т ~ 5, йеасЬ(х, Т) () (х) = Кеведа(у, Т) () (у). Доказательство. Очевидно, что х я аеас)1 (у, 5) с с=гхеасЬ(у, Т)() Т (см. упр. 5.Е7), так что хек гхеасЬ(у, Т). Рис.
а.ам. Пример и опрелелению неразличимых узлов. Теперь мы хотим показать, что Кеведа(х, Т)с= Кеас)1(у, Т)0(у). Пусть г ~ аеас)1 (х, Т). Тогда существует путь (х, зо ..., зо г), где (зь ..., зг) с Т, Если все з, ен5, то доказывать нечего. В противном случае пусть з, — первый узел из множества (зь ..., зг), не принадлежащий 5, т.
е. и, еимеасй(х, 5) П (Т). Отсюда следует ж еи Ттеас)1(у,5), а потому хи аеас)1(у, Т), В совокупности имеем аеас)1 (х, Т) () (х) с" гхеасЬ(у, Т) () (у). Обратное включение следует из симметрии ролей х и у; это и дает нужный результат. !яа Гл. б. Универсальные разреженнив методы Следствие 5.3.4. Пусть к и у неразличимы по отношению к подмнолсеству 5. Тогда для Т:» 5 ~ Кеасп(х, Т) !=! Йеасп(у„Т) !. Другими словами, если два узла становятся неразличимымн на какой-то стадии исключения, то они остаются неразличимы, пока один из них не будет исключен.
Более того, как показывает нижеследующая теорема, они могут быть исключены в алгоритме минимальной степени один за другим. Теорема 5.3.5. Если на каком-то этапе алгоритма минимальной степени два узла становятся неразличимы, то они могут быть исключены один за другим. Доказательство. Пусть к и у неразличимы после исключения подмножества 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
