Дж. Деммель - Вычислительная линейная алгебра, страница 23

Результаты, полученные посредством этой схемы, показаны на нижней паре картинок рис. 2.11; заполнение в Ь снижено еще на 7% (с 9073 элементов до 8440), однако число флопов увеличилось на 9% (с 181525 до 198236). О В системе Ма$1аЬ имеется ряд процедур для обработки разреженных матриц (их список можно получить в Ма11аЪ'е с помощью команды «Ье1р грагбзп») и ряд примеров конкретных разреженных матриц в виде встроенных демосов. Вызвать такой пример на экран можно, вводя команду дешо, затем щелкая мышью на пункте «соп1шпе», потом на «Маг1аЬ/ч'1г11» и, наконец, на «Ма1г1сеэ/Яе1есг а дешо/Ярагэе» либо «Ма1г1сег/Яе1есс а дешо/Сто !ше депюгк Так, на рис.

2.12 воспроизведен пример из Мас1аЬ'а — сетка возле крыла. Задача состоит в том, чтобы рассчитать в узлах сетки поток воздуха возле крыла. Дифференциальные уравнения с частными производными, описывающие поток, приводят (при дискретизации) к несимметричной системе линейных уравнений, структура которой также показана на рис. 2.12. Программное обеспечение для разреженных матриц Помимо Ма11аЬ'а имеется большое количество распространяемых бесплатно либо коммерческих программ для разреженных матриц, написанных на фортране или С. В этой области все еще ведется активная исследовательская работа (особенно в том, что касается высокопроизводительных машин), поэтому невозможно рекомендовать какой-либо алгоритм как наилучший.

Таблица 2.2 [177] дает список имеющихся программ, систематизированный в нескольких отношениях. Мы ограничиваемся программами (общедоступными или коммерческими), пользующимися поддержкой, либо экспериментальными программами в тех случаях, когда никаких других для данного типа задач или компьютеров не существует. Более полные списки и объяснения алгоритмов, упоминаемых ниже, можно найти в [177, 94]. Таблица 2.2 устроена следующим образом.

Верхняя группа программ, называемая «последовательные алгоритмы», предназначена для однопроцессорных рабочих станций и персональных компьютеров. «Алгоритмы с разделяемой памятью» разработаны для таких симметричных мультипроцессорных машин, как Япп ЯРАБСсеп1ег 2000 [238], 801 Роч«ег СЬа!1епйе [223], ПЕС А1рЬа8егчег 8400 [103] и Сгау С90/Л90 [253, 254].

«Алгоритмы с распределенной памятью» создавались для таких машин, как 1ВМ ВР-2 [256], 1п1е1 Рагайоп [257], компьютеры серии Сгау ТЗ [255] и сети рабочих станций. Как видно из таблицы, большая часть программ была написана для последовательных машин, некоторое количество для машин с разделяемой памятью и лишь совсем немногое (если не говорить об исследовательских программах) для машин с распределенной памятью. В первом столбце таблицы указан тип матрицы. Возможные варианты: несимметричные матрицы, матрицы симметричной структуры (т. е. такие, что а; = ад, = 0 либо, будучи неравны, оба элемента отличны от нуля), симме- 101 2.7. Специальные линейные системы Статус/ источник Тип матрицы Алгоритм Название Последовательные алгоритмы РпЪ/ХЕТЫВ РпЪ/74ЕТЫВ ЬЬ, частичный, ВЬАЯ-2.5 МР, Марковиц, В1 АЯ-3 ЯпрегЫ! ПМРРАСК [62, 63] МА38 [то же самое, что и 1)МРРАСК) МА48 [96] весим.

несим. Сош/НЯЬ Анализ: ВЬ, Марковиц Факторизация: ЬЬ, частичный, ВЬАБ-1, ЯР ВЬ, Марковиц, скалярный МР, барьерный, В1 АБ-3 Фронтальный, ВЬАЯ-3 МГ, йРЬ~, В1 АБ-1/ВЬАЯ-3 Ые ВЬАБ-3 несим. РпЪ/Ъ!ЕТЬ1В Сош/НБ1 Сош/НБЬ Сош/НБЬ РпЬ/Автор ЯРАНЯЕ [167] МСРЯ [5] МА42 [98] МА27 [97]/МА47 [95] Х8 й Реувоп 191 несим. сим, стр. сим. с.п.о.

Алгоритмы с разделяемой памятью Алгоритмы с распределенной памятью Вев/Автор чап бег Бварреп [245] 1 исав ес а1. [180] В.Ь, Марковиц, скалярный МР, нет выбора главных элементов, ВЬАЯ-1 НЬ, 2-Р блочный, ВЬАЯ-3 снм. снм. стр. Нев/Автор Вев/Автор НоСЬЪег8 й ЯсЬге1Ьег [207] Спрга й Кишат [132] САРЯЯ [143] с.п.о. Вев/Автор РпЪ/ХЕТЫВ МР, 2-Р блочный, В1 АЯ-3 МР, полностью параллельный, В1 АБ-1 [требует задания координат) с.п.о. с.п.о. Таблица 2.2. Программы для решения разреженных линейных систем прямыми ме- тодами. Сокраи!ения, используемые в таблице: несим.

= несимметричнаи сим. стр. = симметричная структура ненулевых элементов, значения несимметричны сим. = симметричнан, но, возможно, незнакоопределенная с.п.о, = симметричная и положительно определенная МР, ЬЬ и В.Ь = многофронтвльный, смотрящий влево и смотрящий вправо БР = переключается на плотный алгоритм, когда оставшаяся матрица в достаточной степени заполнена РпЪ = распространяется бесплатно; авторы могут помочь в использовании програм- мы Вев = опубликована, но возможность ее получения у авторов не гарантируется Сохи = коммерческая НБЬ = Нагие!! БпЪгопс!пе Ь!Ьгвху: Ьсср://ничик!.ас.п!г/дерагвшепсв/ссб/пашет!са!/Ьв!/Ьв!.Ьвш!. !)СВ = Ьгвр;//ннн.св.Ъег1ге!еу.ебп/ х!аоуе/впрег!п.ЬСш!. ЯсапЕогб = Ь!Ср://иичи-йавЬ.ввапГогд.ебп/арра/ЯРЬАЯН/.

182 Глава 2. Решение линейных уравнений 2.7.5. Плотные матрицы, зависящие от менее чем 0(п2) параметров Это слишком общий заголовок, охватывающий огромное разнообразие типов матриц, встречающихся на практике. Мы сможем упомянуть лишь несколько из них. Матриц1« Вондермонда имеют вид 1 хо хо 2 1 Х1 .2 1 хп 2 х| хп — 1 п п — 1 хо и — 1 1 Заметим, что вычисление следующего матрично-векторного произведения „т Ъ'т.

[аО .,ап] = ~,'~ а1ХО,...,~ а1Х*„~ эквивалентно задаче вычисление значений многочлена, поэтому решение системы»'~а = у равносильно полиномиальной интерполяции. С помощью интерполяцнонного метода Ньютона мы можем решить такую систему за хи~ флопов вместо 2по. Для решения системы Ъ'а = у имеется аналогичный прием и требуется также ~о п2 флопов.

См. [121, с. 178]. Матрица Коши С имеет элементы опВ1 С« »1 гй тричные (но возможно незнькоопределенные) матрицы и симметричные положительно определенные (с.п.о.) матрицы. Во втором столбце указано название программы (лнбо имена ее авторов). В третьем столбце сообщаются характеристики алгоритмов; некоторые из них мы не имел1.

возможности обсудить в данном учебнике. Сокращения Ь1 (смотрящий влево), ВЬ (смотрящий вправо), фронтальный, Мг (многофронтьльный) и ЬРЬт относятся к различным способам организации трех вложенных циклов, определяющих гьуссово исключение. Термины «частичный», «Марковиц» и «барьерный» описывают различные стратегии выбора главных элементов. Обозначение «2-0 блочный» характеризует распределение частей матрицы между параллельными процессорами. Алгоритм САРЯЯ предполагает, что линейная система соответствует некоторой сетке,и требует задания координат х, в и г узлов сетки для того, чтобы распределить матрицу между процессорами.

Кроме того, третий столбец описывает организацию самого внутреннего цикла; возможные варианты — ВЬАБ1, ВЬАБ2, ВЬАБЗ либо скалярный. Символом ЯР обозначается алгоритм, переключающнйся после и-го шага на плотное гауссово исключение, если остающаяся подматрица порядка и — Й уже достаточно заполнена. В четвертом столбце дана информация о статусе и наличии программ. В частности, указано, является ли программа коммерческой нли распространяется бесплатно, а также как получить доступ к ней.

103 2.8. Литература и смежные вопросы к главе 2 где и = [сгы...,а„], 13 = [Д,...ро], с = [сы...,~„] и г1 = [цы..., .] — заданные векторы. Самым известным примером является матрица Гп оерта Н, где ЬЕ = 1/(г + у — 1); она пользуется дурной славой вследствие чрезвычайно плохой обусловленности. Матрицы этого типа возникают при интерполировании посредством рациональных функций. Предположим, что мы хотим определить коэффициенты х рациональной функции с фиксированными полюсами й из условий 7" [(г) = у;, 1 = 1,...,п. Совокупность и уравнений 7"[(,) = у, представляет собой линейную систему порядка п, матрица коэффициентов которой есть матрица Коши.

Оказывается, что обращение матрицы Коши снова дает матрицу этого типа. Имеется замкнутое выражение для С ', использующее ее связь с задачей интерполирования: (С ')с1 = Р, 'о, '% — ей)Рг[ей)М вЂ” Ы, где Р (.) и Я,( ) — интерполяционные многочлены Лагранжа Теплицееы матрицы имеют вид ао аг аг ° ° ° ао а г аг а г а1 а„...аз агав т.е. они постоянны вдоль каждой диагонали.

Эти матрицы возникают в зштачвх обработки сигналов. Имеются алгоритмы для решения линейных систем с такими матрицами, требующие только 0(пг) операций. Все указанные методы обобщаются на многие родственные типы матриц, зависящих только от 0(п) параметров (см. [121, с. 183) или обзор современного состояния этой области в [160)). 2.8. Литература и смежные вопросы к главе 2 Дальнейшую информацию о задаче решения линейных уравнений в общем случае можно получить в главах 3 и 4 книги [121).

Отношение взаимной обратности между числом обусловленности и расстоянием до ближайшей некорректной задачи более подробно исследуется в [71). Вероятностный анализ роста главных элементов проделан в [242), а в [122) приведен пример роста в гауссовом исключении с полным выбором главных элементов, нарушающего гипотезу Уилкинсона. Оценщики обусловленности описаны в [138, 146, 148]. Итерационное уточнение в арифметике обычной точности анализируется в [14, 225, 104 Глава 2. Решение линейных уравнения 226].

Очень полное обсуждение анализа ошибок для методов решения линейных систем, покрывающее большинство вопросов в этой области, можно найти в [149]. По поводу факторизации симметричных незнакоопределенных матриц см. [44]. Алгоритмы для разреженных матриц описаны в [114, 93]; см. также многочисленные ссылки в табл. 2.2. Программные реализации многих алгоритмов для плотных и ленточных матриц, описанных в этой главе, содержатся в пакетах ЬАРАСК и СЬАРАСК [10]; там же можно найти обсуждение блочных алгоритмов, пригодных для высокопроизводительных компьютеров. Параллельные реализации алгоритмов даны в пакете ЯсаЬАРАСК [34].