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

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

История

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

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

Обзор

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

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

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

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

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

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

Алгоритм

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

• Входные данные: M — $n\times n$ матрица
  в предположении, что все ведущие главные миноры $[M]_{k,k}$ не нулевые.
• Положим $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_{k, k} содержит ведущий главный минор $[M]_{k,k}$,
  значение $M_{n,n}$ содержит определитель исходной матрицы M.

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

Анализ

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

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

Литература

• 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. — .
• Erwin H. Bareiss. Multistep integer-preserving Gaussian elimination. — 1966. (Содержит ясное описание последовательности операций)
• Chee Keng Yap. Fundamental Problems of Algorithmic Algebra // Oxford University Press. — 2000.