Obliczanie charakterystycznego wielomianu rzeczywistej macierzy rzadkiej

Biorąc pod uwagę ogólną macierz rzadką z m << n (korekta: ) niezerowe elementy (zwykle ). jest ogólne w tym sensie, że nie ma żadnych specyficznych właściwości (np. Dodatnia definitywność) i nie zakłada się żadnej struktury (np. Pasmowości).$A \in \mathbb{R}^{n\times n}$$m \ll n^2$$m \in {\cal O}(n)$$A$

Jakie są dobre metody numeryczne do obliczenia charakterystycznego wielomianu lub minimalnego wielomianu ?$A$

Jeśli złożoność nie jest ogranicznikiem, możesz przyjrzeć się metodzie Danilewskiego. Jest dość dobrze znany w rosyjskiej literaturze na temat numerycznej algebry liniowej, ale po angielsku niewiele jest informacji. Możesz zacząć od tego linku .$O(n^3)$

Pomysł jest raczej prosty: matryca jest stopniowo redukowana do normalnej postaci Frobeniusa przez transformacje podobieństwa „eliminacji Gaussa”. Jeśli nie znajdziesz informacji, mogę ulepszyć algorytm.

Możesz użyć metody numerycznej, takiej jak faktoryzacja QR lub metoda mocy i jej wartości rzeczywiste (moc odwrotna itp.), Aby obliczyć wartości własne macierzy ogólnej. Następnie możesz obliczyć swój charakterystyczny wielomian przez rozkład na czynniki: (λ-λ1) (λ-λ2) ... (λ-λn) = 0, gdzie λi to obliczone wartości własne. Oto krótka prezentacja na temat metod zasilania i QR:

QR-Power

Nawiasem mówiąc: Czy chcesz powiedzieć, że masz wiele wpisów ? Jeśli rzeczywiście wówczas większość wierszy i kolumn będzie całkowicie pusta i prawdopodobne jest, że charakterystyczny wielomian faktycznie nie ma stopnia ale stopnia .$m \ll O(n^2)$$m \ll O(n)$$n$$O(m)$