Daniel Fischer wrote:
On Aug 16, 2010, at 6:03 PM, Jacques Carette wrote:
Any sequence of numbers given by a linear recurrence equation with constant coefficients can be computed quickly using asymptotically efficient matrix operations. In fact, the code to do this can be derived automatically from the recurrence itself.
This is neat. Is it always M^n for some matrix M? How does it work?
Yes, it's always M^n.
If the relation is
a_n = c_1*a_(n-1) + ... + c_k*a_(n-k)
you have the k×k matrix
c_1 c_2 ... c_(k-1) c_k 1 0 ... 0 0 0 1 0 ... 0 0 0 0 1 0 ... 0 0 ... 0 1 0 0 0 ... 0 0 1 0
to raise to the n-th power,
However, for large k, this isn't particularly efficient since standard matrix multiplication is O(k^3). I said "asymptotically efficient matrix multiplication", which in practice is between O(k^2.7) and O(k^2.5) depending on the implementation.
These matrices have a special structure that allows doing a multiplication in O(k^2). You might want to look into the Cayley-Hamilton theorem for the latter.
Special multiplication by M is indeed O(k^2), but M^n is going to be dense (if the order of the recurrence is k, then M^n is fully dense for n>=k). And the interesting part is getting high iterates out, not having super large recurrences. In any case, this really doesn't matter in practice since k tends to be *fixed*, so it is really a 'small constant'. The real advantage comes through doing *binary powering*, not the matrix arithmetic. Jacques