Dynamic normal forms and dynamic characteristic polynomial

DOI10.1016/J.TCS.2010.11.049MaRDI QIDQ633626zbMATH OpenOpenAlexFDO

Authors Gudmund S. 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

arithmetic complexityCharacteristic polynomialdynamic algorithmeigenproblemlower boundmatrix normal form

Mathematics Subject Classification ID

Canonical forms, reductions, classification (15A21) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Complexity and performance of numerical algorithms (65Y20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Review text

The paper is concerned with the computation of the characteristic polynomial of a matrix and the associated eigenproblem. The authors analyze the dynamic complexity of these fundamental problems, devise efficient algorithms, prove matching lower bounds, and study the arithmetic complexity of the problem.

Recommendations

• Dynamic Normal Forms and Dynamic Characteristic Polynomial
• Dynamic Matrix Rank
• Dynamic matrix rank
• Fast matrix rank algorithms and applications
• Deterministic computation of the characteristic polynomial in the time of matrix multiplication

Cites work

• A Divide-and-Conquer Algorithm for the Bidiagonal SVD
• A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
• Downdating the Singular Value Decomposition
• Dynamic matrix rank
• Faster algorithms for the characteristic polynomial
• Geometric bounds for eigenvalues of Markov chains
• scientific article; zbMATH DE number 1574494 (Why is no real title available?)
• scientific article; zbMATH DE number 19232 (Why is no real title available?)
• scientific article; zbMATH DE number 691245 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 3417498 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Lower bounds for dynamic algebraic problems
• Nearly Optimal Algorithms for Canonical Matrix Forms
• On pointers versus addresses
• Rational matrix functions and rank-1 updates
• The complexity of the matrix eigenproblem
• Two uses for updating the partial singular value decomposition in latent semantic indexing
• Updating LU Factorizations for Computing Stationary Distributions
• Updating finite markov chains by using techniques of group matrix inversion

Cited in

(2)

• Dynamic Normal Forms and Dynamic Characteristic Polynomial
• Updating matrix polynomials

This page was built for publication: Dynamic normal forms and dynamic characteristic polynomial

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q633626)