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