HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Is there a O(log n) algorithm for matrix exponentiation?

Submitted by: @import:stackexchange-cs··
0
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.

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 * M

Code 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 * M

Context

StackExchange Computer Science Q#4998, answer score: 13

Revisions (0)

No revisions yet.