LinBox Code Sample

As part of my project application, the Lmonade developers asked for a
small code sample. I've posted it below. The code is very simple and
not suitable for production use but will compile and run, and helps to
illustrate the LinBox interface and some basic OpenMP use.

The program multiplies two matrices together in parallel using a
single round of Strassens algorithm to split up the work.

Known Bugs:

  - To keep things simple there are no recursive calls, so only a
    maximum of 7 cores will be used.

  - strassen() doesn't check to ensure that the input matrices are
    square and 2n*2n.

  - The locking mechanism could be made significantly more efficient
    with some finer grained locks.

Introductions

This blog will contain status updates on my Google Summer of Code
(GSoC) project "Parallel Computation of Matrix Invariant Factors in
LinBox".

My plan is to implement an algorithm for determining the invariant
factors of a matrix by the Block-Wiedemann algorithm. Some key
details:

  - All of this is being done in LinBox, so a lot of
    the scaffolding is already in place.

  - The input matrix A will be big, sparse and populated by elements
    drawn from a finite field.

  - The real focus of this project is not just to compute invariant
    factors, but to do so fast. To help that along I'm going to use
    shared memory parallelism via OpenMP. Making things work
    efficiently in parallel is almost always harder than you expect,
    so this will most likely be the most time-consuming part of the
    project.

More specifics can be found in my proposal here, and new posts will
appear here as the project progresses.