Improvement for Infinite Horizon

1

I’d like to propose an improvement for infinite horizon models that is quite effective for large grid sizes. In a current project with n_a=1200 and n_z=245 (not uncommon if you have more than one z variable) I realized that doing the Howard acceleration with a sparse matrix improves speed significantly. This applies to the case with howardsgreedy=0: as already discussed in another post, howardsgreedy is beneficial only for very small grid sizes.

Therefore I am proposing the following change. I propose to add vfoptions.howardssparse, which applies to the case howardsgreedy=0.

Step 0

At the beginning of ValueFnIter_Case1, introduce option howardssparse with default value equal to 0 (this is a trivial change, please see attached file).

Step 1

After creating ReturnMatrix, ValueFnIter_Case1 calls ValueFnIter_nod_raw at lines 479-483. The current block of code

if vfoptions.howardsgreedy==1
    [VKron,Policy]=ValueFnIter_nod_HowardGreedy_raw(V0, N_a, N_z, pi_z, DiscountFactorParamsVec, ReturnMatrix, vfoptions.maxhowards, vfoptions.tolerance, vfoptions.maxiter); %  a_grid, z_grid,
 elseif vfoptions.howardsgreedy==0
    [VKron,Policy]=ValueFnIter_nod_raw(V0, N_a, N_z, pi_z, DiscountFactorParamsVec, ReturnMatrix, vfoptions.howards, vfoptions.maxhowards, vfoptions.tolerance, vfoptions.maxiter); %  a_grid, z_grid,
 end

should be replaced by

if vfoptions.howardsgreedy==1
   [VKron,Policy]=ValueFnIter_nod_HowardGreedy_raw(V0, N_a, N_z, pi_z, DiscountFactorParamsVec, ReturnMatrix, vfoptions.maxhowards, vfoptions.tolerance, vfoptions.maxiter); %  a_grid, z_grid,
elseif vfoptions.howardsgreedy==0
   if vfoptions.howardssparse==0
      [VKron,Policy]=ValueFnIter_nod_raw(V0, N_a, N_z, pi_z, DiscountFactorParamsVec, ReturnMatrix, vfoptions.howards, vfoptions.maxhowards, vfoptions.tolerance, vfoptions.maxiter);
   elseif vfoptions.howardssparse==1
      [VKron,Policy]=ValueFnIter_nod_raw_sparse(V0, N_a, N_z, pi_z, DiscountFactorParamsVec, ReturnMatrix, vfoptions.howards, vfoptions.maxhowards, vfoptions.tolerance, vfoptions.maxiter);
   end
end

Step 2

In ValueFnIter_Refine please change this block of code

if vfoptions.howardsgreedy==1
    [VKron,Policy_a]=ValueFnIter_nod_HowardGreedy_raw(V0, N_a, N_z, pi_z, DiscountFactorParamsVec, ReturnMatrix, vfoptions.maxhowards, vfoptions.tolerance,vfoptions.maxiter);
elseif vfoptions.howardsgreedy==0
    [VKron,Policy_a]=ValueFnIter_nod_raw(V0, N_a, N_z, pi_z, DiscountFactorParamsVec, ReturnMatrix, vfoptions.howards, vfoptions.maxhowards, vfoptions.tolerance,vfoptions.maxiter);
end

with this one:

if vfoptions.howardsgreedy==1
    [VKron,Policy_a]=ValueFnIter_nod_HowardGreedy_raw(V0, N_a, N_z, pi_z, DiscountFactorParamsVec, ReturnMatrix, vfoptions.maxhowards, vfoptions.tolerance,vfoptions.maxiter);
elseif vfoptions.howardsgreedy==0
    %[VKron,Policy_a]=ValueFnIter_nod_raw(V0, N_a, N_z, pi_z, DiscountFactorParamsVec, ReturnMatrix, vfoptions.howards, vfoptions.maxhowards, vfoptions.tolerance,vfoptions.maxiter);
    if vfoptions.howardssparse==0
        [VKron,Policy_a]=ValueFnIter_nod_raw(V0, N_a, N_z, pi_z, DiscountFactorParamsVec, ReturnMatrix, vfoptions.howards, vfoptions.maxhowards, vfoptions.tolerance, vfoptions.maxiter);
    elseif vfoptions.howardssparse==1
        [VKron,Policy_a]=ValueFnIter_nod_raw_sparse(V0, N_a, N_z, pi_z, DiscountFactorParamsVec, ReturnMatrix, vfoptions.howards, vfoptions.maxhowards, vfoptions.tolerance, vfoptions.maxiter);
    end
end

Step 3 (Low memory)

In ValueFnIter_Case1 around lines 510-516 please change this block of code:

[VKron,Policy]=ValueFnIter_LowMem_nod_raw(V0, n_a, n_z, a_grid, z_gridvals, pi_z, DiscountFactorParamsVec, ReturnFn, ReturnFnParamsVec, vfoptions.howards, vfoptions.maxhowards, vfoptions.tolerance);

with this:

if vfoptions.howardssparse==0
   [VKron,Policy]=ValueFnIter_LowMem_nod_raw(V0, n_a, n_z, a_grid, z_gridvals, pi_z, DiscountFactorParamsVec, ReturnFn, ReturnFnParamsVec, vfoptions.howards, vfoptions.maxhowards, vfoptions.tolerance);
elseif vfoptions.howardssparse==1      
   [VKron,Policy]=ValueFnIter_LowMem_nod_raw_sparse(V0, n_a, n_z, a_grid, z_gridvals, pi_z, DiscountFactorParamsVec, ReturnFn, ReturnFnParamsVec, vfoptions.howards, vfoptions.maxhowards, vfoptions.tolerance, vfoptions.maxiter);
end

I uploaded in the github repo AiyagariSparse the files that I changed in the toolkit:

  • ValueFnIter_Case1 with the new option howardssparse
  • ValueFnIter_Refine for models with d variable
  • ValueFnIter_nod_raw_sparse which is the new file, called by ValueFnIter_Case1 around lines 480-490 and called by ValueFnIter_Refine around lines 40-45.
  • ValueFnIter_LowMem_nod_raw_sparse which is the new file for the low memory case. It is called by ValueFnIter_Case1 around lines 510-516.

I’m quite satisfied about this change, so I hope it can be officially included in the toolkit as an option, without changing the default settings :slight_smile:

On my laptop, I see the benefit of howardssparse when n_a=1000 and n_z=51, on the desktop (where I have a better GPU), I see the benefits for n_a=1200 and n_z=101.

1 Like
2

You can also find the updated files as forked repo in GitHub - aledinola/VFIToolkit-matlab: A Matlab Toolkit for Macroeconomic Models using Value Function Iteration

3

Cool! I’ve just pushed the implementation to github.

Two very minor changes:
i) I renamed ‘ValueFnIter_nod_raw_sparse’ to ‘ValueFnIter_sparse_nod_raw’ (and did similar to lowmem version).
ii) I have set is so that the default is

if N_a>1200 && N_z>100
    vfoptions.howardssparse=1; % Do Howards iteration using a sparse matrix. Sparse is only faster for bigger models.
else
    vfoptions.howardssparse=0;
end

Thanks for the well documented post. Made it easy :smiley:

1 Like