A parallel algorithm for Gaussian elimination over finite fields

Journal of Algebra, vol. 703, pp. 239–265

Abstract

In this paper we describe a parallel Gaussian elimination algorithm for matrices with entries in a finite field. Our algorithm subdivides a very large input matrix into smaller submatrices by subdividing both rows and columns into roughly square blocks sized so that computing with individual blocks on individual processors provides adequate concurrency. The algorithm also returns the transformation matrix, which encodes the row operations used. We go to some lengths to avoid storing any unnecessary data as we keep track of the row operations, such as block columns of the transformation matrix known to be zero. This helps the algorithm to scale to very large dimensions. The algorithm is accompanied by a concurrency analysis which shows that the improvement in concurrency is of the same order of magnitude as the number of blocks. An implementation of the algorithm has been tested on matrices as large as 1 , 500 , 000 × 1 , 500 , 000 over GF ( 2 ) .

Authors 4

1. Stephen Linton

   University of St Andrews

   Affiliation as printed

   School of Computer Science, University of St. Andrews, St. Andrews, Fife, KY169SX, Scotland, UK

2. Gabriele Nebe Aachen Chair for Algebra and Number Theory

   RWTH Aachen University

   Affiliation as printed

   Chair for Algebra and Number Theory, RWTH Aachen University, Aachen, 52056, Germany

3. Alice C. Niemeyer corresponding Aachen Chair for Algebra and Representation Theory

   RWTH Aachen University

   Affiliation as printed

   Chair for Algebra and Representation Theory, RWTH Aachen University, Aachen, 52056, Germany

4. Jon Thackray
   Affiliation as printed

   Cambridge, UK