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
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
