Clear Filters
Clear Filters

Can Matlab vectorize a generic recursion function?

1 view (last 30 days)
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

Accepted Answer

Walter Roberson
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.

More Answers (1)

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;
s_n = s_i_minus_0;
For some value of "vectorize a generic recursion function," this is a solution.
  1 Comment
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.

Sign in to comment.


Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!