Dynamic normal forms and dynamic characteristic polynomial

作者：Frandsen Gudmund Skovbjerg^*; Sankowski Piotr

来源：Theoretical Computer Science, 2011, 412(16): 1470-1483.

DOI：10.1016/j.tcs.2010.11.049

• Characteristic polynomial
• Matrix normal form
• Eigenproblem
• Dynamic algorithm
• Lower bound

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.

• 出版日期2011-4-1