Re: Matrix multiplication speed up

• To: mathgroup at smc.vnet.net
• Subject: [mg83098] Re: [mg83072] Matrix multiplication speed up
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Sat, 10 Nov 2007 03:46:53 -0500 (EST)
• References: <fgs87d\$3uh\$1@smc.vnet.net> <200711091019.FAA12171@smc.vnet.net>

```Frank Brand wrote:
>   Hi all,
>
> thanks for responding!
> I should be more precise in what Iï¿½m looking for.
> What I'm especially interested in is the preserved order of  FACTORS in
> the sums of the components of the resulting product of the two matrices,
> so e.g.
> I'd like to have a[2,1]*a[27,3]*a[1,5] instead of a[1,5]*a[2,1]*a[27,3]
> (Mathematica's natural order), because I'm interested in the resulting
> index sets like {2, 1, 27, 3, 1, 5}.
> Do you have any idea how to realize this?
>
> Greetings
> Frank

I don't guarantee but possibly what you want can be done more or less as
below. Also I don't guarantee efficiency. We'll use a dummy head,
mylist, so as to avoid dimension issues with Inner.

aInd = Table[mylist[i,j], {i,1,n}, {j,1,n}];
bInd = Table[mylist[i,j], {i,1,n}, {j,1,n}];

We'll use a rule to denest this dummy head.

rul =  mylist[a__ /; !FreeQ[{a},mylist]] :>
mylist[(foo[a] /. mylist->List) /. foo:>Sequence];

I think this gives something along the lines desired.

In[82]:= InputForm[res1 = Inner[List,aInd,bInd,mylist] /. rul]
Out[82]//InputForm=
{{mylist[{{1, 1}, {1, 1}}, {{1, 2}, {2, 1}}, {{1, 3}, {3, 1}}],
mylist[{{1, 1}, {1, 2}}, {{1, 2}, {2, 2}}, {{1, 3}, {3, 2}}],
mylist[{{1, 1}, {1, 3}}, {{1, 2}, {2, 3}}, {{1, 3}, {3, 3}}]},
{mylist[{{2, 1}, {1, 1}}, {{2, 2}, {2, 1}}, {{2, 3}, {3, 1}}],
mylist[{{2, 1}, {1, 2}}, {{2, 2}, {2, 2}}, {{2, 3}, {3, 2}}],
mylist[{{2, 1}, {1, 3}}, {{2, 2}, {2, 3}}, {{2, 3}, {3, 3}}]},
{mylist[{{3, 1}, {1, 1}}, {{3, 2}, {2, 1}}, {{3, 3}, {3, 1}}],
mylist[{{3, 1}, {1, 2}}, {{3, 2}, {2, 2}}, {{3, 3}, {3, 2}}],
mylist[{{3, 1}, {1, 3}}, {{3, 2}, {2, 3}}, {{3, 3}, {3, 3}}]}}

Also it can be iterated.

In[83]:= InputForm[res2 = Inner[List,aInd,res1,mylist] /. rul]

Out[83]//InputForm=
{{mylist[{{1, 1}, {{{1, 1}, {1, 1}}, {{1, 2}, {2, 1}}, {{1, 3}, {3, 1}}}},
{{1, 2}, {{{2, 1}, {1, 1}}, {{2, 2}, {2, 1}}, {{2, 3}, {3, 1}}}},
{{1, 3}, {{{3, 1}, {1, 1}}, {{3, 2}, {2, 1}}, {{3, 3}, {3, 1}}}}],
mylist[{{1, 1}, {{{1, 1}, {1, 2}}, {{1, 2}, {2, 2}}, {{1, 3}, {3, 2}}}},
{{1, 2}, {{{2, 1}, {1, 2}}, {{2, 2}, {2, 2}}, {{2, 3}, {3, 2}}}},
{{1, 3}, {{{3, 1}, {1, 2}}, {{3, 2}, {2, 2}}, {{3, 3}, {3, 2}}}}],
mylist[{{1, 1}, {{{1, 1}, {1, 3}}, {{1, 2}, {2, 3}}, {{1, 3}, {3, 3}}}},
{{1, 2}, {{{2, 1}, {1, 3}}, {{2, 2}, {2, 3}}, {{2, 3}, {3, 3}}}},
{{1, 3}, {{{3, 1}, {1, 3}}, {{3, 2}, {2, 3}}, {{3, 3}, {3, 3}}}}]},
{mylist[{{2, 1}, {{{1, 1}, {1, 1}}, {{1, 2}, {2, 1}}, {{1, 3}, {3, 1}}}},
{{2, 2}, {{{2, 1}, {1, 1}}, {{2, 2}, {2, 1}}, {{2, 3}, {3, 1}}}},
{{2, 3}, {{{3, 1}, {1, 1}}, {{3, 2}, {2, 1}}, {{3, 3}, {3, 1}}}}],
mylist[{{2, 1}, {{{1, 1}, {1, 2}}, {{1, 2}, {2, 2}}, {{1, 3}, {3, 2}}}},
{{2, 2}, {{{2, 1}, {1, 2}}, {{2, 2}, {2, 2}}, {{2, 3}, {3, 2}}}},
{{2, 3}, {{{3, 1}, {1, 2}}, {{3, 2}, {2, 2}}, {{3, 3}, {3, 2}}}}],
mylist[{{2, 1}, {{{1, 1}, {1, 3}}, {{1, 2}, {2, 3}}, {{1, 3}, {3, 3}}}},
{{2, 2}, {{{2, 1}, {1, 3}}, {{2, 2}, {2, 3}}, {{2, 3}, {3, 3}}}},
{{2, 3}, {{{3, 1}, {1, 3}}, {{3, 2}, {2, 3}}, {{3, 3}, {3, 3}}}}]},
{mylist[{{3, 1}, {{{1, 1}, {1, 1}}, {{1, 2}, {2, 1}}, {{1, 3}, {3, 1}}}},
{{3, 2}, {{{2, 1}, {1, 1}}, {{2, 2}, {2, 1}}, {{2, 3}, {3, 1}}}},
{{3, 3}, {{{3, 1}, {1, 1}}, {{3, 2}, {2, 1}}, {{3, 3}, {3, 1}}}}],
mylist[{{3, 1}, {{{1, 1}, {1, 2}}, {{1, 2}, {2, 2}}, {{1, 3}, {3, 2}}}},
{{3, 2}, {{{2, 1}, {1, 2}}, {{2, 2}, {2, 2}}, {{2, 3}, {3, 2}}}},
{{3, 3}, {{{3, 1}, {1, 2}}, {{3, 2}, {2, 2}}, {{3, 3}, {3, 2}}}}],
mylist[{{3, 1}, {{{1, 1}, {1, 3}}, {{1, 2}, {2, 3}}, {{1, 3}, {3, 3}}}},
{{3, 2}, {{{2, 1}, {1, 3}}, {{2, 2}, {2, 3}}, {{2, 3}, {3, 3}}}},
{{3, 3}, {{{3, 1}, {1, 3}}, {{3, 2}, {2, 3}}, {{3, 3}, {3, 3}}}}]}}

This really makes my head hurt.

Daniel Lichtblau
Wolfram Research

```

• Prev by Date: variable capture issues with Module, Block and pure/defined functions
• Next by Date: Re: ContourPlot Problem
• Previous by thread: Matrix multiplication speed up
• Next by thread: Re: Matrix multiplication speed up