z-logo
open-access-imgOpen Access
Dynamic Normal Forms and Dynamic Characteristic Polynomial
Author(s) -
Gudmund Skovbjerg Frandsen,
Piotr Sankowski
Publication year - 2008
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v15i2.21937
Subject(s) - tridiagonal matrix , mathematics , singular value decomposition , matrix (chemical analysis) , combinatorics , singular value , rank (graph theory) , time complexity , randomized algorithm , upper and lower bounds , constant (computer programming) , binary logarithm , discrete mathematics , algorithm , eigenvalues and eigenvectors , computer science , mathematical analysis , physics , materials science , quantum mechanics , composite material , programming language
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 Omega(n^2) lower bound for rank-one updates and an Omega(n) lower bound for element updates.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here