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>