[Haskell-cafe] Question about memory usage

[Jacques Carette]

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