       Re: More memory-efficient inner product for large last

• To: mathgroup at smc.vnet.net
• Subject: [mg106901] Re: [mg106870] More memory-efficient inner product for large last
• From: Leonid Shifrin <lshifr at gmail.com>
• Date: Tue, 26 Jan 2010 06:37:10 -0500 (EST)
• References: <201001251009.FAA09421@smc.vnet.net>

```Hi Vince,

I suggest that you use lazy matrix multiplication, which can be implemented
for example as follows:

Clear[dotLazy];
dotLazy[first_?ArrayQ, second_?ArrayQ] :=
With[{fdims = Most@Dimensions@first, sdims = Most@Dimensions@second},
Module[{a, b, plus},
With[{firstSymbolic = Array[a, fdims],
secondSymbolic = Array[b, sdims]},
plus[x_] := x;
plus[x__] /; Length[{x}] =!= 2 := Fold[plus, First@{x}, Rest@{x}];
plus[x_, y_] /; Head[x] =!= Plus :=
Total[{x, y} /. {a[i_, j_] :> first[[i, j]],
a[i_] :> first[[i]], b[i_] :> second[[i]],
b[i_, j_] :> second[[i, j]]}];
firstSymbolic.secondSymbolic /. Plus -> plus]]];

Here is a function to test the memory consumption:

ClearAll[measureMemoryConsumption];
SetAttributes[measureMemoryConsumption, HoldAll];
measureMemoryConsumption[code_, f_] :=
With[{current = MemoryInUse[], mmu =  MaxMemoryUsed[]},
{f[code], MemoryInUse[] - current, MaxMemoryUsed[] - mmu}];

It returns a list of 3 elements, the first being some function <f> applied
the second is a relative increase of unclaimed memory, the third is a peak
increase of memory used
in a computation.

First let us check that my lazy dot function gives the same as yours dot,
for small lists:

In:=
l1 = RandomReal[1., {3, 5}];
l2 = RandomReal[1., {3, 3, 5}];

In:=
dotLazy[l1, l1] === dot[l1, l1, 1]

Out= True

In:=
dotLazy[l2, l1] === dot[l2, l1, 2]

Out= True

In:=
dotLazy[l2, l2] === dot[l2, l2, 2, 2]

Out= True

Now a more serious test:

In:=
l1 = RandomReal[1., {3, 100000}];
l2 = RandomReal[1., {3, 3, 100000}];

In:=
measureMemoryConsumption[dotLazy[l1, l1], Dimensions]

Out= {{100000}, 800384, 5536}

In:=
measureMemoryConsumption[dot[l1, l1, 1], Dimensions]

Out= {{100000}, 248, 0}

In:=
measureMemoryConsumption[dotLazy[l2, l1], Dimensions]

Out= {{3, 100000}, 2400696, 1603800}

In:=
measureMemoryConsumption[dot[l2, l1, 2], Dimensions]

Out= {{3, 100000}, 248, 40796320}

In:=
measureMemoryConsumption[dotLazy[l2, l2], Dimensions]

Out= {{3, 3, 100000}, 7201640, 0}

In:=
measureMemoryConsumption[dot[l2, l2, 2, 2], Dimensions]

Out= {{3, 3, 100000}, 256, 70808608}

As can be seen, my version is less memory-efficient for list-to-list dot
product, but vastly
more efficient for other operations. I did not test on such huge lists as
I don't have so much memory at my disposal at the moment (running Eclipse
and SQLDeveloper),
but I would expect similar effect.

Hope this helps.

Regards,
Leonid

On Mon, Jan 25, 2010 at 1:09 PM, Vince Virgilio <blueschi at gmail.com> wrote:

> Hello,
>
> I need to compute vector-vector, matrix-vector, and matrix-matrix
> inner products, for vectors and matrices whose elements are not
> scalars, but very large lists (~ 1.2M element each). I need Dot[] to
> ignore the last tensor index, but it has no parameter for this, like
> Outer's last "n_i " arguments. So I implemented my own. Unfortunately,
> the matrix-vector and matrix-matrix products consume excessive amounts
> of memory. The matrix-vector product peak memory footprint is ~ 800MB,
> for ~ 110MB total input, and the matrix-matrix product peaks at ~ 1.8
> GB for ~ 180MB input. Apparently, memory overhead is ~ 8-10X.
>
> Here is a trace of system memory use (working set and its peak) for
> the above Mathematica evaluations. My system is Windows 7, 2.5 GHz
> Intel Core 2 Duo, 4GB RAM (Lenove R61 laptop).
>
> http://tinyurl.com/yfgwp26 (PDF ~ 180KB)
>
> Please find below my implementation of "dot", which ignores sublists
> below level 1 or 2 (depends on product type). Can it be made more
> efficient?
>
> Thank you,
>
> Vince Virgilio
>
>
> dot[l1_, l2_, 1] := l1*l2 // Total;
>
> dot[l1_, l2_, 2, n2_: 1] :=
>  ReleaseHold@Dot[Map[Hold, l1, {2}], Map[Hold, l2, {n2}]];
>
> In:= l1 = RandomReal[1., {3, 1200000}];
> l2 = RandomReal[1., {3, 3, 1200000}];
>
> In:= ByteCount@l1
>
> Out= 28800128
>
> In:= ByteCount@l2
>
> Out= 86400132
>
> (* Vector-Vector inner product *)
>
> In:= l3 = dot[l1, l1, 1];
> Dimensions@l3
>
> Out= {1200000}
>
> (* Matrix-Vector inner product *)
>
> l4 = dot[l2, l1, 2]; (* Memory use peaks @ ~ 800 MB *)
>
> In:= Dimensions@l4
>
> Out= {3, 1200000}
>
> (* Matrix-Matrix inner product *)
>
> l5 = dot[l2, l2, 2, 2]; (* Memory use peaks @ ~ 1.8 GB! *)
>
> In:= Dimensions@l5
>
> Out= {3, 3, 1200000}
>
>

```

• Prev by Date: Re: FindMaximum/NMaximize vs. Excel Solver
• Next by Date: Re: Re: Re: looping
• Previous by thread: Re: More memory-efficient inner product for large last
• Next by thread: Re: More memory-efficient inner product for large last