Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

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

Résumé

Computational problem certificates are additional data structures for each output, which can be used by a—possibly randomized—verification algorithm that proves the correctness of each output. In this paper, we give an algorithm that computes a certificate for the minimal polynomial of sparse or structured n×n matrices over an abstract field, of sufficiently large cardinality, whose Monte Carlo verification complexity requires a single matrix-vector multiplication and a linear number of extra field operations. We also propose a novel preconditioner that ensures irreducibility of the characteristic polynomial of the generically preconditioned matrix. This preconditioner takes linear time to be applied and uses only two random entries. We then combine these two techniques to give algorithms that compute certificates for the determinant, and thus for the characteristic polynomial, whose Monte Carlo verification complexity is therefore also linear.
Fichier principal
Vignette du fichier
det_techreport.pdf (425.28 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01266041 , version 1 (01-02-2016)
hal-01266041 , version 2 (21-10-2019)
hal-01266041 , version 3 (27-11-2019)

Identifiants

Citer

Jean-Guillaume Dumas, Erich Kaltofen, Emmanuel Thomé, Gilles Villard. Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix. ISSAC’2016, Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation, Jul 2016, Waterloo, Canada. pp.199-206, ⟨10.1145/2930889.2930908⟩. ⟨hal-01266041v3⟩
753 Consultations
309 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More