Can Matlab vectorize a generic recursion function?

5 views (last 30 days)
Daniel Armyr on 18 Feb 2011
Hi. I am experimenting with some specialty IIR filters, and the for-loop implementation is just too slow. I have searched, but not found, a function that can help me vectorize a generic recursion function. Does it not exist, or did I simply not find it? The filter() function doesn't allow me to define f() and g() below, otherwise that is of course what I would use.
What I want to do is solve this simple equation for a vector input:
s(n) = x(n) + f(s(n-1)) + g(s(n-2))
Is there a faster way than the for-loop?
Sincerely Daniel Armyr
Oleg Komarov on 18 Feb 2011
Did you preallocate the loop?

Walter Roberson on 18 Feb 2011
Sorry, that recurrence relation cannot be vectorized without knowledge of f and g and two boundary conditions. Even then it might be difficult to solve, depending on what f and g are: if they are non-polynomial it might be quite difficult (and not always easy if they are polynomials.)
If you are able to specify f and g then I can try running it through Maple's rsolve() -- but s(1) and s(2) fixed values would help.

Jonathan on 19 Feb 2011
Please clarify your question and what you mean by vectorize. If I understand your setup correctly, then a function to solve for s(n) requires a length n vector x and a values for s(0) and s(-1).
Vectorizing this function could mean you have multiple sets of x, s(0), and s(-1) for which you want to compute s(n). In this case, it is possible as long as f and g are vectorizable.
% Solve s(n) = x(n) + f(s(n-1)) + g(s(n-2)) for each column of X.
% X is an n-by-m matrix
% Sinit is an 2-by-m matrix.
% Row 1 represents s(-1). Row 2 represents s(0).
s_i_minus_2 = Sinit(1,:);
s_i_minus_1 = Sinit(2,:);
for i = 1:size(X,1)
s_i_minus_0 = X(i,:) + f(s_i_minus_1) + g(s_i_minus_2);
s_i_minus_2 = s_i_minus_1;
s_i_minus_1 = s_i_minus_0;
end
s_n = s_i_minus_0;
For some value of "vectorize a generic recursion function," this is a solution.
~Jonathan
Jonathan on 19 Feb 2011
To address an alternate value of "vectorize a generic recursion function" consider functions f and g for which there is no possible closed form expression for s as a function of n. In this particular case, MatLab is incapable of vectorizing the calculation of s because this is a theoretically impossible feat. Accordingly, MatLab does not provide a method to vectorize a generic recursion function because examples like the theoretical one above exist.
~Jonathan