Multiplying dense matrices with large integer coefficients
Problem specification
The problem is to compute as quickly as possible the product of two square integer matrices. The size of an instance is depending on both the matrix order, and the bit size of the coefficients in the matrix.
The participants are free to use any piece of software for integer arithmetic (e.g.
The GMP library or
MPIR) and matrix computations (e.g.
LinBox,
FFLAS-FFPACK) or any other library of their choice.
Specification of the program input/output
The participant must provide a program with the following specification:
-
Matrix file storage format: a m×n matrix will be stored in a 1 + m×n lines file:
- First line: nrows ncols
- Each of the following lines will contain one coefficient. They are read from the matrix following the row-major order: line ((i - 1)×ncols + j) + 1 contains the coefficient (i, j) of the matrix (indices starting at 1).
Example: the matrix
will be stored in a file as
2 3
1
2
3
4
1515
6
-
Usage: To compute the produte C = A × B:
matmul A B C
where the arguments A, B and C are files storing matrices
Reference implementation
We provide a naive sequential implementation using GMP:
intmatmul.cpp.
Library of instances
For each of the following instances, sorted by increasing difficulty, we provide the two matrices
A
and
B. The challenge is to compute the product
A × B.
n is the matrix dimension and
b is the size in bits of
the largest coefficient.
- Instance 1: n=100, b=10000 A, B
- Instance 2: n=1000, b=200 A, B
- Instance 3: n=10000, b=8,60 A, B
- Instance 4: n=7000, b=50 A, B
