バレースアルゴリズム

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

概要

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

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

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

1. 除算不要アルゴリズム - 除算演算なしで三角形形式への行列縮小を実行します。
2. 分数を使用しないアルゴリズム - 中間の​​エントリを小さく保つために除算を使用しますが、シルベスターの恒等式により、変換は依然として整数を保持します (除算の余りは 0 になります)。

完全性のために、Bareissは分数を生成する乗算を伴わない消去法も提案している。^[2]

アルゴリズム

このアルゴリズムのプログラム構造は、標準的なガウス消去法と同様に、単純な3重ループです。ただし、この場合、行列は各M _k,k要素に主小行列[ M ] _k,kが含まれるように修正されます。アルゴリズムの正しさは、 kに関する帰納法によって簡単に示されます。^[4]

• 入力: M — n正方行列。
  その主小行列[ M ] _k,kはすべてゼロでないと仮定します。
• M _0,0 = 1とする（注: M _0,0は特殊変数です）
• kが1からn -1の場合:
  • k +1からnまでのiについて:
    • k +1からnまでのjについて:
      • セット${\displaystyle M_{i,j}={\frac {M_{i,j}M_{k,k}-M_{i,k}M_{k,j}}{M_{k-1,k-1}}}}$
    • M _i,k = 0 に設定する
• 出力: 行列はインプレースで変更され、
  各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番目の行と交換し、最終的な答えの符号を変更できます。

分析

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

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

使用法

Bareiss アルゴリズムは整数行列にはあまり使用されません。これは、マルチモジュラ演算により、高速乗算で Bareiss アルゴリズムと同等の複雑さが可能になり、実装がはるかに簡単になるからです。

一方、Bareiss アルゴリズムは、正確な除算アルゴリズムを備えた任意の積分領域のエントリ、特に多項式行列に使用できます。

参考文献

1. Middeke, J.; Jeffrey, DJ; Koutschan, C. (2020)、「分数を含まない行列分解における共通因子」、Mathematics in Computer Science、15 (4): 589– 608、arXiv : 2005.12380、doi : 10.1007/s11786-020-00495-9
2. Bareiss, Erwin H. (1968)、「シルベスターの恒等法と多段階整数保存ガウス消去法」（PDF）、Mathematics of Computation、22 (103): 565– 578、doi :10.2307/2004533、JSTOR  2004533
3. Bareiss, Erwin H. (1966)、マルチステップ整数保存ガウス消去法(PDF)（操作手順をより明確に図示しています）
4. Yap, Chee Keng (2000), 『アルゴリズム代数の基礎問題』オックスフォード大学出版局