Блочные символьные матричные алгоритмы тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Зуев, Михаил Сергеевич

• Зуев, Михаил Сергеевич
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Зуев, Михаил Сергеевич

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

Введение

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

Список литературы диссертационного исследования кандидат физико-математических наук Зуев, Михаил Сергеевич, 2007 год

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