Evaluate Squaring Improvement by Marco Bodrato

[Former user]

Marco Bodrato wrote:

"I've found a sequence that can giv some small improvements (in the linear part, not asymptotically) for matrix squaring. As a test for those sequences, I took your "strassen.c" for the M4RI library and modified it to apply the operations I propose. For the general product, the new code should be "as fast as" the old one (and maybe there is no need for the new sequence). For matrix squaring (C=A*A) it should give a small speed-up (around 1%)."

Code:

http://bodrato.it/software/strassen.html#M4R

Description

http://marco.bodrato.it/papers/Bodrato2008-StrassenLikeMatrixMultiplicationForSquares.pdf

[Martin Albrecht]

Committed in Wiki macro error: Changeset 297b5e5f9691 not found. with the following results on a Core2Duo CPU:

orig multiplication (geom)

dim	min	avg	med	max
10000	1.510	1.522	1.520	1.550
16384	5.650	5.654	5.650	5.700
20000	10.890	10.933	10.940	10.940
32000	39.830	39.989	39.990	40.210

new multiplication (geom)

dim	min	avg	med	max
10000	1.520	1.523	1.520	1.550
16384	5.690	5.694	5.690	5.720
20000	10.860	10.901	10.900	10.910
32000	39.870	39.952	39.950	40.090

orig squaring (geom)

dim	min	avg	med	max
10000	1.490	1.499	1.500	1.530
16384	5.640	5.649	5.650	5.690
20000	10.900	10.911	10.910	10.930
32000	39.800	39.955	39.930	40.260

new squaring (geom)

dim	min	avg	med	max
10000	1.460	1.464	1.460	1.490
16384	5.560	5.569	5.570	5.580
20000	10.630	10.680	10.680	10.690
32000	39.330	39.409	39.420	39.590

[Martin Albrecht]

Opteron Timings

old multiplication

dim	min	avg	med	max
10000	2.580	2.616	2.620	2.708
16384	10.097	10.525	10.633	10.753
20000	18.413	18.635	18.677	18.849
32000	67.784	68.484	68.520	69.412

new multiplication

dim	min	avg	med	max
10000	2.620	2.630	2.624	2.676
16384	10.245	10.491	10.577	10.737
20000	18.557	18.773	18.817	19.037
32000	67.972	68.885	68.960	69.704

old squaring

dim	min	avg	med	max
10000	2.644	2.660	2.652	2.696
16384	10.353	10.738	10.837	11.013
20000	18.205	18.526	18.581	18.973
32000	68.120	69.360	69.760	70.236

new squaring

dim	min	avg	med	max
10000	2.568	2.600	2.596	2.652
16384	10.201	10.445	10.573	10.585
20000	18.125	18.534	18.629	18.685
32000	66.856	68.211	68.308	68.952

[Martin Albrecht]

Opteron Timings

old multiplication

dim	min	avg	med	max
10000	2.580	2.616	2.620	2.708
16384	10.097	10.525	10.633	10.753
20000	18.413	18.635	18.677	18.849
32000	67.784	68.484	68.520	69.412

new multiplication

dim	min	avg	med	max
10000	2.620	2.630	2.624	2.676
16384	10.245	10.491	10.577	10.737
20000	18.557	18.773	18.817	19.037
32000	67.972	68.885	68.960	69.704

old squaring

dim	min	avg	med	max
10000	2.644	2.660	2.652	2.696
16384	10.353	10.738	10.837	11.013
20000	18.205	18.526	18.581	18.973
32000	68.120	69.360	69.760	70.236

new squaring

dim	min	avg	med	max
10000	2.568	2.600	2.596	2.652
16384	10.201	10.445	10.573	10.585
20000	18.125	18.534	18.629	18.685
32000	66.856	68.211	68.308	68.952