Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix

DOI10.1145/2930889.2930908zbMath1365.65138arXiv1602.00810OpenAlexW2270001959WikidataQ57434319 ScholiaQ57434319MaRDI QIDQ2985828

Gilles Villard, Emmanuel Thomé, Erich L. Kaltofen, Jean-Guillaume Dumas

Publication date: 10 May 2017

Published in: Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1602.00810

zbMATH Keywords

characteristic polynomialpreconditionermatrix-vector multiplicationmatrix determinantverification algorithminteractive certificatematrix characteristic polynomialmatrix minimal polynomialMonte Carlo verification complexity

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Iterative numerical methods for linear systems (65F10) Numerical computation of determinants (65F40) Algorithms with automatic result verification (65G20) Preconditioners for iterative methods (65F08)

Related Items (4)

Automating algorithm selection: checking for matrix properties that can simplify computations ⋮ Verification protocols with sub-linear communication for polynomial matrix operations ⋮ Elimination-based certificates for triangular equivalence and rank profiles ⋮ Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment

This page was built for publication: Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix