16
$\begingroup$

Suppose we are given a matrix $A \in \mathbb R^{N\times N}$, and let $m \in \mathbb N_0$. How fast can we compute the power $A^m$ of that matrix?

The next best thing in comparison to computing $m$-products is to utilize fast exponentation, that requires $\mathcal O(\log m )$ matrix products.

For diagonalizable matrices, the eigenvalue decomposition can be used. It's natural generalization, Jordan decomposition, is unstable under pertubation and therefore does not count (afaik).

Can matrix exponentiation in the general case be sped up?

Fast exponentation suggest a variation of this question is useful, too:

Can the square of a general matrix $A$ be computed faster than by known matrix multiplication algorithms?

Improve this question
$\endgroup$
2
  • $\begingroup$ If you care about stability under perturbations, fast exponentiation doesn't seem safe, either. $\endgroup$
    – Mahdi Cheraghchi
    Apr 12, 2012 at 19:08
  • $\begingroup$ Well, I assume it is no less safe than repeated multiplication, which is as safe as scalar exponentation, isn't it? $\endgroup$
    – shuhalo
    Apr 12, 2012 at 19:57

1 Answer 1

Reset to default
20
$\begingroup$

As you note, computing $A^m$ can be done in $O(\log m)$ times the number of operations for matrix multiplication on $N \times N$ matrices. The answer to your second question is no, at least for asymptotic complexity -- matrix squaring and matrix multiplication have equivalent time/arithmetic complexity (up to constant factors). Reducing squaring to matrix multiplication is obvious. To reduce multiplication to squaring, suppose we wish to compute the product of $A$ and $B$. Form the $2n \times 2n$ matrix $C$ with the block structure:

$[0~~A]$

$[B~~0]$

That is, $C$ has an $n \times n$ all-zeroes matrix in its upper-left quadrant and lower-right quadrant. Note that $C^2$ contains $A\cdot B$ in its upper-left quadrant.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I had recently asked a question at cs.SE about the complexity of computing $A^m$ in the special case where m=$\mathcal O(n)$. It is easy to give a $\mathcal O(M(n)\log(n))$ upper bound, but the best lower bound I can give is $\mathcal \Omega (M(n))$. Do you have any comments about this problem? I think a lot of interesting problems reduce to this special case. $\endgroup$
    – Shitikanth
    Apr 14, 2012 at 13:32

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.