patternModerate
Is there a O(log n) algorithm for matrix exponentiation?
Viewed 0 times
logalgorithmfortherematrixexponentiation
Problem
Is there an algorithm to raise a matrix to the $n$th power in $O(\log n)$ time?
I have been searching online, but have been unsuccessful thus far.
I have been searching online, but have been unsuccessful thus far.
Solution
Here is the pseudocode for an $O(\lg n)$ matrix exponentiation algorithm. Note that the * operator denotes ordinary matrix multiplication.
MATHPOWER (M, n)
if n == 1
then return M
else
P = MATHPOWER (M, floor(n/2))
if n mod 2 == 0
then return P * P
else
return P * P * MCode Snippets
MATHPOWER (M, n)
if n == 1
then return M
else
P = MATHPOWER (M, floor(n/2))
if n mod 2 == 0
then return P * P
else
return P * P * MContext
StackExchange Computer Science Q#4998, answer score: 13
Revisions (0)
No revisions yet.