MathGroup Archive 2007

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

Search the Archive

Re: Matrix multiplication speed up

  • To: mathgroup at smc.vnet.net
  • Subject: [mg83026] Re: Matrix multiplication speed up
  • From: Szabolcs Horvát <szhorvat at gmail.com>
  • Date: Thu, 8 Nov 2007 06:04:59 -0500 (EST)
  • References: <fgs87d$3uh$1@smc.vnet.net>

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?
> 

Your code looks quite complicated (certainly more complicated than it 
should be ... as a starting point, why not use a single Table instead of 
that double Do with assignments?), and it's completely uncommented, so I 
did not take the time to figure out what it does.

But since you are talking about powers of matrices ... would the 
following help?
NestList[#.mat &, mat, 10]

Also take a look at Inner[], which is a generalization of matrix products.

Szabolcs


  • Prev by Date: Re: Re: ListPointPlot3D
  • Next by Date: Re: Can you get a package back to a notebook easily?
  • Previous by thread: Matrix multiplication speed up
  • Next by thread: Re: Matrix multiplication speed up