Прямые методы для разреженных матриц. О. Эстербю, З.Златев (984134), страница 5
Текст из файла (страница 5)
Теперь выполняются два цикла: а, Проход по строке 1, по позициям от 1.;+ 1 до М; массива СХК, Для каждого столбцового индекса ( проверяется условие Р1УОТ(~) Ф О, Если оно выполнено, то изменяем соответствующий элемент А по формуле (1.2,1), которая сейчас принимает вид а((х+ц а((х) 1а(ц Ц вЂ” Ц вЂ” й~т после чего полагаем Р1Ъ'ОТЦ) = О. б, Проход по строке 1 для проверки, все ли элементы использованы.. Б массиве СМК просматриваются позиции от 1( +1 до М( и для каждого столбцового индекса 1 прове- 'а На а-и и ааоследуадйих ааасатх,— -аара.а, аарга, ряется условие Р1УОТ(~) = О, Если оно выполнено, ВосстанавлиВаем значение Р1ЧОТ(3), Выбирая е из А.
В противном случае в строке 1 возникает новый элемент, что следует из формулы (1.2.1), имеющей теперь вид В след~лощих параграфах мы увидим, куда пОместить этот элемент. В конце Е-го шага мы записываем нули в использовавшиеся позиции (От 1~+ 1 до и) массива Р1ЧОТ; тем самым массив готов к шагу 1+ 1.
Однако мы сохраняем а~~ в позиции Р1ЧОТ(1), поскольку это может ускорить обратную подстановку. Заме~ание 2.4. Приведенное описание близко следует идеям„высказанным в 124, 66„671. И 2.4. Хрйкекие 36ЯОАкакия Всякий раз, как мы пользуемся формулой (3,4), в процессе исключения возникают новые элементы (заполнение). Их следует хранить в ~~ответстви~ с нашими общими принципами, чтобы на по~~~дующи~ ~агах их можно было Обрабатывать так же, как ~старые~ элементы матрицы коэффициентов.
Начнем с приятной информации. В массивах А и СЫК есть свободное пространство, поскольку диагональные элементы а~~~ мы храним В другом месте (а именно, в позициях Р1ЧОТ(1~)); свободное пространство есть и в массиве ЙХЙ„ так как нам не нужны сведения, относящиеся к столбцам с НОмером, меньшим 1~. СВОбодные позиции отмечаются за. писыванием нулей в КМК и СКК, Свободное пространство в середине строки бесполезно, Поэтому, если аы, не стоит еще в позиции Мк„мы переставляем его с элементом, находящимся в этой позиции, отмечаем, что она свободна, полагая СХК(М~) = О, и вычитаем из М~ единицу: М~ — — НА(1~, 3) = М~ — 1.
Аналогичные операции можно было бы проделать в упорядоченном по столбцам списке ЙХК; однако, как уже говорилось, после окончания 1-го шага исключения можно удалить весь 1-Й столбец, Итак, ~ежду стр~~ами (и столбцами), возможно, имеется некоторое свободное пространство. Поэтому при возникновении нового элемента разумно вначале проверить конец или начало строки (столбца)'. 170 180 260 290 ЗОО Еспзь лв месйо Спр0,60 1Г(СНВ(И1+) ) .аТ.О) 60 ТО ')70 ДО. И1 = И1 + А(ИХ) = АХТ СМВ (И1) = Х НА(1,3) = И1 1Р (М1.
ОТ, НВЕЫР) НВЕИР = И1 ДЕЛО СОЕПО.НО ОО ТО ЗОО К1 = НА(1,~) ЕС(ПЬ ЛЫ М8ППО СЛ660. 1Г(СМВ(К1) .6Т,О) СО ТО 180 йа. 11 = 1,1 - '( А(К1) = А(1*1) А(Ы) = АЫ СИВ (К1) = СНВ (Ь1) снВ(ы) = и НА(1,1) = К1 - 1 НА(1,2) = 11 - ) ДЕЛО СаедаНО 0О ТО ЗОО 12 = ИВЯНАЯ ". К1 30.пасйпзь кОпы)0 спз()Окп 1 6 кан6О, 13"-К1+1 по 290 13 а 13, и1 А(13+12) = А(13) СНВ(13+12) = СНВ(13) СИВ (13) = О 11 =11+ 12 НА (1, 1 ) -" ИВЕНП НА(1,2) = 11 - 1 НА(1,3) = ИВЯНАЯ а ИХ ж Щ + 12 + А(ИВкип) = А1,т СМВ (ЗВЕНО) СОЮТ1НУЕ Рис, 2.7. Фрагмент фортраиной подпрограммы, выполняющей запись но- вого элемента в массивм А н СХй.
с Эьпцоь ноиео элеменя0, е омбок, ~по(1ЙЛОченньй пе 0(пел5фи 1 У т НА(У~5) ИУ = НА(У,6) С ЕИПЬ ЛО МЕОП10 ЕНЦЗЦ 365 хР(ВИВ(иУФ1) .Ст,О) Оо то 370 с Да ИУ~ИУ+1 ВИВ (И,У) ° 1 НА(Урб) ~ ИТ хг(и,у.ат.и1еио) К1еко и,у С ДЕЛО 00ЕЛОНО ао то яО 370 КЮ ~ НА(У~4) С КОМЛЬ ЛО ИСЩ0 ЕВФ~Х~ хе(ВИВ(к,у).ат.О) Оо то 380 С йо, ВКВ(К,У) в ВКВ(Х.У) ВИВ(ХУ) а Х НА(,У,4) ~а КУНА(Уу5) ~ ЬУ 1 С ДЕЛО Иеюно ао то 500 380 12 = И1 ЕИО КУ С 3ОПКОВЬ КОПЫ ОП1ОЛЮО,О. Х Е КОНФО„ОПТИКО 480 ХЗ ~ КУ+ 1 РО 490 ХЗ = ХЗФ ИУ ВИН(13+12) ~ ВКВ(ХЗ) 490 ВИВ(ХЗ) ж О ЯА(У,4) а И1ЕИЬ НА(У~В) ~ ЬУ + Х2 К1ЕИО в ИУ + 12 + 1 ВИН(К1ЕИО) ~ Х. нА(у~6) ~ и1еко 500 соитхкве Если свобдных мест нет, то приходится копировать всю р у ( Вец) бд р р Л СН~~й~й) за последней ныне используемой позицией.
Эта стратегия разъясняется фрагментом фортра нного текста, приведенным на рис. 2,7. Выполняется запись нового Я Зак. 67 элемента А13 со строчным индексом 1 и столбцовым индексом 3. ХКЕХ0 — это последняя используемая позиция в А и СХК. Предполагается, что переменным 1.1 и М1 присвоены значения 1.1 = НА(1,2)+ 1, М1 = НА(1,3).
Процесс записи нового элемента в список, упорядоченный по столбцам, вполне аналогичен, но для полноты описания мы иллюстрируем его фортранным текстом на рис, 2.8. Замечание 2.5. Теперь возможны две стратегии: а. Всякий раз, как возникает новый элемент, он добавляется к строчно-упорядоченному и столбцово-упорядоченному спискам, прежде чем вычисления будут продолжены 197, 102).
б. Выполняются два прохода, Сначала процесс исключения моделируется ~толб~ц за столбцом, и возможные элементы заполнения добавляются к столбцово-упорядоченному списку. Затем проводится строка за строкой реальное исключение, вычисляются элементы подматрицы А~+~ и элементы запол~~ния записываются в строчно-упорядоченный список 1481. Преимущество стратегии б в том, что все новые элементы данного столбца (строки) доб~~ляю~ся к столбцово- (строчно-) упорядоченному списку одновременно.
Следовательно, на каждом шаге приходится записывать самое большое одну копию любого столбца (строки), и маловероятно, что мы слишком быстро исчерпаем имеющуюся память. Недостатком является то, что необходимы два прохода. а Пример 2.6. Рассмотрим матрицу примера 2.1, предполагая, что хранящие ее массивы упорядочены, как это описано в ~ 2,2 (см. рис. 2.5). Предположим, что на первом шаге исключения не делается перестановок. Так какаЯ = — 1.2 Ф ФО, то появляется новый элемент. В конце второй строки нет свободных мест, однако имеется вакантная позиция в начале, поскольку диагональный элемент записан в Р1ЧОТ (1).
Поэтому мы сдвигаем ф~ на одну позицию влево, помещаем на это место аД и присваиваем указателям значения 1 ~ = (НА(2, 2) =) 1.~ — 1, К~ = = (НА(2, 1) =) К~ — 1. В столбцово-упорядоченном списке око~о четвертого столбца нет свободно~о пространства„и приходится записывать копию столбца в конец списка. Содержимое массивов после 1-го шага показано на рис. 2,9.
В Пример 2.7. Рассмотрим матрицу и структуру ее хранения, полученные в примере 2.6. Предположим, что на втором шаге исключения не делается перестановок, Так как а®=О.З„-й О, то возникает новый элемент. Теперь имеется свободное пространство в начале третьей строки строчно-упорядоченного Рис. 2.9, Содержимое массовое после 1-го шага исключении. Рис. 2.10.
Содержимое массииои после 2-го шага исил~очеиии. списка и в конце четвертого столбца столбцово-упорядоченного списка. Содержимое массивов после добавления нового элемента показано на рис. 2.1О. И Мы не можем записывать неограниченное число кОпиЙ в наши списки. Однако если мы натолкнулись на верхний КО- нец массива, то, по всей видимости, уже сделано несколько копий, и внутри массива остались свободные места. (Если это не так, то матрица не столь разрежена, как предполагалось„ и программа должна запросить у пользователя большей памяти.) Теперь мы должны сжать структуру хранения, собрав все свободные позиции в одно связное множество, которое можно было бы использовать для будущих копий.
В программировании такого рода процесс часто называют ~сборкой мусораФ. Массив КХК может и должен обрабатываться независимо от Л и СКК, потому что нужда в сборках мусора возникает А сна Вян НА(.,1) НА(.,2) НА (.,3) НА(.,4) НА( «5) НА (.,8) А сыа ВШ НА(.,1) НА(.,2) НА(««3) НА( ° «4) НА(««5) НА (.,8) 3,4 -1.2 4 1 4 2 0 2 о о 1 5 0 2 о 4 3 .4 -1.2 4 1 4 5 о о 3 0 О 1 4 0 2 5 1 4 8 О 2 4 О 2 4 1 3 5 4 1 3 2 2 3 2 2 2 3 5 4 5 4 5 3 О О О 2 3 4 5 1 4 5 2 8 10 8 1О 10 12 12. 8 13 8 16 12 ° 25 .3 3 1.75 2 2 4 3 5 4 3 О а О 2 8 10 8 10 1О 12 12 8 14 9 12 в них с неодинаковой частотой.
Мы опишем сжатие, или сборку мусора, для массива КХР. Нельзя рассчитывать на то, что столбцы упорядочены правильно, поскольку некоторые из них копировались в конце списка. Вместо того чтобы упорядочивать, скажем, элементы вида НЛ1,4), поместим в начало каждого столбца метку, вмв О О -2 О -3 О О О -5 3 4 5 -4 2 $ 4 нА(4Ф4) О 3 3 1 2 Рис.
2.11. Содержимое массива РИЗ и указателей НА(-,4) перед сборкой мусора. с сбарко. м1сара а сеоабц040-уернб0иением списке с цсваноаищь мевки В начале кажбое0 с010лбщъ РО41О Х2 ~К, И КУ ' НА(Х2,4) + 1 нА(х2,4) вив(кт) 41О вив(кх) = - Х2 ~72=КХ=1 ВО 45О Х2 = К„И (2 Пресмавр вкв, пека ке Ефе01 наибен0 ибчайО н040м келлер РО 42О д2 = д2, И1ЕИО 426 хг (внв (л) . х т. О) ао то 430 430 хс - вив(Х2) ХЗ ~ д2 " кх вив(у2) -" нА(хс,4) ИХС ~ НА(хсс6) " ХЗ С Переписсцпь сщолбец, ОО 44О ~УЗ ~ КХ, ИХС д4 м ХЗ + Хз 44О вив(юз) вив(,х4) нА(хс,4) ~ кг - 1 НА(ХС,5) НА(ХС,Ц - ХЗ НА ('ХС, 6) ИХС КХ ~ИХС+ Ю2 аКХ+ ХЗ 4 БО соитх~ще ОО 46О М Кг, И1ЕИО 46О ЮЕР4) Ф О И1ЕК) ИХС Рнс, 2.12.
Фрагмент фортранной подпрограммы, выполняющей сборку му. сора н Списке, упорндоченном БО столбцам с соорко. мусора ю серочно-упоряооченном Опасно с усеанооап~ь мевка оначак кажбоч сврокц ?Ю 210 12 1~И К1 НА(12 1) + НА(12,1) = СИВ(КХ) 210. СЫН (К1) = 12 ВО25012М1, И с просмойр А,смй,поко. нобц666 нйМОНО начало нОООЙ сй()оя) ВО 220 д2 ~ Р2, МВЕМ0 220 1г (смк(ю2) .ьт. О) ао то 230 2зо 1с - смк(т2) 13 - "д2 К1 СМВ(72) НА(1С 1) ИХС = ЯА(1С,З) — 13 С ПЕОЕПНСаЛПЬ СГПРОН,У ЕО 240 ТЗ "- К1, ИХС д4 д ЛЗ + 13 А(ХЗ) = АИ4) смк ( тз) смк (ю4) НА(ХС,1) ~ К1 НА(1с,2) НА(ХС~2) ХЗ нА(1с,з) "- и1с К1 ИХС + 1 62~К1+13 250 сомт1м()е ВО 260 г4 В КХс МЮЕ 260 СМКР4) ° 0 МКВМВ ~ И1С Ь1 а НА(1,2) + 1 И1 ~ НА(1,3) 240 Рис. 2.(3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
