автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Блочные символьные матричные алгоритмы

На правах рукописи

Зуев Михаил Сергеевич

БЛОЧНЫЕ СИМВОЛЬНЫЕ МАТРИЧНЫЕ АЛГОРИТМЫ

Специальность 05 13 11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Тамбов 2008

003169962

Работа выполнена на кафедре компьютерного и математического моделирования Тамбовского государственного университета им Г Р.Державина

Научный руководитель доктор физико-математических наук,

профессор

Малашонок Геннадий Иванович

Официальные оппоненты доктор физико-математических наук,

профессор

Абрамов Сергей Александрович

Защита диссертации состоится « 18 » июня 2008 г в 14 часов на заседании диссертационного совета Д 002 087 01 при Институте системного программирования РАН по адресу

109004, г Москва, ул Большая Коммунистическая, 25, Институт системного программирования РАН, конференц-зал

С диссертацией можно ознакомиться в библиотеке Института системного программирования РАН

Автореферат разослан « 18 » мая 2008 г

Ученый секретарь

диссертационного совета

кандидат физико-математических наук

кандидат фи: наук

Шокуров Владимирович

физико-математических

Александр

Ведущая организация Механико-математический факультет

Московского государственного университета им М В Ломоносова

/Прохоров СП/

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Диссертационная работа посвящена разработке эффективных блочных и блочно-рекурсивных алгоритмов для матриц над полями и коммутативными областями

Актуальность темы

Компьютерная алгебра - интенсивно развивающаяся наука Ее методы находят применение в различных областях науки и практики1 - физике (физика высоких энергий, небесная механика, общая теория относительности, электронная оптика, электротехника и др ), математике (теория чисел, проективная геометрия, дифференциальные уравнения, специальные функции и др ), информатике (численные методы, теория кодирования, криптология и др ) Алгоритмы и системы компьютерной алгебры используются математиками для преобразования сложных символьных выражений или вычислений с большой точностью Но методы компьютерной алгебры требуют выполнения существенно большего количества операций, чем численные методы, предназначенные для решения тех же задач с ограниченной точностью

Поэтому даже при современной мощности вычислительной техники остро стоит проблема получения быстрых, эффективных алгоритмов компьютерной алгебры Среди матричных алгоритмов такими могут быть блочно-рекурсивные алгоритмы со сложностью того же порядка, что и матричное умножение, используемое в них для перемножения блоков В силу свой блочной структуры, такие алгоритмы эффективно используют память, в частности, кэш2 и позволяют добиваться высокой производительности На их основе можно получать быстрые параллельные алгоритмы с высокими показателями масштабируемости и локальности Кроме того, существует интерес к разработке алгоритмов для матриц, хранящихся в древовидном виде3

Получение новых эффективных блочных и блочно-рекурсивных алгоритмов компьютерной алгебры является основной целью диссертационной работы В работе рассмотрены алгоритмы обращения матриц над конечным полем, вычисления присоединенной матрицы и

'ван Хюльзен Я. А , Калме Ж. Применения компьютерной алгебры / Компьютерная алгебра Символьные и алгебраические вычисления Пер с англ / Под ред Бухбергера Б , Коллинза Дж , Лооса Р — M Мир, 1986

2Gustavson F G High-performance linear algebra algorithms using new generalized data structures for matrices // IBM Journal for Research and development January 2003 V 41 Issue 1 P 31-55

3Watt S M 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 P 151-155

определителя над коммутативной областью, алгоритмы для матриц, представленных в древовидном формате хранения Под форматом хранения понимается структура данных, предназначенная для представления матриц в памяти машины

Для вычисления обратной матрицы над полем известны следующие блочные алгоритмы

1 Блочные аналоги алгоритма Гаусса

2 Блочно-рекурсивный алгоритм, основанный на алгоритме LU-разложения Дж Банча и Дж Хопкрофта4

3 Блочно-рекурсивный алгоритм Ф Штрассена5 Алгоритм представляет собой блочно-рекурсивную модификацию алгоритма Гаусса для случая дихотомического разбиения матрицы

4 Алгоритм, основанный на предыдущем алгоритме и предполагающий домножение на сопряженную транспонированную матрицу6

Последние три алгоритма имеют сложность такого же порядка, что и матричное умножение Второй алгоритм требует поиска ненулевого ведущего элемента по строке и не предполагает разбиения матрицы на четыре равных квадратных блока, поэтому не предназначен для реализации с использованием древовидного формата хранения Третий алгоритм требует, чтобы диагональные блоки четного порядка были невырожденными В противном случае алгоритм должен либо прекратить работу, либо изменить размер диагональных блоков (то есть разбить матрицу не на равные по размеру блоки) Это препятствует равномерной загрузке процессоров вычислительной машины, увеличивает количество выполняемых операций, не позволяет реализовать алгоритм с использованием древовидного формата хранения и не гарантирует получение обратной матрицы Четвертый алгоритм основан на третьем, но требует дв\ х дополнительных операций умножения матриц Кроме того, этот алгоритм работает только для матриц над полями характеристики 0 Обобщение его на случай конечных полей, приведенное в работе С Ватта (см стр 3), требует существенно большего количества операций

4Bunch J., Hopkroft J. Triangular factorization and inversion by fast matrix multiplication // Mat Comp V 28 1974 P 231-236

5Strassen V Gaussian elimination is not optimal // Numerische Mathematik 1969 V 13 P 354-356

6Bim D , Pan V Y Polynomial and matrix computations Fundamental algorithms V 1 Birkhauser, 1994

Таким образом, существующие алгоритмы вычисления обратной матрицы либо требуют поиска ведущих элементов или блоков, и не предполагают разбиения матрицы на четыре равных квадратных блока, либо не гарантируют получения корректного результата для произвольной невырожденной матрицы Это выдвигает задачу получения нового блочно-рекурсивного алгоритма, свободного от этих ограничений Такой алгоритм предполагал бы эффективную реализацию с использованием древовидного формата хранения матриц

Хранение матриц в древовидном формате исследовалось в работах Д С Вайза7 Возникает задача построения на его основе более эффективного древовидного формата хранения матриц, который был бы предназначен для блочно-рекурсивных и параллельных алгоритмов компьютерной алгебры и эффективно использовал кэш процессора Следовательно, размер матрицы, соответствующей его листу, должен быть больше 1, и должна существовать возможность его изменения Для параллельных вычислений с машинами с распределенной памятью обычно используется стандарт MPI Формат, предназначенный для таких вычислений, должен предполагать представление матрицы в виде одномерных массивов с элементами примитивного типа и реализацию с использованием языков, поддерживаемых MPI (С, С++, Fortran) Так как формат предназначается для задач компьютерной алгебры, то дотжна существовать как возможность хранения матриц над элементами различных типов, например, полиномами, так и возможность интеграции формата хранения матриц с форматом хранения ее элементов Это позволит хранить не сами элементы, а их коэффициенты и, следовательно, избежать преобразования матрицы перед ее передачей по сети

Для вычисления присоединенной матрицы и определителя в коммутативной области существует блочно-рекурсивный алгоритм, полученный в работе Г И Малашонка8 Этот алгоритм имеет те же ограничения, что и блочно-рекурсивный алгоритм Штрассена вычисления обратной матрицы, так как основан на нем Другой алгоритм получается из рекурсивного алгоритма решения систем линейных уравнений9, и имеет такие же ограничения Кроме того, для случая

7Abdah S К , Wise D. S Experiments with quadtree representation of matrices Proc ISSAC 88, Lecture Notes in Computer Science 358, Springer Verlag, 1989, P 96-108

8Malaschonok G I Effective Matrix Methods in Commutative Domains / Formal Power Series and Algebraic Combinatorics Springer, 2000 P 506-517

9Malaschonok G. I Recursive Method for the Solution of systems of Linear Equations / Computational Mathematics A Sydovv Ed Proc 15th IMACS World Congress V I Berlin, August 1997 Wissenschaft and Technik Verlag, Berlin, 1997

вычисления присоединенной матрицы этот алгоритм имеет больший коэффициент при старшей степени в оценке сложности, чем первый алгоритм Другие известные алгоритмы вычисления присоединенной матрицы и определителя и решения систем линейных уравнений в коммутативной области имеют сложность порядка п3 Поэтому возникает задача получения блочного алгоритма, не имеющего вычислительных ограничений

Цель и задачи работы

Целью настоящей работы является разработка новых блочных матричных алгоритмов компьютерной алгебры и получение оценок сложности этих алгоритмов Сюда относятся следующие задачи

• Получение блочного алгоритма вычисления присоединенных матриц и определителей для матриц над коммутативной областью, левые верхние миноры которых могут быть нулевыми

• Получение блочно-рекурсивных алгоритмов обращения матриц над полем, нахождения и обращения невырожденной подматрицы максимального порядка для вырожденной матрицы, не использующих поиск ненулевых ведущих элементов и предполагающих разбиение матриц на квадратные блоки равного размера, которые могут быть вырожденными

• Получение методов хранения матриц, основанных на блочной рекурсивной дихотомической декомпозиции до подматриц некоторого произвольного порядка, и соответствующих алгебраических алгоритмов

• Программная реализация разработанных алгоритмов и проведение вычислительных экспериментов для сравнения эффективности новых алгоритмов с уже известными

Методы исследования

В работе используются методы компьютерной алгебры, в том числе методы гомоморфных образов, методы детерминантных тождеств, а также методы теории графов и теории вероятностей Для экспериментов использовались пакеты JDK текущих версий

Научная новизна

Научная новизна работы заключается в следующем

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

Р 475-480

Новый алгоритм имеет ту же вычислительную структуру, что и взятый за основу блочно-рекурсивный алгоритм Г И Малашонка, но не имеет ограничений, связанных с вырожденностью ведущих матричных блоков

• Разработаны два алгоритма обращения матриц над полем Эти алгоритмы являются блочно-рекурсивными, имеют сложность матричного умножения и предполагают разбиение матрицы на 4 квадратных блока равных размеров Алгоритмы не содержат процедур поиска невырожденного ведущего блока (элемента) и не используют перестановок строк и столбцов матрицы Для невырожденной матрицы эти алгоритмы возвращают обратную матрицу, а для вырожденной матрицы они находят максимальную невырожденную подматрицу и обратную к ней На основе одного из этих алгоритмов получен алгоритм решения неопределенных систем линейных уравнений над конечным полем и вычисления определителя матриц

• Разработаны методы хранения матриц, предполагающие их блочную рекурсивную дихотомическую декомпозицию Соответствующие структуры данных названы древовидными форматами хранения матриц Лист дерева представляет собой прямоугольную матрицу произвольного размера Для хранения листа можно испотьзовать любой формат хранения матриц, предполагающий их представление в виде двух одномерных массивов

Практическая ценность

Разработанные алгоритмы могут использоваться в пакетах прикладных программ и системах компьютерной алгебры На основе разработанных алгоритмов реализованы программы на языке Java и с ними проведены вычислительные эксперименты, показавшие большую эффективность полученных алгоритмов по сравнению с уже известными Разработанные программы могут использоваться в реальных расчетах

Апробация работы

Результаты исследований в рамках данной работы докладывались на следующих конференциях

- Алгебра и анализ (Казань, 2004),

- 6 Международная конференция "Дискретные модели в теории управляющих систем" (Москва, 2004),

- Проблемы теоретической кибернетики (Пенза, 2005),

- Державинские чтения (Тамбов, 2004-2008),

- 12-я международная конференция, посвященная приложениям

компьютерной алгебры (Варна, Болгария, 2006),

- 11-th Workshop on computer algebra, (Дубна, 2007),

- научные семинары в Тамбовском университете

Публикации автора. Основные результаты диссертации опубликованы в 10 работах

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, приложения, списка литературы Общий объем диссертации - 116 страниц Список литературы включает 75 наименований

Личное участие автора в получении результатов, изложенных в диссертационной работе

В работах, написанных в соавторстве (см публикации 8, 9, 10), автору принадлежат получение перестановочного алгоритма вычисления присоединенной матрицы и определителя, разработка двустороннего и одностороннего алгоритмов обращения матриц и матричных алгоритмов, предназначенных для исследуемых в работе форматов хранения матриц, а также программная реализация этих алгоритмов и проведение экспериментов с ними на однопроцессорной машине

СОДЕРЖАНИЕ РАБОТЫ

Во введении приведена постановка задачи, дан обзор близких работ и кратко изложено содержание диссертации

В первой главе рассматривается б точный алгоритм вычисления

присоединенной матрицы и определителя Использованы обозначения

• - блок матрицы А, стоящий на пересечении ее строк с номерами к,к + 1, ,1 и столбцов с номерами тп,т + 1, , п (0 ^ к <

• ак - верхний левый угловой минор матрицы А порядка к, положено а° = 1

• - минор порядка к, полученный окаймлением верхнего левого углового минора матрицы А порядка к — 1 строкой г и столбцом J, в частности, al, = а,;

• Ак = (а1;) - матрица, составленная из миноров а^, в частности, А1 = А

• А" - присоединенная матрица к матрице А

Известен алгоритм Г И Малашонка, который вычисляет присоединенную матрицу и определитель для невырожденной матрицы

А =

(

£ Л*х», блоки и О которой квадратные и

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

В основе нового алгоритма лежат следующие принципы

1 Перестановочность Предлагается управлять выбором блока матрицы миноров стоящего на его главной диагонали, путем умножения на матрицу перестановок Для этого производятся эффективные вычисления матрицы •Д*^*.!'!11-1, гДе 7711 > т и поиск в ней невырожденной подматрицы требуемого ранга

2 Отказ от рекурсивной записи Эффективные вычисления блока Л;^1;-?1"1 на некотором шаге алгоритма используют подматрицы из предыдущих шагов При этом необходимость обращать на каждом шаге матрицы малого порядка алгоритмически упрощает задачу поиска невырожденной подматрицы в блоке -Д^^Л™1-1

Приведены результаты вычислительных экспериментов с новым алгоритмом Проведено две серии экспериментов с алгоритмами вычисления присоединенной матрицы и определителя для целочисленной матрицы - с использованием китайской теоремы об остатках и без ее использования Перестановочный алгоритм оказался лучшим алгоритмом для матриц над коммутативной областью, не имеющим ограничений Другие алгоритмы вычисления присоединенной матрицы и определителя для матриц над коммутативной областью проиграли перестановочному алгоритму как минимум на 60% в первой серии экспериментов и как минимум на 15% во второй серии экспериментов Поэтому новый алгоритм можно использовать в реальных расчетах

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

Пусть F - поле, полугруппа Рп образована матрицами над Р порядка п, у которых число единичных элементов совпадает с их рангом, а остальные элементы равны нулю Полугруппа £>„ образована диагональными матрицами порядка п с элементами 0 и 1 на диагонали

Пусть п — 2к Алгоритм обращения матриц с двусторонним разложением (двусторонний алгоритм) вычисляет две обратимые матрицы Ли С для произвольной матрицы А 6 РпХп, такие что ЯАС = Е е Рп, Я - нижняя треугольная и С - верхняя треугольная матрицы Если А - обратима, то ЕТЕ = I и А'1 = СЕТЯ

Пусть - невырожденная подматрица максимального порядка матрицы Е Тогда, с точностью до перестановок строк и столбцов, матрица Е имеет вид как на рисунке

Е1 0

0

Двусторонний алгоритм состоит из 3 шагов Пусть матрица А разбита на четыре квадратных блока Ац, А12, А21, А22 Тогда графическое описание каждого шага, с точностью до перестановок, имеет следующий вид

1 Вычислить ЯьСа Я1АС1 = Л1, где матрица А1 выглядит следующим образом

Выполняется рекурсивный вызов алгоритма для левого верхнего блока матрицы А и составляются обратимые сомножители для матрицы А, применяющие результаты вызова алгоритма к ее левому верхнему блоку Затем они домножаются на такие обратимые матрицы, что в А12 появляются нулевые строки на месте строк, ненулевых в Е\\ и в Ац появляются нулевые столбцы на месте столбцов, ненулевых в Ец

2 Вычислить Н.2,С2 ДгА'Сг = -I2, где матрица А2 выглядит следующим образом

Ей 0 0

0 X

0 X X

Параллельно выполняются

рекурсивные вызовы алгоритма для правого верхнего и левого нижнего блоков матрицы А1 и составляются обратимые сомножители для матрицы А1, применяющие результаты этих вызовов к соответствующим блокам матрицы А1 Затем они домножаются на такие обратимые матрицы, что в А22 на месте строк, ненулевых в £21, появляются нулевые строки и в А22 на месте столбцов, ненулевых в Ей, появляются нулевые столбцы

3 Вычислить Дз,Сз ПзЛ2Сз = /I3 = Е, где матрица А3 выглядит следующим образом

Выполняется рекурсивный вызов алгоритма для правого нижнего блока матрицы А2 и построение обратимых сомножителей для матрицы А2, применяющих результаты этого вызова к ее правому нижнему блоку Матрица А3 есть матрица Е (с точностью до перестановок)

Получены верхние оценки сложности этого алгоритма Двусторонний алгоритм использует 17 матричных умножений и 4 рекурсивных вызова в общем случае Пусть М(тг) = + о{"пР) - верхняя оценка

сложности матричного умножения Тогда сложность вычисления матриц Я и С для матрицы порядка п с помощью двустороннего алгоритма не превосходит Ко(/3) -уп13 + о(п0) операции умножения элементов матрицы, где Кв(/3) = ш)^, ? Для получения

обратной матрицы вычисляется произведение СЕТЯ, требующее не более Кт{Р)-уп0 + о(п0) операций, где Кт(/3) = шш(1,

В случае, когда левый верхний блок матрицы невырожден, используются 7 матричных умножений и 2 рекурсивных вызова алгоритма Для этого случая получен сокращенный вариант алгоритма Если сокращенный вариант алгоритма используется во всех его

Еп 0 0

0 Ей 0

0

0 Б21 0 0 0

0 0

Еп 0 0

0 Е^ 0

0

0 Е21 0 0 0

0 0 Е22 о

0

рекурсивных вызовах, то сложность вычисления матриц Я и С для матрицы размера п не превосходит Ьо^утг13 +о(п") операций умножения элементов матрицы, где Ьа{Р) = пип(р^, „ц)

Для формулировки второго алгоритма вводится новый канонический вид матриц Матрица Н £ рпхп имеет главную часть Е € Рп, если Я - 1Н и Е = ЯJ, где I = ЕЕТ 6 и 3 = ЕТЕ 6 !>„, другими словами, множества нулевых строк у матриц Н и Е совпадают, и все ненулевые столбцы Е содержатся в Я В частности, если Я обратима, то

Е = НеР„

Алгоритм с односторонним разложениел1 (односторонний алгоритм) приводит матрицу к такому каноническому виду Для матрицы Л 6 рпхп вычисляется такая обратимая матрица Л, что НА = Н, при этом Н - это матрица с некоторой главной частью Е € Рп Если А - обратима, то Я = Е и А-1 = ЕТЛ

Пусть матрица Е\ - невырожденная подматрица максимального порядка матрицы Е Тогда, с точностью до перестановок строк и столбцов, матрица Я имеет вид

н =

Алгоритм состоит из 3 шагов Пусть матрица А разбита на четыре квадратных блока Лц, Л12, А21, Л22 Тогда графическое описание каждого шага, с точностью до перестановок, имеет следующий вид

1. Вычислить Д1 Лл Л = Л1, где матрица Л1 выглядит следующим образом

Выполняется рекурсивный вызов алгоритма для левого верхнего блока матрицы Л и составляется левый обратимый сомножитель для матрицы Л, применяющий результат этого вызова к ее левому верхнему блоку Затем он домножается слева на обратимые матрицы так, что После домножения матрицы /?1 на обратимый сомножитель в Л21 на месте столбцов, ненулевых в Ец, появляются нулевые столбцы

Е1

0

Еи А' X

0

0

2 Вычислить Дг Дг-41 = А2, где матрица А2 выглядит следующим образом

Параллельно выполняются

рекурсивные вызовы алгоритма для левого нижнего блока матрицы А1 и правого верхнего блока матрицы Л1, у которого все строки с номерами, равными номерам ненулевых строк в Еп, занулены и составляется левый сомножитель для А1, применяющий результаты этих вызовов к ее соответствующим блокам Затем он домножается на такие обратимые матрицы, что в А^ и в А\2 на месте столбцов, ненулевых в Е12, и в А^ на месте столбцов, ненулевых в £21, появляются нулевые столбцы

Е п 0 X 0 X

0 Е12 X

0

0 Ец X 0 0 X

0

3 Вычислить Дз ДзА2 следующим образом

Ей 0 X 0 0 X

0 Ей 0 X

0

Е 21 X 0 0 X

0 0 0 Е22 X

0

А3 = Я, где матрица А3 выглядит

Выполняется рекурсивный вызов алгоритма для правого нижнего блока матрицы А2, после зануления в нем всех строк, номера которых равны номерам ненулевых блоков матрицы Е21, и составляется левый сомножитель для матрицы А2, применяющий результаты этого вызова к ее правому нижнему блоку Затем он домножается на обратимые матрицы так, что в А22 на месте столбцов, ненулевых в Е22, появляется нулевые столбцы Матрица А3 есть матрица Н (с точностью до перестановок)

Получены верхние оценки сложности этого алгоритма Односторонний алгоритм использует 21 матричное умножение и 4 рекурсивных вызова в общем случае Пусть М(п) = 7-пР + о{пе) -верхняя оценка сложности матричного умножения Тогда сложность обращения матрицы порядка п с помощью одностороннего алгоритма не

превосходит Кз{Р)~1п® + о(п/3) операций умножения элементов матрицы, где К5{0) =

В случае, когда левый верхний блок матрицы невырожден, получен сокращенный вариант одностороннего алгоритма При этом используются 6 матричных умножений и 2 рекурсивных вызова алгоритма Если исходная матрица вырождена, то требуется выполнение 7 матричных умножений и 2 рекурсивных вызовов

Если сокращенный вариант алгоритма с 6 умножениями блоков используется во всех его рекурсивных вызовах, то сложность обращения матриц не превосходит Ь$(13)-/п& +о(п") операций умножения элементов матрицы, где ЬвЦЗ) =

Приведены значения коэффициентов в оценке сложности новых алгоритмов для четырех наиболее известных алгоритмов матричного умножения - стандартного, которому соответствует ¡3 = 3, Штрассена и Штрассена-Винограда, которым соответствует ¡3 — и Копперсмита-Винограда, которому соответствует /? ~ 2,375__

[ Двусторонний алгоритм

Односторонний алгорш м

Коэффициенты в оценке сложности вычисления обратной матрицы

р Ко + Кт Ld +Кт Р Ks Ls

3 13 { й 3 '21 4 1

log27 ш 1 Я bg27 7 в 5

2,375 15,32 3,2 2,375 17 69 1 89

Приведены результаты вычислительных экспериментов с новыми алгоритмами для вычисления обратной матрицы в поле вычетов по 28-битному модулю Среди алгоритмов вычисления обратной матрицы, не имеющих ограничений, лучшим оказался односторонний алгоритм, а алгоритмов вычисления определителя и обратной матрицы - двусторонний алгоритм Остальные алгоритмы проиграли одностороннему алгоритму не менее чем на 30-40% Вторым по скорости оказался двусторонний алгоритм Другие алгоритмы ему проиграли как минимум на 10% В работе продемонстрировано преимущество в скорости двух новых алгоритмов по сравнению с алгоритмами обращения матриц по модулю, реализованных в системах Mathematica 6 01 и Maple 11 Поэтому два новых алгоритма можно использовать в реальных вычислениях

В третьей главе разработан древовидный формат хранения матриц, предназначенный для вычислений с блочно-рекурсивными матричными алгоритмами Он назван форматом QTSM (quadtree of sparse matrices) Для экспериментов с ним реализовано еще два формата - QT(quadtree)H SM(sparse matrix)

Формат кватернарного дерева (QT) основан на идеях работ

Д С Вайза - на дихотомическом рекурсивном делении матриц четного порядка на равные квадратные блоки В результате такого деления образуются четыре равных блока Если матрица имеет порядок 2П, то каждый блок снова делится на 4 подблока, и так далее Наименьшим блоком является блок размера 1x1

Соответствующее этой матрице дерево строится следующим образом Когда все четыре блока матрицы ненулевые, то из корневой вершины исходят четыре ребра Эти ребра нумеруются 0,1,2,3, где первый двоичный разряд числа - это номер блочной строки, второй двоичный разряд - номер блочного столбца Аналогично для подблоков Если некоторый блок нулевой, то соответствующее ему ребро в дереве отсутствует

Для вычислений с матрицами, выполняемых на одном процессоре, исследуется упорядоченный строчно-ориентированный формат ЭМ хранения матриц, позволяющий иметь удобный доступ к строкам и столбцам матрицы Данный формат не предполагает блочную структуру вычислений, и может использоваться для хранения разреженных матриц Новый формат С^ТБМ представляет собой дерево, листом которого может быть матрица любого размера, в том числе и прямоугольная Лист дерева хранится в разреженном строчно-ориентированном формате Для хранения листа годится любой формат хранения, предполагающий представление матрицы в виде двух одномерных массивов

Приведены результаты некоторых вычислительных экспериментов с новым форматом Например, при умножении матриц порядка 512 плотности 0 01 - 1 над 32-битными длинными целыми числами, (5Т8М-алгоритмы либо проигрывали остальным по скорости не более чем на 27%, либо выигрывали Следовательно, их можно использовать без существенных потерь в скорости

Проведены эксперименты с односторонним алгоритмом (см главу 2) обращения матриц порядка 128-2048 по простому 28-битному модулю Сравнивались форматы БМ и (ЗТБМ Эксперименты показали, что для невырожденных матриц с невырожденными диагональными блоками наиболее эффективен формат БМ, а для вырожденных - (ЭТБМ

Сравнение алгоритмов умножения плотных матриц порядка 4096 показало эффективность блочно-рекурсивных процедур, листом которых является стандартная процедура, выполняемая с матрицей некоторого размера Кроме того, такие процедуры позволяют реализовывать быстрые процедуры, использующие внешнюю память Результаты этих экспериментов обосновывают идею построения нового древовидного формата СУГБМ, структура которого может повторять вычислительную структуру быстрых блочно-рекурсивных алгоритмов

В заключении сформулированы основные результаты работы

В работе получены следующие результаты-

• Разработаны блочный алгоритм вычисления присоединенной матрицы и определителя для матриц над коммутативной областью и блочно-рекурсивные алгоритмы вычисления обратной матрицы над полем, которые не имеют ограничений, связанных с вырожденностью ведущих матричных блоков Алгоритмы вычисления обратной матрицы предполагают разбиение матрицы на четыре квадратных блока равных размеров

• Разработаны методы хранения матриц, основанные на блочной рекурсивной дихотомической декомпозиции до подматриц произвольного порядка

• На основе полученных алгоритмов реализован пакет программ на языке Java и проведены вычислительные эксперименты

Публикации автора по теме диссертации:

Статьи в изданиях по перечню ВАК-

1 Зуев М С Пилотируемый алгоритм вычисления присоединенной матрицы и определителя // Вестник Тамб ун-та Сер Естеств и техн науки Тамбов, 2006 Т 11, вып 4 С 550-554

Прочие публикации:

2 Зуев М С Быстрые алгоритмы деления полиномов // Вестник Тамб ун-та Сер Естеств и техн науки Тамбов, 2004 Т 9, вып 1 С 150-152

3 Зуев М С Использование жесткого диска в матричных вычислениях // Вестник Тамб ун-та Сер Естеств и техн науки Тамбов, 2008 Т 13, вып 1 С 121-124

4 Зуев М С Сложность алгоритмов для разреженных полиномиальных матриц // Вестник Тамб ун-та Сер Естеств и техн науки Тамбов, 2007 Т 12, вып 1 С 131

5 Зуев М С О сложности алгоритмов умножения матриц над полиномами // XIV Междунар конф "Проблемы теоретической кибернетики" Тез докл М Изд-во механико-математического факультета МГУ, 2005 С 52

6 Зуев М С Об истории параллельных матричных алгоритмов // Современное математическое образование и проблемы истории и методологии науки Тамбов Изд-во Першина Р В , 2006 С 118-124

7 Зуев М С Пилотируемый алгоритм вычисления присоединенной матрицы в коммутативной области // Труды Математического центра им Н И Лобачевского Т 23 Казань Изд-во Казанского математического общества, 2004 С 51-52

8 Малашонок Г И , Валеев Ю Д , Зуев М С Параллельная компьютерная алгебра Введение Тамбов Изд-во ТГУ им Г Р Державина, 2006

В данной работе автору принадлежит написание параграфа 1 5 и главы 4 В параграфе 1 5 автору принадлежит разработка алгоритмов двустороннего и одностороннего обращения матриц Глава 4 написана автором единолично

9 Малашонок Г И , Валеев Ю Д, Зуев М С Параллельные вычисления на бинарных деревьях в задачах компьютерной алгебры Тамбов Изд-во ТГУ им Г Р Державина, 2006

В данной работе автору принадлежит написание глав 2 и 3 В главе 2 автору принадлежит разработка, программная реализация и проведение экспериментов с алгоритмами умножения матриц, предназначенных для хранения в стандартной записи и в форматах хранения 5М и <3Т В главе 3 автору принадлежит получение перестановочного алгоритма вычисления присоединенной матрицы и определителя

10 Малашонок Г И, Зуев М С О представлении матриц кватернарными деревьями // Вестник Тамб ун-та Сер Естеств и техн науки Тамбов, 2005 Т 10, вып 1 С 98-100 В данной работе автору принадлежит разработка, программная реализация и проведение экспериментов с алгоритмами умножения матриц, предназначенных для хранения в стандартной записи, а также в форматах и (¿Т

Подписано в печать 24 04 2008 г Формат 60 х 48/16 Объем 1,0 п л Тираж 100 экз Заказ № 1355 Бесплатно 392008, г Тамбов, Советская, 190г Издательство ТГУ им Г Р Державина

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

Введение

Глава 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. Некоторые вычислительные эксперименты.

Обзор рассматриваемых задач

Диссертационная работа посвящена разработке эффективных блочно-рекурсивных алгоритмов компьютерной алгебры для матриц над полями и коммутативными областями. Рассматриваются алгоритмы умножения матриц, обращения матриц, вычисления присоединенной матрицы и определителя, решения неопределенных систем линейных уравнений. Предложены новые структуры данных для хранения матриц в памяти компьютера.

Для ускорения вычислений на однопроцессорных машинах и улучшения показателей масштабируемости и локальности параллельных алгоритмов для плотных матриц используются блочные алгоритмы. При этом предлагаются блочно-нерекурсивные алгоритмы (например, в [63] предложен алгоритм обращения матриц, в [53] - алгоритм стандартного умножения матриц, в [72] - алгоритм ЬИ-разложения матриц, в [42] - алгоритм умножения и ЫТ-разложения матриц, и др.) и блочно-рекурсивные алгоритмы. В первых в качестве элементов матрицы рассматриваются блоки некоторого фиксированного размера, обрабатываемые стандартным алгоритмом. Таким образом получаются алгоритмы с одним уровнем рекурсии, либо без рекурсивных вызовов. Вторые рассматривают в качестве элементов матриц блоки некоторого размера (обычно равного половине порядка матрицы), а эти блоки обрабатываются рекурсивно. В отличие от первых, они, как правило, имеют сложность такого же порядка, как и применяемое в них матричное умножение. В данной работе будут рассмотрены блочно-рекурсивные алгоритмы.

Получение эффективных блочно-рекурсивных алгоритмов является важной задачей как численных методов, так и компьютерной алгебры.

Такие алгоритмы могут эффективно использовать запоминающие устройства компьютера: процессорный кэш, оперативную память, жесткий диск при вычислениях с использованием записи данных на диск ("out-of-core", см. [64]) и межпроцессорные связи при параллельных вычислениях на машинах с распределенной памятью. При этом возможно использование быстрых алгоритмов матричного умножения, что уменьшает вычислительную сложность таких алгоритмов. Блочно-рекурсивные алгоритмы могут быть реализованы с использованием древовидных форматов хранения матриц (см. [24, 70]), позволяющих реализовывать однопроцессорные и параллельные алгоритмы, предназначенные как для плотных матриц, так и матриц с неизвестной плотностью, или матриц с большим количеством нулевых блоков.

В работах Ф.Г. Густавсона (F.G. Gustavson, 1997, [43], 2003, [42]) предложен подход к построению эффективных алгоритмов численной линейной алгебры (автор исследует алгоритмы для плотных матриц в системе LAPACK). Быстрые алгоритмы должны оптимально работать с процессорным кэшем. Только так можно добиться максимальной производительности процессора. Лучше всего этому требованию отвечают блочно-рекурсивные алгоритмы. На примере LAPACK показано ускорение на 10-100 % для различных алгоритмов (умножение матриц, LU-разложение, разложение Холецкого). В работе Д.С. Вайза. (D.S. Wise, 2006, [53]) предложен блочный вариант классического алгоритма умножения плотных матриц, который может быть быстрее стандартного варианта этого же алгоритма.

Результаты Ф.Г. Густавсона и Д.С. Вайза могут быть справедливы и для задач компьютерной алгебры.

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

Алгоритмы обращения матриц, вычисления присоединенной матрицы и определителя. Известно несколько блочных алгоритмов вычисления обратной матрицы (см., например, [29, 25, 11, 47, 28, 70] и др.). Шур и Баиачиевич (I. Schur, Т. Banachiewicz), вероятно, впервые получили формулу для вычисления обратной матрицы (см. [31]), определяющую блочно-рекурсивный алгоритм вычисления обратной матрицы:

А ß\1=/F + FBGCF -FBG \ ( Т -TBS \ \С D ) V -GCF G J ~ \ -SCT S + SCTBS ) ' ГДе

F = A'1, G = (D - CFB)-\ S = D~\ Т = (А - BSC)'1. Блок D -С А"1 В называется дополнением Шура (Schur complement) к блоку Д блок A — BD~lC называется дополнением Шура к блоку D. Блоки А и D должны быть квадратными. Формула Вудбери (М. A. Woodbury, 1950, [73]) позволяет свести задачу обращения дополнения Шура для одного квадратного блока, стоящего на главной диагонали, к задаче обращения дополнения Шура для другого блока, стоящего на главной диагонали: (А — BD~lC)~l — А-1 + A-lB(D - СА^В^СА'1.

В качестве быстрого алгоритма вычисления обратной матрицы этот алгоритм был рассмотрен в работе Ф. Штрассена (V. Strassen, 1969, [68]). Кроме того, в этой работе был предложен первый известный быстрый алгоритм умножения матриц и показано, что алгоритм обращения матриц имеет оценку сложности того же порядка, что и предложенное матричное умножение, следовательно, он более эффективен, чем алгоритм Гауссова исключения. Поэтому этот алгоритм вычисления обратной матрицы будем в дальнейшем называть алгоритмом Штрассена.

Основное ограничение этого алгоритма обращения матриц: левый верхний блок (или правый нижний) должен быть обратимым. При этом можно выбрать левый верхний блок произвольного порядка. Заметим, что существуют невырожденные матрицы, все левые угловые блоки которой вырожденные. Примером такой матрицы может служить матрица, у которой на побочной диагонали стоят ненулевые элементы, а все остальные элементы равны нулю. Следовательно, такой алгоритм нельзя использовать в общем случае.

В работе Д. Вини и В. Пана (D. Bini, V. Y. Pan, 1994, [28]) предложена формула А-1 = (АНА)~1АН, определяющая алгоритм вычисления обратной матрицы. Эта формула позволяет найти обратную матрицу для любой невырожденной матрицы над полем характеристики 0 с помощью алгоритма Штрассена, но требует в любом случае двух дополнительных матричных умножений. В работе С. Ватта (S. Watt, 2006, [70]) указано обобщение этого алгоритма на случай конечного поля. Но для этого требуется обращение матрицы над полиномами, требующее существенно большего количества операций. Таким образом, этот алгоритм тоже не всегда можно использовать в реальных вычислениях.

Еще один быстрый алгоритм вычисления обратной матрицы основан на быстром алгоритме LU- (точнее, LUP-) разложения матриц, полученных в работе Дж. Банча и Дж. Хопкрофта (J. Bunch, J. Hopcroft, 1974, [29]). Алгоритм LU-разложения матриц, предложенный в их работе, не имеет ограничений, то есть, находит результат для любых невырожденных матриц. Но этот алгоритм предполагает деление матриц на 2 подблока, а не на 4, и требует поиска ненулевого элемента по строке, поэтому не может быть эффективно реализован с использованием древовидного формата хранения матриц. Известна модификация этого алгоритма, предложенная О. Ибаррой и др. (Ibarra О., Moran S., Hui R., 1982, [47]). Этот алгоритм позволяет найти треугольное (ЬЯР-) разложение любых матриц, в том числе вырожденных, но имеет те же недостатки, что и алгоритм Банча-Хопкрофта.

Таким образом, существующие алгоритмы вычисления обратной матрицы либо требуют поиска ведущих элементов или блоков, и не предполагают разбиения матрицы на четыре равных квадратных блока, либо не гарантируют получения корректного результата для произвольной невырожденной матрицы. Поэтому возникает задача получения алгоритма, обладающего следующими свойствами:

• Алгоритм должен быть блочно-рекурсивным, иметь сложность такого же порядка, что и матричное умножение, и предполагать разбиение матрицы на 4 квадратных блока равных размеров.

• Алгоритм не должен включать процедуры поиска невырожденного ведущего блока (элемента) и перестановок строк и столбцов матрицы.

• Алгоритм должен вычислять результат для вырожденного блока. Например, невырожденную подматрицу максимального порядка и обратную для нее.

• Алгоритм должен быть эффективен в реализации.

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

В работе Г. И. Малашонка (2000, [56]) предложен блочно-рекурсивный алгоритм вычисления присоединенной матрицы и определителя в коммутативных областях со сложностью матричного умножения. Для обратимой матрицы М = ^ ^ ^ ^ блок А должен быть обратимым. Другой вариант этого алгоритма предложен Г. И. Малашонком и А. Г. Акритасом (А. С. Акг^аэ, С. I. МаквсЬопок, 2006, [26]), требует дополнительно обратимости блока В или С, но может быть более предпочтителен для параллельных вычислений.

В главе 1 данной работы рассматривается новый алгоритм вычисления присоединенной матрицы и определителя для матриц над коммутативной областью, основанный на блочно-рекурсивном алгоритме Г. И. Малашонка, см. [11]. Данный алгоритм работает с любыми невырожденными матрицами порядка степени двойки. Если некоторый диагональный минор четного порядка оказался вырожденным, то предлагается алгоритм поиска другого, невырожденного минора. Приведены оценки сложности алгоритма и пример вычисления присоединенной матрицы и определителя для невырожденной матрицы размера 8 х 8 с вырожденными диагональными минорами четного порядка.

Известен рекурсивный алгоритм решения систем линейных уравнений Г. И. Малашонка [11] в коммутативной области, имеющий сложность матричного умножения. Все главные миноры четного порядка должны быть невырожденными. Этот алгоритм также позволяет вычислить присоединенную матрицу и определитель со сложностью такого же порядка, как и у матричного умножения. Но он имеет больший коэффициент при старшей степени в оценке сложности, по сравнению с алгоритмом Г. И. Малашонка, предназначенным для вычисления присоединенной матрицы и определителя и имеет те же вычислительные ограничения. Другие известные алгоритмы решения систем линейных уравнений и вычисления присоединенной матрицы в коммутативной области имеют сложность порядка как минимум п3.

Для определенных плотных квадратных систем линейных уравнений над коммутативной областью, или полем, можно выполнять вычисление присоединенной матрицы и определителя для матрицы коэффициентов, или обратной матрицы. В этом случае получается блочно-рекурсивный алгоритм со сложностью такого же порядка, что и у матричного умножения.

В главе 2 предложен алгоритм решения квадратных неопределенных систем над полем со сложностью матричного умножения. Он основан на новом алгоритме вычисления обратной матрицы и не требует, чтобы диагональные миноры были невырожденными.

Форматы хранения матриц. Реализация структур данных, предназначенных для представления матриц в памяти машины (в дальнейшем мы их будем называть форматами хранения матриц) может дать дополнительные преимущества от использования определенных алгоритмов в некоторых случаях. Например, при вычислениях с разреженными матрицами используются специальные алгоритмы и форматы хранения матриц, позволяющие получить серьезное преимущество по скорости по сравнению с обычным форматом и обычными алгоритмами. В данной работе предполагается построить формат хранения матриц, предназначенный для их обработки блочно-рекурсивными быстрыми алгоритмами и для параллельных вычислений.

Среди известных форматов хранения матриц подходящим может быть древовидный формат, основанный на идее представления матрицы в виде дерева, из каждой вершины которого исходит не более четырех ребер quadtree). Термину "quadtree" ("region quadtree") в данной работе будет соответствовать термин "кватернарное дерево". Это - структура хранения данных, используемая не только для алгебраических вычислений (см. [66]). Согласно [66], практически невозможно определить, когда впервые стал использоваться принцип рекурсивной декомпозиции данных. Формулировка термина "quadtree" как рекурсивного дихотомического разбиения некоторой квадратной "картинки" с линейными размерами, равными степени двойки, появилась в 80-х годах в работах [50, 51]. В этих работах использовался термин "Q-tree". Сам термин "quadtree" в данном контексте впервые появился в работе [46].

Данная схема хранения предназначена для реализации блочных рекурсивных алгоритмов, предполагающих дихотомическое деление матриц на блоки, и будет исследована в данной работе.

Формат хранения матриц в древовидном виде предложен в работах Д. С. Вайза ([24, 38] и др.). В работе [24] показано, что такой формат хранения позволяет реализовать матричные алгоритмы, несущественно проигрывающие стандартным алгоритмам в случае плотных матриц, но существенно их обгоняющие в случае матриц с большим количеством нулей или матриц, имеющих регулярную структуру (например, треугольных или ленточных). В данной работе требуется построить более эффективный формат хранения матриц, предназначенный для параллельных вычислений.

С учетом работ Ф.Г. Густавсона и Д.С. Вайза, а также спецификаций стандарта MPI можно сформулировать ряд требований, которые должны учитываться при разработке нового формата хранения матриц, предназначенного для выполнения расчетов с блочно-рекурсивными алгоритмами на параллельных вычислительных машинах с использованием MPI для передачи блоков матрицы:

Новый формат должен быть ориентирован на использование в блочно-рекурсивных алгоритмах, эффективно использовать память компьютера и предполагать быструю передачу по сети матричных блоков в случае параллельных вычислений. Для этого используется древовидная схема хранения.

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

Формат, предназначенный для задач компьютерной алгебры, должен предполагать эффективное хранение не только числовых матриц, что характерно для численных методов, но и, например, полиномиальных матриц. В случае параллельных вычислений выбор формата хранения матриц влияет на количество пересылаемых данных и задержки перед пересылками.

Формат должен учитывать нулевые элементы матриц. Его не предполагается использовать в вычислениях с сильно разреженными матрицами, так как в этом случае используются специальные алгоритмы и форматы хранения для разреженных матриц, предполагающие их построчное хранение. Но последние могут быть неэффективными для матриц с неизвестной плотностью или плотных матриц. Например, если алгоритмы вычисления обратной матрицы над полем, полученные во второй главе этой работы, в некоторой задаче не работают по сокращенным формулам, то в качестве промежуточных данных будут участвовать блоки, у которых некоторые строки и столбцы занулены. Количество таких строк и столбцов зависит от ранга предыдущих обработанных блоков и в общем случае не поддается оценке. Так как оба полученных во второй главе алгоритма являются блочно-рекурсивными, то для их реализации нужен древовидный формат.

• Так как широко используемый стандарт MPI используется с языками С, С++ и Fortran, а так же, благодаря ИСП РАН, и Java, то новый формат должен допускать программную реализацию с использованием такого языка. Для этого требуется описать, каким образом используются стандартные для этих языков структуры данных при кодировании матрицы. Для быстрой передачи матрицы по сети такой структурой данных должен быть одномерный массив с элементами примитивного типа.

• Как следует из предыдущего пункта, должна существовать возможность интеграции формата хранения матрицы с форматом хранения ее элементов. Это позволит хранить не сами ее элементы, а их коэффициенты примитивного типа, следовательно, повысить скорость передачи блоков по сети.

В главе 3 данной работы построен такой древовидный формат. Для экспериментов с ним реализованы еще два формата - древовидный с размером листа 1 и обычный, построчный. Приводятся результаты экспериментального сравнения этих форматов.

Заключение

В данной работе получены следующие результаты:

• Разработаны блочный алгоритм вычисления присоединенной матрицы и определителя для матриц над коммутативной областью и блочно-рекурсивные алгоритмы вычисления обратной матрицы над полем, которые не имеют ограничений, связанных с вырожденностью ведущих матричных блоков. Алгоритмы вычисления обратной матрицы предполагают разбиение матрицы на четыре квадратных блока равных размеров.

• Разработаны методы хранения матриц, основанные на блочной рекурсивной дихотомической декомпозиции до подматриц произвольного порядка.

• На основе полученных алгоритмов реализован пакет программ на языке Java и проведены вычислительные эксперименты.

1. Беклемишев Д. В. Дополнительные главы линейной алгебры. М.: Наука, 1983.

2. Зуев М. С. Использование жесткого диска в матричных вычислениях // Вестник Тамб. ун-та. Сер. Естеств. и техн. науки. Тамбов, 2008. Т. 13, вып. 1. С. 121-124.

3. Зуев М. С. О сложности алгоритмов умножения матриц над полиномами // XIV Междунар. конф. "Проблемы теоретической кибернетики". Тез. докл. М.: Изд-во механико-математического факультета МГУ, 2005. С. 52.

4. Зуев М. С. Об истории параллельных матричных алгоритмов // Современное математическое образование и проблемы истории и методологии науки. Тамбов: изд-во Першина Р. В., 2006. С. 118-124.

5. Зуев М. С. Пилотируемый алгоритм вычисления присоединенной матрицы и определителя // Вестник Тамб. ун-та. Сер. Естеств. и техн. науки. Тамбов, 2006. Т. И, вып. 4. С. 550-554.

6. Зуев М. С. Пилотируемый алгоритм вычисления присоединенной матрицы в коммутативной области // Труды Математического центра им. Н.И. Лобачевского. Т. 23. Казань: Изд-во Казанского математического общества, 2004. С. 51 52.

7. Зуев М. С. Сложность алгоритмов для разреженных полиномиальных матриц // Вестник Тамб. ун-та. Сер. Естеств. и техн. науки. Тамбов, 2007. Т. 12, вып. 1. С. 131.

8. Зуев М. С., Малашонок Г. И. О сложности алгоритмов умножения полиномиальных матриц // Труды б Междунар. конф. "Дискретные модели в теории управляющих систем". М.: Изд-во ВМиК МГУ, 2004. С. 32-40.

9. Казаков В. Н. Сравнение методов исключения в компьютерной алгебре // Вестник Тамб. ун-та. Сер. Естеств. и техн. науки. Тамбов, 2005. Т. 10, вып. 1. С. 104-106.

10. Карацуба А. А., Офман Ю. П. Умножение многозначных чисел на автоматах // ДАН СССР. 1962. Т. 145. N 2. С. 293-294.

11. Малашонок Г. И. Матричные методы вычислений в коммутативных кольцах. Тамбов: Изд-во ТГУ им. Г. Р. Державина 2002.

12. Малашонок Г. И. Решение системы линейных уравнений в области целостности // Журн. вычисл. матем. и мат. физ. 1983. Т. 23. С. 14971500.

13. Малашонок Г. И., Зуев М. С. О представлении матриц кватернарными деревьями // Вестник Тамб. ун-та. Сер. Естеств. и техн. науки. Тамбов, 2005. Т. 10, вып.1. С. 98-100.

14. Малашонок Г. И., Зуев М. С. Обобщенный алгоритм вычисления обратной матрицы //XI Державинские чтения. Тез. докл. Тамбов: Изд-во ТГУ им. Г.Р.Державина, 2006. С. 48-50.

15. Малашонок Г. И., Аветисян А. И., Валеев Ю. Д., Зуев М. С.

16. Параллельные алгоритмы компьютерной алгебры // Труды Института Системного Программирования / Под ред. В.П. Иванникова. М.: ИСП РАН, 2004. С. 169-180.

17. Малашонок Г. И., Валеев Ю. Д., Зуев М. С. Параллельные вычисления на бинарных деревьях в задачах компьютерной алгебры. Тамбов: Изд-во ТГУ им. Г.Р. Державина, 2006.

18. Малашонок Г. И., Валеев Ю. Д., Зуев М. С. Параллельная компьютерная алгебра. Введение. Тамбов: Изд-во ТГУ им. Г.Р. Державина, 2006.

19. Малашонок Г. И. О решении систем линейных уравнений р-адическим методом // Программирование. 2003. N. 2. С. 8-22.

20. Малашонок Г. И. Сложность быстрого умножения на разреженных структурах / Сб. Алгебра, логика и кибернетика (Материалы международной конференции) / Иркутск, Изд-во ГОУ ВПО «ИГПУ», 2004. С. 175-177.

21. Малашонок Г. И., Сатина Е. С. Быстрое умножение и разреженные структуры // Программирование. 2004. N. 2. С. 1-5.

22. Писсанецки С. Технология разреженных матриц. М.: Мир, 1988.

23. Фаддеев Д. К. Лекции по алгебре. М.: Наука, 1984.

24. Фаддеев Д. К., Фаддеева В. Н. Вычислительные методы линейной алгебры. М.: Физматгиз, 1963.

25. Abdali S. К., Wise D. S. Experiments with quadtree representation of matrices // Proc. ISSAC 88, Lecture Notes in Computer Science 358. Springer Verlag, 1989. P. 96-108.

26. Aho A. V., Hopcroft J. E., Ullman J. D. The design and analysis of computer algorithms. Addison-Wesley, 1976. Имеется перевод: Ахо A., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

27. Akritas A. G., Malaschonok G. I. Computation of the Adjoint Matrix // Lecture Notes in Computer Science 3992. Springer Verlag, 2006. P. 486-489.

28. Bareiss, E. H. Sylvester's identity and multistep integer-preserving Gaussian elimination // Mathematics of Computation. V. 22. 1968. P. 565-578.

29. Bini D., Pan V. Y. Polynomial and matrix computations. Fundamental algorithms. V. 1. Birkhauser, 1994.

30. Bunch J., Hopkroft J. Triangular factorization and inversion by fast matrix multiplication. // Mat. Сотр. V. 28. 1974. P. 231-236.

31. Crout P. D. A short method for evaluating determinants and solving systems of linear equations with real or complex coefficients. // Trans Amer. Inst. Elec. Engng. 1941. V. 60. P. 1235-1240.

32. Dahlquist G., Bjorck A. Numerical methods in scientific computing (Web Draft). Режим доступа: http://www.mai.liu.se/~akbjo/NMbook.html.

33. Demmel J. W., Heath M. Т., Vorst H. A. Parallel Numerical Linear Algebra // Acta Numerica 1993. Cambridge: Cambridge University Press, 1993. P. 111-198.

34. Dongarra J., Foster I., Fox J., et al., ed. Sourcebook of parallel computing. Morgan Kaufmann Publishers, 2003.

35. Doolittle M. H. Method employed in the solution of normal equations and the adjustment of a truangularization. U. S. Coast and Geodesic Survey Report. 1878. P. 115-120.

36. Dumas J.-G. Efficient dot product over word-size finite fields. Rapport de recherche, IMAG-RR1064, Mar. 2004.

37. Dumas J.-G., Giorgi P., Pernet C. FFPACK: finite field linear algebra package // Proc. ISSAC'04. ACM Press, 2004. P. 119-126.

38. Eberly W., Giesbrecht M., Giorgi P., et. al. Solving sparse rational linear systems // Proc. ISSAC'06. ACM Press, 2006. P. 63-70.

39. Frens J. D., Wise D. S. Matrix Inversion using Quadtrees Implemented in Gofer. Technical Report 433. Computer Science Department, Indiana University (1995 May).

40. George A., Liu J. W.-H. Computer Solution of Large Sparse Positive Definite Systems. Prentice-Hall Inc., Englewood Cliffs, New Jersey 07632, 1981. Имеется перевод: Джордж А., Лю Дж. Численное решение больших систем линейных уравнений. М.: Мир, 1984.

41. Giesbrecht М., Jacobson М., Storjohann Jr. and A. Algorithms for large integer matrix problems // Proc. AAECC-14, Lecture Notes in Computer Science. V. 2227. Springer Verlag, 2001. P. 297-307.

42. Golub G. H., Van Loan C. F. Matrix Computations. The Johns Hopkins University Press, 1996.

43. Gustavson F. G. High-performance linear algebra algorithms using new generalized data structures for matrices // IBM Journal for Research and development. January 2003. V. 41. Issue 1. P. 31-55.

44. Gustavson F. G. Recursion leads to automatic variable blocking for dense linear-algebra algorithms // IBM Journal for Research and development. November 1997. V. 41. Issue 6. P. 737-756.

45. Higham N. J. Accuracy and Stability of Numerical Algorithms. SIAM, 1996.

46. Huang X., Pan V. Y. Fast rectangular matrix multiplications and improving parallel matrix computations // Proc. PASCO'97. ACM Press, 1997.

47. Hunter G. M. Efficient computation and data structures for graphics. Ph. D. dissertation. Department of Electrical Engineering and Computer Science, Princeton University, Princeton, NJ, 1978.

48. Ibarra O. H., Moran S., Hui R. A generalization of the fast LUP matrix decomposition algorithm and applications // Journal of algorithms. March 1982. V. 3. N. 1. P. 45-56.

49. Kaltofen E. On Computing Determinants of Matrices Without Divisions // Proc. Internat. Symp. Symbolic Algebraic Comput. ISSAC'92. ACM Press, 1992. P. 342-349.

50. Kaltofen E., Villard G. On the complexity of computing determinants // Proc. Fifth Asian Symposium on Computer Mathematics, ASCM 2001. Extended abstract. P. 13-27.

51. Klinger A. Patterns and search statistics, in Optimizing Methods in Statistics / Ed. by J. S. Rustagi. New York, Academic Press, 1971. P. 303-337.

52. Klinger A., Dyer C. R. Experiments in picture representation using regular decomposition // Computer Graphics and Image Processing. March 1976. V. 5, N. 1. P. 68-105.

53. Krammer B. Algorithmische lineare Algebra fur Polynommatrizen. Regensburger mathematische schriften 32, Regensburg. 2002.

54. Lorton К. P., Wise D. S. Analyzing Block Locality in Morton-Order and Morton-Hybrid Matrices // Proc. MEDEA Workshop'06. New York: ACM Press, 2006. P. 5-12.

55. Malaschonok G. I. Algorithms for the solution of systems of linear equations in commutative rings / Effective Methods in Algebraic Geometry. Ed. by T. Mora and C. Traverso, Progress in Mathematics. V. 94. Birkhauser, 1991. P. 289-298.

56. Malaschonok G. I. Complexity Considerations in Computer Algebra / CASC 2004. Techn. Univ. Munchen, Garching, Germany, 2004. P.325-332.

57. Malaschonok G. I. Effective Matrix Methods in Commutative Domains / Formal Power Series and Algebraic Combinatorics. Springer, 2000. P. 506517.

58. Meuer U., Skinner G., Gunnels J. A collection of codes for sparse matrix computations. CSRD, University of Illinois, 1991.

59. Morton G. M. A computer oriented geodetic data base and a new technique in file sequencing. IBM Ltd., Ottawa, Canada, 1966.

60. Pan V. How to multiply matrices faster. Springer-Verlag, 1984.

61. Pan V. Y. Complexity of computations with matrices and polynomials // SIAM Review. June 1992. V. 34, Issue 2. P. 225-262.

62. Parhami B. Introduction to parallel processing. Algorithms and architectures. Kluwer academic publishers, 2002.

63. Per net C. Implementation of Winograd's algorithm over finite fields using ATLAS level 3 BLAS. Technical report. Labo-ratorie Informatique et Distribution. July 2001. Режим доступа: www-id.imag.fr/Apache/RR/RRO11122FFLAS.ps.gz.

64. Quintana E. S., Quintana G., Sun X., et al. A note on parallel matrix inversion // SIAM J. Sei. Comput. V. 22, Issue 5. 2001. P. 1762-1771.

65. Reiley W. C., van de Geijn R. A. POOCLAPACK: Parallel Out-of-Core Linear Algebra Package. Technical report CS-TR-99-33. Austin, TX, USA: University of Texas at Austin. 1999.

66. Saad Y. Iterative methods for sparse linear systems. SIAM, 2000.

67. Samet H. The design and analysis of spatial data structures. Addison-Wesley publishing company Inc., 1994.

68. Sasaki T., Murao H. Efficient Gaussian elimination method for symbolic determinants and linear systems // ACM. Trans. Math. Software. 1968. V. 8. N. 4. P. 277-289.

69. Strassen V. Gaussian elimination is not optimal // Numerische Mathematik. 1969. V.13. P. 354-356.

70. Watkins D. S. Fundamentals of matrix computations. Second edition. Wiley-Interscience, 2002.

71. Watt S. M. 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. P. 151-155.

72. Winograd S. Some remarks on fast multiplication of polynomials // Complexity of Sequential and Parallel Numerical Algorithms / Ed. by J.F.Traub. New York: Academic Press, 1973. P. 181-196.

73. Wise D. S. Undulant block elimination and integer-preserving matrix inversion // Sei. Comput. Program 33, 1 (1999 January). P. 29-85.

74. Woodbury M. A. Inverting modified matrices // Memorandum report 42. Princeton, Statistical Research Group, 1950.

75. Интернет-ресурс www. net 1 ib. org.

76. Интернет-ресурс www. parallel. ru