MathGroup Archive 2008

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

Search the Archive

Re: Fast evaluation of modified dot product

  • To: mathgroup at smc.vnet.net
  • Subject: [mg86750] Re: [mg86720] Fast evaluation of modified dot product
  • From: Daniel Lichtblau <danl at wolfram.com>
  • Date: Thu, 20 Mar 2008 02:53:34 -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]] ];
> 
> I was wondering if there is a good way to compute z that doesn't
> require a lot of memory.
> 
> Thanks,
> Art.

Can be done with ListCorrelate.

Transpose[Map[ListCorrelate[x, #] &, Transpose[y]]]

Compared to your large list dot product approach, the memory hoofprint 
will be negligeable. Also it is nearly 10x faster.

Daniel Lichtblau
Wolfram Research


  • Prev by Date: Re: Find roots in a limited interval
  • Next by Date: Re: Find roots in a limited interval
  • Previous by thread: Fast evaluation of modified dot product
  • Next by thread: Re: Fast evaluation of modified dot product