ベライスアルゴリズム

数学において、エルヴィン・バライスにちなんで名付けられたバライスアルゴリズムは、整数要素を持つ行列の行列式または階段行列を、整数演算のみを用いて計算するアルゴリズムです。実行される除算はすべて正確であることが保証されています（余りは発生しません）。この方法は、（近似）実数要素を持つ行列の行列式を計算するためにも使用でき、入力に既に存在する丸め誤差以外の丸め誤差の導入を回避できます。

行列式の定義には、乗算、加算、減算の演算のみが含まれます。したがって、すべての要素が整数であれば、行列式は整数になります。しかし、定義またはライプニッツの公式を使用して実際に行列式を計算すると、O( n! ) 回の演算が必要となるため、実用的ではありません。ガウス消去法は O( n³ ) の計算量ですが、除算を導入するため、浮動小数点数を使用して実装する^と丸め誤差が発生します。

すべての数値を浮動小数点ではなく整数分数として保持すれば、丸め誤差を回避できます。しかし、その場合、各要素のサイズは行数とともに指数関数的に増加します。^{[ 1 ]}

Bareiss は、中間係数の大きさを適度に小さく保ちながら整数保存消去を実行するという問題を提起しています。2 つのアルゴリズムが提案されています: ^{[ 2 ] [ 3 ]}

1. 除算不要アルゴリズム ― 除算演算を行わずに、行列を三角行列形式に変換する。
2. 分数を含まないアルゴリズム — 中間エントリを小さく保つために除算を使用しますが、シルベスターの恒等式により、変換は依然として整数を保存します（除算の余りはゼロです）。

補足として、ベライスは分数を生成する乗算不要の消去法も提案している。^{[ 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行目と交換して、最終的な答えの符号を変更できます。

ベライスアルゴリズムの実行中、計算されるすべての整数は、入力行列の小行列の行列式です。これにより、アダマールの不等式を用いて、これらの整数のサイズを制限できます。そうでなければ、ベライスアルゴリズムはガウス消去法の変種と見なすことができ、ほぼ同じ数の算術演算を必要とします。

したがって、各要素の最大値（絶対値）が 2 ^Lであるn × n行列の場合、Bareiss アルゴリズムは、必要な中間値の絶対値の上限がO( n ^{n /2} 2 ^nL ) である O ( n ³ )の基本演算で実行されます。したがって、基本算術を使用する場合の計算複雑度は O( n ⁵ L ² (log( n ) ² + L ² )) であり、高速乗算を使用する場合は O( n ⁴ L (log( n ) + L ) log(log( n ) + L ))) となります。          

ベアリスアルゴリズムは、整数行列にはあまり使用されません。なぜなら、多重モジュラ演算は、高速な乗算でベアリスアルゴリズムと同程度の計算量を実現でき、実装もはるかに簡単だからです。

一方、ベライスアルゴリズムは、正確な除算アルゴリズムを備えた任意の積分領域の要素、特に多項式行列に対して使用できます。