Interactive certificate for the verification of Wiedemann's Krylov sequence: application to the certification of the determinant, the minimal and the characteristic polynomials of sparse matrices

Jean-Guillaume Dumas, Erich Kaltofen, Emmanuel Thomé

Certificates to a linear algebra computation are additional data structures for each output, which can be used by a-possibly randomized- verification algorithm that proves the corr…