Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: More memory-efficient inner product for large last

• To: mathgroup at smc.vnet.net
• Subject: [mg106941] Re: [mg106870] More memory-efficient inner product for large last
• From: "Vincent N. Virgilio" <virgilio at ieee.org>
• Date: Fri, 29 Jan 2010 07:45:25 -0500 (EST)
• References: <201001251009.FAA09421@smc.vnet.net>

Leonid,

Here's what I settled on. It's your implementation, without the withs, and a
couple of final integral arguments, which mimic Outer's. I don't think it
sacrifices much if any efficiency.

dot[first_?ArrayQ, second_?ArrayQ, n1_:2, n2_:1] :=
Module[{plus, a, b,
        fdims = Dimensions@first  // If[ArrayDepth@first  > n1, Most@#, #]&,
        sdims = Dimensions@second // If[ArrayDepth@second > n2, Most@#,
#]&},

    plus[x_, y_] := Total[{x, y} /. {z_a :> ( first[[##]]& @@ z),
                                     z_b :> (second[[##]]& @@ z)}];
    plus[x__] := Fold[plus, First@{x}, Rest@{x}];

    Array[a, fdims] . Array[b, sdims] /. Plus -> plus
];

Thanks again.

Vince

On Mon, Jan 25, 2010 at 11:54 AM, Leonid Shifrin <lshifr at gmail.com> wrote:

> Vince,
>
> Actually I must apologize. The intended code was
>
> 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]]];
>
> which is different from the one I posted by plus[x_, y_] /; Head[x] =!=
> plus instead of
> plus[x_, y_] /; Head[x] =!= Plus (plus vs Plus). This was intended to avoid
> infinite recursion
> for cases like plus[plus[1,2],3], but actually, due to the way Fold wroks,
> this is unnecessary
> alltogether. Likewise, the rule plus[x_]:=x is an unnecessary garbage. Some
> intermediate variables
> can also be skipped. The following will work  just as well, while being a
> bit more concise:
>
>
> Clear[dotLazy];
> dotLazy[first_?ArrayQ, second_?ArrayQ] :=
>  Module[{fdims, sdims, firstSymbolic, secondSymbolic, a, b, plus},
>   plus[x_, y_] :=   Total[{x, y} /. {z_a :> (first[[##]] & @@ z),
>       z_b :> (second[[##]] & @@ z)}];
>   plus[x__] := Fold[plus, First@{x}, Rest@{x}];
>   Dot @@ MapThread[
>      Array, {{a, b}, Most@Dimensions@# & /@ {first, second}}] /.
>    Plus :> plus]
>
>
>
> Regards,
> Leonid
>
>
>
>
>
> On Mon, Jan 25, 2010 at 5:53 PM, Vincent N. Virgilio <virgilio at ieee.org>wrote:
>
>>
>>
>> On Mon, Jan 25, 2010 at 9:16 AM, Leonid Shifrin <lshifr at gmail.com> wrote:
>>
>>> Hi Vince,
>>>
>>> I suggest that you use lazy matrix multiplication, which can be
>>> implemented for example as follows:
>>>
>>>
>>>
>> SNIP
>>
>>
>>> 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
>>> your original ones since
>>> 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
>>>
>>>
>> Leonid,
>>
>> Phenomenal work! Yours saved ~ 1.5GB RAM over mine (for 1.2M elements).
>>
>> Thank you very much.
>>
>> Vince Virgilio
>>
>>
>>
>

• References:
  • More memory-efficient inner product for large last dimension?
    • From: Vince Virgilio <blueschi@gmail.com>