AOP_Tom1 (1021736), страница 86
Текст из файла (страница 86)
Поскольку в большинстве алгоритмов обработки матриц используется последовательный доступ к элементам, а не произвольный, то при таком связанном представлении данных работа может выполняться гораздо быстрее, чем при последовательном представлении. Типичным примером нетривиального алгоритма работы с разреженными матрицами такого типа является осевое преобразование (ргпо1 э1ер), которое является пут ОР Рис. 14, Представление матрицы (12) с узлами в виде йпя Сое уй1 Заголовки списков находятся слева н сверху важнейшей частью алгоритмов для решения линейных уравнений, обращения ма- триц и решения задач линейного программирования с помощью симплекс-метода. Осевое преобразование представляет собой следующее преобразование матрицы. Осевой столбец 1/а 6/а Осевая строка — с/а И вЂ” 6с/а (13) Любая другая строка Предполагается, что осевой элемент, а, не равен нулю, Например, применение осевого преобразования к матрице (12), где осевым элементом считается число 10 в строке 2 и столбце 1, приводит к такому результату: -5 0 -100 0 01 0 2 0 0 0 О 0 3 0 0 5 (14) До преобразования Любой Осевой другой столбец столбец а с - с1 После преобразования Любой другой столбец Цель данного исследования заключается в создании алгоритма осевой операции для разреженной матрицы, йодобной матрице, представленной на рис.
14. Ясно, что преобразование типа (13) повлияет только на те строки матрицы, в которых есть ненулевые элементы в осевом столбце, и только на те столбцы матрицы, в которых есть ненулевые элементы в осевой строке. Алгоритм поворота во многом напоминает прямолинейное применение методов связывания, которые рассматривались выше. В частности, он во многом похож на алгоритм 2.2.4А сложения полиномов.
Однако существуют дополнительные соображения, которые немного усложняют нашу задачу: если в (13) Ь Ф О, с ф О, но д = О, в представлении разреженной матрицы не будет элемента с(, то его потребуется вставить; а если Ь ~ О, с ф. О, Н ф О, но Н вЂ” Ьсг~а = О, то придется удалить элемент, который там находился прежде. Эти операции вставки и удаления более интересны при работе с двумерным массивом, чем с одномерным. Для их выполнения необходимо знать обо всех связях, вовлеченных в данный процесс. Алгоритм обрабатывает все строки матрицы последовательно снизу вверх. Для эффективного выполнения операций вставки и удаления необходимо ввести таблицу указательных переменных РТЕ [Л], по одной для каждого рассматриваемого столбца.
С помощью этих переменных совершается обход столбцов по направлению снизу вверх, в результате чего предоставляется возможность обновления соответствующих связей в обоих измерениях. Алгоритм В (Осевое преобразование разреэсенной матирицм). Выполним операцию осевого преобразования (13) для матрицы, показанной на рис. 14. Предположим, что Р1ЧОТ вЂ э переменная связи, которая указывает на осевой элемент. В алгоритме используется вспомогательная таблица переменных связп РТН[Л], по одной для каждого столбца матрицы.
Предполагается, что переменная А1РНА и поле ЧАЕ для каждого узла имеют тип числа с плавающей запятой или рационального числа, а все остальные — целочисленный тип. 81. [Инициализация.] Установить АЕРНА ь- 1.0/ЧА(.(Р1ЧОТ), ЧА1(Р1ЧОТ) +- 1.0 и 10+- КОН(РХЧОТ), РО +- АТОС(ВАБЕКОН[10]); ЛО < — СО1(Р1ЧОТ), ЦО ь- 100(ВАБЕСОЕ[ЛО]). В2.
[Обработка осевой строки.] Установить РО +- 1.ЕРТ(РО), Л +- С01.(РО). Если Л < О, перейти к шагу БЗ (осевая строка пройдена). В противном случае установить РТВ[Л] +- 1ОС(ВАБЕС01[Л]), ЧАЕ(РО) е- АГРБА х ЧАЕ(РО) и повторить шаг 52. ВЗ.[Поиск новой строки.] Установить ЦО +- ОР(ЦО). (В остальной части алгоритма последовательно снизу вверх перебираются все строки, которые содержат элемент данных в осевом столбце.) Установить 1 е- НОН(ЦО). Если 1 < О, выполнение алгоритма прекращается. Если 1 = 10,повторить шаг БЗ (осевая строка обработана). В противном случае установить Р +- ЕОС(НАНЕВОЮ[1]), Р1 т- ЕЕРТ(Р).
(Указатели Р и Р1 позволяют совершить проход по строке 1 справа налево так же, как РО позволяет это сделать для строки 10. Алгоритм 2.2.4А выполняется аналогично. При этом РО = 10С(ВАБЕВОН[10]) ) Б4.[Поиск нового столбца.] Установить РО +- 1.ЕРТ(РО), Л +- С01.(РО). Если Л < О, установить ЧАМЦО) < — — АЕРНА х ЧАЕ(ЦО) и вернуться к шагу БЗ. Если Л = ЛО, повторить шаг 84. (Таким образом, элемент осевого столбца в строке 1 обрабатывается после всех элементов других столбцов; причина заключается в том, что значение ЧАЕ(00) потребуется на шаге 87.) 85.
(Поиск элемента 1, Ц Если СОЕ(Р1) > Л, установить Р +- Р1, Р1 е — ХЕРТ(Р) и повторить шаг 85. Если СОЕ(Р1) = Л, перейти к шагу 87. В противном случае перейти к шагу 86 (вставить новый элемент в столбце Л строки 1). 86. (Вставка элемента 1, Ц Если ЕОЧ(ОР(РТЕ[1])) > 1, установить РТЕ[1] +- ЯР(РТЕ[1]) и повторить шаг 86. (Иначе получим ЕОЫ(ОР(РТЕ[1])) < 1; новый элемент нужно вставить сразу над узлом 8008(РТЕ[Я]) в вертикальном направлении и слева от узла 800Е(Р) в горизонтальном направлении.) В противном случае установить Х ~ АЧА1(., ЧАЕ(Х) < — О, ЕОЧ(Х) е — 1, С01(Х) э — 3, 1ЕРТ(Х) +- Р1, ОР(Х) +- ОР(РТЕ[Я]), (ЕРТ(Р) +- Х, ОР(РТЕ[0] ) +- Х, Р1 е- Х. 87. [Осевое преобразование.] Установить ЧАЕ(Р1) + — ЧАЕ(Р1) — ЧА(.(00) х ЧАЕ(РО).
Если теперь ЧАЕ(Р1) = О, следует перейти к эпагу 88. (Замечание. При использовании системы счисления с плавающей запятой условие "ЧАЕ(Р1) = 0" следует заменить условием "]ЧАЕ(Р1)] < ЕРЯ1008" или, что еще лучше, условием "болыпинство значащих цифр ЧАЕ(Р1) утрачено при вычитании".) В противном случае установить РТЕ[)] < — Р1, Р е — Р1, Р1 е — ХЕРТ(Р) и вернуться к шагу 84. 88.
]Удаление элемента 1, Ц Вшти ОР (РТЕ [1] ) ~ Р1 (или, что, по сути, то же самое, если ЯОЧ(ОР(РТЕ[1] ) ) > 1), установить РТЕ[1] +- ОР(РТЕ[3] ) и повторить шаг 88. В противном случае установить ОР(РТЕ[Я ) е — ОР(Р1), ХЕРТ(Р) +- ЕЕРТ(Р1), АЧА11. ~ Р1, Р1+- 1.ЕРТ(Р). Вернуться к шагу 84. 1 Читателю предлагается (в качестве очень поучительного упражнения) самостоятельно создать программу для реализации этого алгоритма (см, упр, 15). Здесь же стоит отметить„что для каждого узла ЕАЯЕЕОЧ[1] и ВАЯЕСО(.[]] достаточно только одного слова памяти, поскольку большинство их полей не будет востребовано (см. заштрихованные области на рис.
14, а также программу из раздела 2.2.5.) Боле того, в целях дополнительной экономии памяти значение -РТЕ[у] можно хранить как ЕОЧ((.ОС(ЯАЯЕСО(.[]])). Время выполнения алгоритма 8 приблизительно пропорционально количеству матричных элементов, которые вовлечены в операцию осевого преобразования. Такое представление разреженных матриц с помощью ортогональных циклических списков очень поучительно, но специалисты по численному анализу разработали несколько более совершенных методов. [См., например, работу ангес) С.
Спагагзоп, АСМ Тгапа оп Масп. Бочаге 4 (1978), 250 — 269; а также алгоритмы работь1с графами и задачами сетевого планирования в главе 7.] УПРАЖНЕНИЯ 1. [17] Предложите формулу для ьОС(1[1,К] ), если А — это матрица типа (1), а каждый ее узел состоит из двух слов, причем все узлы хранятся последовательно в лексикографическом порядке индексов. ° 2. ]81] Формула (6) выведена на основании предположения, что О < 1, < 4, для 1 < г < А Найдите общую формулу, в которой предполагается,что 1„ < 1 < и„ где А н и любые значения нижней и верхней границ данного измерения 3. [21) В этом разделе рассматривались нижние треугольные матрицы А[),к], где 0 < А < 1 < и.
Как следует видоизменить приведенные рассуждения в случае, если отсчет индексов начинается с единицы, а не с нуля и 1 < А < 1 < и? 4. [22) Покажите, что при хранении верхней треугольной матрицы А[),А], где 0 < ) < ?г < и, в лексикографическом порядке индексов распределение памяти будет удовлетворять условию (8).
Найдите в таком случае формулу для 1.ОС(А[1,К] ) . б. [20] Покажите, что значение А [1, К] можно занести в регистр А компьютера И1Х, выполнив одну команду н использовав инструменты косвенной адресации, которые описываются в упр. 2 2 2-3, даже если А является треугольной матрицей типа(9). (Предполагается, что 1 и К находятся в индексных регистрах.) 6. [М24) Рассмотрим "тетраэдрические массивы" А[(,),А], В[(,),А], где 0 < й < ? < г < и в массиве А и 0 < г < ) < А < и в массиве В, Предположим, что оба эти массива хранятся в последовательных адресах памяти в лексикографическом порядке индексов. Покажите, что ЬОС(А[11К]) = оо -~. Л (1) 4 )г(1) -Ь уз(К) для некоторых функций гм [г, ?г.
Можно лн получить аналогичное выражение для 10С(8 [1. Л,К] )? Т. [М22] Найдите общую формулу распределения памяти для А-мерного тетраэдрического массива АБюгг....,(г], где 0 < гь « . (г < м < и. 8. [22] (Задача П. Вегнера .) Предположим, что в памяти необходимо разместить шесть тетраздрических массивов АП,),К], В[1,),К], С[1,),К], ОП,Х,К], Е[1,1,К] и 2[1.),К], где 0 < К < 1 < 1 < и. Существует ли какой-нибудь эффективный способ выполнения этой задачи, аналогичный (10), но для двумерного случая? 9.
[22] Рассмотрим таблицу такого же типа, как и таблица на рис. 13, но гораздо ббльшую, в которой все связи направлены в одну сторону (а именно — выполняется условие Е1ИК(Х) < Х для всех узлов и ссылок). Придумайте алгоритм для поиска адресов всех голубоглазых блондинок в возрасте от 21 до 23 лет, основанный на обходе различных нолей связей, причем таким образом, что по завершении выполнения алгоритма для каждого из списков выполняется по крайней мере один обход каждого из списков РЕИАХЕ, А21, А22, А23, ВХОИО и В1ЛЕ.
10. [26] Можно ли придумать более совершенный способ организации таблицы с персональными данными, чтобы описанный в предыдущем примере поиск можно было выполнить более эффективным способом? (Простой ответ "Да" или "Нет" в данном случае не годится.) 11. [11) Допустим, что в каждой строке матрицы размера 200 х 200 находится по крайней мере четыре ненулевых элемента Какой объем памяти потребуется для представления ее в виде, показанном на рис. 14, если для каждого узла используется цо три слова, а для заголовков списков в по одному? ь 12.
[20] Чему равны КАь(ЦО), КА~.(РО) и ?АХ(р1) в начале шага Я?, если их выразить с помощью переменных а, Ь, с, И из (13)? ° 13. [22) Почему в матрице на рис. 14 циклические списки используются вместо линейных списков? Можно ли изменить алгоритм Я так, чтобы в нем не использовалась циклическая связь? 14. [22) Алгоритм Я позволяет сэкономить время выполнения осевого преобразования разреженной матрицы, поскольку он предоставляет возможность пропускать столбцы, в которых значение элемента из осевой строки равно нулю Покажите,что такая зкономия может быть получена в большой разреженной матрице, которая хранится в последовательном порядке, за счет применения вспомогательной таблицы ПИК [1], 1 < ) < п.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
