Linear algebra computations modulo tiny primes: purposes, theory, implementation


Séminaire Modèles et Algorithmes Déterministes: CASYS

19/06/2014 - 09:45 Mr B. David Saunders Salle 1 - Tour IRMA

I will discuss some problems which require memory and time efficient computations modulo 2 or 3.  One of these is to determine the ranks of a family of sparse matrices, one for each order n, where n is an odd power of 3.  I will describe the graph theoretic context in which this family arises.
To solve such problems we need the techniques of blackbox linear algebra, specifically block blackbox algorithms.  These are probabilistic algorithms.  I will report some sharpened bounds for the probability of error which lead to efficient implementations with high probability of success.  In addition, matrices with entries 0,1,2 in GF(3) may be stored with 2 bits per entry, many entries per word.  These two factors -- improved probability bounds and bit packing -- give us a a better range of algorithmic choices as we deploy parallelism both at coarse  and fine grained levels.  I will also discuss some of the library design issues for integrating these techniques into the C++ exact linear algebra library, LinBox.