Algoritmo de Samuelson-Berkowitz

Concepto en matemáticas

En matemáticas, el algoritmo de Samuelson-Berkowitz calcula de manera eficiente el polinomio característico de una matriz cuyas entradas pueden ser elementos de cualquier anillo conmutativo unitario . A diferencia del algoritmo de Faddeev-LeVerrier , no realiza divisiones, por lo que puede aplicarse a una gama más amplia de estructuras algebraicas. ${\displaystyle n\times n}$

Descripción del algoritmo

El algoritmo de Samuelson-Berkowitz aplicado a una matriz produce un vector cuyos elementos son el coeficiente del polinomio característico de . Calcula este vector de coeficientes recursivamente como el producto de una matriz de Toeplitz y el vector de coeficientes de una submatriz principal . ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle (n-1)\times (n-1)}$

Sea una matriz particionada de modo que ${\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]}$

La primera submatriz principal de es la matriz . Asociada con la matriz de Toeplitz definida por ${\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]}$

Si es , ${\displaystyle A_{0}}$ ${\displaystyle 1\times 1}$

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

si es , y en general ${\displaystyle A_{0}}$ ${\displaystyle 2\times 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]}$

Es decir, todas las superdiagonales de constan de ceros, la diagonal principal consta de unos, la primera subdiagonal consta de y la enésima subdiagonal consta de . ${\displaystyle T_{0}}$ ${\displaystyle -a_{1,1}}$ ${\displaystyle k}$ ${\displaystyle -RA_{1}^{k-2}C}$

El algoritmo se aplica entonces de forma recursiva a , produciendo la matriz de Toeplitz multiplicada por el polinomio característico de , etc. Finalmente, el polinomio característico de la matriz es simplemente . El algoritmo de Samuelson-Berkowitz establece entonces que el vector definido por ${\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}}$

contiene los coeficientes del polinomio característico de . ${\displaystyle A_{0}}$

Debido a que cada uno de ellos puede calcularse independientemente, el algoritmo es altamente paralelizable . ${\displaystyle T_{i}}$

Referencias

• Berkowitz, Stuart J. (30 de marzo de 1984). "Sobre el cálculo del determinante en tiempos paralelos pequeños utilizando un pequeño número de procesadores". Information Processing Letters . 18 (3): 147–150. doi :10.1016/0020-0190(84)90018-8.
• Soltys, Michael; Cook, Stephen (diciembre de 2004). "La complejidad de la demostración del álgebra lineal" (PDF) . Anales de lógica pura y aplicada . 130 (1–3): 277–323. CiteSeerX  10.1.1.308.6521 . doi :10.1016/j.apal.2003.10.018.
• Kerber, Michael (mayo de 2006). Cálculo sin división de subresultados utilizando matrices de Bezout (PS) (Reporte técnico). Saarbrücken: Max-Planck-Institut für Informatik. Tecnología. Informe MPI-I-2006-1-006.