Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 23
Текст из файла (страница 23)
Естественно, вектор индексов 5)ЕЯ()В можно сжать, устраняя избыточную информацию. Это достигается удалением строчных индексов любого столбца, для 146 Гл. Б. Универсальные ровреженные методы которого оии образуют финальную подпоследовательиость ии. дексов предыдушего. Рнс.
6.4.3. Мотивировка аковомичиой схемы хранения. 01АО ХОЧЕ 1чЮОВ ХИЛЯКОВ Рнс. Гн4.4. Компактная схема хранения аля матрицы на рис 5.4 1. Взамен иа получаемое сжатие приходится вводить дополнительный индексный вектор ХР4ХЯ-3В, указывающий для каждого столбца начало его строчных индексов я массиве г12ЯЗВ. й 84.
Схемы хранения раереасенных матрац 147 Компактная схема для примера с рис. 5.4.1 показана на рис. 5.4.4. Теперь доступ к ненулевому элементу, стоящему в позиции 11,/), осуществляется следующим образом. катит - х< мг<1> КЗТОР Х> Мг(>ч) ) - 1 АП 0.0 1Р (КЗТОР.ЕТ.КЗТКТ) СО ТО 300 кзпв хмгзпв(1) во шо к . катят, кзто 1Р<мгзпв<кзив>.н0.1> со то гоо кзив .
кзпв ч ) СОМТ1МБЕ со то зоо А11 1.мг(к) )ОО гоо ЗОО В экономичной схеме основная память остается прежней, но накладная память изменяется; она всегда не превосходит >)х)опг(г) !+ 2Ф ячеек. Рассмотренный нами пример слишком мал, чтобы выявить достоинства экономичной схемы.
В таблице 5.4.! приведены данные, полученные для девяти больших Таблняа 5.4Д Сравнение обычной н компактной схем хранения. Для обмчиой схемы основная память равна накладной 7<аппп пее пее1ппте йеппа оп папяпь )Фонв <4)! >йопгРЯ Ап оРе(тпоп <гпп паетпапп(поп охеетет охаете< <(аппо урпЯема" задач, которые составляют один из обсуждаемых в главе 9 тестовых наборов.
Упорядочение, использовавшееся при получении этих результатов, было найдено алгоритмом минимальной степени, аналогичным описанному в предыдущем параграфе. В типичном случае для задач такого и большего порядка накладная память сокращается по меньшей мере на 50ой> в сравнении с обычной схемой. 936 1009 1089 1440 1180 1377 1138 1141 1349 2664 2928 3136 4032 3285 3808 3156 3162 3876 13870 19081 18626 19047 14685 16793 15592 15696 23726 14806 20090 19715 20487 15865 18170 16730 16837 25075 6903 8085 8574 10536 8436 9790 8326 8435 10666 148 Гл В универсальные раареженныа методы 5.4.8. О символическом разложении Как указывает название, символическое разложение есть процесс моделирования численного разложения данной матрицы, позволяющий получить структуру нулевых и ненулевых элементов ее множителя Е Поскольку в этом вопросе числовые значения элементов матрицы не играют роли, задачу удобно изучать, пользуясь методами теории графов.
Пусть Оа = (Х", Е) — упорядоченный граф, где ) Х") = М. Для удобства положим а(!) = хь Согласно теореме 5.1.2, символическое разложение можно рассматривать как вычисление множеств йеасЬ(х„(хь ..., х, 1)), ! = 1, ..., А!. Положим 5, = (хь х). Докажем следующий результат относительно достижимых множеств.
Лемма 5.4.1. йеасЬ (кь Еь ~) = А<Ц (к,) () (() (йеасЬ(х», 5»,) )х, ен йеасЬ(х», 3» Д~) — Ю, Доказательство. Пусть ! ) й Тогда по лемме 5.!.! и теореме 5.1,2 условие х! ен йеасЬ(к„5, 1) эквивалентно условию хн х,) ен Е", а оно в свою очередь — условию (х„к,) ~ Ел либо к„х») Я Ег и (кь к») Я Е' длЯ некотоРого й < пйп (ю', !). Последнее же означает, что к! ен АьЦ(х,) либо кь к! ~ енйеасЬ(х»,5» ~) для некоторого й. Отсюда и следует утверждение леммы.
Лемма 5.4.1 подсказывает алгоритм вычисления достижимых множеств (и, следовательно, структуры множителя Е). Он может быть описан следующим образом. Шаг 1 (инициализация). Для й = 1, ..., А! йеасЬ(кы Я» 1) — Аа) (х,) — Я» ь Шаг 2 (символическое разложение). Для й = 1, ..., й! если к, ~ йеасЬ(х», 5» ь), то йеасЬ(хь Я,,) -йеасЬ(кь В,,) () йеасЬ(кы Я»,) — 5ь Иллюстрация этой схемы показана на рнс. 5.4.5.
Алгоритм едва ли удовлетворителен, так как он по существу моделирует полный процесс разложения, и его стоимость будет пропорциональна числу операций, указанному в теореме 2.1.2. Поищем способ повысить эффективность алгоритма. й а,4. Схемы хранения раэреэненных матриц 149 Рассмотрим этап, соответствующий исключенному множеству Я, 1 = (хь ..., х, 1). Для целей этого обсуждения достаточно рассмотреть случай, когда х, имеет две смежные с иим Рчс. 5.4ли Слияние достижимых миожссти для оычислсиия йсасв(х„8~ ~). связные компоненты в 6(5, 1). Пусть ил множества узлов будут С1 и Ся. Как легко видеть, в этом случае аеас)т (хо В,,) = А~Ц (х,) () А<Ц (С,) () Аб) (С,) — Яе Однако в С~ и Ся можно выбрать представителей х, и х, соот» ветствеино так, чтобы А<Ц (С,) = аеас)т (х,, 5,,) Ад)(Ся) = Кеасп(х...
Я...) 150 Гж д Мниеереальнь~е раереженньье методы (см. упр. 5.2,5). Правило выбора представителя указано формулой (5.2.4): это — узел из компоненты, исключенный последним. Теперь достижимое множество можно записать в виде аеас)т(хо 5,,)= А 41(х,)() аеас)1(х,, 5, ~)() КЕае)1 (Х,, Я,,) — оь Таким образом, вместо того чтобы сливать большое количество достижимых множеств, что предлагает лемма 5.4.1, мы Рнс.
В.4.6 Экономия прн слняння постнжнмых множеств для построения кевсь(хь ое — 1). можем выбирать представителей. Описываемые ниже идеи мотивируются этим замечанием. Для й = 1, ..., Ж положим гпя = ппп (! ~ х, я Кеясй (хь, Яь,)). (5.4.1) На матричном языке лть есть индекс первого ненулевого зле. мента, исключая диагональный, в столбце Ь,ь Лемма 5.4.2. аеас)т (хь, 5ь,) ~ ((еасоф (х„ь 5 ь,1() (х Доказательство.
Пусть х, ен кеас)1(хь, Яь ~); тогда й с. ( лть ~1. Если 1= лть то доказывать нечего'). В пРотивном ') То есть хе — — х, очевидно, принадлежит правому множеству. — Прим. ие аерее. 4 5.4 Схема хранения разреженных матриц 1и1 случае по лемме 5.1.1 и теореме 5.!.2 х, ен КеасЬ (х а, 5 а,) Из леммы 5.4.2 вытекает следующий важный вывод. Если хг ен КеасЬ(хм 5а г) и г ~ тх, то при построении множества КеасЬ(хн 5, г) в алгоритме излишне рассматривать КеасЬ(ха,5х г), потому что все узлы, достижимые через хм могут быть найдены в множестве КеасЬ(х,, 5 „,).Таким образом, достаточно сливать достижимые множества некоторых Рис. $.4.7.
Иллюстрация к определению чисел лгм представительных узлов. Рис. 5.4.6 демонстрирует получаемую при этом экономию для примера с рис. 5.4.5. Лемму 5.4.1 можно усилить следуюшим образом: Теорема 5.4.3. КеасЬ(х„5,,) =АгЦ (х,) () (()(КеасЬ(ха 5а г) !лт»=г)) — 5г. Доказательство. Рассмотрим произвольный узел ха такой, что х, ен КеасЬ(хх,5х г). Полагая лг((г) = нг», получим возрастаюшую последовательность индексов, ограниченную сверху числом Ь й < лг(й) < т(т(гг)) < та(lг) « ...
г. Найдется такое натуральное р, что игр+'(и) = г. Из леммы 5.4.2 следует КеасЬ (хю 5х-г) — 5г »: КеасЬ(х мь 5 гм г) — 5, с: КеасЬ(х Р,а, 5 Р, г )5, Отсюда н вытекает утверждение теоремы. Рассмотрим построение множества КеасЬ(ха,54) для графа иа рис. 5.4.7. Если бы использовалась лемма 5.4.1, то пришлось бы сливать с Аг(1(ха) множества КеасЬ(хь 5о), !62 Гл. Б универсальные разреженные метода Кеас)з(хз,51) и Кеас(з (х4,5з) С другой стороны, согласно теореме 5.4.3, достаточно рассмотреть множества КеасЬ(хь 5ь) и Кеас)з(хз, 5з).
Заметим, что пзз — — 4 и Кеа с 5 (хм 5,) = (х„хз) с= КеасЬ (х„5 ) () (хз). Алгоритм символического разложения можно теперь усовершенствовать таким образом. Шаг ! (инициализация). Для я = 1, ..., М Кеасй (хм 5з,) =Ай)(хз) — 5з. Шаг 2 (символическое разложение).
Для я = 1, ..., М если Кеас)з(хз, 5з-1) Ф И, то выполнить аз= ш)п(1 )х, ев Кеес(з(хм 5з,)) Кеас)з(х, 5„,) — Кеас)з(х, 5,)() КеасЬ(хз, 5, ) — (х„). Теорема 5.4.4. Символическое разложение можно выполнить за 0(~Ее~) операций. Доказательство. Для каждого столбца я значение тз единственно. Это значит, что обращение к Квас)з(хз,5з ~) происходит лишь тогда, когда вычисляется Квас)з(х, 5 „~). Таким образом, множество Кеас)з(хз,5з-|) исследуется только один раз на протяжении всего процесса. Кроме того, объединение двух множеств можно выполнить за время, пропорциональное сумме их размеров (см. упр. 5.4.3).
Следовательно, символическое разложение требует 0(~Ее)) операций, где и !Е")= х ~!Квас)з(х„, 5з,)). з-1 5,4.4. Распределение памяти для компактной схемы и подпрограмма ЬМВРСТ Здесь мы представим подпрограмму, выполняющую символическое разложение, как оно описано в предыдущем разделе. Результатом процесса является структура данных для компактной схемы из раздела 5.4 2. Подпрограмма составлена коллективом авторов (Е(зепз1а1 1981) н включена в Иельский пакет для разреженных матриц. По существу, она реализует усовершенствованный алгоритм из предыдущего раздела с перестановкой порядка при слиянии достижимых множеств. Шаг 1 (инициализация). Для з = 1...,, А1 положить В = Я. Шаг 2 (символическое разложение). э д4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
