Numerous applications require linear algebra modulo 2, 3, 5 or another very small prime. For example in the study of graphs, p-rank of adjacency matrices is often a useful discriminator. Integer Smith Normal Form computation by modular methods usually has as its greatest challenge the determination of the tiny prime contribution to the invariant factors.

Modular residues may be packed into machine words so that several arithmetic computations are done in one machine instruction. We report on several packing schemes including packing into doubles and using floating point arithmetic, packing into ints and using a combination of int arithmetic and bit operations, finally a scheme called bit-slicing.

We report performance measurements of the packing strategies on several architectures and discuss tuning issues. Finally we discuss the software design concerning the incorporation of such packing in the LinBox C++ template library for exact linear algebra. The question is how to factor the code so that packed and unpacked vectors are equally usable by algorithms that are generic with respect to ground field representation, vector details, and matrix representation.