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