Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 20
Текст из файла (страница 20)
Предположим, что х становится узлом с наименьшей степенью после того, как исключено множество Т, Т:»5; т. е. ! цеасй(х, Т) !(! Йеасй(г, Т) ! для всех г~Х вЂ” Т. Тогда, по следствию 5.3.4, !цеасп(у, Т () (х)) /=Кеасй(у, Т) — (х) ! = ! цеаси (у, Т) ~ — ! =! Кеасп (х, Т) ! — !. Поэтому для всех г ~ Х вЂ” (Т () (х) ) ! цеасп(у, Т () (х)) 3«= !цеасп(г, Т) ~ — ! (! неасп(г, Т () (х)) !.
Здесь использовано следствие 5.3.2. Другими словами, после исключения узла х узел у становится узлом с наименьшей степенью. Эти замечания можно использовать при реализации алгоритма минимальной степени. Как только поиск минимальной степени определил, что следующим должен быть исключен узел у ~ Х вЂ” 5, сразу вслед за у можно пронумеровать узлы, неразличимые с ним. Вдобавок при пересчете степеней можно сократить работу, пользуясь следствием 5.3.4: нера гличимые узлы имеют одинаковую степень в графах исключения. С того момента, когда узлы квалифицированы как неразличимые, они могут быть «склеены» н рассматриваться впоследствии как единый суперузел Например, рис.
5.3.5 демонстрирует два этапа исключения, где из неразличимых узлов формируются суперузлы. Для простоты не указаны исключенные узлы. После исключения неразличимого множества (а, Ь,с) все узлы имеют одно и то жв Э В.Ю Алгоритм минимальной степени 127 достижимое множество, так что их можно слить в один супер- узел. В общем случае опознание неразличимых узлов, если исходить из их определения (5.3.1), требует большой работы. Поскольку наш прием не требует слияния всех неразличимых узлов, то поищем какое-нибудь простое, легко реализуемое условие. Ниже будет представлено условие, которое, как показала практика, является очень эффективным.
В большинстве случаев с его помощью опознаются все неразличимые узлы. Рнс. З.З.З. Неразличиные узлы на двух этапах исилючения для графа на рис. 5.3Л. Пусть 6 = (Х, Е), а 5 — множество исключенных узлов. Пусть 6(С,) и 6(Сх) — связные компоненты подграфа 6(5), т. е. Сь С, ~= г(5), Лемма 3.3.6. Пусть Я~ — — АсЦ(С1), Дз = АсЦ(Сг). Если уен Я1ДЯя и Аб) (у) с= Й1 Ц Аз () С, () С„ то йеасЬ(у,5)() (у) = Р, () гсх.
Доказательство. Пусть х ен й, () )сх. Предположим,. что х ~ ни Аьь — — А4(Сь). Поскольку 6(Сь) — связная компонента 6(5), то можно найти путь из у в х через С1 и 5. Следовательно, х ен КеасЬ (у, 5) () (у). С другой стороны, у ен гсь О гсх по определению. Если же х ен аеас)т(у, 5), то существует путь из у в х через 5: у, зь зх, ..., зь х. Если 1=0, то к~Ад)'(у) — 5с:)с1()гсх. В противном случае если Г ) О, го вь ~ А4(у)П5~ С, () С,.
Это значит, что (вь ... ..., зг) есть подмножество либо Сь либо Сх, так что х ен Яг(Яя. Следовательно, КеасЬ(у, 5) () (у) с= Д, () Д„ 128 Гл. Ю. Универсальные раэреяеенныв методы Теорема 5.3.7. Пусть Сь Сг и )с», »»»г — те же, что и в лемме 5.3.6. Тогда узлы множества =(уеи )»»» П г»»г! Ас1) (У) с: х»»» () х»»г () С» () Сг) (5.3.2) неразличимы по отношению к исключенному подмножеству Я. Доказательство. Утверждение следует из леммы 5.3.6. Следствие 5.3.8. Для у~ У аеас)»(у, о) )= (А»» () Я,~ — 1.
Теорему 5.3.7 можно использовать для слияния неразличимых узлов из пересечения двух достижимых множеств )с» и )сг'). Проверка на неразличимость проста и выполняется инспекцией смежных множеств для узлов, принадлежащих пересечению )7» () )тг. Представление о неразличимых узлах можно применить к алгоритму минимальной степени. Модифицированный алгоритм формулируется следующим образом. Шаг 1 (инициализация). Я» — 8.
Для хеиХ положить Ре5 (х) = ( Аб) (х) ). Шаг 2 (выбор). Выбрать узел у ви Х вЂ” 5 такой, что Рей (у) = ппп Рей (х). хых-3 Шаг 3 (исключение). Присвоить узлам множества У=(хни Х вЂ” 5 ~х неразличимо с у) номера, следующие за номером у. ') Почему смежные множества й» н йх можно трактовать как Костижи.
мме, равъясняетси в унр. 5,2.5. — Прим. нерее, Э ЗЗ Алгоритм минимальное гтеагни !29 Шаг 4 (пересчет степеней), Для и ев аеас(т(у,5) — У положить Оед(и) =! в!еасп(и, 5 () У) | и найти неразличимые узлы в множестве аеас)!(у,5) — У. Шаг 5 (цикл или остановка) . Положить 5 -5 () У. Если 5 = Х вЂ” остановка.
В противном случае перейти к шагу 2. 5.8.4. Реализация алгоритма минимальной степени Реализация алгоритма минимальной степени, которая будет здесь представлена, включает в себя использование неразличимых узлов, как это описано в предыдущем разделе. Узлы, квалифицированные как неразличимые, сливаются, образуя супер- узел. В остальной части алгоритма они будут обрабатываться, по существу, как один узел. Они имеют одно и то же смежное множество, одинаковую степень н могут быть исключены в алгоритме один за другим.
Ссылка на такой суперузел в реализации производится через его представителя. Алгоритм требует определения достижимых множеств прн пересчете степеней. С этой целью и для повышения обшей эффективности алгоритма используется модель фактор-графов (раздел 5.2.2). Связанные исключенные узлы сливаются, и применяется машинное представление последовательности фактор-графов (раздел 5.2.3). Нужно подчеркнуть, что идея факторизации (или слияния узлов в суперузлы) используется здесь в двух различных контекстах: а) для связанных исключенных узлов, чтобы облегчить определение достижимых множеств; б) для неисключенньсх неразличимых узлов, чтобы ускорить исключение.
Это иллюстрируется рис. 5.3.6. Он поясняет, как в нашей реализации посредством двух видов факторизаций хранится граф рис. 5.3.4. Заштрихованные дважды окаймленные узлы соответствуют исключенным суперузлам; незаштрихованные дважды окаймленные суперузлы сформированы из неразличимых узлов. В этом разделе будет представлен набор подпрограмм, реализующий алгоритм минимальной степени в том варианте, какой описан в .предыдущих разделах. Некоторые из используемых параметров те же, что обсуждались в главе 3. Мы кратко напомним их здесь, а за деталями отошлем читателя в параграф 3.3.
Граф б =(Х, Е) хранится посредством пары целых массивов (ХАО3, АОЛг(СУ); число узлов в Х задается переменной 130 Гд о Униеерсаеьнме разреженнме негода 1чЕЯг)Ь. Полученное подпрограммой упорядочение по минимальной степени хранится вектором РЕЯМ, а обратное упорядочение — вектором 1г)ЧР. Данный набор подпрограмм требует несколько рабочих венторов для реализации модели фактор-графов и техники неразличимых узлов. Текущие степени узлов в (неявном) графе исключения хранятся в массиве ОЕАР. Для узлов, которые уже исключены, в ОЕП устанавливается значение — 1.
Рис. 6,3.а. Фактор. граф, образоиаиимй двумя типами суперузлои. В представлении последовательности фактор-графов связанные исключенные узлы сливаются, образуя суперузел. Как отмечено в разделе 5.2.3, для ссгялок достаточно выбрать в суперузле представителя.
Если 6(С) — такая связная компонента, то мы всегда выбираем для представления С последний исключенный узел хе= С. Это означает, что остальные узлы С можно игнорировать в последующих фактор-графах. То же замечание относится к неразличимым группам неисключенных узлов. Для каждой группы в данной фактор-структуре будет рассматриваться только представитель. Для маркировки тех узлов, которые можно игнорировать в структуре смежности, используется рабочий вектор МАККЕЙ.
Для таких узлов в МАККЕК записываются значения, равные — 1. Тот же вектор используется, чтобы облегчить генерирование достижимых множеств. й Ю.З. Алгоритм минимальной степени 131 Еше два массива ЯБ1ЕЕ и Я).1ХК используются для полного описания неразличимых суперузлов.
Если представителем Я1.1МК Я51сЕ МАЙКЕЙ 1 2 3 4 5 е 7 8 8 Яв) Рнс. 3.3.1. Иллюстрация роли рабочих массивов 1с1.1ЫК, вй51ЕЕ и МАККЕЙ. суперузла является узел А то число узлов этого суперузла задается переменной (;1312Е(1), а сами узлы суть в, Я1.1й)К (1), Я).1)ч)К (Я1.1(х)К (1)), .... Рис. 5.3.7 иллюстрирует использование векторов Я51ХЕ, Я).1ХК и МАККЕК. Узлы (2, 5, 8) образуют неразличимый 11ьюнсн Рнс. Б.ЗЗ. Отношения управления меввду подпрограммами в алгоритме мини- мальной степени суперузел, представляемый узлом 2. Поэтому в массиве МАККЕК значения для узлов 5 и 8 равны — 1.
С другой стороны, (3, 6, 9) есть исключенный суперузел. Его представитель— узел 9, так что МАККЕК(3) и МАККЕК(6) равны — 1. В данном наборе пять подпрограмм, а именно: ОЕХЯМР, ЯМРКСН, ЯМРЯТ, ЯМР1)РР и с1МРМКО. Отношения управления между ними показаны на рнс. 5.3.8. Ниже эти подпрограммы описываются подробно, с ° ° С ° ° ° ° ° ° ° СЕЙ))МО ... УПОРЯДОЧЕННЕ МНННМЛЛЬНОН " ° ° С""" ° СТЕПЕНИ С ИСПОЛЬЗОВАНИЕМ фЛКТОРНЗАЦИИ ° ° ". ° " с. Ф НСПОЛЬЗУЕНЫЕ ПОДПРОГРАММЫ О)ЮЕСН, (>ЬЕХ)Т, ))МОСРО. Се ° ~ ° ° ° ес~* ° ° С С С С С С С С с с с с с с с с с с с с с с с с с с с с с с с с с с с с с с с с ПОДПРОГРАММЛ РЕАЛИЗУЕТ ЛЛГОРИТН ИИНИИЛЛЬНОЙ СТЕПЕНИ* ИСПОПЬЗУ10ТСЯ НЕЯВНОЕ ПРЕДСТАВЛЕНИЕ ГРАФОВ ИСКЛЮЧЕНИЯ последством ч)лктоР- Г лфов и техннкл НЕРАБЛНЧИИЫХ УЗЛОВ ПРЕДУПРЕЖДЕНИЕ - СОДЕРЖИМОЕ ВЕКТОРА СМЕЖНОСТИ АОЗМСУ НЕ СОХРЛНЯЕТСЯ.
ВХОДНЫЕ ПАРЛНЕТРЫЙН"НБ - ЧИСЛО УРАВНЕНИЙ. (ХАО?, АО?МСТ) - СТРУКТУРА СМЕЖНОСТИ, ВЫХОДНЬ)Е ПАИ)МЕТРЫ- РЕЕМ - УПОРЯДОЧЕНИЕ МИНИМАЛЬНОЙ СТЕПЕНИ, ?ЙУР - ОБРАТИОЕ К РЕНИ, РАЕОЧИЕ ПАН)НЕТРЫ ОЕС - ВЕК?ОР СТЕПЕНЕЙ ° ОТРИЦАТЕЛЬНОЕ ОЕО(2) уклзывлет~ что узел 1 нунеРОВАи. МАЕКЕЕ - ВЕКтоР МАРКИРОВКИ.
ОТРИЦАТЕЛЬНОЕ НАНКЕН(1) УКАЗЫВАЕТ, чТО УЗЕЛ 1 СЛИТ С АРУГИН узПОН И ЕГО МОЖНО ИГНОРИРОВАТЬ. ВСНБЕТ - ВЕКТОР ДЛЛ ДОСТИЖНМОГО ИНОЖЕСГВА. ЙВЕНО - ВЕКТОР ДЛЯ ОКРЕСТНОСТИ ° ()Б?2Е - ВЕХТОР ДЛЯ ХРАНЕНИЯ РАЗНЕРОВ НЕРАЗлнчнных СУПЕРУЗЛОВ. 02?Йк - ВЗНТОР1 хРАнящий ненлзличиные узль). 1 <Н.ХМК(Т) ЦЬ1НК(ЦЬ1НК(1)) ° ° ° ЗЛЕМЕНТЫ СУПЕРУЗЛА ПРЕДСТАВЛЯЕМОГО УЗЛОМ Х . БОВНООт?ЙБ ОБЙ))НО ( Йе))ЙБ, хАО?, АО?нст, Реем, ?ЙРР, Оес, 1 НАекее. Нснзет, Йвейо. ()Б?2е, ®?ЙЕ, 1 ЙОРБОВ ) 1ЙТЕОЕЕ АО?ЙСУ(1), РЕЕМ(1), ?ЙУР(1), ОЕО(1), МАЕКЕЕ()).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
