Алгоритм Барейса

Алгоритм Барейса — алгоритм вычисления определителя или приведения к ступенчатому виду матрицы с целыми элементами с помощью исключительно целочисленной арифметики. Назван именем Э. Барейса. Любое деление, выполняемое по алгоритму, гарантирует точное деление (без остатка). Метод может быть использован также для вычисления определителя матрицы с (приблизительными) вещественными элементами, что исключает ошибки округления, за исключением ошибок, уже присутствующих во входных данных.

ИсторияПравить

Общий алгоритм Барейса отличается от одноимённого алгоритма для обращения матриц Тёплица.

В некоторых испаноязычных странах алгоритм известен также как алгоритм Барейса — Монтанте, поскольку Рене Марио Монтанте Пардо, профессор автономного университета штата Нуэво Леон в Мексике, популяризовал метод среди студентов.

ОбзорПравить

Определение определителя использует только операции умножения, сложения и вычитания. Очевидно, что определитель будет целым, если все элементы матрицы целые. Однако фактическое вычисление определителя, исходя чисто из определения или используя формулу Лейбница, непрактично, поскольку требует $O(n!)$$O(n!)$  операций.

Метод Гаусса имеет сложность $O(n^3)$$O(n^{3})$ , но использует деление, которое приводит к ошибкам округления в случае реализации с помощью арифметики с плавающей запятой.

Ошибки округления^[en] можно избежать, если все числа хранить как дроби вместо чисел с плавающей запятой. Однако размер каждого элемента растёт экспоненциально в зависимости от числа строк.

Барейс поставил вопрос проведения исключений в целых числах, сохраняя при этом величину промежуточных коэффициентов достаточно маленькой. Предложено два алгоритма:

1. Алгоритм без деления — осуществляет сведение матрицы к треугольному виду вообще без операции деления.
2. Алгоритм без остатков — использует деление для уменьшения промежуточных значений, но, вследствие тождества Сильвестера^[en], преобразование остаётся целым (деление имеет нулевой остаток).

Для полноты Барейс предложил также методы исключений без умножения, но с дробями.

АлгоритмПравить

Вычислительная структура этого алгоритма представляет собой простой тройной цикл, как и в обычном методе Гаусса. Однако в этом случае матрица модифицируется так, что каждый элемент $M_{k,k}$$M_{k,k}$  содержит ведущий главный минор [M]_{k, k}. Правильность алгоритма легко показывается индукцией по k.

• Входные данные: M — $n\times <!--\; \times \; -->n$$n\times n$  матрица
  в предположении, что все ведущие главные миноры $[M{]}_{k,k}$$[M]_{k,k}$  не нулевые.
• Положим $M_{0,0}=1$$M_{0,0}=1$ 
• Для всех k от 1 до n-1:
  • Для всех i от k+1 до n:
    • Для всех j от k+1 до n:
      • Положим $M_{i,j}=\frac{M_{i,j}{M}_{k,k}-<!--\; -\; -->M_{i,k}{M}_{k,j}}{M_{k-<!--\; -\; -->1,k-<!--\; -\; -->1}}$$M_{i,j}={\frac {M_{i,j}M_{k,k}-M_{i,k}M_{k,j}}{M_{k-1,k-1}}}$ 
• Выходные данные: Матрица изменена на месте^[en],
  каждый элемент M_{k, k} содержит ведущий главный минор $[M{]}_{k,k}$$[M]_{k,k}$ ,
  значение $M_{n,n}$$M_{n,n}$  содержит определитель исходной матрицы M.

Если предположение о неравенству нулю главных миноров окажется неверным, то есть $M_{k-<!--\; -\; -->1,k-<!--\; -\; -->1}=0$$M_{k-1,k-1}=0$ , а некоторые $M_{i,k-<!--\; -\; -->1}\ne <!--\; \ne \; -->0(i=k,\dots <!--\; \dots \; -->,n)$$M_{i,k-1}\neq 0(i=k,\dots ,n)$ , то мы можем переставить строки k-1 и i местами, сменив знак конечного значения.

АнализПравить

Во время выполнения алгоритма Барейса любое вычисленное целое является определителем подматрицы входной матрицы. Это позволяет с помощью неравенства Адамара ограничить размер целых чисел. В остальном алгоритм Барейса можно рассматривать как вариант метода Гаусса, который требует фактически того же числа арифметических операций.

Отсюда следует, что для $n\times <!--\; \times \; -->n$$n\times n$  матрицы с максимальным (абсолютным) значением $2^L$$2^{L}$  для каждого элемента алгоритм Барейса работает за O(n³) элементарных операций с ограничением $O(n^{\frac{n}{2}}{2}^{nL})$$O(n^{\tfrac {n}{2}}2^{nL})$  на абсолютную величину промежуточных значений. Вычислительная сложность алгоритма тогда составляет $O(n^5{L}^2(\log <!--\; \; -->(n{)}^2+L^2))$$O(n^{5}L^{2}(\log(n)^{2}+L^{2}))$  при использовании элементарной арифметики или $O(n^{4}L(\log <!--\; \; -->(n)+L)\log <!--\; \; -->(log(n)+L)))$$O(n^{4}L(\log(n)+L)\log(log(n)+L)))$  при использовании быстрого умножения^[en].

ЛитератураПравить

• Middeke J., Jeffrey D.J., Koutschan C. Common Factors in Fraction-Free Matrix Decompositions // Math.Comput.Sci. — 2020. — doi:10.1007/s11786-020-00495-9.
• Erwin H. Bareiss. Sylvester's Identity and multistep integer-preserving Gaussian elimination // Mathematics of Computation. — 1968. — Т. 22, вып. 103. — С. 565—578. — doi:10.2307/2004533. — JSTOR 2004533.
• Erwin H. Bareiss. Multistep integer-preserving Gaussian elimination. — 1966. (Содержит ясное описание последовательности операций)
• Chee Keng Yap. Fundamental Problems of Algorithmic Algebra // Oxford University Press. — 2000.