A Reliable Block Lanczos Algorithm over Small Finite Fields

B. Hovinen, W. Eberly


Blocked versions of the Lanczos procedure have been successfully applied to sample nullspace elements of very large sparse matrices over small finite fields. The heuristic currently in use, namely, Montgomery's method, is unreliable for certain input matrices. This paper introduces a new biconditional block Lanczos approach based on lookahead, a technique designed to improve the reliability of the scalar Lanczos algorithm. The reliability of this method for arbitrary matrices over small finite fields is then established. Empirical data show that the performance of the lookahead-based algorithm is competitive with that of Montgomery's algorithm when their relative reliability is taken into account.