Sparse Matrix Computations over Small Fields: A Simpler Block Lanczos Algorithm and Its Analysis

Abstract

A simpli ed \block Lanczos" algorithm is presented and its correctness established. While its e ciency in the general case is not proved, preconditioning used for similar algo- rithms is also su cient here. Results concerning reliability and e ciency may be of more general interest because they may serve to (somewhat) better explain the performance of other block algorithms, including block Wiedemann algo- rithms and algorithms that use rectangular blocking.