Прямые методы для разреженных матриц. О. Эстербю, З.Златев (984134), страница 10
Текст из файла (страница 10)
Во многих случаях это не является достаточной компенсацией, так как ВЗ часто дает приемлемую точность, а оценка ошибки может быть полу гена другими средствами (см., например, ,,113, 15, 1091, а также 5 4.8). При обработке разреженных матриц проблема приобретает новое измерение.
Для эффективности важно ограничить размер заполнения при исключении. Оказывается, что многие элементы заполнения довольно малы в сравнении с элементами исходной матрицы. Естественно отбрасывать новый элемент, меньший произведения в (машинной точности) и первоначального элемента. Так как в исключении «допускаютсяъ ошибки (матрица Е), то соблазнительно было бы отбрасывать и другие малые элементы, появляющиеся в ходе процесса 133). Более точно: введем величину Т, называемую барьером, и всякий раз, как формула (2.3.4) порождает новый элемент, меньший Т по абсолютной величине, будем заменять этот элемент нулем.
Случай Т = О соответствует обычной ситуации, Т =: ЕЬ| — зто естестВенный Выбор, а мы предлаГаем брать для Т большее значение, скажем Т = 0.01. Большие значения Т могут иметь результатом большие элементы матрицы ошибок Е из (1.2), что, вполне вероятно, ухудшит точность прямого решения (1.3) до неприемлемой степени. Необходимо восстановить утерянную точность, и для этой цели идеален процесс итерационного уточнения, Вычисления, связанные с формулами (1.4) — (1.6), обычно требуют не- мнОГО Времени ПО сряВнению с треуГольным разложением (1.2), так что легко можно провести 10 или 15 итераций. По следстВию 4.3 сходимость Гарантирована, если матрица Р не слишком велика.
Предположим, что матрица А масштабирована так, чтобы норма ее была близка к единице. Согласно (1.10), !! Р !! ~ !! 11 '1- ' !! !! Е !! = (А) !! Е !!, (2. 1) где х(А) = !!А!! !!А-'!! — число обусловленности А. Уровень элементов Е зависит от величины Т, и соотношение (2.1) указывает, что для хорошо обусловленных матриц можно брать болыпие значения Т, Однако, чтобы обеспечить сходимость для плохо обусловленных матриц, Т следует уменьшить, В примере 1.4 гл. 1 мы видели результаты использования 1К с большим барьером. Значительное уменьшение памяти сопровождается и ощутимым уменьшением времени счета.
Дело в том, что в фазе исключения нужно обрабатывать меньшее число элементов, Само итерационное уточнение занимает (в этом примере) только 10% общего времени. И ко всему этому точность 1К много выше, хотя 05 вычислялось при Т=О. Мы видели положительные эффекты использования большого барьера и в табл. 2.16 гл. 2: не только меньше значение счетчика СОПЧТ, но и при одинаковом жизненном пространстве большое Т, по-видимому, требует меньшего числа сборок МУСОРЯ. 4.3.
Сравнение требований к памяти В этом параграфе мы подробней проанализируем требования к памяти для программы, р~ссчит~нн~й ня пло~~ые матрицы (БМТ)'>, и для двух вариантов программы, испольи ВМТ вЂ” Йепее пиЫх $ес1ш1Чпе. — Прим, иерее. зующей технику разреженных матриц (ЬМТ вЂ” ВЯ, БМТ— 1К) '), В качестве типичной ВМТ-программы можно представлять себе набор ВЕСОМР/ЯО1ЧЕ из 11091, хотя между эффективными ВМТ-программами различие невелико. Наши результаты вполне типичны и для ЬМТ-программ — как и в других обсуждаемых в книге экспериментах, мы пользовались программой У12М.
Для длин массивов мы положим МЫ1 = = ХХ. Память, необходимая для ВМТ, 8МТ вЂ” 03, ЬМТ вЂ” 1К, равна соответственно 81=п +Зп~ (3*1) Б, =ЗКИ+ 13п, (3.2) ~з = 21~1~+ 31~11~1 + 1 "и. (3.3) Предположим, что Как следует из предыдущего, мы Рассчитываем, что для 8МТ вЂ” 1К значение ХХ и ~ меньше, чем для $МТ вЂ” ВЗ.
Поэтому при сравнении этих двух вариантов мы будем снабжать ХХ и м индексами. Из (3,1), (3.2) и (3.4) имеем Я, < Я, с=:- — „, ( д (~, п) = — ) 1 — — „) . (ЗЛ) При ~ .: 2 справедливо д(м, и) < д(2, и) < 11в д(2, и) = —. Из (3,6) выводим следующий критерий. Критерий 4,6. Если более чем 1~6 часть элементов матрицы А отличны от нуля, то ВМТ требует меньшей памяти, чем БМТ вЂ” В8. Трудно сформулировать обращение критерия 4.6х), а именно критерий, когда 8МТ вЂ” В8 эффективней по памяти, чем ВМТ, Причина в том, что обычно наперед не известно„сколько памяти потребует заполнение в ходе исключения. Если информация Об этом (значение СО1)) 1Т) имеется, то, вероятно, правильно будет положить ХХ = СОЬХТ+ 2п (см, табл, 2,16 из гл. 2). Функция ~(~, и) зависит и от п, но при больших значениях п, которые мы рассматриваем, эта зависимОсть слабая, Некоторые значения д(~,п) показаны в табл.
4.1, ') ЯМТ вЂ” зратзе та1пх $есйпщне. — Прим. перев. ~) В терминах заполненности исходной матрицы. — Прим. аеред. 7'аблиЧа 4.1. Функция д (м, о1 ,067 ,075 ,082 .083 50 100 1000 .О89 .100 .110 :!11 .053 .060 .066 ,067 .044 .050 .055 .056 .133 .150 .165 .167 .038 .043 ,047 .048 При сравнении ОМТ и ВМТ вЂ” 1К, пользуясь соотношениями (3,1), (3.3) и (3.4)„получаем 8,<8, м — „, (~'(~, п1 (1 — — „).
(3.7) МХ 1 14 Для функции ~1* справедливы неравенства (~ ~ 2) д'(ч, и) < д'(2, и) < Йп д'(2, и)= —, (3,8) что немедленно дает Опять-таки трудно сформулировать обращение: когда стоит использовать технику разреженных матриц. Ми можем по крайней мере привести таблицу типичных значений функции д'(~, и), которая по поведению очень схожа с Р(~, и). 50 100 1ООО ,065 091 .051 061 .070 ,071 .090 .108 .123 .125 .042 .051 .058 .059 Наконец, мы хо~ели бы сравни~~ требования и памя~и для 8МТ вЂ” ВЬ и ЗМТ вЂ” 1К. Вместо (3.4) предположим теперь ХХ, = ч,ЫЯ, ЖИ — — ~ВИЛ, (3.9) Мы рассчитываем„что ~з с. ч~, Из (3.2), (3.3) и (3.9) имеем 3, < 3,";-~2+ — „~ < 3.(м2 — чз), (3.1О) Критерий 4.7.
Если более чем 1/8 часть влементов матрицы А отличны от нуля„то ВМТ требует меньшей памяти, чем ЬМТ вЂ” 1Й. В Предположим, что Ху. ~ 4п — в атом предположении, вероятно, нет натяжки. Теперь из (3.10) вытекает Критерий 4.8. ЬМТ вЂ” 1К требует меньшей памяти, чем 5МТ вЂ” 03, при условии, что ча ~ ~2 — 1, т.
е, что для варианта 1й длина каждого из трех основных массивов на МХ меньше, чем для варианта ВЯ. Я Уместны несколько слов о предположениях (3.4) и (3.9) и об ожидаемых значениях ~2 и ~а. Никакие утверждения общего характера невозможны; однако мы собрали экспериментальные результаты для наших тестовых матриц, матриц из Харузлла 1231, нескольких практических задач химического происхождения 168, 691 и нескольких термодинамических задач 1100, 101~.
Типичные значения ~2 находятся в интервале 13, 5~, если матрица 1. сохраняется (см. $ 2,6)— если же 1. не нужна, то во многих случаях ~2е=12,3~,— но иногда значения ~ почти достигают 10 (табл. 4,3). При использовании 1К всегда предполагается большое значение барьера (Т вЂ” 0.01), и ~з, большее 3, вряд ли возможно. В табл. 4.3 мы сравниваем программу типа ЯМТ вЂ” ВЯ (РО1ВКЕ + РО4АХЕ из библиотеки ХА6) с программой И2М в режиме 1К (Т = 0.01); сравнение проводится для тестовых матриц Е(п„44), для которых характерно большое заполнение.
Для этого сорта матриц техника 8МТ вЂ” 1К особенно эффективна. Таблица 4.3. Сравнение пажити для БИТ вЂ” 08 и БИТ вЂ” 1й (Т =0.01) на матрицах класса Е (и, 44) змт — оз (РО1ВЙБ) СОБЫТИЕ со онт/нх 7697 8453 9174 9882 11643 12360 12551 14082 1" сли считать, чтО ~2 5 или Уз ~ 3 — предпОложение от" носительно ~э более реалистическое, чем для ~2, то из табл.4.1 и 4.2 можно вывести Критерий 4.9. ЯМТ требует меньшей памяти, чем ВМТ, если в матрице А отл нь от нуля менее 6% злементов. ° Замечание 4,10.
Критерий 4.9 — довольно консервативный. Во многих случаях можно допустить 10 % ненулевых элементов, и все же программы для разреженных матриц будут эффективней. В Замечание 4.11. При выводе формул «3.2) и (3.3) предполагалось, что КХ1 =ХК, Как отмечалось в 5 2.1, часто для ХК1 можно брать меньшее значение, например КХ1 ж 0.6ХМ, и это еще больше увеличивает эффективность разреженных матричных проГрамм. Если хра~~н~е цело~о Числа тр~буе~ меньшего чи~~а разрядов, чем хранение вещественного, то это также будет способствовать выгоде программ для разреженных матриц. В При сравнении времени счета для различных программ, решающих ли~ейные системы, ~ажную роль и~раю~ ~е~~~~~ко факторов, Для прОГрамм, рассчитанных на плОтные матрицы, Ситуация Вполне ясная: время счета прямо пропорциональ- но — при достаточно больших и — числу — и ар~фм~тичес~~~ 1 3 операций, где арифметическая операция определяется как одно умножение, одно сложение и три обращения к элемен- там массива.
В случае программ, предназначенных для разреженных матриц, Важны следующие факторы: размерность и матрицы; числО ХЖ ненулеВых элементоВ; характер разреженности; размер заполнения и стратегия выбора ~л~в~о~о элемента, Даже при приблизительно одинаковом заполнении время счета может быть весьма различным для разных способов Выбора ГлавноГО элемента. Поэтому мы сравним прОГраммы из библиотеки МАО (РО1ВЙЕ и Р04АХЕ) с 05- и 1К-режи- мами программы У12М.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
