Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
more dimensional linear recurrences | Reply
I was wondering for a longer time if this approach can be improved to handle also more dimensional linear recurrences.

For example A(x,y)=k*A(x-1,y)+m*A(x,y-1)+n*A(x-2,y).

Suppose that A(0,x),A(x,0) are given.

Linear recurrences depending on constant last terms can be solved also by generating functions, so I tried also this method, but I do not know what to do with product of functions, for example when:
f(x,y) = 1 - f(x,y-1)*f(x-1,y).

Anyone heard about some multidimensional matrices used for this more variables recurrences? me not, but it would be great if someone had :)
Re: more dimensional linear recurrences (response to post by rasto6sk) | Reply
I don't know of anything that handles this. It could be that tensors would be the tool for the job, but I don't know enough about them to say.

One problem I can see is that a fixed amount of local state can't so easily be extended to find future values. For example, when computing a Fibonacci-like sequence you can extrapolate forwards from any two adjacent values. With the recurrence you give, it isn't possible to extrapolate from, say, a 3x2 block of values.

If one of the dimensions is quite small, you could work with entire rows (or columns) of the grid. From a fixed number of rows, you can extrapolate to the next row.
Re: more dimensional linear recurrences (response to post by bmerry) | Reply
I like your idea to calculate whole new row in one step. It can work up to hundreds or maybe thousand constant long columns, because matrix multiplication is quite fast.

I am certainly going to try to implement this approach, thanks :)
Re: more dimensional linear recurrences (response to post by rasto6sk) | Reply
Thousand might be ambitious, because each matrix multiplication is O(N3) - or O(N2.346) if you don't mind a crazy-high constant factor.

Pascal's triangle is an example of a 2-dimensional recurrence, and I'm not aware of any sub-linear algorithm for computing binomial coefficients that doesn't rely on approximation (e.g., a series for the gamma function).