LinBox is a C++ library that supports high-performance linear algebra routines over integers, rationals, and finite fields and rings. In this paper, the authors demonstrate how the LinBox design can be “adapted for distributed and multi-core computation.”

The authors point out that many linear algebra routines can be sped up by parallel processing, specifically by using a chip in which multiple cores can share their cache. An example of such an operation is computation by modular arithmetic, in which the arithmetic is first performed using small primes, and then the results are combined using the Chinese Remainder Theorem. As the authors say, this is “pleasantly parallelizable.” However, not all linear algebra routines are immediately parallelizable in this sense, and it may be that some of the algorithms used in LinBox may need to be rewritten in order to take advantage of parallel processing.

The authors report on some initial experiments with four processors, operating on sparse matrices and with modular computations; some significant efficiency (50 to 75 percent) is also discussed.

Although this is only an initial report, the authors claim that their experiments indicate that significant efficiency can be obtained by parallelizing LinBox--when particular attention is paid to careful design of the algorithms and the kernels, and to optimizing memory cache.

This work represents the attention being given to the interface between software and hardware; we can look forward to more reports as this research matures.