Probabilistic analysis of Wiedemann's algorithm for minimal polynomial computation

Blackbox algorithms for linear algebra problems start with projection of the sequence of powers of a matrix to a sequence of vectors (Lanczos), a sequence of scalars (Wiedemann) or a sequence of smaller matrices (block methods). Such algorithms usually ...

We investigate the computational complexity of the minimal polynomial of an integer matrix.

We show that the computation of the minimal polynomial is in AC⁰(GapL), the AC⁰-closure of the logspace counting class GapL, which is contained in NC². Our main ...

We investigate the complexity of (1) computing the characteristic polynomial, the minimal polynomial, and all the invariant factors of an integer matrix, and of (2) verifying them, when the coefficients are given as input.It is known that each ...