Algorithm for calculating $A^n$ with as few multiplications as possible

Solution 1:

There seems to be no efficient algorithm for this. Quoting Wikipedia on Addition-chain exponentiation:

… the addition-chain method is much more complicated, since the determination of a shortest addition chain seems quite difficult: no efficient optimal methods are currently known for arbitrary exponents, and the related problem of finding a shortest addition chain for a given set of exponents has been proven NP-complete. Even given a shortest chain, addition-chain exponentiation requires more memory than the binary method, because it must potentially store many previous exponents from the chain simultaneously. In practice, therefore, shortest addition-chain exponentiation is primarily used for small fixed exponents for which a shortest chain can be precomputed and is not too large.

On the same page, however, it does link to a reference* of some methods better than binary exponentiation.

One simple example is to use base-N number instead of base-2. e.g. for A⁵¹⁰,

with binary:   2 = 1 + 1
               3 = 2 + 1
               6 = 3 + 3
               7 = 6 + 1
              14 = 7 + 7
              15 = 14 + 1
              30 = 15 + 15
              31 = 30 + 1
              62 = 31 + 31
              63 = 62 + 1
             126 = 63 + 63
             127 = 126 + 1
             254 = 127 + 127
             255 = 254 + 1
             510 = 255 + 255   (15 multiplications)

with base-8:   2 = 1 + 1
               3 = 2 + 1
               4 = 3 + 1
               5 = 4 + 1
               6 = 5 + 1
               7 = 6 + 1
              14 = 7 + 7
              28 = 14 + 14
              56 = 28 + 28
              63 = 56 + 7
             126 = 63 + 63
             252 = 126 + 126
             504 = 252 + 252
             510 = 504 + 6      (14 multiplications)

with base-4:   2 = 1 + 1
               3 = 2 + 1
               4 = 2 + 2
               7 = 4 + 3
              14 = 7 + 7
              28 = 14 + 14
              31 = 28 + 3
              62 = 31 + 31
             124 = 62 + 62
             127 = 124 + 3
             254 = 127 + 127
             508 = 254 + 254
             510 = 508 + 2      (13 multiplications)

(I don't know how to choose the optimal N.)

_{*: Daniel M. Gordon, A survey of fast exponentiation methods, Journal of Algorithms 27 (1998), pp 129–146}

Solution 2:

Another option would be to use eigendecomposition . It allows you to raise the eigenvalues in the diagonal of the decomposition A = VDV^-1 to a power. It changes the problem from matrix multiplication to the multiplication of the eigenvalues.

Once in eigendecomposition form you could perform the same addition-chain exponentiation technique but it would be with scalars, not matrices. Much more efficient, because each matrix multiplication has n^3 multiplies, but with ed you would only have n.

More is explained here:

http://en.wikipedia.org/wiki/Matrix_decomposition#Eigendecomposition