Services & ResourcesWolfram ForumsMathGroup Archive

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

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

• References:
  • Matrix multiplication speed up
    • From: Frank Brand <frank.brand@t-online.de>