Прямые методы для разреженных матриц. О. Эстербю, З.Златев (984134), страница 3
Текст из файла (страница 3)
1.3 показана матрица Е (1О,4), 4 "1 0 0 -1 0 0 0 0 0 00-10000 0 -1 4 -1 0 0 -1 0 0 0 0 0 -1 4 -1 0 0 -1 0 0 -1 0 0 -1 4 -1 0 0 -1 0 0 -1 0 0 -1 4 -1 0 0 0 0-1 0 0-1 4-1 0 0 0 0 0 0 0 0 0 0 0 Рис 1 3 Ма1'Рнца Е110 4) Тестовые митриЦы клйссй Г2(1п, и, с, Г, Я) — это п1 Х п ма~рицы, которые могут рассматриваться как обобщения матриц класса 0 с добавлением в нижнем левом углу треугольника элементов с катетами 10Х 10.
Ширина ленты, расположенной на расстоянии с от главной диагонали и циклически продолжаемой ПОД ней, раВна à — 1. Элементы Выра жаются формулами а,, „=1, 1=1(1)Гп; а,, „,,=( — 1)' з 1, э=1(1)à — 1, 1=1(1)Гп", здесь ц = О, 1, ..., 1ГП/п~ выбирается так, чтобы 1 ~ 1— — Цп ~~ п, соответственно 1 ~! — Цп+ с+ Б "=- и. СимВОл 1п1, п~ Об~зна~~е~ наименьщее ~~~ура~~ное число, не превосходящее п1/п: а,. „и,,— — 1 ° а, 1=1(1)11 — 1, 1=1(1)10; Я„П+,+А, — — 1/а, 1 = 1(1) 11 — 1, 1= 1(1) 10.
Предполагается, что Гп Э» п: 22, 11 ~ с ' и — 11, 2 ~ Г ~ = пи'п(с — 9, п — 20) и а . 1, Таким образом, наименыцими матрицами этого класса будут Р2 (22, 22, 11, 2, а). На рис. 1.4, 1.5 изображены матрицы 1..2 (26, 26, 12, З„сс) и Г2 (80, ЗО, 12, 4, а). Подчеркнем, что, Варьируя параметры тестовых матриц класса Г2, мы мОжем изменять размер и, Отношение Гп/п, плотность ХУ/п~, структуру разреженности, устойчивость по отношению к процессу исключения.
Тем самым можно провести вполне систематическое исследование зависимости характеристик разреженной матричной программы От этих Величин. В табл. 1.6 для каждого вида тестовых матриц указаны размернОсть, число элементов, наименьщий и наиболь- 111ИЙ ЭЛЕМЕНТЫ. о о о о о о о о о о о х х о о х х х х х х х х х х охообооооооооххооххххххххх О О Х О О О О О О О О О О О Х Х О О Х Х Х Х Х Х Х ОООХО ООООООООООХХООХХ ХХХХХ О О О О Х О О О О О О О О О О О Х Х О О Х Х Х Х Х Х о о о О О Х О О О О О О О О О О О Х Х о О Х х х х Х ООООООХООООО ОООО О ОХХО ОХХХХ ОООО ОООХ ОООО ОООООООХХООХХХ ООООООООХОООООООООООХХООХХ о О О О О О О О О Х О О О О О О О О О О О Х Х О О Х О О О О О О О О О О Х О О О О О О О О О О О Х Х О О О О О О О О О О О О О Х О О О О О О О О О О О Х Х О О О О б б О О О О О О О Х О О О О О О О О О О О Х Х 3С б б б б б б О О О О О О Х О О О О О О О О О О О Х и Х О О О О О О О О О О О О Х О О О О О О О О О О О О Х и а О О О О О О О О О О О Х О О О О О О О О О О Х О Х Х О О О О О О О О О О О О Х О О О О О О О О О Х Х О Х Х О О О О О О О О О О О О Х О О О О О О О О Х Х Х О Х Х О О О О О О О О О О О О Х О О О О О О О Х Х Х Х О Х Х О О О О О О О О О О О О Х О О О О О О Х Х Х Х Х О Х Х О О О О О О О О О О О О Х О О О О О Х Х Х Х Х Х О Х Х О О О О О О О О О О О О Х О О О О Х Х Х Х Х Х Х О Х Х О О О О О О О О О О О О Х О О О Х Х Х Х Х Х Х Х О Х Х О О О О О О О О О О О О Х О О Х Х Х Х Х Х Х Х Х О Х Х О О О О О О О О О О О О Х О Х Х Х Х Х Х Х Х Х Х О Х Х О О О О О О О О О О О О Х Рис.
1.4, Портрет матриц Р2(26,26,12,3,и). Таблица 1,6. Различные характеристики тестоаых матриц Р~~- мер- ХХ пип ~ ап ~ пах (1ООО, и+ 1) 4 пах (сп — и, 1Оа) Матрицы классов В(п, с) и Е(п„с) использовались в работах 186, 9Щ, а матрицы класса Р2 1'гп, и, с, г, сх) — в 189, 1ОЩ. Некоторые сведении о подпрограммах, генерирующих матрицы Этих трех классов, мо)кно иайти в ~98~. "Хх ХХ Х "ХХМ ХХ 'Ям 34ХМ Х "Хэ~: "МХМ ХХХ Х Х Э4 Ж 3ФХХ Рис, 1.5. Портрет матриц. Г213О,ЗО,12,4,к). Кроме матриц назВанных классов, мы пользовались В своих численных экснериментах некоторыми тестОВыми матрицами харузллскОЙ'> коллекции 123~, а также матрицами, возникавшими при дискретизации некоторых химических задач.
~) ХаруЗлл — Центр ядерных исследОВаний ВеликООритании, Где РабОтает труппа изВеетных епщиалистОВ пО 1~аарикенным матдицам (Дафф, РИД И ДР.), — ПАРИМ„, ПЕ1МВ~ 1„4. Пример Чтобы подкрепить утверждения, высказанные в конце ~ 1 2„мы решили линейную систему, матрицей коэффициентов которой служит Е(1000,44) (см, ~ 1.3). Для 1ЭЗ использовались подпрограммы РО1ВКЕ и Р04Ал.Е 1611, а для 1К вЂ” пакет У12М 197, 102~. Для нашей матрицы и = 1000, п2 = 10', ХУ, = 4910. Подробности Вычислений содержатся в табл, 1.7. В этом примере, как и в последующих, мы выбирали правую часть таким образом, чтобы решением х был вектор, состоящий из единиц.
Таблица 1.7. Память, времи и точность при решении лииеииои системы с матрицей ковффициеитов Е 11000,44). Для 1К задано 1=0.01 (см. конец $1.4), и потребовалось 16 итераций С)тметим, что эта задача — Очень большая, если ее нужно решать обычными методами для плотных матриц, и даже если используется наличие ленточной структуры, процесс решения все же требует около 88000 ячеек памяти. Методы для разреженных матриц, ~отор~~ буду~ обсу~дат~ся в гл.
2 и 3, позволяют вдвое сократить запросы к памяти (той же экономии мОжнО дОстигнуть, используя симметрию); Однако ПО-настоя1цему ощутимый выигрыш получается благодари методам гл. 4: итерационное уточнение+ большой барьер. Когда В процессе исключения Возникают нОВые элементы (заполнение), они сравниваются по абсолютной Величине с барьером Т и, оказавшись меньше Т, попросту игнорируются, Этим способОм мы экономим память и время счета, нО заодно Вводим и большие Ошибки. Чтобы Восстановить Утерянную точность, мы проводим итерационное уточнение и, как показь1взет табл.
1.7, действительно получаем лучшее решение, чем ВЯ. Х.Б. Содержание глав 2 — $ В гл. 2 мы Опишем метод хранения, Основанный на ис- пользовании упорядоченных списков и следующий идеям работ ~48, 49~. Мы сравним его с другим методом, исполь. зующим связные списки. Глава 3 посвящена стратегиям выбора главного элемента, В центре внимания здесь хорошо известная стратегия Мар. ковица ~541 и некоторые ее обобщения ~861. В гл.
4 обсуждаются техника отсечения и итерационное уточнение. Мы показываем, как объединить то и другое в алгоритм, который может значительно превосходить 08 по эффективности. Методы, описанные в гл. 2 — 4, можно использовать в более общей ситуации, когда матрица А прямоугольная, а также для других численных методов, В гл. 5 мы определяем общую вычислительную схему, включающую как частные случаи многие хорошо известные и часто применяемые методы. Затем мы кратко рассматриваем приложения к этой общей схеме методов для разреженных матриц, стратегиЙ выбора, барьерной ~е~ни~~ и и~ерац~онного уточнения. Следует упомяну~~, что в основе м~~ер~ала последующих глав — результаты, полученные в ~86, 87, 89, 9О, 971. МЕТОДЫ ХРАНЕНИЯ Я ~ ~РЕ5ОдаиЦВ К ВХОдНОЙ ййфОРМЙЯМИ цредположим, что матрица А — большая и разреженная. Яы не будем делать каких-либо предположении О структуре элементоВ А.
Если имеется дополнительная информация ~например, А положительно определена или имеет ленточную структуру), то этим можно воспользоваться для построения более эффективной вычислительной схемы. Однако мы сосреДОтОчим Внимание на метоДах Общего назначения. Если структура матрицы позволяет применение какого- нибудь итерационного метода, то могут пригодиться подпрограммы пакета Щ. Если элементы матрицы Образук»т узкую ленту ОкОлб главной диагонали, следует Обратиться к какой- либо программе, специализированной для ленточных матриц.
Такие программы есть, например, в библиотеке ХАЯ '» 1611 или в пакете 11гчРАСК'» 1151. Нужно отметить, что подпрограммы 1.1гчРАСК'а позволяют по желанию пользователя вычислять оценку числа обусловленности (при этом используется алгоритм, описанный в 1131„см. также 11О9, 57, 121). Оценка числа обусловленности ленточных матриц обсуждается в 147~.
Симметрия матрицы используется программами двух широко известных пакетов: 8РАЮРАК'а 11О5, 411 и Йельского пакета 127 — ЗО~, В то же время в Йельском пакете есть и программы для матриц общего вида [28~. В ~25) описано применение многофронтальных методов к разреженным симметричным матрицам. Обзор других методов, используемых для разреженных матриц специальной структуры, дан, например, в 119~. ; Когда специальной структуры не имеется, каждый элемент матрицы должен сопровождаться информацией о его местоположении.
Это значит, что кроме числового значения а»» мы Должны знать номер строки 1 и номер столбца 1. Зту информацию мОжно разместить в трех Одномерных массиВах А, С!тат гсгт!гс соответственно ллн аиачений ац, 1, !. (Если на '! р!ао — р!витав!си! А!асс!гата огсир — вввастнав британская груипа РааРаботчикоа прикладного математического обеспечения. — Прим, перед, ') Описание пакета 1.ИРАСК можно найти а книге Дж, Райс, МатРичиме аычисления и математическое обеспечение, — М.: Мир, 1984.— П гг»аИ. ртаврЕвг нашей машине преДстзвление целого числа требует столько же битОВ, скОлькО представление Веществ~ннОгО, тО, чтобы получить экономию памяти' ), необходимо уже здесь потребовать выполнения неравенства ХХ ~ П2/3; позднее мы увидим что нз ХЛ следует наложить еще более жесткие ограничения*) В общем случае мы не можем рассчитывать на то, что порядок, В каком пользователь пожелает задавать элементы матрицы, можно эффективно использовать в дальнейших Вычислениях.
Однако для удобства пользователя мы не накладываем никаких ограничений на этот порядок. Допускается любой, и мы позаботимся о надлежащем переупорядочении элементов (см. Следующий параграф). Пример 2.1 Рассмотрим следующую матрицу (и = 5„ХУ, = 12): На рис. 2.1 иллюстрируется использование массивов А, СХК и КХК. Заметим, что длина ХХ1 массива КХК меньше длины ЬЩебй5ФНЙЫч ИМ00$ А Целый моссоФ СМЯ, Цеай массце Ищ Рис, 2,1. СодеРжимое массивов А, СХК и КК~, отвечаю1цее матрице Л ЫХ массивов А и СХК. Мы увидим в следующем параграфе, почему это происходит. Матрица А мала и не является разреженной в смысле нашего «определенияз, но она исполь.
зуется здесь только как иллюстрация. 2.2, ПВРВцйорядочекие стрцктцры Теперь мы переупорядочим элементы А, чтобы получитЬ структуру, удобную для реализации гауссОВз исключения, Этз. ') По сравнению с хранением плотных матриц, — Прим, верее. структура предполагает упорядочение А по строкам, и мы опиш~~ два способа так~го переупорядочения.
Нам потребуются четыре одномерных массива указателей, каждыЙ длиноЙ и. По практическим соображениям они рассматриваются как столбцы двумерного массива НА. Так как в дальнейшем нам будут нужны еще семь столбцов, то НЛ описывается как массив с размер~ми и,'~( 11, Используются такие указатели: НА(1, 1); число элементов, строчный индекс которых МЕНЬШЕ 1. НА(1, 3): число элементов 1-Й строки (1-й этап); указатель следующего элемента 1-й строки (2-й этап). НА(1, 4): число элементов, столбцовый индекс которых меньше НА(1,6): число элементов 1'-го столбца (1-й этап); указатель следующего элемента 1-го столбца (3-й этап).
К использованию этих указателей " мы вернемся в параграфе 2.3. Первый процесс переупорядочения состоит из трех этапов, Зтаи 1. Записать в позиции массивов А и СКК с номерами от ХУ. +1 до ХЕ+ ИЕ копии элементов тех же массивов с номерами от 1 до ХЕ. (Таким образом, в этом процессе должно выполняться условие ХХ.= 2ИУ.) Подсчитать число элементов каждой строки и записать это число в НА(*,3); подсчита~ь число элем~и~о~ каждого с~олбц~ и записать это число в НА(,6). Подсчитать общее число элементов, строчный индекс которых меньше 1, и записать это число в НА(1, 1) и НА(1,3).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
