Can Matlab vectorize a generic recursion function?

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]

Did you preallocate the loop?

Answer 1

[Walter Roberson]

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.

Answer 2

[Jonathan]

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]

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