Recursive Method for the Solution of Systems of Linear Equations ^{∗}

Gennadi.I.Malaschonok Tambov State University, 392622 Tambov, Russia e-mail: malaschonok@math-univ.tambov.su

Abstract

New solution method for the systems of linear equations in commutative integral domains is proposed. Its complexity is the same that the complexity of the matrix multiplication.

1 Introduction

One of the first results in the theory of computational complexity is the Strassen discovery of the new algorithm for matrix multiplication [1]. He changed the classical method with the complexity O(n^{3}) for the new algorithm with the complexity O(n^{log_{2} 7}). This method may be used for a matrix in any commutative ring. He used matrix multiplication for the computation of the inverse matrix, of the determinant of a matrix and for the solution of the systems of linear equations over an arbitrary field with the complexity O(n^{log_{2} 7}).

Many authors improved this result. There is known now an algorithm of matrix multiplication with the complexity O(n^{2,37}) (see D.Coppersmith, S.Winograd [2]).

We have another situation with the problems of the solution of systems of linear equations and of the determinant computation in the commutative rings. Dodgson [3] proposed a method for the determinant computation and the solution of systems of linear equations over the ring of integer numbers with the complexity O(n^{3}). During this century this result was improved and generalized for arbitrary commutative integral domain due to Bareis [4] and the author (see [5] – [8]). But the complexity is still O(n^{3}).

There is proposed the new solution method for the systems of linear equations in integral domains. Its complexity is the same that the complexity of the matrix multiplication in integral domain.

∗This paper vas published in: Computational Mathematics (A. Sydow Ed, Proceedings of the 15th IMACS World Congress, Vol. I, Berlin, August 1997 ), Wissenschaft & Technik Verlag, Berlin 1997, 475–480. No part of this materials may be reproduced, stored in retrieval system, or transmitted, in any form without prior permission of the copyright owner.

Let

∑_{j=1}^{m−1} a_{ij}x_{j} = a_{im}, i = 1, 2, …, n

be the system of linear equations with extended coefficients matrix

A = (a_{ij}), i = 1, …, n, j = 1, …, m.

whose coefficients are in integral domain R: A ∈ R^{n×m}.

The solution of such system may be written according to Cramer’s rule

x_{j} = \frac{δ_{jm}^{n} − ∑_{p=n+1}^{m−1} x_{p}δ_{jp}^{n}}{δ^{n}} , j = 1, …, n,

where x_{p}, p = n + 1, …, m, are free variables and δ^{n} ≠ 0. δ^{n} = |a_{ij}|, i = 1, …, n, j = 1, …, n, - denote the corner minors of the matrix A of order n, δ_{ij}^{n} - denote the minors obtained by a substitution of the column j of the matrix A instead of the column i in the minors δ^{n}, i = 1, …, n, j = n + 1, …, m. So we need to construct the algorithm of computation of the minor δ^{n} and the matrix G = ( δ_{ij}^{n} ), i = 1, …, n, j = n + 1, n + 2, …, m.

That means that we must make the reduction of the matrix A to the diagonal form

A → (δ^{n}I_{n}, G).

I_{n} denotes the unit matrix of order n.

2 Recursive Algorithm

For the extended coefficients matrix A we shall denote:

A_{ij}^{k} = ( \begin{matrix}a_{11} & a_{12} & ⋯ & a_{1,k−1} & a_{1j} \\ a_{21} & a_{22} & ⋯ & a_{2,k−1} & a_{2j} \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ a_{k−1,1} & a_{k−1,2} & ⋯ & a_{k−1,k−1} & a_{k−1,j} \\ a_{i1} & a_{i2} & ⋯ & a_{i,k−1} & a_{ij} \end{matrix} )

– the matrix, formed by the surrounding of the submatrix of an order k − 1 in the upper left corner by row i and column j,

a_{ij}^{k} = det A_{ij}^{k},

a_{ij}^{1} = a_{ij}, δ^{0} = 1, δ^{k} = a_{kk}^{k}, δ_{ij}^{k} – the determinant of the matrix, that is received from the matrix A_{kk}^{k} after the substitution of the column i by the column j.

We shall use the minors δ_{ij}^{k} and a_{ij}^{k} for the construction of the matricez

A_{k,c}^{r,l,(p)} = ( \begin{matrix}a_{r+1,k+1}^{p} & a_{r+1,k+2}^{p} & ⋯ & a_{r+1,c}^{p} \\ a_{r+2,k+1}^{p} & a_{r+2,k+2}^{p} & ⋯ & a_{r+2,c}^{p} \\ ⋮ & ⋮ & ... & ⋮ \\ a_{l,k+1}^{p} & a_{l,k+2}^{p} & ⋯ & a_{l,c}^{p} \end{matrix} )

and

G_{k,c}^{r,l,(p)} = ( \begin{matrix}δ_{r+1,k+1}^{p} & δ_{r+1,k+2}^{p} & ⋯ & δ_{r+1,c}^{p} \\ δ_{r+2,k+1}^{p} & δ_{r+2,k+2}^{p} & ⋯ & δ_{r+2,c}^{p} \\ ⋮ & ⋮ & ... & ⋮ \\ δ_{l,k+1}^{p} & δ_{l,k+2}^{p} & ⋯ & δ_{l,c}^{p} \end{matrix} )

G_{k,c}^{r,l,(p)}, A_{k,c}^{r,l,(p)} ∈ R^{(l−r)×(c−k)}, 0 ≤ k < n, k < c ≤ n, 0 ≤ r < m, r < l ≤ m, 1 ≤ p ≤ n.

We shall describe one recursive step, that makes the following reduction of the matrix Ã to the diagonal form

Ã → (δ^{l}I_{l−k}, Ĝ)

where

Ã = A_{k,c}^{k,l,(k+1)}, Ĝ = G_{l,c}^{k,l,(l)}

0 ≤ k < c ≤ m, k < l ≤ n, l < c. Note that if k = 0, l = n and c = m then we get the solution of the system.

We can choose the arbitrary integer number s: k < s < l and write the matrix Ã as the following:

Ã = ( \begin{matrix}A^{1} \\ A^{2} \end{matrix} )

where A^{1} = A_{k,c}^{k,s,(k+1)} - the upper part of the matrix Ã consists of the s − k

rows and A^{2} = A_{k,c}^{s,l,(k+1)} - the lower part of the matrix Ã.

2.1 The first step

As the next recurcive step we make the following reduction of the matrix A^{1} ∈ R^{(s−k)×(c−k)} to the diagonal form

A^{1} → (δ^{s}I_{s−k}, G_{2}^{1}),

where G_{2}^{1} = G_{s,c}^{k,s,(s)}.

2.2 The second step

We write the matrix A^{2} in the following way:

A^{2} = (A_{1}^{2}, A_{2}^{2})

where A_{1}^{2} = A_{k,s}^{s,l,(k+1)} consists of the first s − k columns and A_{2}^{2} = A_{s,c}^{s,l,(k+1)} consists of the last c − s columns of the matrix A^{2}.

The matrix Â_{2}^{2} = A_{s,c}^{s,l,(s+1)} is obtained from the matrix identity (see the proof in the next section):

δ^{k} · Â_{2}^{2} = δ^{s} · A_{2}^{2} − A_{1}^{2} · G_{2}^{1}.

The minors δ^{k} must not equal zero.

2.3 The third step

As the next recurcive step we make the following reduction of the matrix Â_{2}^{2} ∈ R^{(l−s)×(c−s)} to the diagonal form

Â_{2}^{2} → (δ^{l}I_{l−s}, Ĝ_{2′′}^{2}),

where Ĝ_{2′′}^{2} = G_{l,c}^{s,l,(l)}.

2.4 The fourst step

We write the matrix G_{2}^{1} in the following way:

G_{2}^{1} = (G_{2′}^{1}, G_{2′′}^{1})

where G_{2′}^{1} = G_{s,l}^{k,s,(s)} consists of the first l − s columns and G_{2′′}^{1} = G_{l,c}^{k,s,(s)} consists of the last c − l columns of the matrix G_{2}^{1}.

The matrix Ĝ_{2′′}^{1} = G_{l,c}^{k,s,(l)} is obtained from the matrix identity (see the proof in the next section):

δ^{s} · Ĝ_{2′′}^{1} = δ^{l} · G_{2′′}^{1} − G_{2′}^{1} · Ĝ_{2′′}^{2}.

The minors δ^{s} must not equal zero.

So we get

Ĝ = ( Ĝ_{2′′}^{1} ; Ĝ_{2′′}^{2} )

and δ^{l}.

2.5 Representation of the one recursive step

We can represent one recursive step as the following reduction of the matrix Ã:

Ã = ( \begin{matrix}A^{1} \\ A^{2} \end{matrix} ) →_{1} ( \begin{matrix}δ^{s}I_{s−k} & G_{2}^{1} \\ A_{1}^{2} & A_{2}^{2} \end{matrix} ) →_{2} ( \begin{matrix}δ^{s}I_{s−k} & G_{2}^{1} \\ 0 & Â_{2}^{2} \end{matrix} ) →_{3}

→_{3} ( \begin{matrix}δ^{s}I_{s−k} & G_{2′}^{1} & G_{2′′}^{1} \\ 0 & δ^{l}I_{l−s} & Ĝ_{2′′}^{2} \end{matrix} ) →_{4} ( \begin{matrix}δ^{l}I_{s−k} & 0 & Ĝ_{2′′}^{1} \\ 0 & δ^{l}I_{l−s} & Ĝ_{2′′}^{2} \end{matrix} ) = ( δ^{l}I_{l−k} Ĝ)

3 The Proof of the Main Identities

3.1 The first matrix identity

The second step of the algorithm is based on the following matrix identity:

δ^{k}A_{s,c}^{s,l,(s+1)} = δ^{s}A_{s,c}^{s,l,(k+1)} − A_{k,s}^{s,l,(k+1)} · G_{s,c}^{k,s,(s)}.

So we must prove the next identities for the matrix elements

δ^{k}a_{ij}^{s+1} = δ^{s}a_{ij}^{k+1} − ∑_{p=k+1}^{s} a_{ip}^{k+1} · δ_{pj}^{s},

i = s + 1, …, l; j = s + 1, …, c.

Let σ_{ij}^{k} denote the minors that will stand in the place of the minors δ^{k} after the replacement the row i by the row j. An expansion of the determinant a_{ij}^{k+1} according to the column j is the following

a_{ij}^{k+1} = δ^{k}a_{ij} − ∑_{r=1}^{k} σ_{ri}^{k}a_{rj}

Therefore we can write the next matrix identity

( \begin{matrix}1 & 0 & ⋯ & 0 & 0 & ⋯ & 0 & 0 \\ 0 & 1 & ⋯ & 0 & 0 & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ... & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & ⋯ & 0 & 0 & ⋯ & 1 & 0 \\ −σ_{1i}^{k} & −σ_{2i}^{k} & ⋯ & −σ_{ki}^{k} & 0 & ⋯ & 0 & δ^{k} \end{matrix} ) · A_{ij}^{s+1} =

= ( \begin{matrix}a_{11} & a_{12} & ⋯ & a_{1,s} & a_{1j} \\ a_{21} & a_{22} & ⋯ & a_{2,s} & a_{2j} \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ a_{s,1} & a_{s,2} & ⋯ & a_{s,s} & a_{s,j} \\ a_{i1}^{k+1} & a_{i2}^{k+1} & ⋯ & a_{i,s}^{k+1} & a_{ij}^{k+1} \end{matrix} )

Note that a_{ip}^{k+1} = 0 for p ≤ k. Finaly we decompose the determinant of the right matrix according to the last row and write the determinant identity correspondingly to this matrix identity.

3.2 The second matrix identity

The fourth step of the algorithm bases on the matrix identity

δ^{s}G_{l,c}^{k,s,(l)} = δ^{l}G_{l,c}^{k,s,(s)} − G_{s,l}^{k,s,(s)} · G_{l,c}^{s,l,(l)}.

So we must prove the next identities for the matrix elements:

δ^{s}δ_{ij}^{l} = δ^{l}δ_{ij}^{s} − ∑_{p=s+1}^{l} δ_{ip}^{s} · δ_{pj}^{l},

i = k + 1, …, s; j = l + 1, …, c.

Let γ_{j,i}^{s} denote the algebraic adjunct of element a_{j,i} in the matrix A_{s,s}^{s}. An expansion of the determinant δ_{ip}^{s} according to the column i is the following

δ_{ip}^{s} = ∑_{q=1}^{s} γ_{qi}^{s}a_{qp}

Therefore we can write the next matrix identity:

( \begin{matrix}1 & 0 & ⋯ & 0 & 0 & ⋯ & 0 & 0 \\ 0 & 1 & ⋯ & 0 & 0 & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ... & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & ⋯ & 0 & 0 & ⋯ & 1 & 0 \\ γ_{1i}^{s} & γ_{2i}^{s} & ⋯ & γ_{s,i}^{s} & 0 & ⋯ & 0 & 0 \end{matrix} ) A_{ij}^{l+1} =

= ( \begin{matrix}a_{11} & a_{12} & ⋯ & a_{1,l} & a_{1j} \\ a_{21} & a_{22} & ⋯ & a_{2,l} & a_{2j} \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ a_{l,1} & a_{l,2} & ⋯ & a_{l,l} & a_{l,j} \\ δ_{i1}^{s} & δ_{i2}^{s} & ⋯ & δ_{i,l}^{s} & δ_{ij}^{s} \end{matrix} )

Note that δ_{ip}^{s} = 0 for p ≤ s and δ_{ii}^{s} = δ^{s}. So to finish the proof we must decompose the determinant of the right matrix according to the last row and write the determinant identity correspondingly to this matrix identity.

4 Evaluation of Operations Number

Let us have a method for matrix multiplications with the complexity M(n) = O(n^{2+β}), then for multiplication of two matrixes of order l × n and n × c we need M(l × n, n × c) = O(lcn^{β}) operations. Let us denote by S(n, m) the complexity of the recursive algorithm for the matrix A ∈ R^{n×m}.

If in the first recursive step upper submatrix consists of the s rows, 1 ≤ s < n, then

S(n, m) = S(s, m) + M((n − s) × s, s × (m − s))+
+S(n − s, m − s) + M(s × (n − s), (n − s) × (m − n)) + O(nm).

For a matrix with k rows we can choose the arbitrary s : 1 ≤ s ≤ k − 1.

If the process of partition is dichotomous, and the number of rows in the upper and lower submatrixes is the same in every step, then S(2n, m) satisfies the recursive inequality:

S(2n, m) = S(n, m) + M(n × n, n × (m − n)) + S(n, m − n)+
+M(n × n, n × (m − 2n)) + O(nm) ≤ 2S(n, m) + 2O(mn^{β+1}).

So we have

S(2n, m) ≤ nS(2, m) + ∑_{i=0}^{(log_{2} n)−1} O((\frac{n}{2^{i}})^{β+1}m)2^{i+1} =

= nS(2, m) + \frac{2}{1 − 2^{−β}} O((n^{β} − 1)nm)

And finally

S(2n, m) ≤ O(mn^{β+1}).

On the other hand

S(2n, m) > M(n × n, n × (m − n)) = O(mn^{β+1}).

Therefore

S(2n, m) = O(mn^{β+1}).

So the complexity of this algorithm is the same that the complexity of the matrix multiplication. In particular for m = n + 1 we have

S(n, n + 1) = O(n^{2+β})

It means that the solution of the system of linear equations needs (accurate to the constant multiplier) the same number of operations that the multiplication of two matrixes needs.

We can get the exact number of operations, that are necessary for the solution of the system of linear equations of order n × m, in the case when on every step upper submatrix is no less then lower submatrix and the number of rows in upper submatrix is some power of 2.

Let F (s, μ−s, ν) = M((ν−s)×s, s×(μ−s))+M(s×(ν−s), (ν−s)×(μ−ν)), then we obtain S(n, m):

∑_{k=1}^{⌊log_{2} n⌋}(F (2^{k}, n−2^{k}⌊\frac{n}{2^{k}} ⌋, m−2^{k}(⌊\frac{n}{2^{k}} ⌋−1))+ ∑_{i=1}^{⌊n/2^{k}⌋} F (2^{k−1}, 2^{k−1}, m−(i−1)2^{k}))

Let n = 2^{p}. If we use simple matrix multiplications with complexity n^{3} than we obtain

A_{nm} = (6n^{2}m − 4n^{3} − 6nm + 3n^{2} + n)/6,
M_{nm} = (6n^{2}m − 4n^{3} + (6nm − 3n^{2}) log_{2} n − 6nm + 4n)/6,
D_{nm} = ((6nm − 3n^{2}) log_{2} n − 6nm − n^{2} + 6m + 3n − 2)/6.

Here we denote by A_{nm}, M_{nm}, D_{nm} the numbers of additions/subtractions, multiplications and divisions, and take into account that (6nm − 2n^{2} − 6m + 2)/6 divisions in the second step are divisions by δ^{0} = 1, so they do not exist in D_{nm}.

For m=n+1 we obtain

A_{n,n+1} = (2n^{3} + 3n^{2} − 5n)/6,
M_{n,n+1} = (2n^{3} + (3n^{2} + 6n) log_{2} n − 2n)/6,
D_{n,n+1} = (3n^{2} log_{2} n − 7n^{2} + 6n log_{2} n + 3n + 4)/6.

The general quantity of multiplication and division operations is about n^{3}/3.

We can compare these results with one-pass algorithm, that was the best of all known algorithms (see [8]): A_{n,n+1}^{O} = (2n^{3} + 3n^{2} − 5n)/6, M_{n,n+1}^{O} = (n^{3} + 2n^{2} − n − 2)/2, D_{n,n+1}^{O} = (n^{3} − 7n + 6)/6, the general quantity of multiplication and division operations is about 2n^{3}/3.

If we use Strassen’s matrix multiplications with complexity n^{log_{2} 7} than we can obtain for n = 2^{p} the general quantity of multiplication and division operations

MD_{n,m}^{S} = n^{2}(log_{2} n − 5/3) + 7/15n^{log_{2} 7} + (m − n)(n^{2} + 2n log_{2} n − n) + 6/5n−

− ∑_{i=1}^{log_{2} n−1} \frac{n}{2^{i}} (8^{i} − 7^{i})\{⌊\frac{m − n}{2^{i}}⌋ − (\frac{n}{2^{i}} − 2)⌊\frac{m − n − 2^{i+1}⌊(m − n)/2^{i+1}⌋}{2^{i}}⌋\}.

For m = n + 1, n = 2^{p} we get

MD_{n,n+1}^{S} = \frac{7}{15}n^{log_{2} 7} + n^{2}(log_{2} n − \frac{2}{3}) + n(2 log_{2} n + \frac{1}{5}).

5 Example

Let us consider next system over the integer numbers

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

5.1 Reduction of the matrix A^{1} = A_{05}^{02(1)} to the diagonal form

We make the next reduction:

A_{05}^{02(1)} → (δ^{2}I_{2}, G_{25}^{02(2)})

5.1.1

A_{05}^{01(1)} → (δ^{1}I_{1}, G_{15}^{01(1)}) = (3; 1, 1, −1, 4)

5.1.2

δ^{0}A_{15}^{12(2)} = δ^{1}A_{15}^{12(1)} − A_{01}^{12(1)}G_{15}^{01(1)} =
= 3(2, 0, 1, 4) − (1)(1, 1, −1, 4) = (5, −1, 4, 8), δ^{0} ≡ 1.

5.1.3

A_{15}^{12(2)} → (δ^{2}I_{1}, G_{25}^{12(2)}) = (5; −1, 4, 8)

5.1.4

δ^{1}G_{25}^{01(2)} = δ^{2}G_{25}^{01(1)} − G_{12}^{01(1)}G_{25}^{12(2)} =
= 5(1, −1, 4) − (1)(−1, 4, 8) = (6, −9, 12)
G_{25}^{01(2)} = (2, −3, 4)

Finally we obtain

(δ^{2}I_{2}, G_{25}^{02(2)}) = ( \begin{matrix}5 & 0; & 2 & −3 & 4 \\ 0 & 5; & −1 & 4 & 8 \end{matrix} )

5.2 Computation of the matrix Â_{2}^{2} = A_{25}^{24(3)}

δ^{0}A_{25}^{24(3)} = δ^{2}A_{25}^{24(1)} − A_{02}^{24(1)}G_{25}^{02(2)} =

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

= ( \begin{matrix}11 & −4 & −18 \\ −2 & 13 & −9 \end{matrix} )

δ^{0} ≡ 1; A_{25}^{24(3)} = ( \begin{matrix}11 & −4 & −18 \\ −2 & 13 & −9 \end{matrix} )

5.3 Reduction of the matrix A_{2}^{2} = A_{25}^{24(3)} to the diagonal form

We make the next reduction:

A_{25}^{24(3)} → (δ^{4}I_{2} G_{45}^{24(4)})

5.3.1

A_{25}^{23(3)} → (δ^{3}I_{1}, G_{35}^{23(3)}) = (11; −4, −18)

5.3.2

δ^{2}A_{35}^{34(4)} = δ^{3}A_{35}^{34(4)} − A_{23}^{34(3)}G_{35}^{23(3)} =
= 11(13, −9) − (−2)(−4, −18) = (135, −135)
A_{35}^{34(4)} = (27, −27)

5.3.3

A_{35}^{34(4)} → (δ^{4}I_{1}, G_{45}^{34(4)}) = (27, −27)

5.3.4

δ^{3}G_{45}^{23(4)} = δ^{4}G_{45}^{23(3)} − G_{34}^{23(3)}G_{45}^{34(4)} =
= 27(−18) − (−4)(−27) = −594, G_{45}^{23(4)} = (−54)

Finally, in step (3) we obtain

(δ^{4}I_{2}, G_{45}^{24(4)}) = ( \begin{matrix}27 & 0; & −54 \\ 0 & 27; & −27 \end{matrix} )

5.4 Computation of the matrix Ĝ_{2′′}^{1} = G_{45}^{02(4)}

δ^{2}G_{45}^{02(4)} = δ^{4}G_{45}^{02(2)} − G_{24}^{02(2)}G_{45}^{24(4)} =

= 27 ( \begin{matrix}4 \\ 8 \end{matrix} ) − ( \begin{matrix}2 & −3 \\ −1 & 4 \end{matrix} ) ( \begin{matrix}−54 \\ −27 \end{matrix} ) = ( \begin{matrix}135 \\ 270 \end{matrix} )

G_{45}^{02(4)} = ( \begin{matrix}27 \\ 54 \end{matrix} )

The solution of the system is the following:

δ^{4} = 27; G_{45}^{04(4)} = ( \begin{matrix}27 \\ 54 \\ −54 \\ −27 \end{matrix} )

5.5 Representation of the first recursive step

We can represent the first recursive step as the following

A →_{1} ( \begin{matrix}5 & 0 & 2 & −3 & 4 \\ 0 & 5 & −1 & 4 & 8 \\ 0 & 1 & 2 & 0 & −2 \\ 1 & 0 & 0 & 2 & −1 \end{matrix} ) →_{2} ( \begin{matrix}5 & 0 & 2 & −3 & 4 \\ 0 & 5 & −1 & 4 & 8 \\ 0 & 0 & 11 & −4 & −18 \\ 0 & 0 & −2 & 13 & −9 \end{matrix} ) →_{3}

→_{3} ( \begin{matrix}5 & 0 & 2 & −3 & 4 \\ 0 & 5 & −1 & 4 & 8 \\ 0 & 0 & 27 & 0 & −54 \\ 0 & 0 & 0 & 27 & −27 \end{matrix} ) →_{4} ( \begin{matrix}27 & 0 & 0 & 0 & 27 \\ 0 & 27 & 0 & 0 & 54 \\ 0 & 0 & 27 & 0 & −54 \\ 0 & 0 & 0 & 27 & −27 \end{matrix} )

6 Conclusion

The described algorithm for the solution of the systems of linear equations over the integral domain includes the known one-pass method and the method of forward and back-up procedures [8]. If in every recursive step the partition of the matrix is such that the upper submatrix consists only of one row then it is the method of forward and back-up procedures. If the lower submatrix consists only of one row in every step then it is the one-pass method.

If the process of partition is dichotomous and the numbers of rows in the upper and lower submatrixes are equal in every step, then the complexity of the solution has the same order O(n^{2+β}) as the complexity of matrix multiplication.

The computation of the matrix determinant and the computation of the adjugate matrix have the same complexity.

This method may be used in any commutative ring if the corner minors δ^{k}, k = 1, 2, …, n, do not equal zero and are not zero divisors.

References

[1] V. Strassen. Gaussian Elimination is not optimal. Numerische Mathematik, 1969, 13, 354–356.

[2] D. Coppersmith, S. Winograd. in Proc. 19th Annu ACM Symp. on Theory of Comput., 1987, 1–6.

[3] C.L. Dodgson. Condensation of determinants, being a new and brief method for computing their arithmetic values. Proc. Royal Soc. Lond., 1866, A.15, 150–155.

[4] E.N. Bareiss. Sylvester’s identity and multistep integer-preserving Gaussian elimination. Math. Comput., 1968, 22, 565–578.

[5] G.I. Malaschonok. Solution of a system of linear equations in an integral domain. USSR Journal of Computational Mathematics and Mathematical Physics, 1983, 23, 1497–1500.

[6] G.I. Malaschonok. On the solution of a linear equation system over commutative ring. Math. Notes of the Acad. Sci. USSR, 1987, 42, N4, 543–548.

[7] G.I. Malaschonok. A new solution method for linear equation systems over the commutative ring. In Int. Algebraic Conf., Theses on the ring theory, algebras and modules. Novosibirsk, 1989, 82–83.

[8] G.I. Malaschonok. Algorithms for the solution of systems of linear equations in commutative rings. In Effective Methods in Algebraic Geometry, Edited by T. Mora and C. Traverso, Progress in Mathematics 94, Birkhauser, Boston-Basel-Berlin, 1991, 289–298.