Matrix Exponentiation — Fast Recurrence Computation

Why it matters

For long-range recurrence values, matrix exponentiation is dramatically faster than iteration.

The architecture

Recurrence as matrix: [F(n+1); F(n)] = M × [F(n); F(n-1)] where M encodes the recurrence.

N-th term: M^n × initial vector.

How it works end to end

Squaring: M^(2n) = (M^n)². M^(2n+1) = M × M^(2n). log n multiplications.

Complexity: matrix mult O(k³) for k×k. Total O(k³ log n).

Applications: Fibonacci at n=10^18, linear recurrences, graph counting problems.