Прямые методы для разреженных матриц. О. Эстербю, З.Златев (984134), страница 4
Текст из файла (страница 4)
Подсчитать также общее число элементов, столб- цОВЫЙ индекс котОрых меньше 1, и записать зто числО НЛ(1,4) и НЛ(1,6). 3таа 2. Записать элементы массивов А и СХК, стоящие в позициях с номерами от ХЕ+ 1 до ЫЕ+ ХХ, обратно в перВые ХЕ позиЦий, но с соблюДением упОряДочения по стрОкам. Использовать НЛ(1, 3) как указатель позиции, в которую должен быть помещен очередной элемент 1-Й строки.
Згйй 3. В массив КХК мы записываем стрОчные индексы матричных элементов, упорядоченные по столбцам. Более точно, в позициях с номерами от НЛ(1,4)+ 1 до НА(1+ 1,4) будут храниться строчные индексы элементов 1-го столбца матриць1 Л. ') Б том состоянии, какое они приобретают после третьего этапа упорядочения, — П~им, П8 086. 20 НА(Х,З) = НА(Х,б) в НА(Х,1) -" НА(Х,4) с поОсчцяОГпь чцоло зйймюнщо6 пюжооц с(п()опц ц ощол$,~~ь ХУО ЗО Х = 1, ИЕ ,у = синО) СИВ(ИЕ+Х) = У А(т+Х) = А(Х) НА( У, 6) = НА(Л~ 6) + У = ВИВ(Х) ' ЗО нА(,у,з) = НА(у,з) + 1 и1 =и-1 с Нацп1ц пцчцпо кажбой сп1()окц ц оаод5Ца (УО 40 Х - "1., И1 НА(Х+1 1) — НА(ху1) * НА(х 3) НА(х+1,4) = НА(Х,4) + НА(х,б) НА(Х,З) = НА(Х,1) 40 НА(Х,6) = НА(хф4) НА(И,З) = НА(И~1) нА(и,б) = нА(и,4) с Обрап1нО.В па()опцсь элемонйОЕ (УО 50 ХЗ "- 1р ИК х = ВНВ(ХЗ) Х2 -" НА(Х,З) + 1 х1 = ий + ХЗ сиВ(х2) = сиВ(Х1) А(Х2) = А(х1) ЪО НА(Х,З) - "Х2 С Помквцп1Ь Ь ВИВ.
Сп1()ОЧНЫ6 цн66КСь( (УО 70 Х 1, И У1 = НА(Х,1) + У2 = НА(Хуз) ЭО 70,УЗ =,У1,,У2 ,У = СИВ(,УЗ) К = НА(3~6) + 1 ВИВ(К) = Х 70 НА(,У,б) = К Рнс, 2.2. Ф(~йРмонт фор*)~пнной подпрогрпммь~, оь~попнййуций перо~порп- ДОЧФННФ. 1 2 5 4 3 2 1 3 1 2 3 2 1 2 З4 54555 З 5 5 4 3 2 1 3 1 2 3 2 З 4 5 4 5 5 5 З4512З О 2 5 3 10 О 2531О О 2 4 5 3 О 2 4 5 3 сии ИА (., 1) иА(., з) иА( ° ~ 4) иА( ° ф б) 5 З 412 З212 З 1 4 2 5 1 3 5 2 4 5 1 2 2 3 3 1 4 5 2 3 0 2 5 310 2 5 31О» 0 2 4 5 3 245312 Рис, 2.3.
Содержимое массивов после этапов 1 и 3„ Текст на рис. 2,2 — это лишь один из способов переупорядочения, причем он содержит несколько искусственное условие ХХ ~ 2ХХ. Хотя процесс исключения часто накладывает на 1Щ бол~е жесткие Ограничения поучи~ель~о все же рассмотреть другой метод переупорядочения, не требующий дополнительного места В А и СКК, Этот процесс также можно разделить на, три этапа: этап 3 совпадает с этапом 3 первого процесса, и это же верно для этапа 1, за исключением копирования элементов А и СИК.
На этапе 2 мы начинаем с Выбора элемента из А и чтения его строчного индекса в К1')К. Используя НА(1, 3) как указатель места, куда должен быть помещен очередной элемент 1-й строки, мы записываем туда наш элемент; на соответствующее место в СХК записывается его столбцовый индекс. Но сначала нужно запомнить элемент '), который хранился там прежде. ПродОлжаем Таким обрззОм до тех пор, пйкз не приходится ~выместит~ О~ередной ~ле~е~т в ~озицию, Откуда 1) И его столбцовый индекс.
— Прил. перев. Нз рис, 2.2 приВеден Гекст фортрзнной реализации этОГО- упорядочения, а на рис. 2,3 показано содержимое массивов А, СКК, КХК и НА после этапов 1 и 3. Заметим, что содержимого массивов А„СХК, НА( °, 1) достаточно для полного описания матрицы А, т. е. хватает 2ХЕ+ и ячеек памяти.
Однако, чтобы процесс исключения ВыпОлнЯлсй более эффективнО, нужна некотОраЯ допОлнительная память (например, массив КХК). 45 Х2 ~ НА(ку1) К~К-1 Х Иж(Х2) ХР (Х. ЬТ. О) И) ТО 4$ КЫВ(12) = -1 хР «л(х2) У а сне(х2) 50 СОИТХЯ(»Е х1 = нл(хЯ + 1 ,нА(1,3) х1 А(Х1) ЖР сна(х1) У ПОМЕСП»ЫП»Ь 6 В,МК СВРОЧй(»(Ф Цй06((,0Ы (»О70Х ж1у И 01 ~ нл(х,1) + 1 н»~(х 3) )»О 70 73 ~ Му М д' а СМВ(УЗ) х в НА(У,6) + 1 ВИВ (К) Х 70 НА(т 6) " К был выбран первый. Чтобы задержать нас*упление этого события, мы начинаем процесс с элемента в позиции ИУ.
(Место, зарезервированное для последнего элемента и-й строки)'. Если процесс Останови~си р~~ь~е, чем раз~~щ~ны все элементы, то находим новый стартовый элемент в позициях, зарезервированных для последних элементов (и — 1) -й, (и — 2)-й, ... строк. При этом компоненты НА(,1) используются как указатели. Чтобы в дальнейшем можно было Определить, что элемент уже выбран из массива А, мы ДОл»кны установить метку, С этой целью в соответствующую позицию КХК записывается отрицательное число. Как отмечено выше, после упорядочения содержимое КХК уже не нужно. Поэтому„записывая — 1 в КХЕ, мы не уничтожаем полезную информацию, На рис, 2.4 приведен текст фортранной реализации этого упорядочения, не требующего дополнительной памяти (за исключением указателей в НА). На рис.
2.5 показано содержимое массивов А, СИЯ и КХЯ после каждого из трех этапов, Новая программа Несколько длиннее. Чем для первого про~ 5 4 3 2 1 3 1 2 3 2 1 2 1 2 3 4 5 4 5 5 5 1 2 4 З 4 5 1 2 З 4 2 З 5 0 2 5 8 10 0 2 5 8 10 0 2 4 5 8 а 2 4 5 8 ннн НА(.,1) НА(«,3) НА(.,4) НА(.,6) 3 5 4 1 2 1 3 2 2 3 2 4 1 2 5 1 2 3 5 4 5 4 5 -1 "1 -1 1 -1 -1 -1 -1 -1 1 -1 -1 Вин НА(.,1) нА(., 3) НА(.,4) НА(.,6) 0 2 5 8 10 2 5 8 10 12 0 2 4 5 8 0 2 4 5 8 10 цесса; ~дн~~~ более ~нима~~~~ное исследов~ние Обнаружи.вает, что число операций примерно одинаково для обеих. Во всЯком случае„ при рабОте разреженнОЙ матричной программы львиная доля вычислений почти наверное придется на какое-то другое местО.
Замечание 2.2. Если элементы матрицы уже упорядочены по стрОкам„тО первый процесс сОхранит порядок„в то время как при втором будет выполнена циклическая перестановка внутри ка~дОЙ строки. Мы ~о~е~ использовать упорядоченность, выполняя лишь этапы 1 и 3 второго процесса, И Нужно заметить, что оба варианта переупорядочения основаны на идеях, предложенных в 148, 49~. 2.8. Й$)оцесс исключеиия Мы готовы теперь приступить к процессу факторизации, или исключения. Как отмечалось в ~ 2.1, атот процесс состоит А 3 5 4 1 сна 4 1 2 5 ВНВ 2 2 3 НА(.,1) 0 2 5 НА(-,3) 2 5 8 НА(.,4) 0 2 4 НА(.,6) 2 4 5 Рис, 2.5.
Содержимое массивов До'ИНИЯ. после каждого иэ трех этапов переупоря- из и — 1 шагов. Предположим, что мы находимся в начале 1~-го шага (1 ==: 1~ ~ п — 1). Элементы 1-й строки матрицы коэффициентов занимают в массиве А позиции с номерами от НА(1, 1)+ 1 до НА(1,3), а их столбцовые индексы — соответствующие позиции в массиве СХК. Полезно также знать расположение элементов подматрицы А~ (и подматриц А~ для ~ <.
1~). Поэтому мы введем указатели НА(1, 2), такие, что элементы А~ (или Аь если 1 к) находятся в позициях массива А с номерами от НА(1,2)+ 1 до НА(1,3). Нам потребуются обозначения К~ — — НА (1, 1), К.1 = НА (1, 4), 1 ~ = НА (1, 2), 1.; = НЛ (1, 5), (3.1) М; = НА (1, 3), М; = НЛ (1, 6).
Выполняются соотношения К~ 1.~ М~ и К; = 1.; в начале процесса (см. рис. 2.6), Заметим, что элементы 1-й строки Элембнп~Ф 1,-0 сВ~Ои.ц Рис. 2.6. Указатели К~, 1.~ и М~. ::;.- матрицы коэффициентов не упорядочиваются в соответствии ,,:- со столбцовым индексом. Однако мы будем поддерживать ,,'- частичный порядок в том смысле„что для элементов в пози,':.' циях от К~+ 1 до Е~ столбцовые индексы меньше, чем ппп(1, 1~), а для элементов в позициях от Ь+ 1 до М;— больше или равны пип(1,Ц. Столбцовые индексы этих элементов находятся в одноименных позициях массива СКЙ (см.
рис. 2.6). Точно так же в упорядоченном по столбцам списке КХК строчные индексы элементов 1'-го столбца (1~::1 ~ и) находятся в позициях от К~ + 1 до Т;, если они меньше К и в позициях от Е,~+ 1 до М;, если они больше или равны К. Замечание 2.3. Роль массива ККК в том, чтобы облегчить поиск элементов нужного столбца, что важно при просмотре А(~.
Однако информаЦиЯ, ОтносЯщаЯсЯ к первым 1 — 1 стОлб" цам матриц А, не ну а 1), соответ Вующ е позиции и КХК могут исиользоиатьси дли других целей. Поэтом~ длина ХХ1 массива КХЙ может быть меньше ХХ. В НВЧаЛЕ 1ь"ГО ШаГа ПРОЦЕССа ИСКЛЮЧЕНИЯ ЭЛЕМЕНТЫ х(-й строки, столбцоВые индексы которых больше или раВны (т. е. находящиеся в позициях от 1(, + 1 до М(, массива А), переписыВаются на соотВетствующие места В последних п — 1+1 позициях вещественного массива Р1ЧОТ (длины и). До начала,' процесса всем компонентам этого последнего массива присваиваются нулевые значения, Мы предполагаем, что необходимые перестановки уже выполнены (см. гл. 3) „ так что элемент а®, находящийся сейчас в Р1ЧОТ(1), не раВен нулю.
Теперь мы проведем вычисления, указанные формулой (1.2.1), для тех строк 1, для которых аф Ф О. Соответствую. щие строчные индексы расположены В позициях От 1.( + 1 дО М(, массива КХЙ. р(1ля каждой такой строки 1 мы сперва определяем местоположение элемента аф~, для чего в массиве СХК просматриваются позиции от 1.;+ 1 до М;, пока не будет найдено число Е, Этот элемент переставляется с элементом, находящимся в позиции 1.(+ 1 (это относится к обоим массивам: А и ('.ХЙ), после чего значение 1( увеличивается на единицу. Вычисляем и помещаем результат в А(Ь) (ср. 5 2.6).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
