Upper bounds on the complexity of solving systems of linear equations

The article is of the nature of a survey and is devoted to direct (exact) methods of solving systems of linear equations examined from the point of view of their computational complexity. The construction of most of the algorithms is outlined. The paper consists of two parts. Series methods of solving systems of linear equations are examined in the first part. It includes the algorithms of Gauss and of Konoval'tsev, Strassen's algorithm and its modifications, the YunGustavson results for Toeplitz systems, etc. The second part is devoted to parallel methods of solving systems of linear equations. Examined here are the parallelization of the Gauss algorithm, the results of Hyafil and Kung on complexity estimate of the parallel solution of triangular systems, Csanky's results based on the parallelization of Leverrier's method, Hyabil's general result on the parallelization of a straight-line program for computing polynomials, Stone's algorithm for the parallel solving of tridiagonal systems. Several new bounds are derived. In particular, if a pair of (n×n) -matrices can be multiplied sequentially by a straight-line program of complexity O(n^d), then it is possible to solve an arbitrary system of m linear equations in n unknowns on p processors with the complexity $$0\left( {\frac{{max(m, n)min(m, n)^{\alpha - 1} }}{p} + min(m, n)log_2 max(m, n)} \right),$$ , and to solve a triangular system of sizen with the complexity $$0\left( {\frac{{n^2 }}{p} + \frac{n}{{p^{1/\alpha } }}log_2^{1 - \tfrac{1}{\alpha }} n + log_2^2 n} \right).$$