Probabilistic analysis of block Wiedemann for leading invariant factors (Q2048159)

For a prime power \(q\), let \(\mathbf F\) denote a finite field of cardinality \(q\). Let \(A\) be a \(n\times n\) matrix over \(\mathbf F\). For a chosen block size \(b\), let \(U\), \(V\) be uniformly random in \(\mathbf{F}^{n\times b}\). Call the sequence \(S= \{U^T A^jV\}_i\), \(i\in Z_+\), the \((U, V)\)-projection of \(A\). A projection and its minimal generator, \(G\), are called \(r\)-faithful to \(A\) if the \(r\) largest invariant factors of \(G\) are the \(r\) largest invariant factor of \(xI - A\). The authors develop an exact formula for the probability \(P_{q, b, r}(A)\) that a random projection is \(r\)-faithful for a given eigenstructure of \(A\). In the worst case the probability bound is improved by incorporating the partial information on the invariant factors of the minimal generating matrix \(G\). The results in this paper extend those in [\textit{G. Harrison} et al., J. Symb. Comput. 74, 55--69 (2016; Zbl 1375.15022)] and have been presented without proofs as a poster at ISSAC 2016 (see [\textit{G. Harrison} et al., ACM Commun. Comput. Algebra 50, No. 4, 173--175 (2016; Zbl 1365.65112)]).