Multiplying dense matrices with large integer coefficients
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
) and matrix computations (e.g. LinBox
) 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:
Example: the matrix
- 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).
will be stored in a file as
Usage: To compute the produte C = A × B:
matmul A B C
where the arguments A, B and C are files storing matrices
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
. The challenge is to compute the product A × B
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