Прямые методы для разреженных матриц. О. Эстербю, З.Златев

Эстербв О., Златев 3. 387 Прямые методы для Р33реженных матриц". Пер. с англ.— М,: Мир, 1987.— 120 с. Небольшая книга датских специалистов, отражающая опыт разработки программ,для уазреженных несимметричных систем, Авторы сосредоточили внимание на ~скайдййавском~ варианте""решенйя" 'затдачн„подробно обсуждагот Возможности его применения. Много внимания уделено деталям разр6- женной технологии — динамическим структурам хранения, организации выбора главного элемента. Для математиков-прикладников, для разработчиков программ, для сту-. дентов и аспирантов университетов. 1702070000 — 054 041(01) — 87 © 1983 Ьу 8рг1паег-ЧСТ1аа Ыетч Уог1г, 1пс, А11 К1дЬ1з йезег~гед.

Аа1Ьог1хед 1гапа!а1юп 1гопт Епд11зЬ 1апапаае ей11оп риЬ11зЬег1 Ьу 5рг1п8ег-Ъег1ад Вег11п — НеЫе1Ьега — Меж Уог1с — То1суо © перевод иа русский язык, 6Миръ, 1987 Небольшая книга датских математиков О, Эстербю и 3. 3латева излагает современный подход к программной реализации метода Гаусса для разреженных несимметричных линейных систем. Она не пересекается с другими известными советскому читателю книгами той же тематики: ни с книгой: Р. Тьюарсон. Разреженные матрицы (М,: Мир, 1977), где описана технология, популярная в 60-е годы; ни с недавней книгой: Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений (М.: Мир, 1984), целиком сосредоточенной на симметричном положительно определен- нОМ случае.

Есть по меньшей мере два принципиальных момента, которые усложняют программироВание метода Гаусса для нОсим. метричных систем по сравнению с системами симметричными и знакоопределенными — различие схем хранения и проблема РОСТа ЭЛЕМЕНТОВ. Для ЗнакоонредЕленныХ СИСТЕМ разумНую— В смысле сохранения разреженности — последоВательность исключения можно определить„не зная числовых значений элементов матрицы и оперируя только с ее графом.

Найдя эту последовательность, выяснив, где появятся новые ненулевые Элементы — так называемое заполнение, — и зарезервирован для них место, реальное исключение можно проводить-при статичной схеме хранения, В несимметричном случае для достижения численной устойчивости приходится накладывать ограничения на относительную величину главных элементов, В результате априорный выбор порядка. исключения становится невозможным, что заставляет обращаться к динамическим структурам. Качество вычисляемого решения может пострадать, если в процессе исключения некоторые элементы матрицы сильно 'возрастают пО сраВнению с уровнем элементов исхОднОЙ системы.

Для положительно определенной матрицы роста элементов не происходит, какова бы ни была последовательность исключения; в несимметричном же случае (и в особенности для разреженных матриц, где требования к величине главного злемента не так строги) контроль роста необходим. Сказанное, вероятно, объясняет„почему сложно создавать программы метода Гаусса для разреженных несимметричных систем. Отметим, например, что описание одной из наиболее авторитетных современных программ для этого класса систем, а именно программы МА28 английской школы, вылилось в пухлую брошюру объемом в 150 страниц (содержащую, правда, и текст программы).

Описание (уже без текста)' другой известной программы У12М (одним из разработчиков является 3. Златев) составило том 121 шпрингеровской серии ~1.ес1пге ХО1ез 1п Согпра1ег БС1епсе~, где опубликована в оригинале и данная книга. Авторы представляют весьма активную датскую школу программирования разреженных систем, для подхода которой характерна большая роль, отводи~ая ~~ерац~онно~у уточнению. То, что этот процесс позволяет — даже для не слишком хорошо обусловленных систем — получать решения практически с полной машинной точностью, давно известно из практики случая плотных систем, Его минусы — увеличение требований к памяти (нужно хранить коэффициенты исходной системы) и некоторое (не очень, впрочем, значительное) увеличение времени счета.

Неожиданно оказывается, что для многих разреженных систем применению итерационного уточнения сопутствуют как повышение точности, так и сокращение памяти и вычислительной работы. Почему это так, читатель узнает из книГи; здесь мы не будем раскрывать ее секрета. В книге суммирован мноГолетний Опыт датских специали стон, накопленный в процессе создания ряда программ для разреженных систем. Составлена она таким образом, что первые четыре ее главы можно рассматривать как пособие для начинающих разработчиков программ для разреженных систем. Особняком стоит пятая глава.

Здесь авторы задались целью показать„что техника, использованная ими при реализации метода Гаусса, имеет более широкую область приложений," например, аналоГичным Образом можно рюализовать ряд известных прямых алгоритмов для линейных задач метода наименьших квадратов, На мой взгляд, принятая в этой главе форма изложения затрудняет понимание самого по себе довольно очевидного тезиса. К тому же предполагается, что читатель знаком с упомянутыми алгоритмами, Лицам, заинтересованным в содержании гл. 5, можно рекомендовать в качестве предварительного чтения мой обзор ~Разреженные линейные задачи метода наименьших квадратов» (аИтоги науки и техникиэ, серия ~Математический анализэ, т. 23), ПРБДИСЛОВИЕ Математические модели многих практических задач приводят к системам линейных алгебраических уравнений с большими и разреженными матрицами коэффициентов, Типичный пример — решение уравнений с частными производными методами конечных разностей или конечных элементов; однако МОЖНО уПОМЯНуТЬ И МНОГО ДруГИХ ПРИЛОЖЕНИЙ, Когда большая доля коэффициентов матрицы состоит из нулей, вполне очевидно, что нам не хотелось бы хранить в памяти вычислительной машины все эти нули; но, может быть, не так очевидно, как обойтись без этого.

Мы опишем вначале способы хранения, удобные для прямых методов, а затем покажем, что очень эффективная вычислительная схема может быть пОстрОена на Основе Гзуссова исключениЯ и итерационного уточнения. Серьезную проблему при хранении и обработке разреженных матриц представляет заполнение, т. е, возникновение новых ~лем~н~о~ В процессе получ~~ия нулей под Г~ЗВНОЙ диа~ональю. Многие из этих новых элементов оказываются меньше элементов исходной матрицы, и если они меньше некоторой величины, которую будем называть барьером (Йгор 1о1егапсе), то мы просто игнорируем их.

Этим путем мы можем в значительной мере сохранить разреженность; в то же время вполне вероятно, что в 1Л5-разложение будут внесены настолько большие ошибки, что вычисленное решение станет неприемлемым, Для восстановления утерянной точности мы применяем итерационное уточнение; теоретически и с помощью практических экспериментов мы показываем, что оно идеальнО для этОЙ цели. В целом комбинация гауссова исключения, большого барьера и итерациОнноГО уточнениЯ Дает Очень эффектиВную и кОнкурентоспособную Вычислительную схему длЯ разрежен" ных задач, В случае плотных матриц итерационное уточнение ВсеГда увеличивает запрОсы к памяти и время счета; пО" вышение точности, которое оно обеспечивает, может быть недостаточной компенсацией за эти издержки.

Однако для разреженных задач итерационное уточнение в сочетании с большим барьером в большинстве случаев дает очень точные результаты и достоверные оценки ошибок при меньших памяти и времени счета. Краткое описание гауссова исключения дано в гл. 1. Различные методы хранения разреженных матриц общего вида обсуждаются в гл.

2. Глава 3 посвящена использованию стратегий выбора главного элемента как средства поддержания баланса между разреженностью и точностью. ВОзмОжнОсть применения итерационного уточнения в соединении с гауссавым исключением — предмет гл. 4. В гл. 5 мы вводим общую вычислительную схему, включающую как частные случаи многие хорошо известные прямые методы для линейных уравнений и переопределенных линейных систем. Мы демонстрируем также, как можно обобщить изложенные ранее методы на случай линейных задач, решаемых В смысле наименьших кВадратов.

Таким образом, мы показали, что теорию большинства прямых методов можно изучать с единой точки зрения и что алгоритмы, описанные в предыдущих главах, применимы не только в связи с гауссовым исключением„но и для многих других методов. Как иллюстрация этих т~з~соВ, Во ~тор~й час~~ гл. 5 пО- дробно обсуждается конкретный алгоритм — ортогонализация Джентльмена — Гивенса. Алгоритмы, описанные В гл. 2 — 4, были реализаВаны В пакете программ для решения больших и разреженных систем линейных алгебраических уравнений, Этот пакет У12М включен в стандартную библиотеку ЙЕСКБ (библиотеку Вычислительного центра при Университете Копенгагена), В настоящее время подпрограммы пакета доступны с полной документацией и многими тестовыми программами (3.

1Чазп1ежзЫ, КЕСКБ, Чегпшпдздаде 5, ОК вЂ” 2100 СорепЬадеп). Нужно отметить, что подпрограммы написаны на Фортране. Имеются версии с обычной и двойной точностью, Машинно-зависимые константы не использовались, как и специальные возможности машины, находящейся в распоряжении КЕСК13, а именно БХ1ЧАС 1100/82. Таким образом, пакет переносим и без каких-либо изменений будет работать на многих больших машинах. Это было проверено пропуском подпрограмм пакета в трех различных системах: 1ЛМ1ЧЛС 1100/82, ЙЕСКЯ; 1ВМ 3033, Вычислительный центр Северо-Европейского университета; СВС СуЬег 173, Вычислительный центр при Университете Орхуса. Пакет У12М содержит также подпрограммы оценки числа обусловленности разреженной матрицы.

К подпрограммам можно обратитьс~, если вычисляется Ш-разложение; они дают сравнительно недорогой и тем не менее заслуживающий доверия способ определения чувствительности результатов к ошибкам округлений. Полная документация подпрограмм пакета 712М с крат- ким Описанием Оснаиных идеи, ВОПЛОН1енных В нем, содержится в одном из более Ранних томов шпрингеровской серии (см, Х. Е!а1еч, 3. Вазп1ежзЫ„К. ЯСЬангпЬнгд, ~712М вЂ” ЯО1цМоп о1 1.агре апг1 Ярагзе Буз1егпз о1 1.1пеаг А1~еЬга1С Бгша6опзэ, 1.ес1иге ХО1ез 1п Согпрц1ег ЯС1епсе, ЧО1, 121, Зрг1паег, Вег11п — НеЫе1Ьегд — Хе~ч Уог1, 1981) . Главы и параграфы нумеруются арабскими цифрами, Так, ф 3 гл.