Dynamic normal forms and dynamic characteristic polynomial

DOI10.1016/j.tcs.2010.11.049zbMath1214.65017MaRDI QIDQ633626

Gudmund Skovbjerg Frandsen, Piotr Sankowski

Publication date: 29 March 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.11.049

zbMATH Keywords

eigenproblem; lower bound; Characteristic polynomial; arithmetic complexity; matrix normal form; dynamic algorithm

Mathematics Subject Classification ID

65F15: Numerical computation of eigenvalues and eigenvectors of matrices

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

65Y20: Complexity and performance of numerical algorithms

15A21: Canonical forms, reductions, classification

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Geometric bounds for eigenvalues of Markov chains
• Dynamic matrix rank
• A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
• Lower bounds for dynamic algebraic problems
• Two uses for updating the partial singular value decomposition in latent semantic indexing
• Rational Matrix Functions and Rank-1 Updates
• The complexity of the matrix eigenproblem
• Updating $LU$ Factorizations for Computing Stationary Distributions
• Updating finite markov chains by using techniques of group matrix inversion
• On pointers versus addresses
• A Divide-and-Conquer Algorithm for the Bidiagonal SVD
• Downdating the Singular Value Decomposition
• Nearly Optimal Algorithms for Canonical Matrix Forms