Вычисление NZR (i) и NZC (i)

NOP(!) iNZR(0-l t (NZR([) -I lN7C(i}- 1 end (lor i) Определение mi i иэ

я NOPOnin) Mi a (NOP ( ))

P(k) irain

Д1Я хаждого T такого что a p О

begin

Для каждого j таког) чт Эрц - О ?

ai О then begin

Обновление данных труктуры Внести art а RMA \ZR(r) NZR (г) 1 N7C(j) NZ(;(j)t!

end end (for j) end (for Г)

Стирание строки p(k) и столбца p(k) И( R4A RMI RMI - p (k}) end (for k) p(n)- RM!

В приведенной процедуре заложены определенные требования к структуре данных, используемых для обработки матрицы Производят ся следуняцие операции:

1) расчет ненулевых элементов в каждой строке и каждом столбце

2) поиск столбца для ненулевого элемента

3) поиск строки для ненулевого элемента;

4) сравнение строки с другой строкой для обнаружения ненулевого элемента в этой строке в столбце в котором в другой строке распо-южен нулевой элемент;

5) занесение ненулевого элемента в матрицу \

6) вычеркивание строки и столбца и* матрицы А

Структура данных должна быть приспособлена к выполнению этих операций над матрицей

S542 СТРУКТУРА ДАННЫХ ДЛЯ ПЕРЕГРУППИРОВКИ

Удобным способом запоминания разрел<енных матриц является способ, при котором используются двойные связанные ортогональные списки liij. В эти списки заносятся ненулевые элементы матрицы. Так как ведущие элементы занесены в диагональные позиции, то диаго нальные элементы обязательно являются ненулевыми и нет необходи

мости в их явном занесении в связанный список. Поэтому только не диагональные ненулевые элементы должны запоминаться В этом слу чае недиагональные ненулевые элементы нумеруются произвольно. Создается запись, соответствующая каждому недн атональном у ненулевому элементу матрицы Для /-го элемента запись состоит из шести составляющих и имеет вид

Здесь в переменных Col и Row хранятся соответственно номер столбца и помер строки этого элемента; Left задает индексный номер левого соседнего элемента, расположенного в той же строке. Right задает индексный номер правого соседнего элемента, расположенного в той же строке; Тор задает индексный номер верхнего соседнего элемента, расположенного в том же столбце и Bottom - номер нижнего соседнего эле мента, расположенного в том же столбце Если элемент не имеет со седнего в каком-либо направлении, т. е если он является первым или последним ненулевым элементом в строке или столбце, то соответствующая запись является нулем

Описанную структуру данных проиллюстрируем на примере следу ющен матрицы, номер ненулевого недиагонального элемента которой записан в подстрочном индексе

1 2 3 4 X X, х«

X X, X, X X, X Х„Х X

X, Х„ X

Таблица 15.2. Вводимы opToroHajbh

массивы данные для примера двойных

Рнс. 15,1 Двсйиые связанные ортогональные списки дтя примера матрицы рас смотренной в подра.чд 15.4 2

Созданные записи показаны на рис. 15,1. Кроме этого, формируются два массива Rowst и Colst. В Rowst (j) записан номер первого ненуле вого неднагонального элемента в строке j, а в Colst (к) - номер перво го недиагонального ненулевого элемента в столбце к. Для рассмотрен ной матричной структуры и нумерации ненулевых элементов, показан ной на рис 15-1 различные вводимые а массивы данные приведены в табл, 15.2. При использовании предложенной структуры данных one рации занесения и стирания которые производятся в процессе пере группирования матрицы, существенно упрощаются.

Рассмотрим заполнение элемента iij,, матрицы А Первоначально на .чначаем недиагональному ненулевому элементу номер, например т (который должен быть на единицу больше максимального номера уже рассмотренных элементов) Затем просматриваем /-ю строку от начала до конца и вносим элемент путем изменения массивов Lett и Right, свя зывающих его с соседними элементами. Затем просматривается стол бец А и изменяются массивы Тор и Bottom Рассмотренный а,1Горитм имеет вид

Col (m) - к; Row (m) -j

/Просмотр j-й строки /

i - - Rowst (j) Col (in К Col (i)

then ./Заполняющий элемент является первым недиго альным ненулевым элементом в строке j/ begin

Left (hi) - = 0 Left(i) Right (m).-i

ifd -Right(i)

While ifd.. Oun<iCol(m)>C 1 (ifd) do begm

1 Richl( )

ifd Right (i) end (while) Right (1] -m Left(m)-i Right (m)-i{d ifdO

then ,/Зл1ол11Як)и1,ии *лем1мт яв,яет(,я i иальным ненулепым элементом в i Left ([fd) til

\ZR (R S7R ,R;wlm,i I При6.,н,*е,1н i к

мента в строке j

Colst (к) Row(ni)<Row( )

bigin

Top (m) 0 Tor (1) m BoUom (m)

ifd Bottom (i)

rhile ifdO and Row(ni)>R,« (ifd) Iv begin

1 - Bottom (i) ifd -Bottom ([) end (wliile) Btttomii) m Top (m) i Bottom (m) ifd If ifdQffien Top (ifd) m

SZC (C<l(mH NZC (Col(m)) I

Рнс. 15.2. Иэмеиенне .iCBNX и правых указателей двух ближай-II] их элементов при стирании ь го столбца

В этой процедуре i

ые NZR (j) н NZC(k) содержат номера не

нулевых элементов в строке /ив столбце к соответственно и, следовательно, обновляются когда генерируется заполнение в позиции (/ к) массива \.

Стирание строк и столбцов из данной структуры также упрощается Чтобы стереть столбец из матрицы для каждого к-го элемента в этом столбце левые и правые указатели соседних элементов в строке следует изменить как показано на рнс. 15-2. Процедура вычеркивания столбца / и строки / нз матрицы может быть описана следующим образом:

Вычеркивание столбца j/ к--Colst (J) While кфО d hesin

ll Left (k)0 then Right (Lelt(k)t - Right fk) Right(k)0 then Left (Riht jk))-Left (k) NZR (Row(k)) NZR (Row(k))-1 к Bottwn (k) end {while)

cost(j) -0 . Означает что j и ст »лбеи вычеркнут

Вычеркивание строки / выполняется аналогично

В приведенной процедуре NZR обновляется для каждой строки, ко торая содержит элемент в /-м столбце, а номер ненулевых элементов \меньшается на единицу после стирания столбца.

J5-4.i. /.(У-ФДКТОРИЗАЦИЯ И ПРЯМОЕ МСКЛЮЧЕННЬ-ОБРАТНАЯ ПОДСТАНОВКА (12-14]

В этом разделе рассматривается метод/,(/-фактори.зации и прямо го исключения - обратной подстановки используемый в технике разреженных матриц. Эти операции существенно упрощаются при использовании треугольной индексации матрицы Предполагается, что матрица перегруппирована с целью миннмизации числа заполнений, положения которых уже определены и которые необходимо ввести в данные структуры. Эю значит, что на этой стадии определены только положе ния заполняющих элементов и в этих местах записаны нули. Значения которые должны быть занесены в эти позиции, определяются в процес се LU факторизации

Все элементы, записываемые в матрицу А (т. е, ненулевые и запол няняцие), нумеруются- Ведущие элементы на главной диагонали нуме руются первыми. Оставшиеся элементы разделяются на две части - элементы а L и элементы в U Для каждого столбца и строки к остав шиеся элементы нумеруются от i до п - 1 в следующем чередующемся порядке: 1) элементы к го столбца L сверху вниз; 2) элементы к-й строки - слева направо Покажем пример нумерации элементов мат-рИ1Ш

1 2

3 4

X, Х„ Х,4 Xt

х„ Х[«

Затем формируется массив Rowcol. В позиции Rowcol ( ) записыва ется номер столбца i-ro недиагонального элемента, если он находится в и, и номер строки этого элемента, если он находится в L. Для эле ментов на главной диагонали в Rowcol (!) записывается сам индекс i который является номером строки и столбца. Для только что показан ной структуры матрицы в массив Rowcoi записывается следующая ин формация:

Индекс 12345678QI0 12 14

18 S9

Rowcol 4 4 5 4 5 4 5 5 5 Аналогично создаются два массива Lcolst н Urowst В позиции Lcolst (к) содержится индексный номер верхнего неднагон ал ьного элемента столбца й в L а в позиции Urowst (j) содержится индексный номер крайне левого неднагон ал ьного элемента строки j в U. Для рассмот ренной структуры матрицы эти массивы содержат следующую инфор мацию

Значения элементов записываются в массив А В А (i) записывается значение элемента с индексным номером /.

Перечислим ненулевые операции, необходимые в процессе LU факторизации матрицы рассмотренной структуры --

Деление а,,* а,з и„

Корректировка Ои "зя ~ <hi°ii м - attOu

Л(9)Л(9)М(1)

А(ЩА{1б)~А(а)хА(9)

А(4)А(*)~А(7)КА{9)