15
$\begingroup$

I am interested in calculating the $n$'th power of a $n\times n$ matrix $A$. Suppose we have an algorithm for matrix multiplication which runs in $\mathcal{O}(M(n))$ time. Then, one can easily calculate $A^n$ in $\mathcal{O}(M(n)\log(n))$ time. Is it possible to solve this problem in lesser time complexity?

Matrix entries can, in general, be from a semiring but you can assume additional structure if it helps.

Note: I understand that in general computing $A^m$ in $o(M(n)\log(m))$ time would give a $o(\log m)$ algorithm for exponentiation. But, a number of interesting problems reduce to the special case of matrix exponentiation where m=$\mathcal O(n)$, and I was not able to prove the same about this simpler problem.

Improve this question
$\endgroup$
3
  • $\begingroup$ what are the entries of the matrix? Integers? $\endgroup$
    – Kaveh
    Apr 9, 2012 at 2:43
  • 1
    $\begingroup$ The entries can, in general, be from a semiring but you can assume additional structure if it helps. $\endgroup$
    – Shitikanth
    Apr 9, 2012 at 3:10
  • $\begingroup$ I could not get a reduction from multiplation to squaring from the above proposed method (i.e. using $(A\pm B)^2$). However, using $\left( \begin{array}{cc} 0 & A \\ B & 0 \end{array} \right)^2 $ works. However, this only gives a $\Omega(M(n))$ on computing $A^n$. $\endgroup$
    – Shitikanth
    Apr 13, 2012 at 18:25

2 Answers 2

Reset to default
12
$\begingroup$

If the matrix is diagonalizable then taking the $n$th power can be done in time $$O(D(n)+ n\log n)$$ where $D(n)$ is the time to diagonalize $A$.

Just to complete the details, if $A=P^{-1}DP$ with a diagonal $D$, then $$A^n = (P^{-1}DP)^n = P^{-1}D^nP$$

and $D^n$ can be computed by just taking each element of the diagonal (each eigenvalue of $A$) to the $n$th power.

Improve this answer
$\endgroup$
2
  • 6
    $\begingroup$ Even if the matrix is diagonalizable, the best known algorithms for eigendecomposition take $O(n^3)$ time. Using the Coppersmith-Winograd algorithm, we already have a $O(n^{2.3727}\log(m))$ algorithm for computing $A^m$. $\endgroup$
    – Shitikanth
    Apr 9, 2012 at 5:24
  • 2
    $\begingroup$ (1) The time bound you cite is not by Coppersmith-Winograd (as you probably know). (2) All algorithms of that form only work for rings; they do not work for general semirings (as you allow in your question). $\endgroup$
    – Ryan Williams
    Apr 14, 2012 at 20:36
5
$\begingroup$

One good way out is Singular Value Decomposition SVD. Given an $n\times n$ real matrix $A$ of full rank , SVD splits it apart as $A=U\Sigma U^T$ where $\Sigma$ is a diagonal matrix, in time $O(n^3)$. By the properties of SVD, $A^m = U \Sigma^m U^T$, so only the diagonal matrix need be exponentiated, and this can be done in $O(n\log m)$ time. Performing the final multiplication $U \times \Sigma^m \times U^T$ takes $O(n^{2.3727})$, so we have altogether $O(n^3 + n \log m)$ operations.

Update after comment The point is that once the SVD is found, any power takes only $O(n^{2.3727}+n \log m)$ time to compute by your own C-W algorithm. But this isn't your question.If there were really an $o(M(n)\log(m))$ algorithm, it would convert immediately to an $o(\log n)$ algorithm for integers. I suspect that one such doesn't exist.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Since Coppersmith–Winograd algorithm finds the product of two matrices in $O(n^{2.3727})$ time, we already have a $O(n^{2.3727}\log(m))$ algorithm for computing $A^m$. I am interested in knowing if this can be improved upon without requiring a better matrix multiplication algorithm, especially for $m=O(n)$. $\endgroup$
    – Shitikanth
    Apr 9, 2012 at 0:54
  • 1
    $\begingroup$ the SVD doesn't give $A = U \Sigma U^\top$ in general - the right hand side matrix is $V \ne U^\top$ $\endgroup$
    – Suresh
    Apr 9, 2012 at 4:10
  • 1
    $\begingroup$ It's a bit misleading to have $n$ for the power as well, so I'll use $m$. If $n=1$ it should take $O(M(1)\log m$ time to find $A^m$, which is equivalent to multiplying integers $\endgroup$
    – PKG
    Apr 9, 2012 at 16:10
  • 2
    $\begingroup$ @Shitikanth see ccrwest.org/gordon/jalg.pdf for a survey of fast-exponentiation algorithms. In general, it's not possible to use fewer than $\log m$ multiplications. $\endgroup$
    – Joe
    Apr 9, 2012 at 18:33
  • 1
    $\begingroup$ This was unclear from your question, as stated. $\endgroup$
    – PKG
    Apr 10, 2012 at 5:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.