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

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

История

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

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

Обзор

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

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

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

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

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

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

Алгоритм

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

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

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

Анализ

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

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

Примечания

1. Middeke, Jeffrey, Koutschan, 2020.
2. Bareiss, 1968, с. 565—578.
3. Bareiss, 1966.
4. Yap, 2000.

Литература

• 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.