В математике алгоритм Барейсса , названный в честь Эрвина Барейсса, представляет собой алгоритм вычисления определителя или ступенчатой формы матрицы с целочисленными элементами , используя только целочисленную арифметику; любые выполняемые деления гарантированно будут точными ( остатка нет ). Этот метод также можно использовать для вычисления определителя матриц с (приблизительными) действительными элементами, избегая любых ошибок округления, помимо тех, которые уже присутствуют во входных данных.
Алгоритм был первоначально анонсирован Джеком Эдмондсом в 1966 году и опубликован в 1967 году.[1] Общий алгоритм Барейсса отличается от алгоритма Барейсса для матриц Теплица .
В некоторых испаноязычных странах этот алгоритм также известен как Bareiss-Montante в честь Рене Марио Монтанте Пардо, профессора Автономного университета Нуэво-Леона в Мексике , который популяризировал этот метод среди своих студентов.
В определении определителя есть только операции умножения, сложения и вычитания. Очевидно, что определитель является целым, если все элементы матрицы целые. Однако фактическое вычисление определителя с использованием определения или формулы Лейбница непрактично, поскольку требует O( n! ) операций.
Метод исключения Гаусса имеет сложность O( n 3 ), но вводит деление, что приводит к ошибкам округления при реализации с использованием чисел с плавающей запятой.
Ошибок округления можно избежать, если все числа хранить в виде целых дробей, а не с плавающей запятой. Но затем размер каждого элемента увеличивается экспоненциально с увеличением количества строк. [1]
Барейсс поднимает вопрос о выполнении исключения, сохраняющего целые числа, сохраняя при этом величины промежуточных коэффициентов достаточно небольшими. Предлагаются два алгоритма: [2] [3]
Для полноты картины Барейс также предлагает методы исключения без умножения, производящие дроби. [2]
Структура программы этого алгоритма представляет собой простой тройной цикл, как и в стандартном методе исключения Гаусса. Однако в этом случае матрица модифицируется так, что каждая запись M k,k содержит ведущий главный минор [ M ] k,k . Корректность алгоритма легко показать индукцией по k . [4]
Если предположение о главных минорах окажется неверным, например, если M k −1, k −1 = 0 и некоторые M i , k −1 ≠ 0 ( i = k ,..., n ), то мы можем поменять местами k −1-ю строку с i -й строкой и поменяйте знак окончательного ответа.
Во время выполнения алгоритма Барейсса каждое вычисляемое целое число является определителем подматрицы входной матрицы. Это позволяет с помощью неравенства Адамара ограничить размер этих целых чисел. В противном случае алгоритм Барейсса можно рассматривать как вариант исключения Гаусса , требующий примерно такого же количества арифметических операций.
Отсюда следует, что для матрицы размера n × n с максимальным (абсолютным) значением 2 L для каждой записи алгоритм Барейсса выполняет O( n 3 ) элементарных операций с ограничением O( n 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 )) ) с помощью быстрого умножения .
