새뮤얼슨-베르코위츠 알고리즘

본 기사는 해당 기사에서 독일어로 번역된 텍스트로 확장될 수 있다.(2020년 7월) 중요한 번역 지침을 보려면 [표시]를 클릭하십시오. 독일어 기사의 기계 번역 버전을 보십시오. DeepL이나 Google Translation과 같은 기계 번역은 번역의 유용한 출발점이지만 번역자는 기계 번역된 텍스트를 단순히 영어 위키백과에 복사하는 것이 아니라 필요에 따라 오류를 수정하고 번역이 정확한지 확인해야 한다. 이 템플리트에 주제를 추가하는 것을 고려하십시오. 기본 카테고리에 이미 7,877개의 기사가 있으며, 다음을 지정하십시오. topic=분류에 도움이 될 것이다. 신뢰할 수 없거나 품질이 낮은 텍스트는 번역하지 마십시오.가능한 경우 외국어 기사에 제공된 참조 자료로 텍스트를 확인하십시오. 번역 출처에 대한 상호 언어 링크를 제공하여 번역에 수반되는 편집 요약에 저작권 귀속성을 제공해야 한다.모델 속성 편집 요약은Content in this edit is translated from the existing German Wikipedia article at [[:de:Algorithmus von Samuelson-Berkowitz]]; see its history for attribution. 템플릿도 추가하십시오.{{Translated de Algorithmus von Samuelson-Berkowitz}}토크로 자세한 내용은 Wikipedia:번역.

수학에서 Samuelson-Berkowitz 알고리즘은 입력된 항목이 단수 교환 링의 요소가 될 수 있는 $n{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle n}$ ${\displaystyle n\times n}$ 행렬의$$ 특성 다항식을 효율적으로 계산한다.Faddeev-LeVerrier 알고리즘과는 달리 어떤 분할도 수행하지 않기 때문에 더 넓은 범위의 대수 구조에 적용할 수 있다.

알고리즘 설명

매트릭스 $A{\displaystyle }${\displaystyle A}에 적용된 Samuelson-Berkowitz 알고리즘은 A {\$displaystyle A}$의 특성 다항식의 계수인 벡터를 생성하며$,$ 이 계수 벡터 a $({\displaystyle \mathrm{n}}$- 1${\displaystyle }$) ${\displaystyle \times }$(${\displaystyle n}$- ${\displaystyle 1}$) ${\disp$)를 반복적으로 계산한다.$레이스타일(n-1)\cHB(n-1)}$ 주 서브매트릭스.

$A{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$ 행렬을$$ $n$ ${\displaystyle \times }$ ${\displaystyle n}$ ${\displaystyle$ n$\times$ n$} 칸막이$하도록 두십시오.

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

The first principal submatrix of ${\displaystyle A_{0}}$ is the ${\displaystyle (n-1)\times (n-1)}$ matrix ${\displaystyle A_{1}}$. Associate with ${\displaystyle A_{0}}$ the ${\displaystyle (n+1)\times n}$ Toeplitz matrix ${\displaystyle T_{0}}$$$ 에 의해 정의된.

${\displaystyle T_{0}=\왼쪽[{\begin{array}{c}1\\-a_{1,1}\end{array}\오른쪽]}$

${\displaystyle {0\mathrm{}}_{}}$ ${\$이 $1{\displaystyle \mathrm{}}$ ${\displaystyle \times }$ ${\displaystyle 1}$인 경우$(\displaystyle 1\times$ 1$\}),$

${\displaystyle T_{0}=\left[{\begin{array}{c1&0\\\-a_{1,1}\-RC&a_{11}\end{array}\오른쪽]}$

${\displaystyle {0\mathrm{}}_{}}$ ${\$이(가) $2{\displaystyle \mathrm{}}$ $×$ ${\displaystyle 2}$인 경우(\$displaystyle$2\$times$ 2$}$이고 일반적으로$,$

${\displaystyle T_{0}[{\begin{배열}{ccccc}1&, 0&, 0&, 0&, \cdots{1,1}및 \\-a_, 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{배열}}\right].}$

That is, all super diagonals of ${\displaystyle T_{0}}$ consist of zeros, the main diagonal consists of ones, the first subdiagonal consists of ${\displaystyle -a_{1,1}}$ and the ${\displaystyle k}$th subdiagonal consists of ${\displaystyle -RA_{1}^{k-2}C}$.

그런 다음 알고리즘을 $A{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$}에 재귀적으로 적용하여$$A ${\displaystyle {2\mathrm{}}_{}}$ ${\$$2$}}배의$$ 특성 다항식을 토플리츠 매트릭스 T ${\displaystyle {1\mathrm{}}_{}}$ ${\$}{1$}}$를 생성한다.마지막으로 $1{\displaystyle \mathrm{}}$ ${\displaystyle \times }$ ${\displaystyle 1}$ ${\displaystyle 1\times$ 1$} 행렬$ ${\displaystyle A_{}}$ ${\displaystyle {\mathrm{n}}_{}}$- 1 ${\$}의$$특성 다항식은 간단히 $T$ ${\displaystyle n_{}}$ -${\displaystyle {}_{}}$1 ${\$이다$.$Samuelson-Berkowitz 알고리즘에 따르면 $벡터{\displaystyle }$ v ${\displaystyle$ v$}$은(는$$)

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

$A{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$의 특성 다항식 계수를 포함한다$.$

각각의 ${\displaystyle {Ti}_{}}$ ${\$는 독립적으로 계산될 수$$ 있기 때문에 알고리즘은 병렬화가 매우 용이하다.

참조

• Berkowitz, Stuart J. (30 March 1984). "On computing the determinant in small parallel time using a small number of processors". Information Processing Letters. 18 (3): 147–150. doi:10.1016/0020-0190(84)90018-8.
• Soltys, Michael; Cook, Stephen (December 2004). "The Proof Complexity of Linear Algebra" (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 (May 2006). Division-Free computation of sub-resultants using Bezout matrices (PS) (Technical report). Saarbrucken: Max-Planck-Institut für Informatik. Tech. Report MPI-I-2006-1-006.