Войти
В математике алгоритм Барейса, названный в честь, является алгоритмом для вычисления определителя или эшелонированной формы матрицы матрицы с целым числом. записи, использующие только целочисленную арифметику; любые выполняемые деления гарантированно будут точными (нет остатка ). Этот метод также можно использовать для вычисления определителя матриц с (приближенными) действительными записями, избегая введения любых ошибок округления, помимо тех, которые уже присутствуют во входных данных.
Во время выполнения алгоритма Барейса каждое вычисляемое целое число является определителем подматрицы входной матрицы. Это позволяет, используя неравенство Адамара, ограничить размер этих целых чисел. В противном случае алгоритм Барейсса можно рассматривать как вариант исключения Гаусса и требует примерно того же количества арифметических операций.
Отсюда следует, что для матрицы n × n максимального (абсолютного) значения 2 для каждой записи алгоритм Барейсса выполняется за O (n) элементарных операций с O (n 2) ограничивается абсолютным значением необходимых промежуточных значений. Его вычислительная сложность, таким образом, составляет O (nL (log (n) + L)) при использовании элементарной арифметики или O (nL (log (n) + L) log (log (n) + L))) с помощью быстрого умножения.
Общий алгоритм Барейсса отличается от алгоритма Барейса для матриц Теплица.
В некоторых испаноязычных странах этот алгоритм также известен как Барейс-Монтанте благодаря профессору Автономного университета Нуэво-Леон, Мексика, который популяризировал этот метод среди своих учеников.
