Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Dynamic Normal Forms and Dynamic Characteristic Polynomial
verfasst von : Gudmund Skovbjerg Frandsen, Piotr Sankowski
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We present the first fully dynamic algorithm for computing the characteristic polynomial of a matrix. In the generic symmetric case our algorithm supports rank-one updates in
O
(
n
2
log
n
) randomized time and queries in constant time, whereas in the general case the algorithm works in
O
(
n
2
k
log
n
) randomized time, where
k
is the number of invariant factors of the matrix. The algorithm is based on the first dynamic algorithm for computing normal forms of a matrix such as the Frobenius normal form or the tridiagonal symmetric form. The algorithm can be extended to solve the matrix eigenproblem with relative error 2
−
b
in additional
O
(
n
log
2
n
log
b
) time. Furthermore, it can be used to dynamically maintain the singular value decomposition (SVD) of a generic matrix. Together with the algorithm the hardness of the problem is studied. For the symmetric case we present an
Ω
(
n
2
) lower bound for rank-one updates and an
Ω
(
n
) lower bound for element updates.