サムエルソン・バーコウィッツアルゴリズム

数学では、サムエルソン・バーコウィッツアルゴリズムは、${\displaystyle n\times n}$要素が任意の単位元を持つ可換環の要素である行列。ファデエフ・ルヴェリエアルゴリズムとは異なり、除算を行わないため、より広範な代数構造に適用できる。

行列に適用されたサムエルソン・バーコウィッツアルゴリズム${\displaystyle A}$は、その要素が特性多項式の係数であるベクトルを生成する。${\displaystyle A}$この係数ベクトルは、トープレッツ行列と係数ベクトルの積として再帰的に計算されます。${\displaystyle (n-1)\times (n-1)}$主小行列。

させて${\displaystyle A_{0}}$になる${\displaystyle n\times n}$行列を分割して

${\displaystyle A_{0}=\left[{\begin{array}{c|c}a_{1,1}&R\\\hline C&A_{1}\end{array}}\right]}$

最初の主小行列${\displaystyle A_{0}}$は${\displaystyle (n-1)\times (n-1)}$マトリックス${\displaystyle A_{1}}$と提携する${\displaystyle A_{0}}$の${\displaystyle (n+1)\times n}$トープレット行列${\displaystyle T_{0}}$ 定義される

${\displaystyle T_{0}=\left[{\begin{array}{c}1\\-a_{1,1}\end{array}}\right]}$

もし${\displaystyle A_{0}}$は${\displaystyle 1\times 1}$、

${\displaystyle T_{0}=\left[{\begin{array}{cc}1&0\\-a_{1,1}&1\\-RC&-a_{1,1}\end{array}}\right]}$

もし${\displaystyle A_{0}}$は$2×2$一般的に

${\displaystyle T_{0}=\left[{\begin{array}{c c c c c}1&0&0&0&\cdots \\-a_{1,1}&1&0&0&\cdots \\-RC&-a_{1,1}&1&0&\cdots \\-RA_{1}C&-RC&-a_{1,1}&1&\cdots \\-RA_{1}^{2}C&-RA_{1}C&-RC&-a_{1,1}&\cdots \\\vdots &\vdots &\vdots &\vdots &\ddots \end{array}}\right]}$

つまり、すべてのスーパー対角線は${\displaystyle T_{0}}$はゼロで構成され、主対角線は 1 で構成され、第 1 副対角線は 0${\displaystyle -a_{1,1}}$そして${\displaystyle k}$番目のサブ対角線は、${\displaystyle -RA_{1}^{k-2}C}$。

アルゴリズムはその後再帰的に適用され、${\displaystyle A_{1}}$トープレッツ行列を生成する${\displaystyle T_{1}}$特性多項式の倍数${\displaystyle A_{2}}$など。最後に、の特性多項式は${\displaystyle 1\times 1}$マトリックス${\displaystyle A_{n-1}}$単に${\displaystyle T_{n-1}}$サムエルソン・バーコウィッツアルゴリズムでは、ベクトルは次のように述べられています。${\displaystyle v}$定義される

${\displaystyle v=T_{0}T_{1}T_{2}\cdots T_{n-1}}$

特性多項式の係数を含む${\displaystyle A_{0}}$。

なぜなら、${\displaystyle T_{i}}$独立して計算することができ、アルゴリズムは高度に並列化可能である。

• Berkowitz, Stuart J. (1984年3月30日). 「少数のプロセッサを使用して短い並列時間で行列式を計算することについて」. Information Processing Letters . 18 (3): 147–150 . doi : 10.1016/0020-0190(84)90018-8 .
• Soltys, Michael; Cook, Stephen (2004 年 12 月). 「線形代数の証明複雑性」(PDF) . Annals of Pure and Applied Logic . 130 ( 1– 3): 277– 323. CiteSeerX 10.1.1.308.6521 . doi : 10.1016/j.apal.2003.10.018 . 
• Kerber, Michael (2006年5月).ベズー行列（PS）を用いた部分結果式の除算不要計算 （技術報告書）。ザールブリュッケン：マックス・プランク情報科学研究所。技術報告書 MPI-I-2006-1-006。