Re: Matrix multiplication speed up
- To: mathgroup at smc.vnet.net
- Subject: [mg83065] Re: Matrix multiplication speed up
- From: dh <dh at metrohm.ch>
- Date: Fri, 9 Nov 2007 05:15:23 -0500 (EST)
- References: <fgs87d$3uh$1@smc.vnet.net>
Hi Frank,
you wrote that you want to preserve the ordering of the terms in the
product. This may be done by defining a new multiply that is not
commutative, lets call it CircleTimes. We want Circle Times to be
distributive, what we must define. For convenience we define a new Dot
operator using CircleTimes. Here is a small example:
CircleTimes[x2_,x3_+x4__]:=CircleTimes[x2,x3]+CircleTimes[x2,x4];
CircleTimes[x2_+x3_,x4__]:=CircleTimes[x2,x4]+CircleTimes[x3,x4];
myDot[x1_,x2_]:=Inner[CircleTimes,x1,x2,Plus]
X1=Array[a,{3,3}];
X2=Array[b,{3,3}];
X3=Array[c,{3,3}];
X12=myDot[X1,X2]
X123=myDot[X12,X3]
hope this helps, Daniel
Frank Brand wrote:
> Dear mathgroup members,
>
> is anyone out there being able to help me with the following problem.
>
> I need to analyze iteratively the powers of large matrices (not
> necessarily sparse). Finally I came up with the following approach in
> order to avoid symbolic calculation:
>
> 1.
> Describe the components of the matrices via the index pair {i,j} like
>
> n = 3;
> AInd = Table[{{{i, j}}}, {i, 1, n}, {j, 1, n}]
> BInd = Table[{{{i, j}}}, {i, 1, n}, {j, 1, n}]
>
> 2.
> Declaration of the "matrix product" with
>
> MatProd = Table[0, {i, 1, n}, {j, 1, n}];
>
> Do[
> Do[
> MatProd[[i, k]] =
> Flatten[Table[
> Map[Map[Partition[Flatten[#], 2] &,
> Tuples[{{#}, BInd[[j, k]]}]] &, AInd[[i, j]]], {j, 1, n}],
> 2]
> ,
> {k, 1, n}
> ]
> ,
> {i, 1, n}
> ];
>
> MatProd
>
> 3.
> The result ist exactly what we expect, namely
>
> {{{{{1, 1}, {1, 1}}, {{1, 2}, {2, 1}}, {{1, 3}, {3, 1}}}, {{{1,
> 1}, {1, 2}}, {{1, 2}, {2, 2}}, {{1, 3}, {3, 2}}}, {{{1, 1}, {1,
> 3}}, {{1, 2}, {2, 3}}, {{1, 3}, {3, 3}}}}, {{{{2, 1}, {1,
> 1}}, {{2, 2}, {2, 1}}, {{2, 3}, {3, 1}}}, {{{2, 1}, {1, 2}}, {{2,
> 2}, {2, 2}}, {{2, 3}, {3, 2}}}, {{{2, 1}, {1, 3}}, {{2, 2}, {2,
> 3}}, {{2, 3}, {3, 3}}}}, {{{{3, 1}, {1, 1}}, {{3, 2}, {2,
> 1}}, {{3, 3}, {3, 1}}}, {{{3, 1}, {1, 2}}, {{3, 2}, {2, 2}}, {{3,
> 3}, {3, 2}}}, {{{3, 1}, {1, 3}}, {{3, 2}, {2, 3}}, {{3, 3}, {3,
> 3}}}}}
>
> BUT for large matrices and/or large exponents this approach is slow.
>
> How can this method be accelerated?
>
> Thanks very much in advance
> Frank
>
>
>
>
>
>