Highly Memory-Efficient Recursion

Let us assume we observe data over a 6-month horizon on a monthly basis (k = 6). Let us also assume the following recursive structure (example below).

I wonder, how this structure can be programmed most efficiently considering the following aspects (Efficiency will be absolutely necessary):

• The period of 6 months is for simplicity and is not generally fixed to this value. Accordingly, this value needs to be redefined;
• The monthly calculations have to be stored because I need it for further calculations.

MWE:

beta = sym("beta", [1 2]).';
phi = sym("phi", [2 2]);

In k1 we calculate a matrix of the following form:

K1 = beta * beta.'

In k2 we have a similar expression, but now it also depends on phi times the previous period.

K2 = beta * beta.' + phi * K1

In period k3 it is the same as in k2, only that K1 changes to K2. So from here on it is recursive and repeats itself. So for the last observation (k6) it is the same formula with K5.

[Rik]

Is it really impossible to clarify your question with edits and comments? I doubt it.

[Stephen23]

http://web.archive.org/web/20210126191006/https://www.mathworks.com/matlabcentral/answers/725787-highly-memory-efficient-recursion

Answer 1

[Sindar]

Do they need to be symbolic? That probably adds a decent cost

Similarly, if you have many zeros, sparse matrices will store more efficiently

Are both beta and phi measured monthly?

If k remains small, it may be more efficient to store phi_i and beta_i, then manually unwrap the recursion and directly calculate the Ki you want, like so:

% K6 = beta6*beta6.' + phi6 * K5
% K6 = beta6*beta6.' + phi6 * (beta5*beta5.' + phi5 * K4)
% K6 = beta6*beta6.' + phi6 * (beta5*beta5.' + ...
%     phi5 * beta4*beta4.' + phi4 * (beta3*beta3.' + phi3 * K2))
K6 = beta6*beta6.' + phi6 * (beta5*beta5.' + ...
    phi5 * beta4*beta4.' + phi4 * (beta3*beta3.' + phi3 * (beta1 * beta1.' + phi1 * K1)));

This will save memory, but there's also good chance it will run faster than recursion when you need a single Ki

[M R]

Thank you very much for your reply.

First, the expression must be symbolic. Second, both beta and phi are measured monthly. Finally, manually unpacking the recursion is not an option for two reasons: (I) the expression is only an MWE and is actually much larger, (II) k can get quite large.

I hope you have an idea for this implementation.

[Sindar]

Hmm, not sure how much help I can be without digging into the specific code, but a few questions to get a rough estimate of the problem:

• How big are beta, phi, Ki? elements and memory
• What's a reasonable k you might need?
• How long does a single Ki iteration take (e.g., K2 = beta * beta.' + phi * K1)?

[M R]

Beta is a 3 by 1 vector, phi is a 3 by 3 matrix. K can get very large. I currently use monthly data, but daily data is conceivable. But if we assume, for example, weekly data for a period of 5 years, then k = 260.

[Sindar]

Ah, I'd assumed that beta and phi were much larger. So, is each individual K 3x3?

Can you explain why symbolic expressions are necessary? This is probably the main reason for large memory requirements, and may interact poorly with recursion

How long do iterations take?

[M R]

Yes, each in dividual K in this case is 3 by 3.

Symbolic Expressions are necessary because I want to differentiate these expressions afterwards. Moreover, I need these expressions for an optimization.