[Numeric] column vector faster than row vector in mat multiply?

[Zhang Le]

Hi,
I did a small benchmark of matrix-vector multiply operation using
Numeric module. I'm a bit suprised to find matrix*col-vector is much
faster than row-vector*matrix. I wonder whether other people have
observed this fact too, and why?

Below is the code I used, with output from my machine.

python bench.py
running 1000 iterations of matrix multiply of row 1000-vector
10.5609340668 sec
running 1000 iterations of matrix operation of column 1000-vector
4.11953210831 sec

-----code begin-----
import random
import time
from Numeric import *

n = 1000
k = 1000

r = array([ random.gauss(0, 1) for i in range(n)])
c = array([ [random.gauss(0, 1)] for i in range(n)])

M = zeros((n, n), Float)
for i in range(n):
for j in range(n):
M[j] = random.gauss(0, 1)

print 'running %d iterations of matrix multiply of row %d-vector' % (k,
n)
t = time.time()
for i in xrange(k):
matrixmultiply(r, M)
print time.time()-t, 'sec'

print 'running %d iterations of matrix operation of column %d-vector' %
(k, n)
t = time.time()
for i in xrange(k):
matrixmultiply(M, c)
print time.time()-t, 'sec'

------code end----------


Zhang Le

 

[Terry Reedy]

Hi,
I did a small benchmark of matrix-vector multiply operation using
Numeric module. I'm a bit suprised to find matrix*col-vector is much
faster than row-vector*matrix. I wonder whether other people have
observed this fact too,

Yes, common knowledge in numerical analysis community. Using the faster
direction for a particular system as much as possible is part of tuning
linear algebra software.

and why?

I presume that Numeric, like Python, stores matrices by row. So M*v
multiplies contiguous rows by a contiguous vector. Multiplying a vector by
non-contiguous columns requires requires skipping thru the matrix, which
may require more computation and generate more cache misses and page
faults.

Terry J. Reedy