Early Termination over Small Fields II: On the Reliability of Block Krylov-Based Algorithms in a Generic Case

Abstract

Block Hankel matrices, generated according to a particular distribution, arise in the analysis of Block Wiedemann and Block Lanczos algorithms. It is shown that if the input matrix A has entries in a small finite field Fq and satisfies a condition that holds generically, then the expected nullities of these matrices are low — as needed to establish the efficiency and reliability of these algorithms. A sparse matrix preconditioner, that ensures that the above-mentioned condition holds with high probability, is also contributed.