MathGroup Archive 2007

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

Search the Archive

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

> 

> 

> 

> 

> 

> 




  • Prev by Date: Simulate finite-state process with RandomChoice
  • Next by Date: Re: machine precision number plot fixed in V6?
  • Previous by thread: Re: Matrix multiplication speed up
  • Next by thread: Re: Matrix multiplication speed up