НЕКОТОРЫЕ ЗАДАЧИ В МОДУЛЯХ НАД КОММУТАТИВНЫМИ КОЛЬЦАМИ

\begin{matrix}c \\ ◯ \end{matrix} Г.И. Малашонок

Аннотация

G.I.Malaschonok. Some problems in the modules over commutative rings. There is stated a theorem about the solutions of the linear equations systems over a commutative domain that are obtained in the domain and in the field of fractions. Two algorithms are described for rings of principal ideals with zero devisors: an algorithm for computing the characteristic polynomials and an algorithm for computing adjoint matrices. Both algorithms have complexity O(n^{3}) ring operations. There are discussed the using of modular method for solving problems in Euclidean domain.

О РЕШЕНИИ ЛИНЕЙНЫХ СИСТЕМ В КОММУТАТИВНЫХ ОБЛАСТЯХ

Известен уже не один алгоритм решения линейных систем в поле частных коммутативной области (см. обзор в [1] и [2]). Однако нет алгоритма, позволяющего находить решения линейной системы в любой коммутативной области.

В работе [3] описан метод решения линейных систем для случая коммутативного кольца главных идеалов. Сложность этого метода – O(n^{β}) кольцевых мультипликативных операций (такая же, как и сложность матричного умножения). Этод метод позволяет построить наиболее быстрый из известных методов решения систем линейных диофантовых уравнений со сложностью O(n^{3}) бит операций для квазиквадратных систем и O(mn^{β+1}) для прямоугольных n × m систем. Оценки приведены с точностью до логарифмического множителя.

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

В общем случае неизвестно, как строить такую обратимую матрицу. Но для колец главных идеалов в [3] описан метод построения такой обратимой матрицы. Он требует O(n^{β}) операций в кольце.

Теорема 1 Пусть Ax = b – неоднородная система линейных уравнений над коммутативной областью R,A ∈ R^{n×m}, e = (1, 0, …, 0) ∈ R^{m+1}, A^{∗} = (b, A), Ã = (A^{∗T} , e^{T}),

UÃP = T,

где U = ( \begin{matrix}U_{0} & U_{1} \\ x_{0} & x_{1} \\ W_{0} & W_{1} \end{matrix} ), T = ( \begin{matrix}T_{1} \\ t \\ 0 \end{matrix} ),

U – обратимая матрица, T – верхняя треугольная матрица, T_{1} – верхний треугольный блок, диагональные элементы которого не равны нулю, t – последняя ненулевая строка матрицы T, (x_{0}, x_{1}) – строка матрицы U с тем же номером, что и строка t, x_{0} – первый элемент этой строки, P = diag(P_{1}, 1), P_{1} – матрица перестановок. Тогда

(1) Система Ax = b совместна в поле частных кольца R в том и только в том случае, когда в строке t отличен от нуля только один последний элемент.

(2) Если система Ax = b совместна в поле частных, то x = −x_{0}^{−1}x_{1}^{T} – ее решение, а строки матрицы W_{1} образуют базис пространства всех решений однородной системы Ax = 0.

(3) Система Ax = b совместна в кольце R в том и только в том случае, когда x_{0} – обратимый элемент R. При этом x = −x_{0}^{−1}x_{1}^{T}

– решение системы в кольце R, а строки матрицы W_{1} образуют базис модуля всех решений однородной системы Ax = 0.

Доказательство.

Пусть в строке t найдется ненулевой элемент, стоящий не в последнем столбце, тогда ранг матрицы T не уменьшится после вычеркивания последнего столбца. Так как U и P обратимы, то значит и ранг Ã не уменьшается при вычеркивании последнего столбца. Но система с расширенной матрицей Ã^{T}, очевидно, несовместна. Следовательно несовместна система с расширенной матрицей A^{∗}.

Пусть теперь в строке t только последний элемент не равен нулю. Имеем

( \begin{matrix}x_{0} & x_{1} \\ W_{0} & W_{1} \end{matrix} ) · ( \begin{matrix}b^{T} \\ A^{T} \end{matrix} ) = 0.

Очевидно, что первый столбец матрицы U совпадает с последним в матрице T, поэтому x_{0} ≠ 0 и W_{0} = 0. Получим Ax_{1}^{T} = −x_{0}b и AW_{1}^{T} = 0. Строки матрицы W_{1} линейно независимы, так как U обратима и W_{0} = 0. Число строк в матрице T_{1} равно rank(A), поэтому число строк в матрице W_{1} будет m − rank(A). Следовательно строки матрицы W_{1} образуют базис пространства всех решений однородной системы Ax = 0, и x = −x_{0}^{−1}x_{1}^{T} – решение системы Ax = b в поле частных.

Если x_{0} обратимый элемент кольца R, то решение x = −x_{0}^{−1}x_{1}^{T} лежит в кольце R. Предположим теперь, что x_{0} необратим в R и докажем, что система Ax = b несовместна в R.

Пусть y – некоторое решение системы Ax = b в поле частных. Тогда найдется такой вектор g в поле частных, что y^{T} = −x_{0}^{−1}x_{1} + gW_{1}. Запишем вектор g в виде g = g_{0}^{−1}g_{1}, где g_{0} ∈ R, g_{1} ∈ R^{m}, g_{0} необратим или равен 1, когда g ∈ R^{m}. Получим

y^{T} = −x_{0}^{−1}x_{1} + g_{0}^{−1}g_{1}W_{1}.

Предполагая, что y ∈ R^{m}, получим вектор −g_{0}x_{1} + x_{0}g_{1}W_{1} = x_{0}g_{0}y^{T}, все компоненты которого являются кратными x_{0}g_{0}.

Если строку (x_{0}, x_{1}) матрицы U заменить на линейную комбинацию g_{0}(x_{0}, x_{1})−x_{0}g_{1}(W_{0}, W_{1}), то определитель матрицы U умножится на g_{0}. Но все компоненты новой строки кратны x_{0}g_{0}. Следовательно определитель должен делиться на x_{0}g_{0}. Запишем g_{0} det(U) = kx_{0}g_{0}, отсюда g_{0}(det(U) − kx_{0}) = 0, k ∈ R. Но в R нет делителей нуля, и det(U) обратим, поэтому det(U)^{−1}kx_{0} = 1. Следовательно и x_{0} обратим. Мы пришли к противоречию.

Осталось доказать, что когда x_{0} обратим в R, то строки матрицы W_{1} образуют базис модуля всех решений однородной системы Ax = 0 над кольцом R.

Строки матрицы W_{1} образуют базис пространства всех решений однородной системы Ax = 0 в поле частных, поэтому всякое решение однородной системы y имеет вид y^{T} = gW_{1}.

Запишем вектор g в виде g = g_{0}^{−1}g_{1}, где g_{0} ∈ R, g_{1} ∈ R^{m}, получим g_{0}y^{T} = g_{1}W_{1}.

Пусть строки матрицы W_{1} не образуют базис модуля и y – решение системы, которое не может быть получено как линейная комбинация строк W_{1} с коэффициентами из R. Следовательно, хоть одна из компонент вектора g_{1} не делится на g_{0}. Пусть это будет компонента g_{r}.

Если соответствующую компоненте g_{r} строку матрицы W_{1} заменить на g_{1}W_{1}, то определитель матрицы U умножится на g_{r}. Однако g_{1}W_{1} = g_{0}y^{T}, поэтому этот определитель должен делиться на g_{0}: g_{r} det(U) = kg_{0}, k ∈ R. Мы пришли к противоречию, так как det(U) – обратим в R, а g_{r} не делится на g_{0}.

Пример. Пусть 3x + 4y = −2 – диофантовое уравнение. A = (3, 4), b = (−2). Матричное уравнение UÃ = T имеет вид

( \begin{matrix}1 & 1 & 0 \\ 1 & 2 & −1 \\ 0 & 4 & −3 \end{matrix} ) ( \begin{matrix}−2 & 1 \\ 3 & 0 \\ 4 & 0 \end{matrix} ) = ( \begin{matrix}1 & 1 \\ 0 & 1 \\ 0 & 0 \end{matrix} )

Так как элемент в первой строке W [2, 1] = 1, то −(W [2, 2], W [2, 3]) = (−2, 1) – диофантово решение (W [3, 2], W [3, 3]) = (4, −3) – решение уравнения 3x + 4y = 0.

ВЫЧИСЛЕНИЕ ХАРАКТЕРИСТИЧЕСКОГО МНОГОЧЛЕНА НАД КОЛЬЦОМ ГЛАВНЫХ ИДЕАЛОВ

Вычисление характеристического многочлена для матрицы над полем имеет асимптотическую оценку сложности такую же, как и матричное умножение – O(n^{β}). Для матриц над произвольным коммутативным кольцом лучшая сегодня оценка сложности – O(n^{1+β} log n), для коммутативных областей – O(n^{3}) [4].

Рассмотрим случай коммутативного кольца главных идеалов R, которое может не являться областью и содержать делители нуля. Приведем алгоритм вычисления характеристического многочлена для этого случая со сложностью O(n^{3}).

Элементы матрицы, стоящие сразу под элементами главной диагонали, образуют поддиагональ. Квазитреугольной матрицей называют матрицу, у которой все элементы расположенные ниже поддиагонали нулевые. Ее характеристический многочлен вычисляется непосредственно разложением определителя det(λI − A) по правому столбцу. Асимптотическая оценка числа умножений в кольце R при таком вычислении определителя составляет n^{3}/6 [4].

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

Диофантовы матрицы. Пусть R кольцо главных идеалов, в котором существует алгоритм вычисления генератора g идеала (p, q), p, q ∈ R. Будем называть его GI алгоритм:

{g, a, b} = GI(p, q),

(g) = (p, q), ap + bq = g.

Для ненулевой пары α = (p, q) диофантовой матрицей будем называть матрицу

E_{α} = ( \begin{matrix}a & c \\ b & d \end{matrix} ) , где c = −\frac{q}{g} , d = \frac{1 + bc}{a}.

Два главных свойства диофантовой матрицы – это унимодулярность det(E_{α}) = 1 и обращение первого элемента пары в ноль αE_{α} = (0, g), g ≠ 0. Если g не делитель нуля, то диофантова матрица определена однозначно. В этом случае d = \frac{p}{g}. Если g – делитель нуля, то c и d определяются неоднозначно. Число c определяется с точностью до аннулятора g, а число d – с точностью до аннулятора a. Если в кольце ввести порядок и выбирать c и d как минимальные из множеств c + Ann(g) и d + Ann(a), то диофантова матрица будет определена однозначно.

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

Алгоритм вычисления подобной квазитреугольной матрицы. Пусть A = (a_{i,j})

– матрица порядка n над R. [k, s] – обозначение для квадратной подматрицы, стоящей на пересечении строк и столбцов с номерами k, k + 1, …, s. D_{ij} – диофантова матрица для пары (a_{i,j}, a_{i,j+1}), E_{ij} обозначает матрицу, полученную из единичной матрицы порядка n заменой блока [j, j + 1] на D_{ij}, det(E_{ij}) = 1. Тогда в матрице AE_{ij} элемент (ij) равен нулю.

В дальнейшем будем считать, что матрица A, из которой берутся элементы для построения матриц E_{i,j}, не является фиксированной, элементы (a_{i,j}, a_{i,j+1}) всегда берутся из той матрицы, на которую умножается матрица E_{i,j}. Тогда в матрице AE_{k,1}E_{k,2} ⋯ E_{k,k−2} будут нулевыми элементы 1, 2, …, k − 2 строки k, (k = 3, 4, ⋯, n).

Обозначим E_{k} = E_{k,1}E_{k,2} ⋯ E_{k,k−2}, k = n, n − 1, …, 3 и для обратных матриц E_{k}^{−1} = E_{k,k−2}^{−1}E_{k,k−3}^{−1} ⋯ E_{k,1}^{−1}, (k = 3, 4, ⋯, n).

Матрица E_{k}^{−1}AE_{k} будет подобна матрице A, и у нее будут нулевыми элементы 1, 2, …, k − 2 строки k. Действительно, матрица E_{k}^{−1} отличается от единичной только блоком [1, k − 1], и если она умножается слева на матрицу, то в результате не меняются последние строки, начиная со строки k.

Кроме того, если элементы первых k − 1 столбцов матрицы A были нулевые во всех строках, начиная с k +1, то они останутся нулевые в матрице E_{k}^{−1}AE_{k}, так как E_{k} отличается от единичной только блоком [1, k − 1] и при умножении справа переводит каждый из первых k − 1 столбцов в некоторую их линейную комбинацию.

Следовательно, последовательно умножая на матрицы E_{n}, E_{n−1}, …, E_{3} справа и, соответственно, на обратные к ним слева, получим матрицу U^{−1}AU, имеющую квазитреугольный вид и подобную матрице A, U = E_{n} ⋯ E_{4}E_{3}, U^{−1} = E_{3}^{−1} ⋯ E_{n−1}^{−1}E_{n}^{−1}.

Оценка сложности. С каждым нулевым элементом связано вычисление диофантовой матрицы. Следовательно, необходимо n^{2}/2 раз вычислять диофантовы матрицы. Для умножения на матрицу E_{i,j}^{−1} достаточно 4n операций умножения. При умножении на матрицу E_{i,j} достаточно 4i операций умножения, так как элементы ниже строки i нулевые. Поэтому всего получим ∑_{i=3}^{n}(i − 2)(4i + 4n).

Следовательно, общая асимптотическая оценка сложности вычисления квазитреугольной матрицы будет \frac{8}{3}n^{3}.

ВЫЧИСЛЕНИЕ ПРИСОЕДИНЕННОЙ МАТРИЦЫ В КОЛЬЦЕ ГЛАВНЫХ

ИДЕАЛОВ

Вычисление присоединенной матрицы для матрицы над полем, а так же для матрицы над произвольной коммутативной областью, имеет асимптотическую оценку сложности такую же, как и матричное умножение – O(n^{β}) [2].

Рассмотрим случай коммутативного кольца главных идеалов R, которое может не являться областью и содержать делители нуля. Приведем алгоритм вычисления характеристического многочлена, который имеет сложность O(n^{3}). Присоединенную матрицу A^{∗} для невырожденной матрицы A над кольцом R определим уравнением

A^{∗}A = AA^{∗} = det(A) I.

Если R не является областью, то присоединенная матрица может быть определена неоднозначно. Будем называть задачей вычисления присоединенной матрицы задачу вычисления какой-нибудь одной присоединенной матрицы.

Воспользуемся результатом из работы [3]. Для заданной невырожденной матрицы A порядка n вычисление унимодулярной матрицы Q и верхней треугольной матрицы U, таких, что QA = U, можно выполнить за O(n^{β}) операций. Для вычисления определителя матрицы A достаточно перемножить элементы на главной диагонали матрицы U. Обозначим его d = det(A). Легко видеть, что i-тый столбец присоединенной матрицы – это решение системы линейных уравнений Ax = d_{i}, где d_{i} = (0, …, 0, d, 0, …, 0)^{T} – нулевой столбец, у которого i-тый элемент заменен на d, (i = 1, 2, …, n). Следовательно, достаточно решить n систем Ux = Qd_{i}. Так как матрица U – верхняя треугольная, то для вычисления одного решения каждой из этих систем достаточно O(n^{2}) операций. Всего для n систем достаточно O(n^{3}) операций.

ВЫЧИСЛЕНИЯ В МОДУЛЯХ НАД ЕВКЛИДОВЫМИ КОЛЬЦАМИ

Рассмотрим следующие задачи: вычисление определителя, решение системы линейных уравнений (определенной или неопределенной), вычисление присоединенной матрицы, вычисление характеристического многочлена.

Известно, что эти задачи могут быть решены за O(n^{β}) мультипликативных операций, если они решаются для матриц над некоторым полем F.

В этом параграфе мы обсудим применение китайской теоремы об остатках и p-адического подъема для решения этих задач в евклидовых областях Z и F [x].

Согласно китайской теореме об остатках, если m_{1}, …, m_{n} – взаимно простые элементы кольца R, (m_{i}, m_{j}) = 1 для всех i ≠ j, и r_{1}, …, r_{n} – произвольные элементы из R, то существует единственный элемент r, r ≤ m, m = ∏_{i=1}^{n} m_{i}, такой, что r_{i} = r mod m_{i} для всех i, (i = 1, …, n).

Пусть m_{1}, …, m_{n} – простые элементы коммутативной области R, тогда каждый фактор F_{i} = R/m_{i} является полем. Решение в поле F_{i} каждой из рассматриваемых задач имеет сложность O(n^{β}) мультитликативных операций.

Вычисление определителя. Пусть A = (a_{i,j}) – матрица порядка n.

Если R = ℤ, то можно воспользоваться неравенством Адамара det(A)^{2} ≤ ∏_{i=1}^{n} ∑_{j=1}^{n} a_{i,j}^{2} и получить оценку для определителя матрицы | det(A)| ≤ n^{n/2}a^{n}, где a = | max(a_{i,j})|.

Пусть m_{1}, …, m_{n} – простые числа, такие что ∏_{i=1}^{n} m_{i} > 2| det(A)|, тогда достаточно вычислить det(A) в каждом поле R/m_{i}. После этого det(A) можно будет однозначно наити в ℤ. Для восстановления одного числа p по остаткам r_{1}, r_{2}, …, r_{n} достаточно O(n^{2}) операций над целыми числами порядка O(a\sqrt{n}),

p_{j} = r_{1} + (r_{2} − r̃_{1})e_{2}m_{1} + (r_{3} − r̃_{2})e_{3}m_{1}m_{2} + …

+(r_{j} − r̃_{j−1})e_{j}m_{1}m_{2} ⋯ m_{j−1},

где e_{j} = (m_{1}m_{2} ⋯ m_{j−1})^{−1} mod m_{j}, r̃_{i} = p_{i} mod m_{i+1}. В итоге получим p = p_{n}.

Таким образом, можно вычислить определитель за O(n^{β+1}) операций над целыми числами порядка O(a\sqrt{n}). Если используется стандартное умножение целых чисел, то получим всего O(n^{β+1}(log(n) + log(a))^{2}) бит операций.

Если R = F [x], то можно воспользоваться оценкой deg(det A) ≤ ∑_{i=1}^{n} max_{j=1}^{n} deg a_{i,j} ≤ n deg a, где a – элемент матрицы A имеющий наибольшую степень. Если выбрать, например, n deg a модулей первой степени, то всего потребуется O(n^{β+1} deg a) операций в поле F.

Будем считать a константой и пренебрегать логарифмом n. Тогда оценка сложности вычисления определителя в обоих случаях равна O(n^{β+1}).

Решение определенной системы линейных уравнений. Если определитель δ = det A матрицы коэффициентов определенной системы линейных уравнений Ax = b уже найден, то можно умножить его на столбец свободных членов. В результате получим систему Ax = δb, решение которой лежит в кольце R и каждая компонента не превосходит по абсолютной величине наибольшего минора матрицы (A, b). Следовательно оценку можно получить также, как для определителя матрицы, только теперь a - наибольший по соответствующей эвклидовой мере элемент расширенной матрицы (A, b).

Для решения системы в поле F_{i} достаточно O(n^{β}) операций, а количество полей пропорционально n, как в предыдущем случае. Поэтому общая оценка снова будет O(n^{β+1}).

Однако p-адический метод [9] имеет лучшую оценку. Нет необходимости вычислять предворительно det A, достаточно выбрать границу для модуля m = p^{s} > 2(d)^{2}, где d – оценка для максимального минора матрицы (A, b). Всякой дроби, у которой числитель и знаменатель не превосходят по модулю d и знаменатель не кратен p, ставится в соответствие единственный элемент в кольце R/mR. Поэтому достаточно решить систему по модулю m и затем найти соответстующий этому решению вектор в поле частных кольца R.

Будем последовательно искать коэффициенты (p-ичные цифры) в разложении вектора

x = ∑_{i=0}^{s} x_{i}p^{i}

по степеням p. Пусть A_{p}^{−1} – матрица, обратная к A_{p} в поле R/pR и b_{0} = b, тогда

МУЛЬТИПЛИКАТИВНАЯ СЛОЖНОСТЬ АЛГОРИТМОВ

Вычис-  Решение систем  Вычисление Вычисление
ление  линейных уравнений  присоеди- характерис-
опре-  Определенной Неопределенной  ненной  тического
делителя  n × n  n × m  матрицы  многочлена
\frac{R}{F}  n^{β}  n^{β}  \frac{∗}{mn^{β−1}}  n^{β}  n^{3}
R′  n^{β}  n^{β}  mn^{β−1}  n^{3}  n^{3}
\frac{R′′}{F′′}  n^{β+1}  n^{3}  \frac{(m − n + 1)n^{β+1}}{(m − n + 1)n^{3}}  n^{4}  n^{β+1}

x_{0} = A_{p}^{−1}b mod p, b_{i} = (b_{i−1} − Ax_{i−1})/p, x_{i} = A_{p}^{−1}b_{i} mod p, i = 1, 2, …, s − 1.

Если p порядка O(a\sqrt{n}), то s = 2n. Вычисление A_{p}^{−1} можно выполнить за O(n^{β}) операций, умножение матрицы на вектор требует n^{2} операций и это нужно выполнять 4n раз. Восстановление одной дроби имеет сложность порядка O(n^{2}), а количество компонент вектора x равно n. Следовательно общее число операций имеет порядок O(n^{3}). Если переходить к бит операциям, то получим O(n^{3}(log a + log n)^{2}).

Вычисление присоединенной матрицы. Если определитель уже известен, то присоединенную матрицу можно вычислить, решая n определенных систем, как и в параграфе 3. Если применять p-адический метод, то потребуется O(n^{4}).

Решение неопределенной системы линейных уравнений. Пусть Ax = b неопределенная система линейных уравнений, A = (A_{0}, A_{1}) ∈ R^{n×m}, A_{0} – квадратный блок и det(A_{0}) ≠ 0. Решая системы A_{0}_{i} = b_{i}, где b_{i} – столбцы матрицы (A_{1}, b), очевидно, получим базисное множество решений системы Ax = b. Если применять p-адический метод, то число операций будет O(n^{3}(m − n + 1)).

Вычисление характеристического многочлена. Коэффициенты характеристического многочлена – это суммы диагональных миноров матрицы. Поэтому количество модулей и в этом случае пропорционально размерам матрицы. Поэтому, как и при решении определенной системы, получим общую сложность O(n^{β+1}).

ЗАКЛЮЧЕНИЕ

В заключение сведем оценки сложности описанных алгоритмов в одну таблицу. Сюда же добавим оценки сложности алгоритмов для коммутативных областей (см. [2], [4], [6]) и алгоритмов решения систем линейных уравнений и вычисления определителя для колец главных идеалов [7], [3].

В таблице введены следующие обозначения. R – коммутативная область, F – поле частных области R, R′ – кольцо главных идеалов, в котором могут быть делители нуля, R′′ – евклидова область (ℤ или F [x]), F′′ – поле частных R′′. Все оценки приведены с точностью до лога-

рифмических множителей. Для R′′ оценки даны в числе бит операций в случае R′′ = ℤ (операций в поле F при R′′ = F [x]). В средней колонке для областей в числителе стоит сложность решения системы в области [7], а в знаменателе – сложность решения системы в поле частных.

Следует отметить, что библиография, приведенная в этой статье, очень не полная. Возможно историки установят авторство для алгоритмов в евклидовых областях. Например, модулярный способ вычисления определителя известен очень давно (см. например [8]), он остается лучшим и сегодня. Нужно отметить, что в работе [10] приводится алгоритм, у которого ожидаемая сложность уменьшена в log n раз, хотя в наихудшем случае оценка остается такая же. Основная идея состоит в том, что решается несколько раз система линейных уравнений со случайными столбцами свободных членов с помощью p-адического метода. Находится общий знаменатель решений, который является делителем искомого определителя, а затем продолжается стандартный модулярный метод.

ЛИТЕРАТУРА

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

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

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

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

5. Chistov A.L. Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic // Proc. FCT ’85. Springer, LNCS V. 199, 1985. P. 147–150.

6. Malaschonok,G.I. Recursive Method for the Solution of Systems of Linear Equations // Computational Math. V.I. Wiss. & Tech., Berlin 1997. P. 475-480.

7. Malaschonok G.I. Solution of Systems of Linear Diophantine Equations // Computer Algebra in Scientific Computing, CASC’01. Springer, Berlin, 2001. P. 101–115.

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

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

10. Abbott,J. Bronstein,M., Mulders,T. Fast Deterministic Computation of Determinants of Dense Matrices // Proc. of ISSAC’99. Vancouver, ACM Press, 1999. P. 197–204.

Поступила в редакцию 1 июня 2001 г.