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

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

История

Алгоритм был первоначально анонсирован Джеком Эдмондсом в 1966 году и опубликован в 1967 году. [1] Общий алгоритм Барейсса отличается от алгоритма Барейсса для матриц Теплица .

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

Обзор

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

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

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

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

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

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

Алгоритм

Структура программы этого алгоритма представляет собой простой тройной цикл, как и в стандартном методе исключения Гаусса. Однако в этом случае матрица модифицируется так, что каждая запись M _k,k содержит ведущий главный минор [ M ] _k,k . Корректность алгоритма легко показать индукцией по k .

• Входные данные: M — n -квадратная матрица.
  предполагая, что все его ведущие главные миноры [ M ] _k,k не равны нулю.
• Пусть M _0,0 = 1 (Примечание: M _0,0 — специальная переменная)
• Для 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} ≠ 0 ( i = k ,..., n ), то мы можем поменять местами k −1-ю строку с i -й строкой и поменяйте знак окончательного ответа.

Анализ

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

Отсюда следует, что для матрицы размера n × n максимального (абсолютного) значения 2 ^л для каждой записи алгоритм Барейсса выполняется за O( n ³ ) элементарные операции с O( n ^{н /2}  2 ^{Нидерланды} ) привязано к абсолютному значению необходимых промежуточных значений. Таким образом, его вычислительная сложность равна O( n ⁵ л ² (журнал( п ) ² + Л ² )) при использовании элементарной арифметики или O( n ⁴ L (log( n ) + L ) log(log( n ) + L ))) с помощью быстрого умножения .