[Date Index] [Thread Index] [Author Index]

Re: Fast evaluation of modified dot product

• To: mathgroup at smc.vnet.net
• Subject: [mg86747] Re: [mg86720] Fast evaluation of modified dot product
• From: Carl Woll <carlw at wolfram.com>
• Date: Thu, 20 Mar 2008 02:53:01 -0500 (EST)
• References: <200803191026.FAA05128@smc.vnet.net>

Art wrote:

>I have (below) a vector x and matrix y and would like to compute z
>efficiently:
>
>{n, m, b} = {10000, 100, 10};  (* n >> m > b *)
>x = RandomReal[{-1.,1.}, n - b +1]
>y = RandomChoice[{-1,1}, {n, m}];
>
>w = Partition[y, b, 1];
>z = Dot[x, w];
>
>I have to compute z for many different x with w fixed. For large n, w
>becomes prohibitively big.
>
>Doing the below is much slower but doesn't require large memory
>allocation:
>
>z2 = Fold[(#1 + x[[#2]] y[[#2;;#2+b-1]]) &, 0., Range[Length[x]] ];
>  
>
This is slow because y is not packed. If you use:

y = Developer`ToPackedArray@RandomChoice[{-1,1}, {n,m}];

and then run z2, it will be a bit faster than your Dot approach.

>I was wondering if there is a good way to compute z that doesn't
>require a lot of memory.
>
>Thanks,
>Art.
>  
>
If speed is a major concern, and you don't mind a bit more memory usage, 
then ListCorrelate might be a good option:

In[1]:= MemoryInUse[]
MaxMemoryUsed[]

Out[1]= 5850248
Out[2]= 7176816

Your x, y modified to pack y:

In[3]:= {n, m, b} = {10000, 100, 5};(*n>>m>b*)
x = RandomReal[{-1., 1.}, n - b + 1];
y = Developer`ToPackedArray@RandomChoice[{-1, 1}, {n, m}];

In[5]:= MemoryInUse[]
MaxMemoryUsed[]

Out[5]= 10861576

Out[6]= 19951840

Using ListCorrelate:

In[7]:= z3 = Transpose@ListCorrelate[{x}, Transpose@y]; // Timing

Out[7]= {0.031,Null}

In[8]:= MemoryInUse[]
MaxMemoryUsed[]

Out[8]= 11210072

Out[9]= 23306376

An increase of a bit more than 3 MB in max memory used. The results 
aren't identical, because of the vagaries of machine arithmetic, but z3 
runs about 15 times faster on my machine.

Carl Woll
Wolfram Research

• References:
  • Fast evaluation of modified dot product
    • From: Art <grenander@gmail.com>