Block Black Box Algorithms Over Small Fields
Authors:   , Harrison Gavin M. , Johnson Jeremy Russell 
Published: July 2021

Black box linear algebra algorithms treat matrices as black boxes that can be applied to input vectors but whose elements cannot be accessed or modified. Since they avoid the fill-in of non-zero entries that occurs with elimination based approaches, black box algorithms provide an efficient approach to computing with sparse matrices and can be used to compute matrix invariants such as minimal polynomial, characteristic polynomial, rank, determinant, and Frobenius normal form for very large sparse matrices over finite fields. Many of these algorithms are probabilistic and often require preconditioning to ensure certain properties hold with high probability. To guarantee a high probability of success it is often necessary that the underlying field contain a large number of elements. Consequently, when computing over small fields, such as GF(2), which is the case for many important applications, these algorithms may require computation over an extension field or repeated computation. This can lead to a significant slow down in practice. Block black box algorithms, such as the block Wiedemann algorithm, which apply black box matrices simultaneously to blocks of input vectors, have been developed for linear system solving. Block algorithms improve performance through better data locality and parallelism and can avoid the need for repeated computation or the use of extension fields needed by approaches without blocking. In this thesis, adaptations of the block Wiedemann algorithm for computing minimal polynomial, characteristic polynomial, rank, determinant, and Frobenius normal form over finite fields, especially small fields, are designed, implemented, analyzed and compared to existing implementations in the LinBox linear algebra library. The key algorithm, LIFs, uses the block Wiedemann algorithm to compute the largest invariant factors of a matrix. A tight probability bound is obtained showing that, with high probability, LIFs correctly computes the r largest invariant factors, even for small fields, using a block size slightly larger than r. An efficient implementation of LIFs requires fast computation of the Smith normal form (SNF) of a polynomial matrix over a finite field. This thesis compares a variety of SNF algorithms and provides an efficient implementation appropriate for use in LIFs. When LIFs is able to compute all of the invariant factors then it can be used to compute minimum polynomial, rank, determinant, characteristic polynomial and Frobenius normal form significantly faster, for matrices over small fields, than existing approaches based on the scalar Wiedemann algorithm with various preconditioners. When there are a large number of invariant factors LIFs cannot be used directly. For rank and determinant computation heuristic preconditioners are used to produce equivalent matrices with a small number of invariant factors for which LIFs can be used. For characterstic polynomial and Frobenius normal form LIFs is used iteratively and for small fields, even when a relatively large block size is needed, the iterated LIFs algorithm outperforms existing approaches. When very large block sizes are needed a new approach for Frobenius form computation based on repeated rank computation is outlined and experiments show it to be promising compared to general black box algorithms for Frobenius normal form.