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
- References:
- Fast evaluation of modified dot product
- From: Art <grenander@gmail.com>
- Fast evaluation of modified dot product