Dynamic normal forms and dynamic characteristic polynomial |
| |
Authors: | Gudmund Skovbjerg Frandsen Piotr Sankowski |
| |
Affiliation: | a Department of Computer Science, University of Aarhus, Aabogade 34, DK-8200 Aarhus N, Denmarkb Warsaw University, Polandc University of Rome “La Sapienza”, Italy |
| |
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. |
| |
Keywords: | Characteristic polynomial Matrix normal form Eigenproblem Dynamic algorithm Lower bound |
本文献已被 ScienceDirect 等数据库收录! |
|