Fast Recurrences

Quite a while ago, I wrote a post on how to compute an arbitrarily large Fibonacci number F_n in essentially O(\log n) steps. Turns out, that technique generalizes to other recurrence relations, and of any order.

Let’s recall (and change the notation somewhat), that for the Fibonacci numbers,

\left[~  \begin{matrix}  1 & 1 \\  1 & 0  \end{matrix}  ~\right]^{n-1}  \left[~  \begin{matrix}  1\\  1  \end{matrix}  ~\right]  =  \left[~  F_{n+1}\\  F_n  ~\right].

With the special case were the matrix to the zeroth power is the identity matrix. We know this will work as intended, because

\left[~  \begin{matrix}  F_{n+1}\\  F_n  \end{matrix}  ~\right]  =  \left[~  \begin{matrix}  1 & 1 \\  1 & 0  \end{matrix}  ~\right]  \left[~  \begin{matrix}  F_{n}\\  F_{n-1}  \end{matrix}  ~\right]  =  \left[~  \begin{matrix}  F_{n}+F_{n-1}\\  F_{n}  \end{matrix}  ~\right]  =  \left[~  \begin{matrix}  F_{n+1}\\  F_{n}  \end{matrix}  ~\right].

This is basically a recursive definition of the matrix exponentiation.

This clever strategy is efficient because we can compute the power of the matrix in O(\log n) matrix products—which, in this particular case, are each rather inexpensive.

*
* *

What if we’re interested in some arbitrary recurrence relation, say,

r_n=r_{n-1}+2r_{n-2}-3r_{n-3},

with initial conditions r_1=1, r_2=2, r_3=4? We now discover something the previous example hid well:

\left[~  \begin{matrix}  1 & 2 &3 \\  1 & 0 & 0 \\  0 & 1 & 0  \end{matrix}  ~\right]^{n-1}  \left[~  \begin{matrix}  4\\  2\\  1  \end{matrix}  ~\right]  =  \left[~  \begin{matrix}  r_n\\  r_{n-1}\\  r_{n-2}  \end{matrix}  ~\right].

The first row of the matrix is the coefficients of the recurrence relation, the column-vector contain the initial conditions (r_1, r_2, and r_3). You can check that both methods—simple recurrence and matrix version—yield the sequence

1, 2, 4, 5, 7, 5, 4, -7, -14, -40, -47, -85, …

*
* *

The general method for a recurrence relation of order k,

r_n = a_0 r_{n-1} + a_1 r_{n-2} + \cdots + a_{k-1}r_{k-1}

with k initial conditions r_0, r_1, … r_{k-1}, we have

\left[~  \begin{matrix}  a_0 & a_1 & a_2 & \cdots & a_{k-2} & a_{k-1}\\  1   & 0   & 0   & \cdots & 0       & 0 \\  0   & 1   & 0   & \cdots & 0       & 0 \\  \vdots & \vdots & \vdots & \cdots & \vdots & \vdots\\  0   & 0   & 0   & \cdots & 1       & 0  \end{matrix}  ~\right]^{n-k+1}  \left[~  \begin{matrix}  r_{k-1}\\  r_{k-2}\\  \vdots\\  \vdots\\  r_{0}  \end{matrix}  ~\right]  =  \left[~  \begin{matrix}  r_n\\  r_{n-1}\\  \vdots\\  \vdots\\  r_{n-k+1}  \end{matrix}  ~\right].

Clearly, the first line of the matrix is composed of the a_i, the coefficients of the recurrence relation, but what are the other lines’ function? They act as a shift mecanism, so that we move down the k-1 previously computed values one position down in the sequence, making some place for the new value given by the dot product with the first line. That is, it computes:

(r_{n-1},r_{n-2},r_{n-3}\ldots,r_{n-k}) \to (r_{n},r_{n-1},r_{n-2}\ldots,r_{n-k+1}),

with

\displaystyle r_n = \sum_{i=0}^{k-1} a_i r_{n-i-1}.

*
* *

So, now, we can compute any recurrence relation for arbitrarily large n in O(\log n) matrix multiplications. The matrix multiplications do get more expensive as k grows. If we do it simply, as we were taught in school, multiplying two k\times{k} matrices costs O(k^3), or, if we use Strassen’s algorithm, we can do it in O(k^{\lg 7}) (or about O(k^{2.8})). That brings the complexity to O(k^3 \log n), which is rapidly smaller than n.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: