Введение к работе
Диссертационная работа посвящена разработке эффективных алгоритмов для матриц над полями и коммутативными областями
Актуальность темы.
С появлением параллельных вычислительных машин возникает необходимость в построении эффективных параллельных алгоритмов для решения задач численными методами и методами компьютерной алгебры Это привело в области программного обеспечения параллельных вычислительных комплексов к созданию нового научного направления - параллельной компьютерной алгебры Появились параллельные алгоритмы умножения матриц, вычисления обратных матриц, определителей, решения систем линейных уравнений и др
Одной из важных характеристик параллельной программы является ее масштабируемость Известно, что масштабируемость матричного умножения может быть очень высокой Поэтому одним из путей создания алгоритмов с высоким показателем масштабируемости является построение блочных матричных алгоритмов, которые используют параллельное матричное умножение С другой стороны, блочные рекурсивные алгоритмы позволяют получать параллельные алгоритмы со сложностью матричного умножения, эффективные как для однопроцессорных, так и для параллельных вычислений Кроме того блочные алгоритмы дают одно из лучших решений для параллельных машин с распределенной памятью, так как с их использованием можно эффективнее использовать межпроцессорные коммуникации и обеспечивать равномерную загрузку процессоров
Одним из главных препятствий для использования известных блочных матричных алгоритмов является возможность вырождения ведущего блока При этом алгоритм должен либо прекратить работу, либо должна произойти реорганизация вычислений, уменьшающая количество его параллельных инструкций Отметим, что С Ватт1 предлагает обращать матрицу АтА, у которой все главные миноры невырожденные, а затем вычислять А~1 = (АТА)~1АТ Но за это ему приходится расплачиваться дополнительными двумя матричными умножениями
Цель работы.
Целью настоящей работы является разработка новых матричных методов компьютерной алгебры и получение оценок сложности матричных
1Watt SM Pivot-Free Block Matrix Inversion Proc 8th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, (SYNASC 2006), Sept 26-29 2006, Timisoara, Romania
алгоритмов Сюда относятся следующие задачи
Вычисление присоединенных матриц и определителей для матриц над коммутативной областью
Обращение матриц над полем Нахождение и обращение максимальной невырожденной подматрицы для вырожденной матрицы
Решение неопределенных систем над полем
Построение эффективных форматов хранения матриц для блочно-рекурсивных и параллельных алгоритмов
Получение оценок сложности для алгоритмов умножения разреженных числовых и полиномиальных матриц
Методы исследования.
В работе используются методы компьютерной алгебры, в том числе методы гомоморфных образов, методы детерминантных тождеств, а также методы теории графов и теории вероятностей Для экспериментов использовались пакеты JDK текущих версий, а для экспериментов с параллельными алгоритмами - среда Par Java ИСП РАН
Научная новизна.
Получен метод вычисления присоединенной матрицы и определителя для матриц над коммутативной областью В отличие от известного блочного метода, новый метод не имеет ограничений, связанных с вырожденностью ведущих матричных блоков
Получено два новых метода обращения матриц над полем Данные методы являются рекурсивными, блочными, имеют сложность матричного умножения Для невырожденной матрицы эти методы возвращают обратную матрицу, а для вырожденной матрицы они находят максимальную невырожденную подматрицу и обратную матрицу к этой подматрице Данные методы позволяют находить решения неопределенных систем уравнений
Получены оценки сложности матричных операций сложения и умножения для различных разреженных числовых и полиномиальных матриц Для этого вычислено математическое ожидание количества аддитивных и мультипликативных операций, требуемых каждым алгоритмом Получены оценки сложности в числе арифметических операций и в числе бит-операции для рациональных чисел При этом учитывается изменение как плотности матриц и плотности матричных элементов (полиномов), так и изменение битовой длины числовых коэффициентов во время вычислений
Практическая ценность.
Разработанные методы могут использоваться в пакетах прикладных программ и системах компьютерной алгебры Разработанные программы могут использоваться в реальных вычислениях
Апробация работы
Результаты исследований в рамках данной работы докладывались на следующих конференциях
Алгебра и анализ (Казань, 2004),
6 Международная конференция "Дискретные модели в теории управляющих систем" (Москва, 2004),
Проблемы теоретической кибернетики (Пенза, 2005),
Державинские чтения (Тамбов, 2004—2007),
12-я международная конференция, посвященная приложениям компьютерной алгебры (Варна, Болгария, 2006),
научные семинары в Тамбовском университете
Публикации автора. Основные результаты диссертации опубликованы в 14 работах
Структура и объем работы Диссертация состоит из введения, четырех глав, включающих 11 параграфов, заключения, приложения, списка литерат>ры и изложена на 138 страницах
