Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 22
Текст из файла (страница 22)
Если места не хватает, то программа использует память, отведенную для узлов массива НВ((НР. Согласно разделу 5.2.3, этой дополнительной памяти уже всегда достаточно. Прежде чем закончить работу, программа добавляет узел- представитель КОРТ в список соседей каждого узла из КСНЯЕТ, Это делается циклом РО 600 .. ОМР()РР (Оцо((еп( МР РРРа(е) ОМРМКО (Яцо()еп( МР Ме(хбе) Эта подпрограмма осуществляет проверку условия (5.3.2) для того, чтобы определить неразличимые узлы.
Пусть Сь Сь Эта подпрограмма выполняет пересчет степеней в алгоритме минимальной степени. Узлы, чьи новые степени и)жно определить, задаются парой (Н(ВВТ, ) (5Т), Подпрограмма также сливает неразличимые узлы этого подмножества, пользуясь теоремой 5.3.7. Первый цикл РО 200 ... и обращение к подпрограмме ОМРМКО определяют группы неразличимых узлов в заданном множестве. Они сливаются, и их степени пересчитыва)отся.
Для узлов, которые не подвергаются слиянию, новые степени определяются в цикле РО 600 ... посредством обращения к подпрограмме ЯМРКСН. Векторы ((СНЭЕТ и 5(ВКНР используются как рабочие массивы. с. * Се С ° С ° С ИСПОЛЬЗУЕМЫЕ ПОДПРОГРЛМНЫОИСНЙС, ((ЫОЙСН * Сеее ° ° *е* ° ° **е ° е ее ° ° е* ее е ° * * ° е С БСВЙОСт1ме 0)е)ОРО ( хАО), АОгмст, м1.1Бт, СТБт, ОеС, 1 ОБ1ЕЕ, ()11МК, ИАЙКЕЙ, ЙСНБЕТ, МВЙНО ) С Се ° ° ° С Се С С С С С С С С С С С С С С С С С С С С 9 С 4 5.8. Алгоритм минимилвной стенени 139 ()МОНРО ....
ПЕРЕСЧЕТ СТЕПЕНЕЙ В АЛГОРИТМЕ н ° ° МИНИМАЛЬНОЙ СТЕПЕНИ ° ° ° ° ° ° е ° е ПОДПРОГР(НМЛ ВЬНЮЛНЯЕТ ПЕРЕСЧЕТ СТЕПЕНЕН ДЛЛ ЗЛДЛННОГО МНОЖЕСТВА УЗЛОВ. ВХОДНЫЕ ПАРЛНЕТРЫ- (хАО), АОгмст) - стРуктуРА смежнОсти. (М11БТ, 11БТ) - СПИСОК УЗЛОВ Г ЧЬИ СТЕПЕНИ НУЖНО ПЕРЕВЫЧИСЛНТЬ. ИЗМЕНЯЕМЫЕ ПАРАМЕТРЫ " ОЕС вЂ” ВЕКТОР СТЕПЕНЕЙ. ()Б1ЕЕ - РАЗМЕРЫ НЕРАЗЛИЧИМЫХ СУПЕРУЗЛОВ. ()11МК - СВЯЗНЫЙ СПИСОК ДЛЯ НЕРАЗЛИЧИМЫХ )ЗЛОВ. ИАЙКЕЙ - ИСПОЛЬЗУЕТСЯ ДЛН МАРКИРОВКИ УЗЛОВ РАБОЧИЕ ПАРАМЕТРЫЙСНЯЕТ - ДОСТИЖИМОЕ МНОЖЕСТВО.
МВЙНО - ОКРЕСТНОСТЬ. 1мтеСБЙ АО)мст(1), Б1ят(1), Оес(1). ИАйкей(1), ЯСНЕЕТ(1), МВЙНО(1), ОЯ1ЕЕ(1), 011МК(1) 1мтесей хАО)(1), Оес0, Оес1, 11., 1мнО, 1НООе, 1йсн, 1 3, )Бтйт, )БУОР, НАЙК, НАНОЙ, мнОБЕе, ме1Бт, 1 МООЕ, ЯСЛЯМ, ЙООТ НЛЙТИ ВСЕ ИСКЛЮЧЕННЫЕ СУПЕРУЭЛЫ ~ СМЕЖНЫЕ С УЗЛАМИ ДАННОГО СПИСКА ЬХБТ. ПОМЕСТИТЬ ИХ В (МНОЗХЕв МВННО). ОЕОО " ЧИСЛО УЗЛОВ В СПИСКЕ. 1Р ( М11БТ .ЬЕ. 0 ) ЙЕТОЙМ ПЕСО 0 МНОЯЕЕ 0 ОО 200 11 1, М11БТ МООЕ ПБТ(1Ь) ПЕСО ПЕСО е ()Я1ЕЕ(МОВЕ) )БТЙТ ХАО)(МООЕ) )БТОР ХЛО)(МООЕ+1) - 1 ОО 100 2 гйтйт, )БУОР МАВОй АОЛЧСТ(1) 1Р ( ИАйКЕЙ(ЛАВОЙ) .МЕ.
0 .Ой. ОЕС(ЛАВОЙ) .СЕ. 0 ) СО ТО 100 ИАЙКЕЙ(ЛАВОЙ) - 1 140 Гл Ф. Универсальные разреженные методы МНРБ2Е МНР52Е + 1 МВЯНР(МНОБЕЕ) . МАНОН СОМТ1МОЕ сечт)мое 100 200 с С С с СЛИТЬ НЕРАЗЛИЧИМЫЕ УЗЛЫ В ЗАДАННОМ СЛИСНЕь ВЫЗВАВ ОМРИНС. (Г ( МНР52Е .СТ. 0 ) САЬЬ ОЬЮМЯС ( ХАО), АОЗМСУ, РЕС, 0512Е, ф.1МК, МАЯКЕЯ, РЕСО, МНО52Е, МВЯНР, ЯСНБЕТ, МВЯНО(МНРБЕЕ+!) ) 1 1 1 С С НАЙТН НОВЫЕ СТЕПЕНИ УЗЛОВ КОТОРЫЕ НЕ ВЫЛИ СЛИТЫ. СО 600 1й 1, МЬ15Т МОРЕ Ь)БТ(1Ь) МАЯК МАЯКЕН(МОРЕ) тГ ( МАЯК СТ 1 ОЯ МАЯК .Ьт. 0 ) 60 ТО 600 МАЯКЕЯ(МОРЕ) 2 СА( С ОМОЯСН ( МОРЕ, ХАО1, ' АОЛЧСУ, РЕС, МАЯКЕЯ, ЯСНБЕЕ, ЯСНБЕТ, )ЧНОБЕЕ, МВЯНО ) РЕ61 ОЕСР !Г ( ЯСН52Е .ЬЕ. 0 ) СО ТО 400 РО 300 1ЯСН " 1, ЯСНБЕЕ 1МОРЕ ЯСНБЕТ(1ЯСН) ОЕС! РЕС! + 05125(!МОРЕ) МАЯКЕЯ(1МООЕ) 0 сомттмсе ОЕС(МОРЕ) РЕС1 - ! 1Г ( МНР52Е .ЬЕ.
0 ) СО ТО ьоо РО 500 ПЧНР 1, МНРБ2Е 1МОРЕ МВЯНО(1МНР) МАЯКЕЯ(1МООЕ) 0 СОМТ1 МОЕ 500 600 сонттиоГ йетпйм еип Й1, Йз н У вЂ” те же, что н в лемме 5.3.6. Подпрограмма предполагает, что С! и Й! былн найдены ранее. Для узлов нз Й! значения в масснве МАККЕЙ равны 1. Подпрограмма ()МРМЙО может иметь на входе несколько компонент Се. Онн содержатся в паре (ХНРВУЕ, НВЙНР), где каждая переменная МВЙНР(!) )казывает исключенный суперузел (т.
е. связную компоненту). Цикл РО 1400 ... применяет условие к каждой заданной связной компоненте. Вначале в цикле РО 600 ... определяется множество Йз — Йь хранимое посредством (ЙСНВХЕ, ЙСНВЕТ), н пересечение Йз П Й), описываемое парой (ХОЧЙ(.Р, ОЧЙЕР). Для каждого узла нз пересечения в цнкле РО 1100 ... проверяется условне (5.3.2). Если условие удовлетворено, то узел включается в сливаемый суперузел, что достигается помеще- нием его в вектор (;)).!(т(К.
Вычисляется также размер нового суперузла. Упражнения 3.3.1. Пусть хь — узел, выбранный из си, в алгоритме минимальной степени. Пусть у~Ай)а, (х,) и (тека (у) = ()ееа, (х,) — 1. Показать, что у будет узлом минимальной степени в оь 3.3.2. Пусть х~ и 0~-~ — те же, что в упр. 5.3.1, и утВАй)а(,(» ), Доказать, что если Ай)а, , (у) ~ Ай)а, ,(х,) 0 (»1), то у будет узлом минимальной степени в 0~ С' С' с ° ' Омомнс ....
спияние В АПГОРнтме минимАльнОЙ С ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° * С Бовйоотгне ()ьпхинс ( хлоя, лоянст, оес, Озтее, ()ьтнк 1 МАЯКЕН, ПЕСО, ННОБЕЕ. НайНО НСНБЕТ С С С С С С С С С с С С С С С С С С С С С С С С й 5.8. Алгоритм минимальной степени 141 ПОДПРОГРАММА СЛИВАЕТ НЕРАЗЛИЧИМЫЕ УЗЛЫ В АЛГОРИТМЕ МИНИМАЛЬНОЙ СТЕПЕНИ И ВЫЧИСЛЯЕТ НОВЫЕ СТЕПЕНИ НОВЫХ СУПЕРУЗЛОВ.
Вт ЭДНЫЕ ПАРАМЕТРЫ (хАоя, Аоянст( — стРуктуРА смежнОСти. ОЕСО - ЧИСЛО УЗЛОВ В ЗАДАННОМ МНОЖЕСТВЕ. (ННОБЗЕ, НВННО) — МНОЖЕСТВО ИСКЛЮЧЕННЫХ СУПЕРУЗЛОВе СМЕЖНЫХ С УЗЛАНИ ЗАДАННОГО МНОЖЕСТВА ЛЗМЕНЯЕМЫЕ ПАРАМЕТРЫОЕС вЂ” ВЕКТОР СТЕПЕНЕЙ, Ьгз!ЕЕ - РАЗМЕРЫ НЕРАЗЛИЧИМЫХ СУПЕРУЗЛОВ ° ~11.1НК - СВЯЗНЫЙ СПИСОК ДЛЯ НЕРАЗЛИЧИМЫХ УЗЛОВ МАНКЕй - В ЗАДАННОЕ МНОЖЕСТВО ВХОДЯТ УЗЛЫ ь КОТОРЫМ Б МАНКЕй СООТВ.
ЗНАЧЕНИЕ 1. ДЛЯ УЗЛОВ, СТЕПЕНЬ КОТОРЫХ НЗ~ЕНЕИАь БУДЕТ УСТАНОВЛЕНО ЗНАЧЕНИЕ 2. РЛБОЧИЕ ПАРАМЕТРЫНСНБЕТ - ДОСТИЖИМОЕ МНОЖЕСТВО ° очйьй - ВектОРт хРАнЯщий пеРесечениЯ дВУх ДОСТИЖИМЫХ МНОЖЕСТВ . 4 64. Схемы хранения разреженных магриц !4$ С С С С узел паинндлежит новому слитому суперузлу. модиФицировнть нсхмк и цзгее .
МКС5ЕЕ МКС5ЕЕ н 051ЕЕ(МООЕ! МАККЕЙ(МОРЕ) — 1 ЬМООЕ МООЕ щмк же (. О 1Р ( 1.1МК ЬЕ 0 ) СОТО !000 ЬМООЕ ЩМК СОТО 900 ОЬТМК(ЬМООЕ) НКАО НЕАО МООЕ СОМТ1МОЕ 1Р ( НЕАО . ).Е. 0 ) СОТО 1200 051ЕЕ(НКАО! МЙСЕЕЕ ОЕС(НЕАО) ОЕСО ОЕС! . ! МАККЕЙ(НЕАО\ ° 2 900 1000 1100 С С С 120! МОДИФИЦИРОВАТЬ ЗНАЧЕНИЯ В МАССИВЕ МАйИЕЛ. ЧООТ МЕЙКО(1МИО) (АККЕК(КООТ! 0 Р ( КСН521 ЬЕ 0 \ СОТО )400 ОО 1300 1КСН 1 КСН521 МООЕ ЙСН5ЕТ( 1ЙСН! МАККЕЙ(МООЕ! О СОМТ1МОЕ СОМТ1МПЕ Йетцям Е)(О 1300 1400 В 5.4.
Схемы хранения разреженных матриц 5.4П. Обычная схема ') ') В оригинале — (не ансон)ргеззеа зспеп)е. — Прим. нерее. Структура данных для универсальных разреженных методов должна предусматривать хранение только (логически) ненулевых элементов факторизуемой матрицы. Обсуждаемая здесь схема ориентирована на алгоритм разложения в форме скалярных произведений (см. раздел 2.!.2); ее можно найти, например, в работах (Оцз(ауэоп (972) и (Б))еггпап !975). В схеме имеется основной массив !.Х2, содержащий все ненулевые элеменгы нижнего треугольного множителя. Отводится ячейка для хранения каждого логически ненулевого элемента в множителе.
При этом ненулевые элементы Е, исключая диагональные, хранятся в (.!)(7 столбец за столбцом. Предусмотрен сопровождающий вектор !)(ХВ()В, дающи)1 строчные индексы ненулевых элементов Кроме того, для указания начала ненулевых элементов каждого столбца в массиве !.!))7. (нлн, что все равно, в массиве !)(ЛБОВ) используется индекс- Ем бм бзз ам Симметрична азз аы азз 7 г а» а» аьз азз азь азз ойдо Ф Разложение зз.ьМ Х1.447 Рнс.
5.4.2, Обычная схема хранения для матрицы и треугольного множителя иа рис, 5.4Л. 144 Гл 5, Унааерсальные ралреженные летоды Ряс. БА.1. 7 Х 7-матрица А и ее множитель з.. г 4 бзз Рм Еы е„ сзз езь 8м Р Ю.4. Схемы хранения ривреженных митрии 146 ный вектор ХЬ5)Е. диагональные элементы хранятся отдельно в векторе Р1АО. Если нужен доступ к ненулевому элементу аи или г„, то нет. никакого прямого метода для вычисления соответствующего индекса в массиве Ь5)Х. Приходится выполнять проверку индексов в 5125()В. С этой целью можно использовать приводимый ниже фрагмент программы. Заметим, что всякий элемент, не представленный в структуре данных, равен нулю.
кзтв) - хеьх()) КБТОР Х(И2()+1) — ) А11 - О.О 1Р (КБТОР ЕТ КБТВТ) СО ТО 300 00 1ОО К КБТВТ, КБТОР 1Р (НЕБОВ(К).Е().1) СО ТО БОО СОЫПКОЕ со то зоо А11 (.Н2(К) )ОО Хотя эта схема не слишком хорошо приспособлена для случайного доступа к ненулевым элементам, она вполне пригодна при разреженной факторизации и решении. Основная память в этой схеме, т. е. векторы ).5)Е и Р1АО, составляет 1)Чопз()Р))+А( ячеек; такова же накладная память (5)ЕВРВ и ХЕМА) — ()н)опх(Р) )+ А(.
5.4.2 Компактная схема ') ') В оригинале — соо)ргеаае() ас))егпе.— Прим. перев. Эта схема, являющаяся модификацией обычной, принадлежит Шерману (5))егшап 1975). Мотивировку схемы можно дать, рассматривая упорядочение по минимальной степени в той форме, как оно описано в разделе 5.3.3. Мы видели, что можно одновременно пронумеровать или исключить целое множество узлов у. узлы из у удовлетворяют условию неразличимости 1(еасЬ(х, 5)() (х) =1(еасЬ(у, 5)() (у) для всех х, у~ У, С точки зрения матричного множителя Ь это означает, что все строчные индексы ниже диагонального блока, соответствующего У, одинаковы во всех столбцах. Иллюстрацией является рис. 5.4.3. Если бы для хранения использовалась обычная схема, то в этом блоке строчные индексы любого столбца, кроме первого, составляли финальную подпоследовательность строчных индексов предыдущего столбца.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
