Верхние оценки сложности решения систем линейных уравнений

Статья носит обзорный характер и посвящена прямым (точным) методам решения систем линейных уравнений, которые рассматриваются с точки зрения их вычислительной сложности. Для большинства алгоритмов приводятся в общих чертах идеи их построения. Статья состоит из двух частей. В первой части рассматриваются методы последовательного решения систем линейных уравнений. Сюда вошли алгоритмы Гаусса Коновальцева, алгоритм Штрассена и его модификации, результаты Юна и Густавсона для теплицевых систем и др. Вторая часть посвящена параллельному решению систем линейных уравнений. Здесь рассматриваются распараллеливание алгоритма Гаусса, результаты Яфиля и Кунга по оценке сложности параллельного решения треугольных систем, результаты Ксанки, основанные на распараллеливании метода Леверье, общий результат Яфиля о распараллеливании неветвящихся программ вычисления многочленов, алгоритм Стоуна для параллельного решения трехдиагоналышх систем. Приводятся несколько новых оценок. В частности, если умножение пары $(n\times n)$-матриц возможно последовательно при помощи не ветвящейся программы со сложностью $O(n^\alpha)$, то решение произвольной системы $m$ линейных уравнений с $n$ неизвестными на $p$ процессорах возможно со сложностью
$$ O\left(\frac{\max(m, n)\min(m, n)^{\alpha-1}}{p}+\min(m, n)\log_2\max(m, n)\right), $$
а решение треугольной системы размера $n$ возможно со сложностью
$$ O\left(\frac{n^2}{p}+\frac{n}{p^{1/\alpha}}\log_2^{1-\frac{1}{\alpha}}n+\log_2^2n\right). $$