[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
-><-