[Shootout-list] Proposal: revised matrix multiplication test

Aaron Denney wnoise@ofb.net
Wed, 3 Nov 2004 21:41:33 +0000 (UTC)


I'm proposing a new matrix multiplication test, with two parameters:
a square matrix M, and an integer N.  The program must print out M^(2^N).

(Note that this is doable with O(N) matrix multiplications: repeated
squaring gets all powers of 2.  M^N is doable asymptotically in log(N)
time, using this trick.)

N is given on the command line, and the matrix is given on standard
input, in the form dimension D on the first line, and then D lines
each having D numbers being the elements of the matrix in row-major
order.

To avoid differences in handling overflow between implementations, I
would suggest using a signed permutation matrix[1] to test, though the code
must, of course, work on any square matrix.

Rationale:
The current tests relies on doing the same work multiple times, in order
to get the times high enough to get reliable measurements.  Rather
than this, I would prefer that all the work actually be necessary.

Alternatives:
It's not strictly necessary that we read in the matrix.  Like the
current test, we could have a parametrized family of matrices depending
on the dimension D.  We would, of course, want to pick a family that
avoids overflow for high N.

[1] each row and column is zero, except for one entry which may be
    either plus or minus one.  There are D!*2^D different ones.

-- 
Aaron Denney
-><-