Upper bounds on complexity of solving systems of linear equations.

Direct methods for solving systems of linear equations are surveyed here from the viewpoint of the computational complexity. Construction ideas of the most of the algorithms are given in outline.
The paper is divided into two parts.
Sequential methods for solving systems of linear equations are discussed in the first part. It includes Gauss's and Konovaltsev's algorithms, Strassen's algorithm and its modifications, Yun and Gustavson's results for Toeplitz systems, etc.
The second part is devoted to parallel methods for solving systems of linear equations. Parallelizating of Gauss's algorithm, Hyafil and Rung's results for triangular systems, Csanky's algorithm based on Leverrier's method, Hyafil's general result for parallelizating of a straight-line program computing multivariate polynomials, Stone's algorithm for solving of tridiagonal systems are discussed here. The author provides several new bounds. Specificaly, if one can multiply two $(n\times n)$-matrices by straight-line program of complexity $O(n^\alpha)$, then with $p$ processors it is possible to solve an arbitrary system of $m$ linear equations with $n$ variables with complexity being
$$ O\left(\frac{\max(m, n)\min(m, n)^{\alpha-1}}{p}+\min(m, n)\log_2\max(m, n)\right), $$
a triangular system of size $n$ with complexity being
$$ O\left(\frac{n^2}{p}+\frac{n}{p^{1/\alpha}}\log_2^{1-\frac{1}{\alpha}}n+\log_2^2n\right) $$
and to inverse a triangular $(n\times n)$-matrix with complexity being
$$ O\left(\frac{n^\alpha}{p}+\log_2^2n\right). $$