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

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

Введение

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

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

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

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

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

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

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

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

Глава 2. Решение систем линейных уравнений в коммутативных кольцах

2.1. Невырожденные системы.

2.2. Вырожденные системы

2.3. Присоединенная функция и построение канонической системы

Глава 3. Решение систем линейных уравнений в коммутативных областях

3.1. Решение системы сведением к факторкольцу.

3.2. Решение системы в коммутативной области путем обратимого приведения к треугольному виду.

•3.3. Решение системы сведением к определенным системам.

3.3.1. Решение системы в поле частных

3.3.2. Вероятностный метод.

3.3.3. Детерминистский метод.5G

Глава 4. Методы кубической сложности в коммутативной области

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

4.2. Метод прямого и обратного хода: А —> Ы —> Q.

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

4.2.2. Прямой ход: А-ь U.

4.2.3. Обратный ход: U —> Q.

4.2.4. Пример

4.3. Метод одного прохода: А Q

4.3.1. Пример

4.4. Обобщенный метод.

4.4.1. Вычислительная схема обобщенного метода.

4.4.2. Алгоритм обобщенного метода.

4.4.3. Пример

4.5. Вычисление определителей, присоединенных и обратных матриц, ядра линейного оператора

4.6. Оценка сложности алгоритмов

4.6.1. Оценка по количесту операций в области Rq.

4.6.2. Оценка алгоритмов в кол вне М[х15х2,. . . xs].

4.6.3. Оценка алгоритмов в кольце Z[xi,x2,. . . xs].

Глава 5. Методы субкубической сложности в коммутативной области 77 5.1. Рекурсивный метод.

5.1.1. Вычислительная схема заключительного этапа.

5.1.2. Вычислительная схема промежуточного этапа.

5.1.-3. Сложность рекурсивного метода.

5.1.4. Пример

5.2. Вычисление присоединенной матрицы.

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

5.2.2. Теоремы о факторизации присоединенной матрицы

5.2.3. Алгоритм

5.2.4. Бинарная факторизация

5.2.5. Оценка сложности.

5.2.6. Пример

Глава 6. Вычисление характеристического полинома в коммутативной области

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

6.2. Квазитреугольная и трехдиагональная матрицы.

6.3. Матричная запись прямого хода.

6.4. Сопряженный прямой хода.

6.5. Разложение Гаусса

6.6. Вычисление подобной квазитреугольной матрицы.

6.7. Вычисление подобной трехдиагоналытой матрицы.

6.8. Оценка сложности

6.9. Пример вычисления характеристического многочлена.

Глава 7. Вычисление субрезультантной последовательности полиномиальных остатков

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

7.2. Вычисление ППО с помощью алгори тма прямого хода

7.3. Дихотомический рекурсивный метод.

7.4. Пример

Глава 8. Кольца главных идеалов

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

8.2. Конструктивные кольца главных идеалов.

8.3. Разложение матрицы в конструктивном кольце главных идеалов

8.4. Субкубические алгоритмы разложения матриц

8.5. Субкубические алгоритмы решения систем

8.6. Вычисление характеристического многочлена.

8.7. Вычисление присоединенной матрицы.

Глава 9. Решение систем в евклидовых областях

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

9.2. Вычислительная модель.

9.3. Стандартный и модулярный метод.16

9.3.1. Общий алгоритм решения.

9.3.2. Стандартная арифметика.

9.3.3. Модулярная арифметика.

9.4. Решение системы р-адичес:ким методом в поле частных.

9.5. Вероятностный метод решения системы в коммутативной области

9.6. Решение системы в евклидовой области р-адическим детерминистским методом.

9.7. Обсуждение результатов.

9.7.1. Оценки сложности решения системы в поле частных Z

9.7.2. Оценки сложности решения системы в Z и F[x]

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

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

Первые работы по компьютерной алгебре появляются в середине прошлого столетия ( см. например [15]) , а первая коллективная монография по компьютерной алгебре вышла двадцать лет назад [55]. В ней дается обзор основных результатов и систематизация главных направлений развития компьютерной алгебры. Эта книга, также как и другие две [59], [42], изданные в конце восьмидесятых годов, были переведены на русский язык. Сегодня уж. изданы десятки книг по компьютерной алгебре и отдельным ее разделам, а книги по приложениям компьютерной алгебры исчисляются сотнями.

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

Основные задачи, которые здесь рассматриваются:

• Решение систем линейных уравнений в поле частных коммутативной области.

• Решение систем линейных уравнений в коммутативных кольцах.

• Вычисление определителей матриц.

• Вычисление обратных и присоединенных матриц.

• Вычислен не характеристического многочлена.

• В ы ч и ('Л е н и е су б р ез у л ьтант н о й по с л едо в ат ел ь н о ст и п о л и н о м и ал ьных о ста'] -ков и наибольшего общего делителя двух многочленов.

Вычислительные-) методы исследуются в четырех классах колец:

1. Коммутативных кольцах (тождества и общие1 подходы)

2. Коммутативных областях (задачи 1-6)

3. Кольцах главных идеалов (задачи 2-5)

4. Евклидовых областях (задачи 1-3)

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

Основная область приложения этих алгоритмов - это системы компьютерной алгебры, такие как Mathematica, Maple, Reduce, Cocoa и др. Эти алгоритмы составляют основу пакетов по линейной алгебре в таких системах и позволяют эффективно решать задачи, которые ставятся в символьной и рациональной арифметике, в кольцах многочленов, дробно-рациональных выражений, в функциональных кольцах.

Такие пакеты находят применение в физике, химии, биологии, экономике, в задачах управления и многих других областях.

Приведем краткий обзор излагаемого материала.

Детерминантные тождества и общий подход к решению систем в коммутативных кольцах

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

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

Решение систем в коммутативной области

В третьей главе приводятся три основных метода решения систем в коммутат и в н о й о б; i асти.

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

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

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

Решение систем в поле частных коммутативной области и близкие задачи

Можно ли применять метод Гаусса для решения системы линейных уравнений!! поле частных коммутативной области? Как показывает пример конечных нолей систему размера п х п можно решить в Zp за у + 0(п2) операций умножения даже используя схему умножения и вычитания метода Гаусса. Столь же успешно в Zp можно применить и любой быстрый метод для решения систем линейных уравнений над полем,

Возьмем другой пример - кольцо Z. Будем рассматривать каждую дробь как пару чисел - числитель и знаменатель. Стандартная схема, метода Гаусса требует ^n'J + 0(n2) операций умножения и |п'}+0(п2) операций вычисления наибольшего общего делителя. Отметим, что отказываться от вычисления на каждом шаге наибольшего общего делителя нельзя, так как это приводит к экспоненциальному росту чисел и экспоненциальной зависимости от п сложности алгоритма. В Z для вычисления наибольшего общего делителя потребуется ^(nlog.p |а|) операций деления, где и - наибольший по модулю коэффициент. В результате сложность метода. Гаусса в Z составит #(н' log2 |а|) мультипликативных операций (операций умножении и деления). Можно оценить сложность в количестве операций над машинными словами определенного размера, предполагая применение стандартной арифметики. Тогда получим сложность 9(пв log2 |а|). Такую же оценку можно получить и в случае кольца F[x] ~ полиномов над полем F.

Ч.Л.Доджсон (C.L.Dodgson, 1866, [61], перевод имеется в [27]), известный также под псевдонимом Лыоис Кэрролл, применял детерминантные тождества, чтобы 'заменить опера,цию деления на прямом ходе метода Гаусса на операцию деления нацело. При этом в конце прямого хода он вычислил миноры, отношение которых дает одно неизвестное системы по правилу Крамера. Для такого прямого хода нужно n3 -f- О (г/г) операций умножения и точного деления и не требуется операций вычисления наибольшего общего делителя чисел. Сложность таких вычислений в мультипликативных операциях над машинными словами составляет 0(пГ) log.j |а|).

Е.Н.Барейс (E.N.Bareiss, 1968. [46]) предложил алгоритм, который использовал такие же детерминантные тождества, что и Ч.Л. Доджсон как во время прямого хода, так и во время обратного хода, то есть дважды применил прямой ход Доджсона и нашел все неизвестные системы за fi//J + 0(?г) операций умножения и деления. При этом во время обратного хода появился несокращенный сомножитель, равный произведению всех диагональных миноров и сход н о й м атр и цы ко э ф ф и ци е нто в.

Идея Доджеона - использовать детерминантные тождества для вычисления миноров исходной матрицы коэффициентов, а затем находить решение как отношение этих миноров, будет развита в четвертой и пятой главе. В четвертой главе излагается метод прямого и обратного хода, имеющий сложность п'5 + 0(тг2) операций, метод одного прохода со сложностью -f 0(п2) и обобщенный метод со сложностью -f О (и2).

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

Методы быстрого матричного умножения, история которых берет свое начало с работы В. Штрассена (V.Strassen, 1969, [101]), лежат в основе многих быстрых алгоритмов над полем. Сегодняшним рекордом считается метод матричного умножения [56], имеющий оценку 0(п2-37()). Будем обозначать сложность алгоритма матричного умножения, который применяется в анализ и р у е м о м а л г о р и т м е, ч е р е з

77>Jj + о{пР), где 7 и Р - постоянные. С уменьшением (3 растет, как правило, числовой коэффициент при старшем члене в оценке сложности анализируемого алгоритма. Важна оценка этого числового коэффициента. В этом введении приведем оценки сложности алгоритмов для быстрого матричного умножения, когда f3 = log.) 5. Это число « 2.322, что меньше, чем 2.376. Поэтому будут охвачены все известные методы матричного умножения.

Сложность приведенного в пятой главе рекурсивного метода решения систем линейных уравнений составляет + 0(п2) операций при стандартном матричном умножении и r/ynJ4 + о(пР) при быстром матричном умножении. Этот алгоритм можно применить и для вычисления определителя.

В этой главе приводится метод вычисления присоединенной матрицы, который требует п3 + 0(п2) операций при стандартном матричном умножении и 27п^ + o(nd) операций при быстром матричном умножении. Лучший известный алгоритм вычисления присоединенной матрицы в произвольном коммутативном кольце имеет сложность 0(n/3+1/3 log' п log logii) [76].

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

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

Для случая произвольного коммутативного кольца лучшими алгоритмами являются алгоритм А.Л.Чистова [52] и улучшенный алгоритм Берковича (Berkowitz), предложенный Дж. Абделаусдом (J.Abdeljaoued, 1997, [37]), у которых число арифметических операций имеет порядок logn) .

В шестой главе приводятся два метода вычисления характеристического полинома в коммутативной области: это трехдиагональный метод со сложностью |п3 + С)(п2) и квазитреугольный метод со сложностью Зп3 + 0(п2) мультипликатиiпых операций. В основе методов лежат детерминантные тождества в коммутативных кольцах.

Матричный метод вычисления субрезультантной последовательности полиномиальных остатков в коммутативной области

Матричный метод вычисления субрезультантной последовательности полиномиальных остатков А.Акритаса (A.G.Akritas. 1988., |41]) имеет сложность 8 max3 (п,т) + О (max2 (п. т)) для полиномов степени п и т.

В седьмой главе приводятся два метода вычисления субрезультантной последовательности полиномиальных остатков : это метод прямого хода со сложностью (п + г/л)3 + 0((п + т)1) и рекурсивный метод со сложностью п + тУ + о((п + т)Р) операций для быстрого матричного умножения.

Матричные методы в кольцах главных идеалов

Для колец главных идеалов известен алгоритм триангуляризации матрицы Дж.Л.Хафнера и К.С.МакКели (J.L.Hafner, K.S.McCurley, 1991, [69]), а также алгоритм Т.Мулдерса и А.Сториохана (T.Mulders, A.Storjoliann, 1998, 2000, [90], [94]) для триангуляризации матрицы и решения системы линейных уравнений со сложностью 0(rnn>j~[) арифметических операций и операций вычисления генератора идеала, порожденного двумя элементами.

В восьмой главе приводятся алгоритмы триангуляризации матрицы, решения системы линейных уравнений и вычисления присоединенной матрицы со сложностью в{тп^~]) арифметических операций и 9{тп) операций вычисления генератора идеала. А также приводится алгоритм вычисления характеристического многочлена, который имеет сложность уп''4-0(п2) арифметических операций и |п2 + 0(п) операций вычисления генератора идеала.

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

Решение систем линейных уравнений в евклидовых областях

Решение систем линейных уравнений в двух евклидовых областях - в кольце целых чисел и в кольце полиномов над полем наиболее часто встречается в приложениях. Отметим, например, применение систем линейных диофан-товых уравнений: это вычисление канонической структуры абеловых групп см. [73] и [47]), использование в целочисленном программировании и диофан-товом анализе [92], применение в химии для составления уравнений реакций [66] и др. Наиболее известные современные алгоритмы решения диофанто-вых систем линейных уравнений - это алгоритмы В.А.Бланкиншипа [49], Р.Т.Грегори и Е.В.Кришнамурти [66], К.С. Илиополоса [73], Дж.Л.Хафнера и К.С'.МакКели [69], М.Гисбрехта [64], Т.Мулдерса и А.Сториохана [91], А.Сториохана [94], Г.Лабана и А.Сториохана [79].

Лучший результат получен в работе [79]. Он имеет сложность 0~(пР~1 тШ(п log Nr (А))). Здесь Nr (Л) = max,- j(\Ahj\), 9{M{t)) ~ сложность умножения двух ^-битных чисел. Для стандартных алгоритмов М(t) = t?, для FFT алгоритмов М(£) = t log t log log t [40], [106]. Для стандартных алгоритмов умножения оценка сложности алгоритма [79] составляет 0~ (пАт log2 Nr (Л)), а для FFT алгоритмов умножения - 0~(r)Prri log Nr (А)).

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

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

В р-адическом методе вычисляется базисное множество точек на плоскости всех рациональных решений системы с помощью р-адического подъема. А затем для получения решений в евклидовой области вычисляются все целые точки на этой плоскости. Оценка сложности р-адического и модулярного алгоритмов для стандартных алгоритмов умножения составляет 0~(n3m log2 Nr(A)), а для быстрых алгоритмов — 0~(n3m log Nr(A)), где А Е Znxm ранга п. Сравнение этих оценок с оценками сложности алгоритма [79] показывает, что для быстрых алгоритмов умножения оценки сложности этих алгоритмов хуже в раз, а для стандартных алгоритмов умножения оценки для них лучше в п раз. Это позволяет считать алгоритм [79] теоретически лучшим, а приведенные в этой главе р-адический и модулярный алгоритмы — практически лучшими.

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

Приложение

В приложении приводится пакет процедур в системе компьютерной алгебры Mathematica — 4.1, разработанный на основе полученных в диссертационной работе алгоритмов. Быстродействие процедур, составляющих пакет, оценивалось путем сравнения с аналогичными процедурами последней версии системы Mathematica. Результаты сравнения, показывающие преимущество новых алгоритмов, представлены в таблице для разных типов матриц.

Схема распределения материала по главам

КОММУТАТИВНЫЕ КОЛЬЦА (1,2)

КОММУТАТИВНЫЕ КОЛЬЦА ГЛАВНЫХ

ОБЛАСТИ ИДЕАЛОВ з, 4, 5, 6, 7) (8)

ЕВКЛИДОВЫ ОБЛАСТИ (9)

Заключение

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

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

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

1. Абрамов С.А. Задачи компьютерной алгебры, связанные с поиском полиномиальных решений линейных дифференциальных и разностных уравнении // Вести. МГУ. 1989. Сер. 15. N 3. С. 56 60.

2. Абрамов С.А. Рациональные решения линейных дифференциальных и разностных уравнений с полиномиальными коэффициентами // Журн. вычисл. матем. и матем. физ. 1989. Т. 29. N 11. С. 1611-1620.

3. Абрамов С.А. Некоторые оценки, связанные с алгоритмом Евклида // Журн. вычисл. матем. и матем. физ. 1979. Т. 19. С. 756-760.

4. Ван дер Варден B.J1. Алгебра. М.: Наука, 1979.

5. Гатмахер Ф.Р. Теория матриц. М.: Наука, 1968.

6. Гердт В.П., Григорьев Д.Ю. Алгоритмы, системы и применения компьютерной алгебры i В кн.: Компьютерная алгебра. Символьные и алгебраические вычисления. Под.ред. Б.Бухбергера, Дж.Коллинза, Р.Лооса. М.: МИР, 1986. С. 373-383.

7. Григорьев Д.Ю. Разложение многочленов над конечным полем и решение систем алгебраических уравнений / Зап. научи, семин. ЛОМИ АН СССР. 1984. Т. 137. С. 20-79.

8. Григорьев Д.Ю. Сложность разрешения теории первого порядка алгебраически замкнутых полей // Изв. АН СССР. Сер. мат. 1986. Т. 50. N 5. С, 1106-1120.

9. Григорьев Д.Ю., Чистов A.JI. Быстрое разложение многочленов на неприводимые и решение систем алгебраических уравнений // Докл. АН СССР. 1984. Т. 275. N 6. С. 1302-1306.

10. Елизаров В.П. Условия совместности систем линейных уравнений над кольцами // Фундаментальная и прикладная математика, 2000. Т. 6. N 3. С. 777-788.

11. Каткова М.А., Малашонок Г.И. О сложности рекурсивного метода решения линейных систем над коммутативными кольцами / II Держа-винские чтения. Тамбов, 1996. С. 16-17.

12. Клейнер Г.Б. С) системах линейных уравнении над коммутативными кольцами ,7 УМН. 1973. Т. 28. Вып. 6. С. 211-212.

13. Кнут Д.Е. Искусство программирования на ЭВМ. Т. 2. Получисленные алгоритмы. М.: МИР. 1977.

14. Латышев В.Н. Комбинаторная теория колец. Стандартные базисы. М.: Изд-во МГУ, 1988.

15. Люстерник Л.А., Абрамов А.А., Шестаков В.И., Шура-Бура

16. М.Р. Решение математических задач на автоматических цифровых машинах. М.: Изд-во АН СССР, 1952.

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

18. Малашонок Г.И. Система линейных уравнений над коммутативным кольцом. Препринт 114. Львов, Физ.-мех. ин-т АН УССР, 1986.

19. Малашонок Г.И. О решении системы линейных уравнений над коммутативным кольцом // Мат. заметки. 1987. Т. 42. N. 4. С. 543-548.

20. Малашонок Г.И. Обобщенный метод решения линейных уравнений над областью целостности / I Державинские чтения. Тамбов, 1995. С. 3334.

21. Малашонок Г.И. Алгоритмы вычисления определителей в коммутативных кольцах // Дискретная математика. 1995. Т. 7. N. 4. С. 68-76

22. Малашонок Г.И. Рекурсивный метод решения линейных систем над коммутативными кольцами / II Державинские чтения. Тамбов, 1996. С.17-18.

23. Малашонок Г.И. A computation of the characteristic polynomial of an endomorphisni of a free module , Записки научных семинаров ПОМИ.1999. Т. 258. С. 101-114.

24. Малашонок Г.И. Быстрый алгоритм вычисления присоединенной матрицы /7 Вестник Тамбов, ун-та, Сер. Естеств. и технич. науки. 2000. Т. 5. N. 1. С. 142-146

25. Малашонок Г.И. Решение систем линейных уравнений в коммутативных областях /7 Вестник Тамбов, ун-та. Сер. Естеств. и технич. науки.2000. Т. 5. N. 1. С. 147-154.

26. Малашонок Г.И. Решение систем линейных диофаитовых уравнений ,// Вестник Тамбов, ун-та. Сер. Естеств. и технич. науки. 2000. Т. 5. N. 5. С. 620-627.

27. Малашонок Г.И. Неко горые задачи в модулях над коммутативными кольцами. // Вестник Тамбов, ун-та. Сер. Естеств. и технич. науки.2001. Т. 6. N. 3. С. 320-326.

28. Малашонок Г.И. Матричные методы вычислений в коммутативных кольцах. Монография. Тамбов: Изд-во ТРУ, 2002. 214 с.

29. Мальцев А.И. Основы линейной алгебры. М.: Наука, 1970.

30. Михалев А.В., Панкратьев Е.В. Компьютерная алгебра. Вычисления в дифференциальной и разностной алгебре. М.: Изд-во МГУ, 1989.

31. Нечаев А.А. Цикловые типы линейных подстановок над конечными коммутативными кольцами // Мат. сб. 1993. Т.184. N. 3. С. 21-56.

32. Панкратьев Е.В. Компьютерная алгебра. Факторизация многочленов. М.: Изд-во МГУ, 1988.

33. Чистов А.Л. Алгоритм полиномиальной сложности для разложения многочленов и нахождения компонент многообразия в субэкепоненци-альное время /' Зап. научн. семин. ЛОМИ АН СССР. 1984. Т.137. С. 124188.

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

35. Фрумким М.А. Применение модулярной арифметики к построению алгоритмов решения систем линейных уравнений // Докл. АН СССР. 1976. Т. 229. N. 5. С. 1067 1070.

36. Abbott J., Bronstein М., Mulders Т. Fast Deterministic Computation of Determinants of Dense Matrices / Proceedings of ISSAC'99. Vancouver, ACM Press, 1999. P. 197-204.

37. Abdeljaoued J. Algoritlimes rapides pour le calcul clu polynomecaracteristique. These de lTJniversite de Franclie-Comte, 1997.

38. Abdeljaoued J. Berkowitz Algorithm, Maple and computing the characteristic polynomial in an arbitrary commutative ring // Computer Algebra MapleTech. V. 4. N. 3. Birkhauser Boston 1997.

39. Abdeljaoued J., Malaschonok G.I. Efficient Algorithms for Computing the Characteristic Polynomial in a Domain // J. of Pure and Appl. Algebra. 2001. V. 156. I. 2-3. P. 127-145.

40. Abramov S.A. A Note oil the Number of Division Steps in the Euclidean Algorithm. SIGSAM Bulletin, V.34. N. 4. Issue 134, December 2000. P. 1-2.

41. Aho A.V., Hopcroff J.E. and Ullman J.D. The design and Analysis of Computer Algorithms. Acldison-Wesley, 1974. Имеется перевод: Ахо A., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: МИР, 1979.

42. Akritas A.G. A new method for computing polynomial greatest common divisors and polynomial remainder sequences // Numerishe Mathematik. 1988. V. 52. P. 119-127.

43. Akritas A.G. Elements of Computer Algebra with Applications. J. Wiley Interscience, New York, 1989.Имеется перевод: Акритас А. Основы компьютерной алгебры с приложениями. М., Мир, 1994.

44. Akritas A.G., Akritas Е.К., Malaschonok G.I. Various proofs of Sylvester's (determinant) identity // Mathematics and Computer in Simulations. 1996. V. 42. N. 4-6. P. 585-593.

45. Akritas A.G., Akritas E.K., Malaschonok G.I. Matrix computation of subresultant polynomial remainder sequences in integral domain // Reliable Computing. 1995. V. 1. N. 4. P. 375-381.

46. Akritas A.G., Malaschonok G.I. Fast, Matrix Computation of Subresultant Polynomial Remainder Sequences / Computer Algebra in Scientific Computing. Springer, 2000. P. 5-16.

47. Bareiss E.N. Sylvester's identity and multistep integer-preserving Gaussian elimination // Math. Comput. 1968. V.22. P. 565-578.

48. Cannon J. and Havas G. Algorithms for groups // Australian Computer Journal. 1992. V. 24. N. 2. P. 51 58.

49. Bareiss E.N. Computational solutions of matrix problems over an integral domain // J. Inst. Maths Applies. 1972. V. 10. P. 68-104.

50. Blankinship W.A. Algorithni288, solution of simultaneous linear diophantine equations // Communications of the ACM. 1966. V. 9 N. 7. P. 514.

51. Brown W.S. The Subresultant PRS Algorithm // ACM TOMS 4. 1978. P. 237-249.

52. Cayley A. A Memoir on the Theory of Matrices. Philosophical Transactions, 1858.

53. Chistov A.L. Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic // Proc. FCT '85. Springer Lecture Notes in Computer Science, 1985. V. 199. P. 147-150.

54. Cohen H. A course in computational algebraic number theory. Graduate Texts un Maths, V. 138. Springer Verlag, 1993.

55. Collins G.E. and Encarnacion M.J. Efficient rational number reconstruction /'/ Journal of Symbolic Computation. 1995. V. 20. P. 287297.

56. Coppersmith D. and Winograd S. Matrix multiplication via arithmetic progressions /'/ Journal of Symbolic Computation. 1990. V. 9. P. 251-280.

57. Cramer G. Introduction a l'analyse des lignes courbes algebrigues. Gen., 1750.

58. Csanky L. Fast parallel inversion algorithms // SIAM J. Comput. 1976. V. 5. N. 4. P. 618-623.

59. Dixon J. Exact solution of linear equations using p-adic expansions // Numer. Math. 1982. V. 40. P. 137-141.

60. Dodgson C.L. Condensation of determinants, being a new and brief method for computing their arithmetic values // Proc. Royal Soc. Lond. 1866. V. A.15. P. 150-155.

61. Durand E. Solutions numeriques des equations algebriques. Tome II. Masson к Co Editeurs, Paris, 1961.

62. Geddes K.O., Czapor S.R., Labahn G. Algorithms for computer algebra. Ivluwer, Boston, MA, 1992.

63. Giesbrecht M. Efficient parallel solution of sparse system of linear diophantine equations. / M. Hitz and E. Ivaltofen editors, Second Int. Symp. oil Parallel Symbolic Computation: PASCO'97. ACM Press, 1997. P. Ы0.

64. Giesbrecht, M., Lobo A., Saunders B.D. Certifying inconsistency of sparse linear system. // Proc. ISSAC'98, 1998. P. 113-119.

65. Gregory R.T., Krishnamurthy E.V. Methods and Applications of Error-Free Computation. Berlin, 1984.

66. Grigoriev, D., Karpinski M., Singer M. Computational Complexity of Sparse Rational Interpolation // SIAM J. Comput. 1994. V. 23. N. 1. P. 1-11.

67. Habicht W. Eine Verallgemeinerung des Sturmschen Wurzelzahlverfahrens // Commentarii Mathematici Helvetica. 1948. V. 21. P. 99-116.

68. Hafner J.L. and McCurley K.S. Asymptotically Fast Triangularization of Matrices over Rings // Siam Journal of Computation. 1991. V. 20, N. 6. P.1068-1083.

69. Hurt M.F.,Waid C.A. A generalized inverse wicli give all the integral solutions to a system of linear equations / SIAM J. Appl. Math. 1970.1. V. 10. P. 547-550.

70. Huang X., Pan V.Y. Fast rectangula matrix multiplications and improving parallel matrix computations / Proc. PASCO'97. ACM Press, 1997. P. 11-23.

71. Iliopoulos C.S. Worst-case complexity bounds on algorithms for computing the canonical stracture of finite abelian groups and Hennite ancl Smith normal forms of an integer matrix /7 SIAM J. of Computing. 1989. V. 18. N. 4. P. 658-669.

72. Iliopoulos C.S. Worst-case complexity bounds on algorithms for computing the canonical stracture of infinite abelian groups and solving systems of linear diophantine equations // SIAM J. of Computing. 1989. V. 18. N. 4. P. 670678.

73. Jacobi C.G.L. Uebcr die Bildung und die Eigenschaften der Determinanten / De formatione et proprietatibus Determinantum. Edited by Stakel. 1841.

74. Kaltofen E., Pan. V. Processor efficient parallel solution of linear systems over an abstract field. / Proc. SPAA'91 3rd Ann. ACM Symp. Parallel Algor. Architecture, New-York. N.Y.: ACM Press, 1991. P. 180-191.

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

76. Kondrat'eva M.V., Levin A.V., Mikhalev A.V., Pankrat'ev

77. E.V. Differential and difference dimension polynomials. Kluwer Academic Publisher, 1999. 422 p.

78. Kowalewski G. Einfiirung in die Determinantentheorie. New York: Chelsea, 1948.

79. Labahn G., Storjohann A. Asimptoticallv fast computation of Hermite normal forms of integer matrices. // Proc. ISSAC'96, ACM Press, 1996, P. 259-266.

80. Levin A.V., Kondrat'eva M.V., Mikhalev A.V., Pankrat'ev E.V.

81. Computation of dimensional polynomials // International J. of Algebra and Computation. 1992. V. 2. N. 2. P. 117-137.

82. Le Verrier U.J.J. Sur les variations seculaires des elements elliptiques des sept planetcs principales : Mercure, Venus, La Terre, Mars, Jupiter, Saturne et Uranus ' J. Math. Pures Appli. 1840. V. 4. P. 220-254.

83. Malaschonok G.I. A new solution method for linear equation systems over the commutative ring. / Int. Algebraic Conf. Theses on the ring theory, algebras and modules. Novosibirsk, Aug. 21-26, 1989. P. 82.

84. 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. Traverse, Progress in Mathematics. V. 94. Birkhauser, 1991. P. 289-298.

85. Malaschonok G.I. On the solution of systems of linear equations. /' COCOA-IV, Computational Commutative Algebra. Abstracts. Genova, May 29-June 2, 1995. P. 32.

86. Malaschonok G.I. Recursive method for solution of systems of linear equations / New computer technologies on control systems. Pereslavl-Zalessky, August 13-19, 1996. P. 42.

87. Malaschonok G.I. Gaussian Elimination is not Optimal in Commutative Ring / Int. Algebraic conf. dedicated to the memory of D.K.Faddeev. Abstracts. St.Peterburg, June 24-30, 1997. P. 85-86.

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

89. Malaschonok G.I. Solution of Systems of Linear Diophantine Equations / Computer Algebra in Scientific Computing. CASC 2001. Springer, 2001. P. 401-415.

90. Mulders Т., Storjohann A. Fast Algorithms for Linear Algebra Modulo N. / Algorithms ESA '98. LNCS 1461. 1998. P. 139-150

91. Mulders Т., Storjohann A. Diophantine Linear System Solving / Proceedings of ISSAC'99. Vancouver, ACM Press, 1999. P. 181-188.

92. Newman N. Intergal Matrices. Academic Press, 1972.

93. Preparata F.P., Sarwate D.V. An improved parallel processor bound in fast matrix inversion // Inf. Proc. Letters. 1978. V. 7. N. 3. P. 148-150.

94. Storjohann A. Algorithms for Matrix Canonical Forms, Ph. D. Thesis. Swiss Federal Inst, of Technology, Zurich, 2000.

95. Smith H.J.S. On system of linear indeterminate equations and congruences // Phil. Trans. Royal Soc. London. 1861. V. A151. P. 293-326.

96. Smith H.J.S. On the arithmetical invariants of a rectangular matrix // of which the constituents are integral numbers, Proc. London. Math. Soc. 1873. V. 4. P. 236-349.

97. Schonhage A., Strassen V. Sclmelle Multiplikation grosser Zalilen // Computing. 1971. V. 7. P. 281-292.

98. Schonhage A. Sclmelle Bereclmung von Kettenbruchentwicklungen // Acta Informali< a. 1971. V. 1. P. 139-144.

99. Schonhage A. Unitare Transformationen grober Matrzen. // Mum. Math. 1973. V. 20. P. 409-4171.

100. Schonhage A. Asymptotically fast algorithms for the numerical multiplication and division of polynomials with complex coefficients // Lect. Notes Comput. Sci. 1982. V.144. P. 3-15.

101. Strassen V. Gaussian Elimination, is not optimal // Numerische Mathematik. 1969. V.13. P. 354-356.

102. Sasaki Т., Murao H. Efficient Gaussian elimination method for symbolic determinants and linear systems // A.C.M. Trans. Math. Software. 1968. V. 8. N. 4. P. 277-289.

103. Sylvester J.J. On a theory of the syzygetic: relations of two rational integral functions, comprising an application to the theory of Sturm's functions, and that of the greatest common measure // Philoshophical Transactions. 1853. V. 143. P. 407-548.

104. Sylvester J.J. On a the relation between the minor determinants of linearly equivalent quadratic functions // Philoshophical Magazine. 1851. V. 1. Fourth Series. P. 295- 305.

105. Van Vleck E.B. On the determination of a series of Sturm's functions by the calculation of a single determinant // Annals of Mathematics. 1899-1900. V. 1. Second Series. 1-13.

106. Von zur Gatlien J. and Gerhard J. Modern Computer Algebra. Cambridge University Press, 1999.

107. Wang P.S. A p-aclic algorithm for univariate partial factors / Proc. SYMSAC'81. ACM Press, 1981. P. 212-217.

108. Waugh F.V., Dwyer P.S. Compact computation of the inverse of a matrix // Annals of Mathemaical Statistic. 1945. V. 16. P. 259 271.

109. Wiedemann D. Solving sparse linear equations over finite fields // IEEE Trans. Inf. Theory. 1986. IT. 32. P. 54-62.

110. Wolfram S. The Mathematica book/'/ 4th ed. Cambridge University Press, 1999. 1470 p.