Early Termination over Small Fields II: On the Reliability of Block Krylov-Based Algorithms in a Generic Case
Date
2014-07-15
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Keywords
Algorithms, Performance, Reliability, Theory