Algoritmo Samuelson – Berkowitz - Samuelson–Berkowitz algorithm
Em matemática, o algoritmo Samuelson-Berkowitz calcula com eficiência o polinômio característico de uma matriz cujas entradas podem ser elementos de qualquer anel comutativo unital sem divisores zero . Ao contrário do algoritmo Faddeev – LeVerrier , ele não realiza divisões, portanto, pode ser aplicado a uma gama mais ampla de estruturas algébricas.
Descrição do algoritmo
O algoritmo Samuelson – Berkowitz aplicado a uma matriz produz um vetor cujas entradas são o coeficiente do polinômio característico de . Ele calcula esse vetor de coeficientes recursivamente como o produto de uma matriz de Toeplitz e o vetor de coeficientes uma submatriz principal .
Seja uma matriz particionada de modo que
A primeira submatriz principal de é a matriz . Associe-se à matriz Toeplitz definida por
se é ,
se é , e em geral
Ou seja, todas as superdiagonais de consistem em zeros, a diagonal principal consiste em uns, a primeira subdiagonal consiste em e a décima subdiagonal consiste em .
O algoritmo é então aplicado recursivamente , produzindo a matriz de Toeplitz vezes o polinômio característico de , etc. Finalmente, o polinômio característico da matriz é simples . O algoritmo Samuelson-Berkowitz então afirma que o vetor definido por
contém os coeficientes do polinômio característico de .
Como cada um deles pode ser calculado independentemente, o algoritmo é altamente paralelizável .
Referências
- Berkowitz, Stuart J. (30 de março de 1984). "Sobre o cálculo do determinante em pequeno tempo paralelo usando um pequeno número de processadores". Cartas de processamento de informações . 18 (3): 147-150. doi : 10.1016 / 0020-0190 (84) 90018-8 .
- Soltys, Michael; Cook, Stephen (dezembro de 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 (maio de 2006). Cálculo sem divisão de sub-resultantes usando matrizes de Bezout (PS) (relatório técnico). Saarbrucken: Max-Planck-Institut für Informatik. Tech. Relatório MPI-I-2006-1-006.