Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 24
Текст из файла (страница 24)
Схемы хранения разреженных матриц 1БЗ Для(= 1, ..., тч' Йеас(т(хо Я,,) =АсЦ (хе) — Зь Для й ен йе выполнить Йеас(т(хо Яе ~) — Йеасй(хо Я,,)()йеасй(хе, Зе ) — 3, не= ппп(1 1х~ ~ Йеасй(хь 3,,)) й — й () (е). В этом алгоритме используется множество Йь аккумулирующее тех представителей, чьи достижимые множества воздействуют иа достижимое множество хи Имеется одно очевидное следствие теоремы 5.4.3, которое можно применить для ускорения алгоритма.
Кроме того, оно полезно при формировании компактной схемы хранения. Следствие 5.4.5. Если для данного е' имеется лишь одно от» такое, что тя=е', и при этом Ад) (х,) — Яе с: Кеасй (хы Яя,), то Йеас)т (хн 3,,) = Йеас)з (х„Яя,) — (хе). Входными данными подпрограммы ЗМВГСТ являются граф матрицы, хранимый парой массивов (ХАОС, АОЛ)х)СУ), а также вектор перестановки РЕЙМ и вектор обратной перестановки 11нЧР.
Назначение подпрограммы — сформировать структуру данных для компактной разреженной схемы, т. е. вычислить компактный вектор индексов )чУЬ()В и индексные векторы Х(.'г(с и Хг)с81)В. Присваиваются также значения переменным МАХ(."г)с и МАХЗ()В, равные соответственно числу внедиагональных ненулевых элементов треугольного множителя и числу индексов в компактной схеме. Подпрот ранна ЗМВРСТ использует три рабочих вектора ЙСН).НК, МЙСе(.5)К и МАККЕЙ. Вектор ЙСН1МК облегчает операцию слияния достижимых множеств, в то время как вектор МЙЯ.1)К осуществляет слежение за представительными множествами (й;), введенными выше.
Вектор МАККЕЙ используется для проверки условия, указанного в следствии 5.4.5. Работа подпрограммы начинается с присвоения начальных значений рабочим векторам МЙСЫ%К и МАККЕЙ. Затем выполняется основной цикл, в котором вычисляется достижимое множество для каждого узла, Вначале определяется множество Ад)(хх) — Зх, помещаемое в вектор ЙСН(.МК. В то же время проверяется условие следствия 5.4.5. Если оно удовлетворяется, то слияние достижимых множеств можно опустить.
В противном случае на основе информации из МЙ01)х)К в ЙСН(.МК осу- )ОО с С с С С С С С 300 300 С С С С С 350 400 С С С 500 ИНИЦИАЛИЗАЦИЯ .. МЕВЕС ! МЕЕМО 0 ХЕМ2(!) ° ! ОО 100 К 1, МЕОМ5 МКСЬМК(К) - О МАККЕЙ(К) 0 СОМТ ГНОЕ ДЛЯ КАЖДОГО СТОЛБЦА.... КМЕ ПОДСЧИТЫВАЕТ ЧИСЛО НЕНУЛЕВЫХ ЭЛЕМЕНТОВ К-ОГО СТОЛБЦА, НЛКЛПЛИВАЕНОГО В КСНЕИК. МР! МЕ((М5 + 1 ОО 1500 К 1, МЕ()МР КМ2 0 МВСК МКС!.МК(К) МККР!.С 0 МАККЕК(К) К 1Р (МКСК МЕ 0 ) МАККЕЙ(К) МАККЕЙ(МВСК) ХМ25ОВ(К) МЕЕМО МОВЕ РЕКМ(К) 35ТВТ ХАО3(МОРЕ) 35ТОР ХАО3(МООЕ4!) — ! 1Р (35ТЙТ.СТ.35ТОР) СО ТО 1500 ИСПОЛЬЗУЯ НСНЕМК, СОСТАВИТЬ СПИСОК НЕНУЛЕВЫХ ПОДДИАГОНАЛЬНЫХ ЭЛЕМЕНТОВ СТОЛБЦА А! ° К) . КСНЕМК(К) МР1 00 300 3 35ТКТ, 35ТОР МАВОК АО3МСУ(3) МАКОВ 1МУР(МАВОК) !Р ( МАВОй .!.Е. К ) СО ТО 300 йСНМ К М КСНМ кснм Йснемк(м) 1Р ( КСНМ .ЕЕ. МАВОК ) СО ТО 200 КМ2 КМ24! КСНЕМК(М) МАВОК КСН!.МК(МАВОК) КСНМ 1Р ( МАККЕВ(МАВОВ) .МЕ.
МАККЕЙ(К) ) МЙКРЕС ! СОМТ!М!)Е ВОЗМОЖНО ЛИ ГРУППОВОЕ СИМВОЛИЧЕСКОЕ ИСКЛЮЧЕНИЕ... Е МАХ 0 1Р ( МККГЬС МЕ. 0 ОК. МВСК .Е(). 0 ) СО ТО 350 1Р ( МЙСЕМК(МВСК) МЕ 0 ) СО ТО 350 ХМ25ОВ(К) ХМ2508(МВСК) + 1 КМ2 ХЗ.М2(МВСК+!) - (ХЕМ2(МВСК) + 1) СО ТО !400 ДЛЛ КАЖДОГО СТОЛБЦА 1 ВОЗДЕИСТВУЮ)ЦЕГО НА Е(4 !К) е 1 ° К 1 МКС)ЛЧК(1) 1Р (1.Е().0) СО ТО 800 1М2 ХЗ.М2(1+!) — (ХЕМ2(1)+!) 35ТВТ ХМ25()В(1) 4 ! 35ТОР ХМ25ОВ(1) 4 1М2 1Р (1МЕ.ЕЕ.!.МАХ) СО ТО 500 !.МАХ 1М2 ХМ25СВ(К) 35ТйТ ПРИСОЕДИНИТЬ К КСНЬМК СТРУКТУРУ Е(~, 1) ИЗ МЕЗНВ. КСНМ К ОО 700 3 35ТВТ, 35ТОР еоо уоо с с с БОО с с с 900 !ооо !>оо с с С С 1200 >ЗОО С с с С с 14ОО 1600 С С С 1500 МАвои - мгвов(1> М - ИСНМ ИСНМ - ИОН>2(К(М> 15 (йснм.ьт.м»вой> Со то воо ЗР (иснм.ез>.НАВои> Со то тоо кмг .
ю(г»1 ИСН1.МК(М) НАВОИ ИОН(МК(НАВОИ> . ИСНМ йСНМ МАВОР сомпмое СО ТО 400 дублийуют ли индексы индексы дРТГОГО столвцй !Р (Кмг.Е(>.!МАХ) 60 ТО !400 СООТВ. ЛИ КОНЕЦ (К-1)" ОГО СТОЛБЦА НАЧАЛУ К-ОГО.- 15 (НЕВЕС.СТ.ЯЕМО) СО ТО 1200 1 . ИСй(2(К(К) ОО 900 15тйт мгВес,мгемо ЗР (мгвов(15тит>-1> Воо, !ооо, >воо сомтпмое СО ТО 1200 хяБОВ(к> - 15тйт 00 1100 1 15тит,мгемо 15 (МЕБОВ(1).МЕ. 1) СО ТО 1200 1 - ИСНЬМК(1> 15 (1.СТ.МЕОМБ) СО ТО 1400 СОМТ1МОЕ яе»зо ЗБтйт ПЕРЕНЕСТИ СТРУКТУРУ Ь(» К) ИЗ НСНЬМК В стРУктуРУ дйнных (ХМЬ(>В» мгв(зв).
мгВес яе>зо + 1 яемо мгемо + кя 1Р (мгемо.ст.млхвов> со то Звоо 1 - К оо !Боо 1 мгвео,яемо 1 ИСНЬМК(1) МЕБОВ( 1 > 1 МАИКЕИ(1) К СОМПМ(ЗЕ хяБОВ(к) мгВес МАИКЕИ(К) К МСЩНФИЦИРОВАТЬ МНСЬМК. НАЙДЕННЫЙ »1»» К) ПОТРЕБУЕТСЯ ПРИ ОПРЕДЕЛЕНИИ СТОЛБЦА Е(»» Ю) 4 ГДЕ Цг К) - ПЕРВЫЙ НЕНУЛЕВОЙ ПОДДИАГОНАЛЬНЫЙ ЭЛЕМЕНТ В 1.(» К), 1Р (КЯ.ЕЕ.1) СО ТО 1500 КХЯЗВ ХЯ5ОВ(К) 1 мгя>В(кхБОВ) МИСЬМК(К) МЕСЬ>й((1) МИСЮК(?) К ХЬЯ(К+1) Х! Я(К) + Кмг МАХ1.Я Х(Я(МЕЗ>МБ) - 1 ИАхя>В хмг50В(меомв) хмгвов(меомБ»!> - хявив(мв>МБ> Р(АС 0 йЕТойм ОШИБКА - МАЛО ПАМЯТИ ДЛЯ ИНДЕКСОВ НЕНУЛЕВЫХ ВЛЕМЕНТСВ, Р1А6 1 йЕТОИМ ЕМО б 5Х Подпрограммы численного разложения и решения )57 ществляется слияние с предыдущими достижимыми множествами.
Когда новое достижимое множество полностью сформировано в )тСН1ЫК, подпро~ рамма проверяет возможность сжатия индексов и с учетом ситуации устанавливает соответствующую часть структуры данных Наконец, соответственно изменению множеств ()г,) перестраивается вектор М)гСт(.)ч'К. Благодаря слиянию лишь тщательно отобранных достижимых множеств подпрограмма БМВгСТ способна очень эффективно находить новое достижимое множество. Поскольку число индексов, нужных в компактной схеме, заранее не известно, длина вектора ЫХЯ/В может оказаться недостаточной для хранения всех индексов. В этом случае выполнение программы прекращается и устанавливается значение 1 для индикатора ошибки г1АП.
Упражнения 5.4.!. Пусть А — матрица, удовлетворяюшая условию й(А) ( ! для 2 ее <! < )т'. Поназатзн что гп, = й+ ! для всех й, й < П. Вывести отсюда (нлн показать каким-лабо иным способом), что для 1 < ! ( )т' йеась(хь хг,) =(дб)(х,)0кеасп(хг ь Я, з)) — 5ь 5.4.2.
Пусть А — ленточная матрица с шириной ленты В. Предположим, что лента А заполнена, а) Сравнить для А обычную я компактную схемы хранення. б) Сравнить два алгоритма снмволнческого разложения, содержашнеся в лемме 5.4,1 н теореме 5.4 3 соответственно 5.4.3. Пусть й| я йт — два заданных множества целых чисел, значення которых не превосходят ХГ.
Предположим, что нмеетсн рабочий массив длины й!, компонентам ноторого присвоены нулевые значения. Показать, что объеднненне л~ 0 йт можно определить за время, пропорцнональное 1Р,1 + )йз), й б.б. Подпрограммы численного разложения и решения В этом параграфе будут описаны подпрограммы, выполняющие численное разложение и решение линейных систем, хранимых компактной схемой. Подпрограмма разложения ПБгСТ (от слов депега) зрагзе зупппе1г!с 1ас1оггдаПоп ') использует алгоритм разложения в форме скалярных произведений. Так как ненулевые элементы нижнего треугольника А (или множителя Е) хранятся по столбцам, то вариант со скалярными произведениями должен быть адаптирован к этому способу хранения.
Подпрограмма ПЕРСТ получена незначительной мо. дификацией подпрограммы из Йельского пакета для разрежен. ных матриц. ') Симметричное рааложенне пронввольных разреженнмх матриц. -Прим. перев. 1М Гл 5. Униеерсольнае раереженнае метода 5.5П. Подпрограмма ПЕРСТ (Пепега! врагве Ьупипе1Нс РаСТолга1юп) Входными данными подпрограммы ПЯРСТ являются структура компактной схемы (Х11)Х, ХМХЬБВ, )х)ХЯ()В) и векторы основной памяти 01АСт и ) ЫХ.
На входе массивы 01АП и (.МЕ содержат ненулевые элементы матрицы А'). На выходе на места элементов матрицы А будут записаны ненулевые элементы множителя С,. Подпрограмма использует три рабочих вектора 1.1)х)К, Р1КЬТ и ТЕМР, все длины М, тХявт Пусть нужно вычислить столбец С.„множителя. Участвуют в формировании этого столбца в точности те столбцы С.„ь для которых 1н Ф О. Перестройку 1-го столбца можно провести по шагам, так что на каждом шаге добавляется лишь один столбец.
Именно: Для С.ю таких, что 1н Ф О, вьтполниттн — С о Сит ') В повипиих массива ьтнс, соотвеьстыуюыьвх заполнению, ы Л стоят аулы. — Прим. нерее. Р 55 Подирограммм ниеленного разложения и рея~ения (Б1 ОШИБКА - НУЛЬ ИЛИ КОРЕНЬ ИЗ ОТРЯД. ЧИСЛА ° С С 700 1РЬАО 1 ает(луч ЕМО На 1'-м шаге номера тех столбцов, которые воздействуют на !.„, задаются списком РЕШЕНИЕ ПРОИЗВОЛЬНОЙ РАЗРЕЖЕННОЙ *'' СИММЕТРИЧНОЙ СИСТЕМЫ л ° ° ° ° ° ° ° я ° я я зе С* ° ° ° ° .
655ЬУ Ся ° з ° ° ° я* ° я ° ° ВЫЧИСЛЯЕТ РЕШЕНИЕ ФАКТОРИЗОВАННОЙ СИСТЕМЫ з МАТРИЦА с которой хранится в Формлте компактного' с ИНДЕКСИРОВАНИЯ. с С с с с с ИЗМЕНЯЕМЫЙ ПАРАМЕТР— ЯНЗ - НА ВХОДŠ— ЭТО ВЕКТОР ПРАВЫХ ЧАСТЕР, с НА ВЫХОДŠ— ВЕКТОР РЕШЕНИЯ.
С с ° *я ВХОДНЫЕ ПАРАМЕТРЫ- мецм5 — числО уРАВнений. (хьмг, > мг> - структуРА йенулевых Элементов ь . (хмгзцв. мазов> - стр> ктуРА комплктного нндексировлния. Р1АС - ДИАГОНАЛЬНЫЕ ЭЛЕМЕНТЫ ° ея а с ацвяоцттме 655ьу ( меомз, хь>ж, ьмг, хмгзцв, мгзцв, 1 СТАО, ЯНЗ ) С ° ° " ° ° ° ° ° ° ° ° я ° ° . ° . ° ° ° . ° ° ° ° ° ° ° ° ° ° я ° е с ООСВЬЕ РЯЕС1510М СООМТ, ОР5 СОНМОМ >ЗРКОРЗ/ ОР5 ЯЕА1 О1АО(!), Ьнг(1), ЯН5(1), ЯН51, 5 Тьтеоея мазов(1) Тнтеоеа хьмг(1>, хмгзцв(1>, 1, ж, 15ТОР.
15тат. 15цв, з, зз, мщмз 1.1Й)К (!), 1.1Й)К (1.1)ч)К (!)),.... Чтобы сократить поиск индексов, используется вектор Р1кэТ. Для ! = 1.1ХК(!), 1.1Й)К(1.!)ч!К(!)), ... переменная Р1коТ(!) указывает позицию в векторе 1.)ЧЕ ненулевого элемента !ц, Тем самым модификация Ь„, посредством Е„может начинаться с позиции Р1КЕТ(!) в (.Й)У. Третий рабочий вектор ТЕМР служит для накапливания поправок к столбцу 1.„ Работа подпрограммы (зоРСТ начинается с присвоения начальных значений рабочим векторам 1.1!ЧК и ТЕМР. Циклом РО 600 )... обрабатывается каждый столбец.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
