Матричные методы вычислений над коммутативными кольцами в компьютерной алгебре

• Автор: Малашонок, Геннадий Иванович
• Шифр специальности: 05.13.11
• Научная степень: Докторская
• Год защиты: 2002
• Место защиты: Тамбов
• Количество страниц: 243 с.

ОГЛАВЛЕНИЕ

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

Введение .

Глава 1. Матричные и детерминантные тождества

1.1. Матрицы миноров

1.2. Тождество Сильвестра.

1.3. Детерминантное тождество спуска

1.4. Тождество замены столбцов

1.5. Дегерминантное тождество подъема.

1.6. Общее тождество днагонализацш.

1.7. Сводка детерм и нянтных тождеств.

Глава 2. Решение систем линейных уравнений в коммутативных
кольцах
2.1. Невырожденные системы
2.2. Вырожденные системы .
2.3. Присоединенная функции м построение канонической системы .
Глава 3. Решение систем линейных уравнений в коммутативных
областях
3.1. Решение системы сведением к фак гор кольцу
3.2. Решение системы в коммутативной области путем обратимого приведения к треугольному виду
3.3. Решение системы сведением к определенным системам.
3.3.1. Решение системы г поле частных
3.3.2. Вероятностный метод
3.3.3. Детерминистский метод5б
Глава 4. Методы кубической сложности в коммутативной области
4.1. Постановка задачи.СО
4.2. Метод прямого и обратного хода Л Ы 0
4.2.1. Постановка задачи
4.2.2. Прямой ход А Ы
4.2.3. Обратный ход Ы .
4.2.4. Пример.
4.3. Метод одного прохода А 0
4.3.1. Пример.
4.4. Обобщенный метод
4.4.1. Вычислительная схема обобщенного метода
4.4.2. Алгоритм обобщенного метода
4.4.3. Пример.
4.5. Вычисление определителей присоединенных и обратных матриц, ядра линейного оператора
4.6. Оценка сложности алгоритмов .
4.6.1. Оценка по кол и месту операций в области Я о.
4.6.2. Оценка алгоритмов в колкие 1Кхьх2,. х.
4.0.3. Оценка алгоритмов в кольце Ъх. х2,. хТо
Глава 5. Методы субкубической сложности в коммутативной области 7
5.1. Ре к у рс и вн ы й I етод.
5.1.1. Вычислительная схема заключительного этапа.
5.1.2. Вычислительная схема промежуточного этапа
5.1.3. Сложность рекурсииного метода.
5.1.4. Пример
5.2. Вычисление присоединенной матрицы
5.2.1. Постановка задачи.
5.2.2. Теоремы о факторизации присоединенной матрицы .
5.2.3. Алгоритм
5.2.4. Бинарная факторизация
5.2.5. Оценка слжности.
5.2.6. Пример
Глава С. Вычисление характеристического полинома в коммутативной области
6.1. Постановка задачи
6.2. Квазигрсугольная и трехдиагональная матрицы
6.3. Матричная запись прямого хода
6.4. Сопряженный прямой хода.
6.5. Разложение Гаусса
6.6. Вычисление подобной квазитреугольной матрицы
6.7. Вычисле ние подобной трехдиагоналмюй матрицы
6.8. Оценка сложности
6.9. Пример вычисления характеристического многочлена
Глава 7. Вычисление субрезультантной последовательности полиномиальных остатков
7.1. Постановка задачи.
7.2. Вычисление ППО с помощью алгори тма прямого хода .
7.3. Дихотомический рекурсивный метод
7.4. Пример .
Глава 8. Кольца главных идеалов
8.1. Постановка задачи.
8.2. Конструктивные кольца главных идеалов.
8.3. Разложение матрицы в конструктивном кольце главных идеалов
8.4. Субкубические алгоритмы разложения матриц.
8.5. Субкубические алгоритмы решения систем
8.. Вычисление характеристического многочлена.
8.7. Вычисление присоединенной матрицы.
Глава 9. Решение систем в евклидовых областях
9.1. Постановка задачи.
9.2. Вычислительная модель.
9.3. Стандартный и модулярный метод
9.3.1. Общий алгоритм решения.
9.3.2. Стандартная арифметика.
9.3.3. Модулярная арифметика
9.4. Решение системы радическим методом в поле частных
9.5. Вероятностный метод решения системы в коммутативной области
9.6. Решение4 системы в евклидовой области радическим детерминистским методом.
9.7. Обсуждение результатов
9.7.1. Оценки сложности решения системы в ноле чашных
и x.
9.7.2. Оценки сложности решения системы в и x .
Заключение .
Приложение. Пакет процедур в системе i.
Литература


Решение систем линейных уравнений в двух евклидовых областях - в кольце целых чисел и в кольце полиномов над нолем наиболее часто встречается в приложениях. G6| и др. Наиболее известные современные алгоритмы решения диофанто-вых систем линейных уравнений - это алгоритмы В. А.Бланкиншипа ||, Р. Т.Грегори и Е. В.Кришнамурти [], К. С. Илиополоса [], Дж. Л.Хафнераи К. С.МакКели |]. М.Гисбрехта [], Т. Мулдерса и А. Сториохана [], А. Сториохана [], Г. Лабан а и А. Сториохана []. Лучший результат получен в работе []. Он имеет сложность Nr (А))). Здесь Nr (А) = max^dAjjl), 0(М(2)) - сложность умножения двух 2-битных чисел. Для стандартных алгоритмов М(2) = 2“, для FFT алгоритмов М(2) — 2 log 2 log log 2 [4U|, ]. Для стандартных алгоритмов умножения оценка сложности алгоритма [] составляет U~(n4m log2 Nr (А)), а для FFT алгоритмов умножения - 0~{r? Nr (А)). Каждый из них сводит задачу к решению системы в кольце вычетов, поэтому можно применить алгоритм решения системы в кольце главных идеалов, описанный в главе 8. В модулярном алгоритме исходная система сводится к эквивалентной системе с матрицей коэффициентов, имеющей диагональный левый квадратный блок с диагональными элементами, равными определителю этого блока. Затем решается система по модулю этого определителя. В р-адическом методе вычисляется базисное множество точек на плоскости всех рациональных решений системы с помощью р-адического подъема. А затем для получения решений в евклидовой области вычисляются все целые точки на этой плоскости. Оценка сложности р-адического и модулярного алгоритмов для стандартных алгоритмов умножения составляет ()~"(плт log” Nr (А)), а для быстрых алгоритмов — 0~(nzmlog Nr (А)). А Е Znxm ранга п. Сравнение этих оценок с оценками сложности алгоритма [] показывает, что для быстрых алгоритмов умножения оценки сложности этих алгоритмов хуже в п'’~: раз, а для стандартных алгоритмов умножения оценки для них лучше в п раз. Это позволяет считать алгоритм [] теоретически лучшим, а приведенные в этой главе р-адический и модулярный алгоритмы практически лучшими. В заключительном разделе главы обсуждаю гея полученные алгоритмы и сравниваются их оценки сложности для разных видов систем. Такое сравнение позволяет описать рекомендуемые области применения этих алгоритмов, что важно для практических целей. В приложении приводится пакет процедур в системе компьютерной алгебры Ма&НатаЫса, - 4. Быстродействие процедур, составляющих пакет, оценивалось путем сравнения с аналогичными процедурами последней версии системы МаЬЫмпаИса. Результаты сравнения, показывающие преимущество новых алгоритмов, представлены в таблице для разных типов матриц. В этой главе доказываются детерминантные тождества, для матриц над коммутативными кольцами. Эти детерминантные тождества необходимы будут* в дальнейшем для обоснования развиваемых вычислительных методов. Пусть Я - коммутативное кольцо, А Е Япхт - матрица размера и х т над кольцом Я. Будем пользоваться следующими обозначениями для подматриц. Л^У- Л^,""'^] подматрица, стоящая на пересечении строк ц + 1. Л-‘у-Л[[ *! Введем обозначения для миноров. Будем обозначать миноры малыми греческими буквами, при этом верхний индекс будет всегда обозначать порядок минора. Л, 1 ^ к ^ тіи(п? Л, 1 ^ к ^ тіп(п,т), /,? Л(А) — алгебраическое дополнение элемента (і,кі) в матрице Л(ДД,. Введем матрицы миноров матрицы Л. Л* присоединенная матрица для квадратной матрицы Л. Пусть I = тіп(п,т). Для к = 1,2,. Ятхт, (1. С(л),АС = Й,(Л). У матриц 0к и Чк в верхнем левом углу находится скалярный блок Д Д. Н все элементы в столбцах к + 1,. О, ^ „д. Матрица 5 при //, ^ т будет скалярной 5 = <*т/т. О а? Рассмотрим свойства матриц миноров. Предложение 1. Свойства . Для любой матрацы А. Ак =