Прямые методы для разреженных матриц. О. Эстербю, З.Златев (984134), страница 6
Текст из файла (страница 6)
Фрагмент фортраииой подпрограммм, имполнянзшей сборку му сора о строчно-упорядоченном списке. указыва(ощу)о его номер. Это делается так: проходим по позициям НАО 4) 1 = к(1)п за~~сы~~~ в 1-(о ст1зочный индекс первого элемента )-го столбца, а в соответству(ощее место КХК вЂ” число — ) (см.
рис. 2,11, отвечающий примеру 2.7, но с ХК1 = 16, что делает необходимой сборку му сора). Теперь мы просматриваем позиции КХй(1),1 1(1)Х1ЕХВ (обозначение последней используемой позиции). Если КХК(1) = О, то место вакантно, и мы идем дальше. Если КХК(1) ~ О (скажем, равно — 1), то мы находимся в начале 1-го столбца. Изменяем указа гели НА(1, 1~), Е = 4, 5, 6. Далее, если КХК(1) Ф О, то элемент в позиции ~ должен быть переписан в первую свободную позицию нового„составляемого сейчас списка.
На рис, 2.12 приведен фортранный текст этого сжимающего алгоритма, а на рис. 2.13 — (аналогичный) текст для сжатия в строчно-упорядоченном списке. Разумеется, выполнять сборку мусора слишком часто было бы накладно. Один из способов избежать этого состоит в том, чтобы работать с большими массивами, т, е. Задавать большие значения для ХХ и ХК1. Однако приходится поддержиВать некоторый баланс ~~~ду ра~~ером памяти и Временем счета, так что результатом будет компромисс, и какое-то число сборок мусора неизбежно, Кроме того, заранее не известен размер заполнения, исключая весьма специальные ситуации. Поэтому значения для КК и ХЫ1 выбирают, опираЯсь главным образом на интуицию или предыдущую практику. В этой связи следует отметить, что программа должна проверять, создалось ли в результате сборки мусора свободное пространство, достаточное для продолжения процесса. Если нет, то пользователю должны быть переданы соответствующее сообщение и 'запрос о большей памяти.
Тексты на рис. 2.12 и 2.13 используют идеи, реализованные в пакете МА28 1171. При решении линейноЙ системы с плотнОЙ матрицей коэффициентов не возникает проблем с хранением элементов матрицы 1., поскольку имеется свободное пространство в нижней треугольиОЙ части А. Если нужно решить несколько систем уравнений с одной матрицей коэффициентов, возможно, в последовательном режиме, то, используя 1Л3 разложение, можно сОкратить Время счета; при этом хранение 1. не потребует ни дополнительной памяти, ни добавочного времени, С разреженными матрицами ситуация иная.
Зачастую матрицы очень велики, а мы Резервируем для них так мало памяти„что ПРИХОДИТСЯ в ПроцЕССЕ Ш разложЕниЯ ВЫПОЛ- нять сборки мусор . В этом случае, Отказываясь От хранения 1„, мы можем сэкОпомить памЯть, т. е. Резервировать меньшее пространство„или сэкономить время на сборках мусора. Всякий раз„как ~сключается поддиагональный элемент, освобождается занимаемое им место; оно может быть использовано, например, для хранения заполнения. Если все же требуется Сделать копию СтрОки, мы КОпируем лишь наддиагональные элементы; при сборке мусора структуру хранения ~ожно сжать Сильнее, чем раньше, ~ос~~льку в учет принимаются Опять же тОлькО наддиагональньге элементы. Время счета тоже (нескОлько) сокращается, так как нужно обрабатывать меньшее число элементов.
С другой стороны, если нужно решать, быть может, в последовательном режиме, несколько систем 'ь сохранять 1., если это в принпипе возможно, Затраты памяти при этом компенсируются ощутимым сокращением времени счета. Мы вернемся к этому вопросу в следующем параграфе ивгл,4, Табл.
2.14 демонстрирует сокращение памяти, измеряемое значением счетчика СО13КТ (см. 5 1.2), для некоторых матриц классов 0(п, с) и Е(п, с) при и = 1ООО. Видно, что отказ от хранения 1. дает для этих тестовых матриц экономию памяти от 25 до 40 %. Таблица 2.14. Сравнение памяти, необходимой в процессе исклвченин для тестовых матриц, соответственно при хранении Е и при отказе от ее хранении Матрицы класса Б 1и, с) Матрицы класса О ~и, с) Бса Ь с ь 2.7. Кяйсемфмкйция айдйч П С одной и той ке матрицей коэффициентов, . Прим, перга.
Задача, требуюшая решения одной или нескольких систем линейных алгебраических уравнений, обязательно принадлежит к одной из следующих пяти категорий; (1) Ах=Ь Нужно решить одну систему. (2) Ах,=Ь, Нужно Решить несколько систем с одной и той же ма'*Рицей коэффиц~е~~о~. (3) А,х,=Ь, Нужно решить несколько систем одинако.- вой структуры (см. определение 2.8 ниже). (4) А,х„,=Ь„ А,х„= Ь,2 (5) Ах=Ь Ву=с Нужно решить большое число систем одинаковой структуры. Кроме ТОГО> Одна и та же матрица коэффициентов повторяется несколькО раз.
Нужно решить несколько систем с различными матрицами коэффициентов различной структуры. Определение 2.8. Говорят, что матрицы А1 и А2 имеют одинаковую структуру, если их элементы занимают одинаковые позиц и, -' ат--0 а(2,'Фо И Замечание 2.9. Мы будем говорить, что матрицы Аь А2,... ..., А„... имеют одинаковую структуру, и в том случае, если для некоторых значений г какие-то из элементов '~ становятся НУЛЯМИ.
Вопрос о том„какие из методов для разреженных матриц наиболее эффективны„в большой мере зависит, как мы сейчас увидим, от категории задачи. Категории (1) и (5): нет необходимости хранить нижнюю треугольную матрицу 1., и можно сэкономить память, умен~шая размерность в Описании массив~в А и СИР. Другой вариант — сохранить прежнюю длину этих массивов в расчете на то, что сборки мусора не потребуют много времени. Категория (2); при решении первой системы нижняя треугольная матрица 1. вычисляется и записывается в память; все последующие системы решаются подстановками с использованием найденного 1Л3-разложения.
Очень часто время вычисления вектора х| — — 913-"1.-'РЬ составляет лишь малый процент времени факторизации (точно так же, как в случае плотных матриц), и мы можем получить значительный выигрыш благодаря хранению 1.. Категория (3): 1. хранить не нужно, однако некоторая информация, полученная в ходе первого разложения, может пригодиться. Именно, в последующих исключениях можно А. избежать выбора главных элементов (см, гл, 3).
Б. уменьшить число сборок мусора. В. сократить число копий строк/столбцов, Категория (4): то же, что и для категории (3), с тем отличием, что ~. следует сохранять, как и в случае категории (2). Читатель увидит, что категории (2) и (4) являются, с нашей точки зрения, наиболее важными. и Общего портрета этих матиц.
— Прим. перев. 2.8, СРЙВИГЙИВ ДШРЯдОЧГИИЫХ И СВЯЗИЯХ СПИСКОВ ДО сих пор Обсуждался метОд хранения, испОльзующий упорядоченньге списки, Другой метод, Очень популярный в шестидесятые годы„— это так называемые связные списки. Мы проиллюстрируем Основные идеи этой техники -на матрице примера 2.1. Снова необходимы три больших массива (вещественный и два целых; сохраним за ними наименования А, СХЙ и КХК); правда, нет оснований сообщать им разные длины (т.
е. теперь ХК = КХ1). Понадобятся два дополнительных целых массива длины и, указывающие первьге элементы каждой строки и столбца (мы используем НА(, 1) и НА(, 4) ). Как видно из рис. 2.15, компоненты массива КХК указывают расположение следующего элемента той же строки. Чтобы отметить последний элемент строки, в КХК помещают число, большее КК; обычно берут сумму ХХ+ номер строки.
Для определения строчного индекса какого-либо элемента массива (если он не известен заранее) мы должны просматривать список, пока не дойдем да последнего элемента строки; после этого из содержимого" КХЙ вычитается КХ. Ясно, что это не слишком быстрый способ, разве что матрица очень разрежена и остается таковой на протяжении всего процесса.
Массив СКК используется (по отношению к столбцам) точно таким же образом; подробности см. на рис. 2,15. Замечание 2.11. Хотя мы и пользовались терминами апервыйэ, ~следующийъ и «последнийэ, мы не предполагаем эле- менты или связки упорядоченными внутри строк/столбцов. «Первый» элемент строки — это простО элемент, которыи Оказался первым В няшем СВязном списке. и На изложенных идеях основана программа МА18 1141, Сейчас мы опишем обобщение этой техники, полезное, если мы не сохраняем матрицу 1., или вводим большой барьер, или храним диагональные элементы где-то В другом месте (В мас' сиве Р1Ъ'ОТ), В этих случаях в массивах А, СХК и КХЦ Образуются свободные места, и их можно было бы использовать, Свяжем друг с другом Все вакантные позиции в А, СКК и ЙХК; в результате получится так называемый <свободный список», куда можно записывать элементы заполнения. Если в процессе исключения освобождаются какие-то места, их можно добавить к свободному списку.
Единственное, что требуется дополнительно, — это указатель начала свободного списка (на рис. 2.15 свободный список начинается с тринадцатой позиции), А теперь сравним Оба метода хранения. А. Переупорядочение структур~. Это легче делать со связными списками, так как нет необходимости переупорядочивать элементы в А. По сравнению с упорядОченными списками время сОкращается бОлее чем вдвое; однако эта часть программы во всех случаях отнимает очень малую долю общего времени.
Б. Арифметические операции и поиск главного элемента. Многие операции требуют определения столбцового (строчного) индекса элемента данной строки (столбца). Как уже отмечалось, это весьма неудобный процесс в связных списках, разве что в матрице на всех этапах исключения очень мало ненулевых элементов. Это главный недостаток связных Сп~~~о~ и, ~О~~О~ИО, еди~с~~енный, но зато ~ер~езный. В. Хранение заполнения.
Это легко делать в связных списках. Добавление нового элемента в строку 1 и столбец 1 сводится к выборке первого элемента свободного списка и установлению соответствующих связок. Никаких копий и сборок мусора не требуется. Г. Объем памяти. При рабо~е со Связными списками нет необходимости запасать в массивах больше места, чем требует собственно процесс исключения. В этом отношении ситуация сходна с описанной в последнем разделе 5 2.7 ситуацией для задач категорий (3) и (4). Упорядоченные же списки в общем случае предполагают некоторое дополнительное ~жизненное пространство» для записи копий, чтобы мы не тратили все свое время на сборку мусор~.
При~ер, показывающий зав~симост~ числа сборок мусора и общего времени счета от свободного пространства, приведен в табл. 2.16. Нужно отметить, однако, что при испОльзовании связных спискОВ массив ЙХЙ должен иметь длину ХК, а для упорядоченных списков он может быть значительнО короче. 3тО Отчасти уменьшает преимущество первых перед вторыми. Нужно еще упомянуть, что обычно заранее не известно, сколько потребуется памяти, и потому трудно извлечь полную выгоду из хороших свойств СВЯЗНЫХ СПИСКОВ. Т ° 0.0, СОПЯТ 3474 Т ° 0.1„СОПИТ 1904 Число сборок мусоре Процент 100 122 119 127 129 1З6 158 0 11 12 16 19 25 43 0 3 5 7 9 16 29 В настоящее время считается, что недостаток Б перевешивает преимущества А, Б и à — мнение, которое подтверждается практикой последних лет. Но ничто не бывает абсолютно черным или белым, и выбор между двумя методами хранения зависит От языка программирования, компилятора и конкретной задачи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
