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

Bareiss algorithm

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

Анализ

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

Отсюда следует, что для п × п матрица максимального (абсолютного) значения 2L для каждой записи алгоритм Барейса выполняется в O (п3) элементарные операции с O (пп/2 2nL) ограничивается абсолютным значением необходимых промежуточных значений. Его вычислительная сложность таким образом, O (п5L2 (бревно(п)2 + L2)) при использовании элементарной арифметики или O (п4L (бревно(п) + L) журнал (журнал (п) + L))) используя быстрое умножение.

История

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

В некоторых испаноязычных странах этот алгоритм также известен как Bareiss-Montante, потому что Рене Марио Монтанте Пардо, профессор Universidad Autónoma de Nuevo León, Мексика, который популяризировал метод среди своих учеников.

Рекомендации

  • Барейсс, Эрвин Х. (1968), "Идентичность Сильвестра и многоступенчатое целочисленное исключение Гаусса" (PDF), Математика вычислений, 22 (103): 565–578, Дои:10.2307/2004533, JSTOR 2004533.
  • Барейсс, Эрвин Х. (1966), МНОГОСТУПЕНЧАТЫЕ ЦЕЛОГО СОХРАНЕНИЯ Гауссовского искоренения (PDF). (Содержит более четкое представление о последовательности операций)