Algoritmus Samuelson – Berkowitz - Samuelson–Berkowitz algorithm
![]() | tento článek lze rozšířit o text přeložený z odpovídající článek v němčině. (Červenec 2020) Kliknutím na [zobrazit] zobrazíte důležité pokyny k překladu.
|
V matematice je Algoritmus Samuelson – Berkowitz efektivně počítá charakteristický polynom z matice, jejíž záznamy mohou být prvky libovolného unitalu komutativní prsten bez nulové dělitele. Na rozdíl od Algoritmus Faddeev – LeVerrier, neprovádí žádné dělení, takže jej lze použít na širší škálu algebraických struktur.
Popis algoritmu
Algoritmus Samuelson – Berkowitz aplikovaný na matici vytvoří vektor, jehož položky jsou koeficientem charakteristického polynomu . Vypočítává tento vektor koeficientů rekurzivně jako součin a Toeplitzova matice a vektor koeficientů an hlavní submatice.
Nechat být matice rozdělená tak, že
The první hlavní submatice z je matice . Spojit s the Toeplitzova matice definován
-li je ,
-li je a obecně
To znamená, všechny super diagonály se skládají z nul, hlavní úhlopříčka se skládá z těch, první subdiagonální se skládá z a th subdiagonalconsists of .
Algoritmus je poté rekurzivně aplikován na , produkující Toeplitzovu matici násobek charakteristického polynomu A konečně charakteristický polynom z matice je prostě . Algoritmus Samuelson – Berkowitz pak uvádí, že vektor definován
obsahuje koeficienty charakteristického polynomu o .
Protože každý z lze vypočítat nezávisle, algoritmus je vysoce paralelizovatelný.
Reference
- Berkowitz, Stuart J. (30. března 1984). "O výpočtu determinantu v malém paralelním čase pomocí malého počtu procesorů". Dopisy o zpracování informací. 18 (3): 147–150. doi:10.1016/0020-0190(84)90018-8.
- Soltys, Michael; Cook, Stephen (prosinec 2004). „Důkazní složitost lineární algebry“ (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.
- Keber, Michael (květen 2006). Výpočet dílčích výsledků bez rozdělení pomocí matic Bezout (PS) (Technická zpráva). Saarbrucken: Max-Planck-Institut für Informatik. Tech. Zpráva MPI-I-2006-1-006.