Open AccessDynamic 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.