Services & ResourcesWolfram ForumsMathGroup Archive

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

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?

Thanks very much in advance
Frank