LEC-27 (Материалы к лекциям), страница 2

В схеме имеется основной массив ENV, содержащий элементы профиля (кроме диагональных) из всех строк матрицы. Для указания начала отрезка каждой строки используется вспомогательный индексный вектор XENV длины N+1. Чтобы добиться единообразия при индексировании, полагаем XENV (N+1) равным ENV (А)+1. Индексный вектор XENV дает возможность удобного доступа к любому ненулевому элементу. Отображение ENV(А) на множество 1,2,... ,ENV (А) задается таким образом: i,jXENV( i+1)-( i-j )

Другими словами, значение недиагонального элемента a_ij находится в ENV(XENV(i+1)-(i-j))

Пусть, например, нужно найти значение элемента a₂₁.

Имеем: XENV( 2+1)-(2-1)=2-1=1 поэтому a₂₁ хранится в ENV(1). Но попытка найти элемент a₃₂ приведет к тому же результату, что говорит о необходимости какого-то дополнения к алгоритму.

Чаще всего используемой операцией является выделение профильного отрезка какой-либо строки. Это удобно делать, пользуясь следующим фрагментом для поиска элементов a_ij:

J1=XENV(I); J2=XENV(I+1)-1

IF(J2.LT. J1) GO TO 200

DO 100 J= J1, J2

ЕLEMENT=ENV(J)

.........................................

100 СONTINUE

200 ........................

Пользуясь этим фрагментом, получим:

для a₂₁: J1=1; J2=2-1=1, поэтому ELEMENT=ENV(1);

для a₃₂: J1=2; J2=2-1=1 и т.к. J2 < J1, то a₃₂ в схеме нет или , что то же самое, a₃₂ =0;

Преимущество такого варианта в том, что он легко приспосабливается к случаю несимметричной матрицы А.

Обычная схема (Густавсон 1972, Шерман 1975).

В схеме имеется основной массив LN, содержащий все ненулевые элементы нижнего треугольного множителя. Отводится ячейка для хранения каждого логически ненулевого элемента в множителе. При этом ненулевые элементы, исключая диагональные, хранятся в LN столбец за столбцом. Предусмотрен сопровождающий вектор NZ, дающий строчные индексы ненулевых элементов. Кроме того, для указания начала ненулевых элементов каждого столбца в массиве LN (или, что всё равно, в массиве NZ используется индексный вектор XL. Диагональные элементы хранятся отдельно в векторе DIAG.

Если нужен доступ к ненулевому элементу a_ij, то нет никакого прямого метода для вычисления соответствующего индекса в массиве LNZ]. Приходится выполнять проверку индексов в NZSUB. С этой целью можно использовать приводимый ниже фрагмент программы. Заметим, что всякий элемент, не представленный в структуре данных, равен нулю.

K1=XL(J); K2=XL(J+1)-1

ATJ=0,0

IF (K2.LT.K1) GOTO 300

DO 100 K=K1,K2

IF (NZ(K).EQ.I ) GOTO 200

100 CONTINUE

GOTO 300

200 ATJ=LN(K)

300

Примеры нахождения a_ij

a₄₁=? K1=1= XL(1)=1; K2= XL(2) -1=2;

K=1: NZ(1)=2  4;

K=2: NZ(2)=4 = 4, следовательно AIJ=LN(2);

a₄₂=? K1=XL(2)=3; K2=XL(3) -1=4-1=3;

K=3: NZ(3)=4 = 4, следовательно AIJ=LN(3);

a₄₃=? K1=XL(3)=4; K2=XL(4) -1=6 -1=5;

K=4: NZ(4)=5  4;

K=5: NZ(5)=6  4, следовательно AIJ= 0;

a₆₁=? K1=XL(1)=1; K2=XL(2)-1=3-1=2;

K=1: NZ(1)= 2  6;

K=2: NZ(2)= 4  6, следовательно AIJ= 0;

a₆₅=? K1=XL(5)=7; K2=XL(6)-1=8-1=7;

K=7: NZ(7)=7  6, следовательно AIJ= 0;

a₆₃=? K1=XL(3)=4; K2=XL(4)-1=5;

K=4: NZ(4) = 5  6;

K=5: NZ(5) = 6 = 6, следовательно AIJ=LN(5);

a₇₆=? K1=XL(6)=8; K2=XL(7)-1=9-1=8;

K=8: NZ(8) = 7 =7, следовательно AIJ=LN(8);

a₆₄=? K1=XL(4)=6; K2=XL(5)-1=7-1=6;

K=6: NZ(6) = 5  6, следовательно AIJ= 0;

a₇₂=? K1=XL(2)=3; K2=XL(3)-1=4-1=3;

K=3: NZ(3) = 4  7, следовательно AIJ= 0;

Компактная схема.

Эта схема является модификацией обычной, принадлежит Шерману (1975 г.) Идея состоит в уменьшении вектора NZ, что достигается удалением строчных индексов любого столбца, для которого они образуют финальную подпоследовательность индексов предыдущего.

Взамен на получаемое сжатие приходится вводить индексный дополнительный вектор XNZSUB, указывающий для каждого столбца начало его строчных индексов в массиве NZSUB

Теперь доступ к элементу, стоящему в позиции (i,j) осуществляется следующим образом: