Блочные символьные матричные алгоритмы

• Автор: Зуев, Михаил Сергеевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Тамбов
• Количество страниц: 116 с. : ил.

ОГЛАВЛЕНИЕ

Условные обозначения .

Введение

Глава 1. Алгоритм вычисления присоединенной матрицы и

определителя

1.1. Постановка задачи

1.2. Перестановочный алгоритм

1.3. Некоторые вычислительные эксперименты.

Глава 2. Алгоритмы вычисления обратной матрицы

2.1. Алгоритм с двусторонним разложением.

2.2. Алгоритм с односторонним разложением

2.3. Некоторые вычислительные эксперименты.
Глава 3. Форматы хранения разреженных матриц
3.1. Алгоритмы для матриц в формате хранения СТ.
3.1.1. Стандартные алгоритмы с Гматрицами.
3.2. Алгоритмы для матриц в формате хранения БМ
3.2.1. Стандартные алгоритмы с БМматрицами
3.3. Алгоритмы для матриц в формате хранения ТвМ.
3.3.1. Стандартные алгоритмы с уГЭМматрицам и
3.4. Некоторые вычислительные эксперименты.
Заключение
Приложение 1
Приложение 2 .
Приложение 3 .
Литература


Такие алгоритмы могут эффективно использовать запоминающие устройства компьютера: процессорный кэш, оперативную память, жесткий диск при вычислениях с: использованием записи данных на диск (“out-of-core”, см. При этом возможно использование быстрых алгоритмов матричного умножения, что уменьшает вычислительную сложность таких алгоритмов. Блочно-рекурсивные алгоритмы могут быть реализованы с использованием древовидных форматов хранения матриц (см. В работах Ф. Г. Густавсона (F. G. Gustavson, , [], , []) предложен подход к построению эффективных алгоритмов численной линейной алгебры (автор исследует алгоритмы для плотных матриц в системе LAPACK). Быстрые алгоритмы должны оптимально работать с процессорным кэшем. Только так можно добиться максимальной производительности процессора. Лучше всего этому требованию отвечают блочно-рекурсивные алгоритмы. На примере LAPACK показано ускорение на -0 % для различных алгоритмов (умножение матриц, LU-разложспие, разложение Холецкого). В работе Д. С. Вайза. D.S. Wise, , []) предложен блочный вариант классического алгоритма умножения плотных матриц, который может быть быстрее стандартного варианта этого же алгоритма. Результаты Ф. Г. Густавсона. Д.С. Вайза могут быть справедливы и для задач компьютерной алгебры. Получение новых эффективных блочных и блочно-рекурсивных алгоритмов компьютерной алгебры является основной целью диссертационной работы. Алгоритмы обращения матриц, вычисления присоединенной матрицы и определителя. Известно несколько блочных алгоритмов вычисления обратной матрицы (см. Шур и Ваначиевич (I. Schur, Т. Banachiewicz), вероятно, впервые получили формулу для вычисления обратной матрицы (см. F = А~ G = (D - CFB)- S = D~ Т = (А - BSC)~l. Блок U -СА~1В называется дополнением Шура (Schur complement) к блоку Л, блок А-BD 1С называется дополнением Шура к блоку D. Блоки А и D должны быть квадратными. Формула Вудбери (М. А-'Вф-СА-'Ву'СА-1. В качестве быстрого алгоритма вычисления обратной матрицы этот алгоритм был рассмотрен в работе Ф. Штрассена (V. Strassen, G9. Кроме того, в этой работе был предложен первый известный быстрый алгоритм умножения матриц и показано, что алгоритм обращения матриц имеет оценку сложности того же порядка, что и предложенное матричное умножение, следовательно, он более эффективен, чем алгоритм Гауссова исключения. Поэтому этот алгоритм вычисления обратной матрицы будем в дальнейшем называть алгоритмом Штрассена. Основное ограничение этого алгоритма обращения матриц: левый верхний блок (или правый нижний) должен быть обратимым. При этом можно выбрать левый верхний блок произвольного порядка. Заметим, что существуют невырожденные матрицы, все левые угловые блоки которой вырожденные. Примером такой матрицы может служить матрица, у которой на побочной диагонали стоят ненулевые элементы, а все остальные элементы равны нулю. Следовательно, такой алгоритм нельзя использовать в общем случае. В работе Д. Вини и В. Пана (D. Bini, V. Y. Pan, , [|) предложена формула Л~1 = (Л А)~1 А, определяющая алгоритм вычисления обратной матрицы. Эта формула позволяет найти обратную матрицу для любой невырожденной матрицы над полем характеристики 0 с помощью алгоритма Штрассена, но требует в любом случае двух дополнительных матричных умножений. В работе С. Ватта (S. Watt, , []) указано обобщение этого алгоритма на случай конечного поля. Но для этого требуется обращение матрицы над полиномами, требующее существенно большего количества операций. Таким образом, этот алгоритм тоже не всегда, можно использовать в реальных вычислениях. Еще один быстрый алгоритм вычисления обратной матрицы основан на быстром алгоритме LU- (точнее, LUP-) разложения матриц, полученных в работе Дж. Банча и Дж. Хоикрофта (J. Bunch, J. Hopcroft, , []). Алгоритм LU-разложения матриц, предложенный в их работе, не имеет ограничений, то есть, находит результат для любых невырожденных матриц. Но этот алгоритм предполагает деление матриц на 2 подблока, а не на 4, и требует поиска ненулевого элемента по строке, поэтому но может быть эффективно реализован с использованием древовидного формата хранения матриц. Известна модификация этого алгоритма, предложенная О. Ибаррой и др. Ibarra О. Moran S. Hui R.