Цель данного исследования заключается в создании алгоритма осевой операции для разреженной матрицы, подобной матрице, представленной на рис. 14. Ясно, что преобразование типа (13) повлияет только на те строки матрицы, в которых есть ненулевые элементы в осевом столбце, и только на те столбцы матрицы, в которых есть ненулевые элементы в осевой строке.

Алгоритм поворота во многом напоминает прямолинейное применение методов связывания, которые рассматривались выше. В частности, он во многом похож на алгоритм 2.2.4А сложения полиномов. Однако существуют дополнительные соображения, которые немного усложняют нашу задачу: если в (13) b ф О, с О, но cf = О, в представлении разреженной матрицы не будет элемента cf, то его потребуется вставить; а если Ь О, с О, cf О, но cf - bcja = О, то придется удалить элемент, который там находился прежде. Эти операции вставки и удаления более интересны при работе с двумерным массивом, чем с одномерным. Для их выполнения необходимо знать обо всех связях, вовлеченных в данный процесс. Алгоритм обрабатывает все строки матрицы последовательно снизу вверх. Для эффективного выполнения операций вставки и удаления необходимо ввести таблицу указательных переменных PTR [ j], по одной для каждого рассматриваемого столбца. С помощью этих переменных совершается обход столбцов по направлению снизу вверх, в результате чего предоставляется возможность обновления соответствующих связей в обоих измерениях.

Алгоритм S (Осевое преобразование разреженной матрицы). Выполним операцию осевого преобразования (13) для матрицы, показанной на рис. 14. Предположим, что PIVOT - это переменная связи, которая указывает на осевой элемент. В алгоритме используется вспомогательная таблица переменных связи PTR[j], по одной для каждого столбца матрицы. Предполагается, что переменная ALPHA и поле VAL для каждого узла имеют тип числа с плавающей запятой или рационального числа, а все остальные - целочисленный тип.

51. [Инициализация.] Установить ALPHA 4- 1.0/VAL(PIVOT), VAL(PIVOT) 1.0 и

10 ROW (PIVOT), РО LOC (BASEROW [10]); JO <- COL (PIVOT), QO LOC (BASECOL [JO]).

52. [Обработка осевой строки.] Установить РО LEFT(PO), J COL(PO). Если J < О, перейти к шагу S3 (осевая строка пройдена). В противном случае установить PTR[J] LOC (BASECOL [J]), VAL(PO) 4- ALPHA x VAL(PO) и повторить шаг S2.

53. [Поиск новой строки.] Установить Q0 UP(QO). (В остальной части алгоритма последовательно снизу вверх перебираются все строки, которые содержат элемент данных в осевом столбце.) Установить I <- ROW(QO). Если I < О, выполнение алгоритма прекращается. Если I = 10, повторить шаг S3 (осевая строка обработана). В противном случае установить Р <- LOC(BASEROW[I]), ?1 <г- LEFT(P). (Указатели Р и Р1 позволяют совершить проход по строке I справа налево так же, как РО позволяет это сделать для строки 10. Алгоритм 2.2.4А вьшолняется аналогично. При этом РО - LOC(BASEROW[10]).)

54. [Поиск нового столбца.] Установить РО 4- LEFT(PO), J <- COL(PO). Если J < О, установить VAL(QO) <--ALPHA х VAL(QO) и вернуться к шагу S3. Если J = JO,

повторить шаг S4. (Таким образом, элемент осевого столбца в строке I обрабатывается после всех элементов других столбцов; причина заключается в том, что значение VAL(QQ) потребуется на шаге S7.)

55. [Поиск элемента I, J.] Если COL(Pl) > J, установить Р Р1, Р1 LEFT(P) и повторить шаг S5. Если COL(Pl) = J, перейти к шагу S7. В противном случае перейти к шагу S6 (вставить новый элемент в столбце J строки I).

56. [Вставка элемента I, J.] Если ROW(UP(PTR[J])) > I, установить PTR[J] 4-UP(PTR[J]) и повторить шаг S6. (Иначе получим ROW(UP(PTR[J])) < I; новый элемент нужно вставить сразу над узлом NODE(PTR[J]) в вертикальном направлении и слева от узла NODE(P) в горизонтальном направлении.) В противном случае установить X Ф= AVAIL, VAL(X) О, ROW(X) I, COL(X) J, LEFT(X) Pl, UP(X) UP (PTR [J]), LEFT(P) X, UP (PTR [J]) X, Pl X.

57. [Осевое преобразование.] Установить VAL(Pl) VAL(Pl) - VAL(QO) x VAL(PO). Если теперь VAL(Pl) = 0, следует перейти к шагу S8. {Замечание. При использовании системы счисления с плавающей запятой условие "VAL(Pl) = О" следует заменить условием "VAL(P1) < EPSILON" или, что еще лучше, условием "большинство значащих цифр VAL (Р1) утрачено при вычитании".) В противном случае установить PTR[J] Pl, Р Pl, Pl LEFT(P) и вернуться к шагу S4.

58. [Удаление элемента I, J.] Если UP(PTR[J] ) ф?! (или, что, по сути, то же самое, если ROW(UP(PTR[J])) > I), установить PTR[J] UP(PTR[J]) и повторить шаг S8. В противном случае установить UP(PTR[J]) UP(Pl), LEFT(P) 4- LEFT(Pl), AVAIL < Pl, Pl LEFT(P). Вернуться к шагу S4.

Читателю предлагается (в качестве очень поучительного упражнения) самостоятельно создать программу для реализации этого алгоритма (см. упр. 15). Здесь же стоит отметить, что для каждого узла BASEROW[i] и BASECOL[j] достаточно только одного слова памяти, поскольку большинство их полей не будет востребовано (см. заштрихованные области на рис. 14, а также программу из раздела 2.2.5.) Боле того, в целях дополнительной экономии памяти значение -PTR[j] можно хранить как ROW(LOC(BASECOL[j])). Время вьшолнения алгоритма S приблизительно пропорционально количеству матричных элементов, которые вовлечены в операцию осевого преобразования.

Такое представление разреженных матриц с помощью ортогональных циклических списков очень поучительно, но специалисты по численному анализу разработали несколько более совершенных методов. [См., например, работу Fred G. Gustavson, ACM Trans, on Math. Software 4 (1978), 250-269; a также алгоритмы работщ с графами и задачами сетевого планирования в главе 7.]

УПРАЖНЕНИЯ

1. [17] Предложите формулу для LOC(A[J.K]), если А - это матрица типа (1), а каждый ее узел состоит из двух слов, причем все узлы хранятся последовательно в лексикографическом порядке индексов.

► 2. [21] Формула (6) выведена на основании предположения, что О < Ir < rfr для 1 < г < к Найдите общую формулу, в которой предполагается, что Ir < I < Мг, где I, и Ur - любые значения нижней и верхней границ данного измерения

3. [21] В этом разделе рассматривались нижние треугольные матрицы A[j,fc], где О < к < j < п. Как следует видоизменить приведенные рассуждения в случае, если отсчет индексов начинается с единицы, а не с нуля ul<k<j<n?

4. [22] Покажите, что при хранении верхней треугольной матрицы A[j,fc], где О < J < к < п,в лексикографическом порядке индексов распределение памяти будет удовлетворять условию (8). Найдите в таком случае формулу для LOC(A[J,K]).

5. [20] Покажите, что значение A[J,K] можно занести в регистр А компьютера MIX, выполнив одну команду и использовав инструменты косвенной адресации, которые описываются в упр. 2.2.2-3, даже если А является треугольной матрицей типа (9). (Предполагается, что J и К находятся в индексных регистрах.)

► 6. [М24] Рассмотрим "тетраэдрические массивы" kU.j.ki, B[j,j,fc], где О < к < j < i < п в массиве АиО<г<<А;<7гв массиве В. Предположим, что оба эти массива хранятся в последовательных адресах памяти в лексикографическом порядке индексов. Покажите, что LOC(A[I,J,K]) = ао + /i(I) + /2(1) -i- /з(К) для некоторых функций /1, /2, /з- Можно ли получить аналогичное выражение для LOC(B[I,J,K])?

7. [М23] Найдите общую формулу распределения памяти для fc-мерного тетраэдриче-ского массива A[n ,«2,.. • где О < и < • • < «2 < Ч < п.

8. [33] (Задача П. Вегнера .) Предположим, что в памяти необходимо разместить шесть тетраздрических массивов A[I.J,K], B[I.J.K], C[I.J.K], D[I,J,K], ECI.J.K] и F[I,J,K], где 0<K<J<I<7i. Существует ли какой-нибудь эффективный способ выполнения этой задачи, аналогичный (10), но для двумерного случая?

9. [22] Рассмотрим таблицу такого же типа, как и таблица на рис. 13, но гораздо большую, в которой все связи направлены в одну сторону (а именно - выполняется условие LINK(X) < X для всех узлов и ссылок). Придумайте алгоритм для поиска адресов всех голубоглазых блондинок в возрасте от 21 до 23 лет, основанный на обходе различных полей связей, причем таким образом, что по завершении выполнения алгоритма для каждого из списков выполняется по крайней мере один обход каждого из списков FEMALE, А21, А22, А23, BLOND и BLUE.

10. [26] Можно ли придумать более совершенный способ организации таблицы с персональными данными, чтобы описанный В предыдущем примере поиск можно было выполнить более эффективным способом? (Простой ответ "Да" или "Нет" в данном случае не годится.)

11. [11] Допустим, что в каждой строке матрицы размера 200 х 200 находится по крайней мере четыре ненулевых элемента Какой объем памяти потребуется для представления ее в виде, показанном на рис. 14, если для каждого узла используется по три слова, а для заголовков списков - по одному?

► 12. [20] Чему равны VAL(QO), VAL(PO) и VAL(Pl) в начале шага S7, если их выразить с помощью переменных а, 6, с, d из (13)?

► 13. [22] Почему в матрице на рис. 14 циклические списки используются вместо линейных списков? Можно ли изменить алгоритм S так, чтобы в нем не использовалась циклическая связь?

14. [22] Алгоритм S позволяет сэкономить время выполнения осевого преобразования разреженной матрицы, поскольку он предоставляет возможность пропускать столбцы, в которых значение элемента из осевой строки равно нулю Покажите, что такая экономия \южет быть получена в большой разреженной матрице, которая хранится в последовательном порядке, за счет применения вспомогательной таблицы LINK[j], 1 < J < п.