Matrix multiplication speed up

• To: mathgroup at smc.vnet.net
• Subject: [mg83013] Matrix multiplication speed up
• From: Frank Brand <fbrand at fhw-berlin.de>
• Date: Wed, 7 Nov 2007 06:35:02 -0500 (EST)

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?