БЫСТРЫЙ АЛГОРИТМ ВЫЧИСЛЕНИЯ ПРИСОЕДИНЕННОЙ МАТРИЦЫ ^{∗}

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

Malaschonok G.I. Fast algorithm for computing adjoint matrix. There is suggested new fast method for computing adjoint matrices in commutative domains. The complexity of these methods has the same order as the complexity of matrix multiplication. The evaluation of the complexity and the comparison with the complexity of the matrix multiplication is given

∗Вестник ТГУ, Т.5, N.1, 2000, 142–146.

ВВЕДЕНИЕ

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

Известен метод вычисления присоединенной матрицы в произвольном коммутативном кольце, который требует O(n^{3}\sqrt{n}lognloglogn) операций сложения, вычитания и умножения [1]. Если же в кольце допустима операция сокращения (точного деления), то лучший известный метод для этого случая требует O(n^{3}) операций [2]. В настоящей работе предполагается, что в кольце имеется операция сокращения, и предлагается метод вычисления присоединенной матрицы, требующий, с точностью до константы, такое же количество операций, которое требуется для умножения матриц того же размера.

Рассмотрим разложение на множители

обратной матрицы. Если A = ( \begin{matrix}A & C \\ B & D \end{matrix} )

– обратимая матрица и A – ее обратимый блок, то можно разложить на множители ее обратную матрицу A^{−1}:

A^{−1} = ( \begin{matrix}I & −A^{−1}C \\ 0 & I \end{matrix} ) ( \begin{matrix}I & 0 \\ 0 & (D − BA^{−1}C)^{−1} \end{matrix} )

× ( \begin{matrix}I & 0 \\ −B & I \end{matrix} ) ( \begin{matrix}A^{−1} & 0 \\ 0 & I \end{matrix} ) .  (1)

При этом требуется только две операции умножения и две операции обращения блоков. Если предположить, что для обращения блоков можно снова воспользоваться разложением (1) и этот процесс можно продолжить до блоков второго порядка, то для такого разложения на множители матрицы A^{−1} порядка n = 2^{p} потребуется 2^{p−1} операции обращения блоков второго порядка, а так же по 2^{p−k} операций умножения блоков порядка 2^{k} (k=1,2,…,p-1). Если для умножения матриц воспользоваться алгоритмом Штрассена [3], то для вычисления всех сомножителей матрицы A^{−1} необходимо N = n^{log7} − n/2 мультипликативных операций. В общем случае, если сложность матричного умножения O(n^{α}), то и вычисление множителей обратной матрицы имеет сложность O(n^{α}). Аналогичный подход, позволяющий вычислять присоединенную матрицу, предлагается в данной работе.

ТЕОРЕМЫ О ФАКТОРИЗАЦИИ ПРИСОЕДИНЕННОЙ МАТРИЦЫ

Пусть R – коммутативное кольцо, A = (a_{i,j})

– квадратная матрица порядка n над кольцом R. Обозначим

A_{i,j}^{k} = ( \begin{matrix}a_{1,1} & … & a_{1,k−1} & a_{1,j} \\ … & … & … & … \\ a_{k−1,1} & … & a_{k−1,k−1} & a_{k−1,j} \\ a_{i,1} & … & a_{i,k−1} & a_{i,j} \end{matrix} ) (2)

ее квадратную подматрицу порядка k, полученную окаймлением верхнего левого блока порядка k − 1 строкой i и столбцом j, (i, j > k). Обозначим ее определитель a_{i,j}^{k} = detA_{i,j}^{k}. Угловой минор порядка k обозначим δ_{k} = a_{k,k}^{k}. Определитель матрицы, полученной заменой в верхнем левом блоке A_{k,k}^{k} порядка k столбца i на столбец j, обозначим δ_{k(i,j)}, (1 ≤ i ≤ k, k < j ≤ n).

Введем также матрицы

A_{t}^{(s)} = (a_{i,j}^{s})_{j=s,...,t}^{i=s,...,t} и G_{s}^{(t)} = (δ_{t(i,j)})_{j=t+1,...,n}^{i=s,...,t} размера (t−s+1)×(t−s+1) и (t−s+1)×(n−t) соответственно.

В этих обозначениях детерминантное тождество Сильвестра [4] можно записать так

detA_{t}^{(s)} = δ_{s−1}^{t−s}δ_{t}  (3)

где 1 < s < t ≤ n.

Докажем две главные теоремы о факторизации присоединенной матрицы.

Теорема 1 Пусть квадратная матрица A порядка n над кольцом R разбита на блоки

A = ( \begin{matrix}A & C \\ B & D \end{matrix} ) ,

A – квадратный блок порядка s, (1 < s < n), опpеделитель котоpого, δ_{s}, не является нулем или делителем нуля в R, тогда присоединенная матрица A^{∗} раскладывается на множители

A^{∗} = ( \begin{matrix}δ_{s}^{−1}δ_{n}I & −δ_{s}^{−1}F C \\ 0 & I \end{matrix} ) ( \begin{matrix}I & 0 \\ 0 & G \end{matrix} )

× ( \begin{matrix}I & 0 \\ −B & δ_{s}I \end{matrix} ) ( \begin{matrix}F & 0 \\ 0 & I \end{matrix} ) ,  (4)

где F = A^{∗}, G = δ_{s}^{−n+s+1}A_{n}^{(s+1)∗}, I – единичная матрица и справедливо тождество

A_{n}^{(s+1)} = δ_{s}D − BF C.  (5)

Доказательство: Вычислим последовательно результаты произведения матрицы A на сомножители матрицы (4) справа налево:

A → ( \begin{matrix}δ_{s}I & F C \\ B & D \end{matrix} ) → ( \begin{matrix}δ_{s}I & F C \\ 0 & δ_{s}D − BF C \end{matrix} ) →

→ ( \begin{matrix}δ_{s}I & F C \\ 0 & δ_{n}I \end{matrix} ) → δ_{n}I.

При этом необходимо доказать только тождество (5) и тождество

δ_{s}^{−n+s+1}A_{n}^{(s+1)∗}A_{n}^{(s+1)} = δ_{n}I.  (6)

Так как δ_{s(i,j)} = ∑_{l=1}^{s} a_{l,i}^{∗}a_{l,j}, где a_{l,j}^{∗} обозначает алгебраическое дополнение элемента (l, j) в матрице A_{s,s}^{s}, то F C = A^{∗}C = G_{1}^{(s)}. А так как a_{i,j}^{s+1} = a_{i,j}δ_{s} − ∑_{l=1}^{s} a_{i,l}δ_{s(l,j)}, то A_{n}^{(s+1)} = δ_{s}D − BG_{1}^{(s)} = δ_{s}D − BF C.

Тождество (6) следует из детерминантного тождества Сильвестра (3)

detA_{n}^{(s+1)} = δ_{s}^{n−s−1}δ_{n}.

Теорема 2 Пусть квадратная матрица A_{n}^{(s+1)} порядка n − s, (s > 0, n − s > 2), над кольцом R разбита на блоки

A_{n}^{(s+1)} = ( \begin{matrix}A & C \\ B & D \end{matrix} ) ,

A – квадратный блок порядка t−s, (1 < s < t < n), δ_{s} и δ_{t} не являются нулями или делителями нуля в R, тогда матрица δ_{s}^{−n+s+1}A_{n}^{(s+1)∗} раскладывается на множители

( \begin{matrix}δ_{t}^{−1}δ_{n}I & −δ_{t}^{−1}FC \\ 0 & I \end{matrix} ) ( \begin{matrix}I & 0 \\ 0 & δ_{s}^{−1}G \end{matrix} )

× ( \begin{matrix}I & 0 \\ −B & δ_{t}I \end{matrix} ) ( \begin{matrix}F & 0 \\ 0 & I \end{matrix} ) ,  (7)

где F = δ_{s}^{−t+s+1}A_{t}^{(s+1)∗}, G = δ_{t}^{−n+t+1}A_{n}^{(t+1)∗}, I – единичная матрица и справедливо тождество

A_{n}^{(t+1)} = δ_{s}^{−1}(δ_{t}D − BFC).  (8)

Доказательство: Вычислим последовательно результаты произведения матрицы A_{n}^{(s+1)} на сомножители матрицы (7) справа налево:

A_{n}^{(s+1)} → ( \begin{matrix}δ_{t}I & FC \\ B & D \end{matrix} ) →

( \begin{matrix}δ_{t}I & FC \\ 0 & δ_{t}D − BFC \end{matrix} ) → ( \begin{matrix}δ_{t}I & FC \\ 0 & δ_{n}I \end{matrix} ) → δ_{n}I.

При этом необходимо доказать только тождество (8) и тождества

FA = δ_{t}I  (9)
δ_{t}^{−n+t+1}A_{n}^{(t+1)∗}A_{n}^{(t+1)} = δ_{n}I  (10)

Так как A = A_{t}^{(s+1)}, то (9) следует из тождества Сильвестра

detA_{t}^{(s+1)} = δ_{s}^{t−s−1}δ_{t}.

Тождество (10) следует из тождества Сильвестра

detA_{n}^{(t+1)} = δ_{t}^{n−t−1}δ_{n}.

Перейдем к доказательству тождества (8). Обозначим a_{l,j}^{(s+1)∗} алгебраическое дополнение эле-

мента (l, j) в матрице A_{t}^{(s+1)}, тогда по детерминантному тождеству Сильвестра получим

δ_{s}^{t−s−1}δ_{t(i,j)} = ∑_{l=s+1}^{t} a_{l,i}^{(s+1)∗}a_{l,j}^{s+1}.

Так как F = δ_{s}^{−t+s+1}A_{t}^{(s+1)∗}, а C – блок матрицы A_{n}^{(s+1)}, то из последнего равенства для элементов следует матричное тождество G_{t}^{(s)} = FC.

Раскладывая определитель матрицы A_{i,j}^{s+1} по последнему столбцу, получим

a_{i,j}^{s+1} = a_{i,j}δ_{s} − ∑_{l=1}^{s} a_{l,j}σ_{s(l,j)},  (11)

где σ_{s(l,j)} – определитель матрицы, полученной из A_{s,s}^{s} заменой строки l на строку j. Обозначим

α = (a_{1,j}, a_{2,j}, …, a_{t,j}),
β = (a_{i,1}^{s+1}, a_{i,2}^{s+1}, …, a_{i,t}^{s+1}),
σ = (σ_{s(1,i)}, σ_{s(2,i)}, …, σ_{s(s,i)}, 0, 0, …, 0)

строки из t элементов, тогда в соответствии с (11) получим матричное тождество

( \begin{matrix}I & 0 \\ −σ & δ_{s} \end{matrix} ) · A_{i,j}^{t+1} = ( \begin{matrix}A_{t,t}^{t} & α^{T} \\ β & a_{i,j}^{s+1} \end{matrix} ) .

Запишем соответствующее ему детерминантное тождество, в котором детерминант матрицы, стоящей справа, разложен по последней строке

δ_{s}a_{i,j}^{t+1} = δ_{t}a_{i,j}^{s+1} − ∑_{l=1}^{t} a_{i,l}^{s+1}δ_{s(l,j)}.

В матричном виде это уравнение запишется так

δ_{s}A_{n}^{(t+1)} = δ_{t}D − BG_{t}^{(s)}.

Принимая во внимание, что G_{t}^{(s)} = FC, приходим к тождеству (9).

Замечание 1: В теореме 2 рассмотрен случай, когда порядок матрицы A_{n}^{(s+1)} больше двух. Если же он равен двум, т.е. n = s + 2, то,

очевидно, A_{n}^{(s+1)∗} = ( \begin{matrix}a_{n,n}^{s+1} & −a_{n−1,n}^{s+1} \\ −a_{n,n−1}^{s+1} & a_{n−1,n−1}^{s+1} \end{matrix} ).

Если же n = s + 1, то A_{n}^{(s+1)∗} = 1.

Замечание 2: Определитель δ_{n} в разложении (4) можно найти по тождеству Сильвестра (3)

δ_{n} = δ_{s}^{−n+s+1}detA_{n}^{(s+1)}.

Если же n = s + 2, то δ_{n} = detG.

Аналогично находятся определители δ_{t} и δ_{n} в разложении (7) : δ_{t} = δ_{s}^{−t+s+1}detA_{t}^{(s+1)}, δ_{n} = δ_{t}^{−n+t+1}detA_{n}^{(t+1)}. Если же t = s + 2, то δ_{t} = detF. Если n = t + 2, то δ_{n} = detG.

БИНАРНАЯ ФАКТОРИЗАЦИЯ

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

Будем называть такое разложение присоединенной матрицы бинарной факторизацией.

Пусть n – порядок матрицы A, 2^{h} < n ≤ 2^{h+1} и все миноры δ_{2i}, i = 1, 2, … не являются нулями или делителями нуля в кольце R. По теоремам 1 и 2 будем последовательно вычислять присоединенные матрицы для левых верхних блоков порядка 2, 4, 8, 16, … матрицы A.

1. Для блока второго порядка.

A_{2,2}^{2} = (a_{i,j})_{i,j=1,2}, δ_{2} = det A_{2,2}^{1},

A_{2,2}^{2∗} = ( \begin{matrix}a_{2,2} & −a_{1,2} \\ −a_{2,1} & a_{1,1} \end{matrix} ) .

2. Для блока четвертого порядка.

A_{4,4}^{4∗} = ( \begin{matrix}δ_{2}^{−1}δ_{4}I & −δ_{2}^{−1}F C \\ 0 & I \end{matrix} ) ×

( \begin{matrix}I & 0 \\ 0 & G \end{matrix} ) ( \begin{matrix}I & 0 \\ −B & δ_{2}I \end{matrix} ) ( \begin{matrix}F & 0 \\ 0 & I \end{matrix} ) ,

где F = A_{2,2}^{2∗}, B = (a_{i,j})_{j=1,2}^{i=3,4}, C = (a_{i,j})_{j=3,3}^{i=1,2}, D = (a_{i,j})_{i,j=3,4}, A_{4}^{(3)} = δ_{2}D − BF C = (a_{i,j}^{3})_{i,j=3,4}, G = δ_{2}^{−1}A_{4}^{(3)∗}, δ_{4} = det G. 3. Для блока восьмого порядка.

A_{8,8}^{8∗} = ( \begin{matrix}δ_{4}^{−1}δ_{8}I & −δ_{4}^{−1}F C \\ 0 & I \end{matrix} ) ×

( \begin{matrix}I & 0 \\ 0 & G \end{matrix} ) ( \begin{matrix}I & 0 \\ −B & δ_{4}I \end{matrix} ) ( \begin{matrix}F & 0 \\ 0 & I \end{matrix} ) ,

где F = A_{4,4}^{4∗}, B = (a_{i,j})_{j=1,...,4}^{i=5,...,8}, C =

(a_{i,j})_{j=5,...,8}^{i=1,...,4}, D = (a_{i,j})_{i,j=5,...,8},

G = ( \begin{matrix}δ_{6}^{−1}δ_{8}I & −δ_{6}^{−1}FC \\ 0 & I \end{matrix} ) ×

( \begin{matrix}I & 0 \\ 0 & δ_{4}^{−1}G \end{matrix} ) ( \begin{matrix}I & 0 \\ −B & δ_{6}I \end{matrix} ) ( \begin{matrix}F & 0 \\ 0 & I \end{matrix} ) ,

A_{8}^{(5)} = δ_{4}D − BF C = (a_{i,j}^{5})_{i,j=5,...,8}, F = δ_{4}^{−3}A_{6}^{(5)∗}, δ_{6} = det F, B = (a_{i,j}^{5})_{j=5,6}^{i=7,8}, C = (a_{i,j}^{5})_{j=7,8}^{i=5,6}, D = (a_{i,j}^{5})_{i,j=7,8}, A_{8}^{(7)} = δ_{4}^{−1}(δ_{6}D − BFC) = (a_{i,j}^{7})_{i,j=7,8}, G = δ_{6}^{−1}A_{8}^{(7)∗}, δ_{8} = det G.

ОЦЕНКА СЛОЖНОСТИ

Пусть M (n) — это сложность вычисления (количество мультипликативных операций) для произведения двух матриц порядка n, αn^{β} — асимптотическая оценка M (n), т.е.

lim_{n→∞} M (n)/n^{β} = α.

Тогда сложность вычисления присоединенной матрицы порядка n = 2^{p} с помощью бинарной факторизации будет

C (n) = ∑_{k=0}^{p−2} 6 · 2^{k}M (2^{n−k−1}),

с точностью до членов n^{2}, а асимптотическая оценка для вычисления присоединенной матрицы будет 3αn^{β}/(1 − 2^{1−β}).

Асимптотическая оценка отношения сложности вычисления присоединенной матрицы к сложности умножения двух матриц будет k(β) = lim_{n→∞} \frac{C (n)}{M (n)} = \frac{3}{1−2^{1−β}} . Для стандартного матричного умножения k(3) = 4, а для умножения по методу Штрассена k(log_{2} 7) = 4, 2.

ПРИМЕР

Пусть A матрица восьмого порядка

A = ( \begin{matrix}M & M^{T} \\ M^{T} & M \end{matrix} ) ,

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

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

Будем вычислять последовательно присоединенные матрицы для левых верхних блоков порядка 2, 4, 8 матрицы A в соответствии с алгоритмом, описанным в разделе 3.

1. Для блока второго порядка:

A_{2,2}^{2} = ( \begin{matrix}0 & 2 \\ 1 & −3 \end{matrix} ) , δ_{2} = det A_{2,2}^{2} = −2,

A_{2,2}^{2∗} = ( \begin{matrix}−3 & −2 \\ −1 & 0 \end{matrix} ) .

2. Для блока четвертого порядка:

A_{4,4}^{4∗} = ( \begin{matrix}δ_{2}^{−1}δ_{4}I & −δ_{2}^{−1}F C \\ 0 & I \end{matrix} )

× ( \begin{matrix}I & 0 \\ 0 & G \end{matrix} ) ( \begin{matrix}I & 0 \\ −B & δ_{2}I \end{matrix} ) ( \begin{matrix}F & 0 \\ 0 & I \end{matrix} ) ,

где F = A_{2,2}^{2∗},

B = ( \begin{matrix}3 & 0 \\ −1 & 3 \end{matrix} ) , C = ( \begin{matrix}−2 & 2 \\ 1 & −2 \end{matrix} ) , D =

( \begin{matrix}−3 & 0 \\ −1 & 1 \end{matrix} ) , A_{4}^{(3)} = δ_{2}D − BF C = ( \begin{matrix}−6 & 6 \\ 0 & 2 \end{matrix} ) ,

G = δ_{2}^{−1}A_{4}^{(3)∗} = ( \begin{matrix}−1 & 3 \\ 0 & 3 \end{matrix} ), δ_{4} = δ_{2} det G = 6,

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

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

= ( \begin{matrix}−9 & −12 & 4 & −6 \\ −6 & −6 & 2 & 0 \\ −9 & −12 & 2 & −6 \\ 0 & −6 & 0 & −6 \end{matrix} ) .

3. Для блока восьмого порядка:

A_{8,8}^{8∗} = ( \begin{matrix}δ_{4}^{−1}δ_{8}I & −δ_{4}^{−1}F C \\ 0 & I \end{matrix} ) ×

( \begin{matrix}I & 0 \\ 0 & G \end{matrix} ) ( \begin{matrix}I & 0 \\ −B & δ_{4}I \end{matrix} ) ( \begin{matrix}F & 0 \\ 0 & I \end{matrix} ) =

= ( \begin{matrix}S & S^{T} \\ S^{T} & S \end{matrix} ) ,

где

S = ( \begin{matrix}17640 & 9135 & 10836 & −8946 \\ 7182 & 441 & 4914 & 1575 \\ 1071 & −945 & −1323 & −3654 \\ −10899 & −8190 & −5607 & 14553 \end{matrix} ) ,

F = A_{4,4}^{4∗}, B = C = M^{T} , D = M,

A_{8}^{(5)} = δ_{4}D − BF C =

= ( \begin{matrix}112 & −95 & 111 & 107 \\ 118 & −152 & 12 & 92 \\ −198 & 225 & −171 & −189 \\ 74 & −70 & 24 & 76 \end{matrix} ) ,

G = ( \begin{matrix}δ_{6}^{−1}δ_{8}I & −δ_{6}^{−1}FC \\ 0 & I \end{matrix} ) ×

( \begin{matrix}I & 0 \\ 0 & δ_{4}^{−1}G \end{matrix} ) ( \begin{matrix}I & 0 \\ −B & δ_{6}I \end{matrix} ) ( \begin{matrix}F & 0 \\ 0 & I \end{matrix} ) =

= \frac{1}{6} ( \begin{matrix}17640 & 9135 & 10836 & −8946 \\ 7182 & 441 & 4914 & 1575 \\ 1071 & −945 & −1323 & −3654 \\ −10899 & −8190 & −5607 & 14553 \end{matrix} ) ,

F = δ_{4}^{−1}A_{6}^{(5)∗} = \frac{1}{6} ( \begin{matrix}−152 & 95 \\ −118 & 112 \end{matrix} ),

δ_{6} = δ_{4} det F = −969, B = ( \begin{matrix}−198 & 225 \\ 74 & −70 \end{matrix} ),

C = ( \begin{matrix}111 & 107 \\ 12 & 92 \end{matrix} ), D = ( \begin{matrix}−171 & −189 \\ 24 & 76 \end{matrix} ),

A_{8}^{(7)} = δ_{4}^{−1}(δ_{6}D − BFC) = ( \begin{matrix}14553 & 3654 \\ 5607 & −1323 \end{matrix} ),

G = δ_{6}^{−1}A_{8}^{(7)∗} = \frac{1}{−969} ( \begin{matrix}−1323 & −3654 \\ −5607 & 14553 \end{matrix} ),

δ_{8} = δ_{6} det G = 41013.

ЛИТЕРАТУРА

1. Kaltofen E. On Computing Determinants of Matrices Without Divisions Proc. Internat. Symp. Symbolic Algebraic Comput. ISSAC’92, Wang, ed., ACM Press, 1992. P. 342-349.

2. 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 94, Birkhauser, 1991. P. 289-298.

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

4. Akritas A.G., Akritas E.K., Malaschonok G.I. Various proofs of Sylvester’s (determinant) identity // Mathematics and Computations in Simulation. 1996. V. 42. P. 585-593.

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