Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10333939 | Theoretical Computer Science | 2011 | 14 Pages |
Abstract
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(n2logn) randomized time and queries in constant time, whereas in the general case the algorithm works in O(n2klogn) 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(nlog2nlogb) 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 Ω(n2) lower bound for rank-one updates and an Ω(n) lower bound for element updates.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Gudmund Skovbjerg Frandsen, Piotr Sankowski,