Newbie : innerproduct function from Numarray

[Ohkyu Yoon]

I have two vectors that have about 2000 elements.
I need to calculate the innerproducts of those vectors 2000 times where
one of them cycles left(ie 1234, then 2341, then 3412, etc)
Basically, I want to calculate A*x, where A is a left-circulant cyclic
matrix,
and x is a vector.

I tried it two ways.
vector1 & vector2 are lists.

1)
from Numarray import innerproduct
output = []
temp = vector1 + vector1 # temp is twice the length of vector1
for i in range(2000):
output.append(innerproduct(temp[ii+2000)],vector2)
2)
output = []
temp = vector1 + vector1
for i in range(2000):
sum = 0
for j in range(2000):
sum += temp[i+j] * vector2[j]
output.append(sum)

I thought the first method using Numarray should be faster.
But it looks like the second method is faster.
Am I doing anything wrong?
Do you guys know any faster way to do this?

Thank you.

 

[Diez B. Roggisch]

1)

from Numarray import innerproduct
output = []
temp = vector1 + vector1 # temp is twice the length of vector1
for i in range(2000):
output.append(innerproduct(temp[ii+2000)],vector2)
2)
output = []
temp = vector1 + vector1
for i in range(2000):
sum = 0
for j in range(2000):
sum += temp[i+j] * vector2[j]
output.append(sum)

I thought the first method using Numarray should be faster.
But it looks like the second method is faster.
Am I doing anything wrong?
Do you guys know any faster way to do this?

First of all, I assume that both results are equal

From the numarray-docs:

----
innerproduct(a, b)
innerproduct produces the inner product of arrays a and b. It is equivalent
to matrixmultiply(a, transpose(b)).
----

I'm not sure what this means mathematically (I understand the operation
made, but I'm not sure what an inner product _means_).

However, what you do with your hand-written code doesn't look like what I
would write if I would come up with my own implementation of the
aforementioned definition of innerproduct. Matrix-multiplication is
O(n**3), while your code is in O(n**2). So it seems that your special-case
with vectors, not arrays, produces an easier to compute variant of
innerproduct - and the differenes of n-times is of course important.

BTW: Its better to use xrange instead of range, it won't create the actual
list of numbers, but an iterable object instead - saves memory and time

Diez

 

[David M. Cooke]

I have two vectors that have about 2000 elements.
I need to calculate the innerproducts of those vectors 2000 times where
one of them cycles left(ie 1234, then 2341, then 3412, etc)
Basically, I want to calculate A*x, where A is a left-circulant cyclic
matrix,
and x is a vector.

I tried it two ways.
vector1 & vector2 are lists.

^^^^^^

This is your problem: everytime you pass these to innerproduct, it
turns them into arrays (which, with the current version of numarray,
is a relatively expensive operation).

Try something like

import numarray as na
output = []
vector1 = na.array(vector1)
vector2 = na.array(vector2)
temp = na.concatenate((vector1,vector1)) # temp is twice the length of vector1
for i in range(2000):
output.append(na.innerproduct(temp[ii+2000)],vector2)

This uses arrays always.

You might be better off explicity constructing your left-circulant
cyclic matrix A, and doing the full matrix multiply -- for this size
of matrix, the multiply is going to be fast (because it's going to be
done by code written in C, and, depending on how you set it up, using
an optimized BLAS routine).

 

[Colin J. Williams]

I have two vectors that have about 2000 elements.
I need to calculate the innerproducts of those vectors 2000 times where
one of them cycles left(ie 1234, then 2341, then 3412, etc)
Basically, I want to calculate A*x, where A is a left-circulant cyclic
matrix,
and x is a vector.

I tried it two ways.
vector1 & vector2 are lists.

1)
from Numarray import innerproduct
output = []
temp = vector1 + vector1 # temp is twice the length of vector1
for i in range(2000):
output.append(innerproduct(temp[ii+2000)],vector2)
2)
output = []
temp = vector1 + vector1
for i in range(2000):
sum = 0
for j in range(2000):
sum += temp[i+j] * vector2[j]
output.append(sum)

I thought the first method using Numarray should be faster.
But it looks like the second method is faster.
Am I doing anything wrong?
Do you guys know any faster way to do this?

Thank you.

You might consider something like the following:

# ohkyu.py a sliding cross-product
import numarray as N
_nc= N.numarraycore
_nt= N.numerictypes
import numarray.random_array.RandomArray2 as _ra


# The sliding array
a= _nc.zeros(shape= (2, 10), type= _nt.Float64)
b= _nc.arange(10, shape= (10,), type= _nt.Float64) # data for the
sliding array
a+= b # the data from b is broadcast to both rows
print a # to show the 'wraparound'

a.ravel() # the second row is appended to the first
c= _ra.random(shape= (10,)) # data for the fixed array
for i in range(10):
z= _nc.dot(a[i:i+10], c)
print i, z

I would be interested to know how the time compares.

Colin W.

 

[Ohkyu Yoon]

Wow! Thank you all.
My program runs super fast now.
The biggest problem was changing lists into arrays.
By starting with arrays, the program runs almost infinitely faster.

Ohkyu