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

История

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

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

Обзор

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

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

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

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

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

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

Алгоритм

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

Если предположение о неравенству нулю главных миноров окажется неверным, то есть ${\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 ³ ) элементарных операций с ограничением ${\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)))}$ при использовании .

Примечания

Литература

• Middeke J., Jeffrey D.J., Koutschan C. Common Factors in Fraction-Free Matrix Decompositions // Math.Comput.Sci. — 2020. — doi : .
• Erwin H. Bareiss. // Mathematics of Computation. — 1968. — Т. 22 , вып. 103 . — С. 565—578 . — doi : . — JSTOR .
• Erwin H. Bareiss. . — 1966. (Содержит ясное описание последовательности операций)
• Chee Keng Yap. Fundamental Problems of Algorithmic Algebra // Oxford University Press. — 2000.