Dynare now incorporates new features which significantly speed-up deterministic simulation and steady state computation in middle and large scale models.
The speed-up is achieved by the combination of three new features:
- block decomposition of the model;
- bytecode representation of the model;
- new variants of Newton algorithm.
The various options in this page only work with deterministic simulation at this time: they won't work with stochastic simulation, estimation or Ramsey policy. For the very same reason, in Dynare 4.1 they are also not compatible with the check command. This latter restriction has been alleviated in Dynare 4.2.
Contents
1. Block decomposition of the model
1.1. Description of the steps of the algorithm
1.1.1. Model simplification
In a first step, to get rid of nearly zero elements in the jacobian, a threshold (cutoff) is used to determine whether a jacobian element has to be considered as null or not. If the absolute value of a jacobian element is below the threshold then it is considered as null and is discarded form the sparse representation of the jacobian. Eliminating nearly zero elements improves the sparsity of the model and hence the simulation time. Note that if the cutoff value is too high then the model properties could be strongly modified and the simulation could fail.
1.1.2. Prologue and Epilogue determination
In a second step, the equations and the variables of the model could be reordered to get purely recursive initial and final blocks. The purely recursive equations are easily found.
- The first block, called prologue, is composed of equations involving only exogenous variables or endogenous variables determined by previous equations.
- The last block, the epilogue, is composed of variables which are pure output in the model: they do not appear in the previous equations of the model.
1.1.3. Model normalization
To get a block decomposition of the model, each endogenous variable has to be assigned unambiguously to an equation or equivalently the model has to be normalized: this normalization is performed using the maximum cardinality matching with Edmondsâ€™ matching algorithm (Boost-graph library). Attention has to be paid to potential singularity in the matching process (to avoid for example a normalisation where the variable
latex error! exitcode was 2 (signal 0), transscript follows: [Thu Sep 09 08:40:18.812051 2021] [wsgi:error] [pid 3351:tid 139902167504640] [client 192.168.1.1:36066] failed to exec() latexis assigned to the following equation:
latex error! exitcode was 2 (signal 0), transscript follows: [Thu Sep 09 08:40:18.859799 2021] [wsgi:error] [pid 3352:tid 139902167504640] [client 192.168.1.1:36066] failed to exec() latex). The matching algorithm is applied iteratively using the normalized Jacobian matrix (each row is divided by its maximum absolute value component) with a decreasing cutoff (all the elements in the Jacobian matrix below the cutoff are set to zero) until a matching is found.
1.1.4. Equations renormalization
Once the model has been normalized, the preprocessor tries to rewrite the equations in a normalized form: for the variable
latex error! exitcode was 2 (signal 0), transscript follows: [Thu Sep 09 08:40:18.909939 2021] [wsgi:error] [pid 3353:tid 139902167504640] [client 192.168.1.1:36066] failed to exec() latexassociated to the equation
latex error! exitcode was 2 (signal 0), transscript follows: [Thu Sep 09 08:40:18.951479 2021] [wsgi:error] [pid 3354:tid 139902167504640] [client 192.168.1.1:36066] failed to exec() latex, the equation has of the following form
latex error! exitcode was 2 (signal 0), transscript follows: [Thu Sep 09 08:40:18.991714 2021] [wsgi:error] [pid 3355:tid 139902167504640] [client 192.168.1.1:36066] failed to exec() latex. For equations belonging to a recursive block, the normalized equation has not to be solved but only evaluated. For equations normalized belonging to a simultaneous block, they could be simply evaluated if they belong to the recursive set of the block in the feedback variables determination.
1.1.5. Block decomposition
The simultaneous block composed of equations and endogenous variables that do not belong to the prologue or the epilogue could be split sub recursive blocks. Those sub recursive blocks form the strong component of the graph representation of the model. To find them a depth search Tarjan algorithm is used.
1.1.6. Splitting the variables of a simultaneous block in feedback and recursive variables
The simultaneous blocks computed in the previous step are rewritten in a quasi triangular form. The non normalized equations that could not be evaluated are forced to belong to the feedback variables set. In addition, for dynamic model the static variables associated with non static equation or the non static variables are imposed in the feedback variables set. The equations of the block are reordered as follow:
- First, the equations associated to variables belonging to the recursive set, ordered in a recursive way;
- Second, the equations associated to variables belonging to the feedback set.
1.2. Dynare syntax
1.2.1. Computing block decomposition
The block decomposition of the model is triggered by the block option of the model keyword:
model(block); ... end;
1.2.2. Controlling the model simplification
The default value of the cutoff described in the first step of the algorithm is
latex error! exitcode was 2 (signal 0), transscript follows: [Thu Sep 09 08:40:19.051819 2021] [wsgi:error] [pid 3356:tid 139902167504640] [client 192.168.1.1:36066] failed to exec() latex. It can be modified with cutoff option of the model keyword:
model(block,cutoff=1e-13); ... end;
Note that the jacobian is evaluated considering the initial value of the parameters provided in the mod file. If the parameters value are modified (the model is estimated for example) before the simul command, some components of the jacobian could be wrongly discarded. To prevent such a result you may need to decrease the cutoff (or even set it to zero).
1.2.3. Controlling equation renormalization and the set of feedback variables
The mfs option of the model keyword controls equation renormalization and the set of feedback variables:
mfs = 0: (default value) all the endogenous variables are considered as feedback variables;
mfs = 1: the endogenous variables assigned to equation naturally normalized (i.e. of the form
latex error! exitcode was 2 (signal 0), transscript follows: [Thu Sep 09 08:40:19.112269 2021] [wsgi:error] [pid 3357:tid 139902167504640] [client 192.168.1.1:36066] failed to exec() latex
wherelatex error! exitcode was 2 (signal 0), transscript follows: [Thu Sep 09 08:40:19.159502 2021] [wsgi:error] [pid 3358:tid 139902167504640] [client 192.168.1.1:36066] failed to exec() latex
does not appear inlatex error! exitcode was 2 (signal 0), transscript follows: [Thu Sep 09 08:40:19.207282 2021] [wsgi:error] [pid 3359:tid 139902167504640] [client 192.168.1.1:36066] failed to exec() latex
) are potentially recursive variables. All the other variables are forced to belong to the set of feedback variablesmfs = 2: in addition of variables with mfs = 1 the endogenous variables related to linear equation which could be normalized are potential recursive variables. All the other variables are forced to belong to the set of feedback variables;
mfs = 3: in addition of variables with mfs = 2 the endogenous variables related non-linear equation which could be normalized are potential recursive variables. All the other variables are forced to belong to the set of feedback variables.
Example:
model(block,mfs=2); ... end;
1.2.4. Exploring the block structure of the model
The model_info command provides information about:
- the normalization of the model: an endogenous variable is attributed to each equation of the model;
the block structure of the model: for each block model_info indicates its type, the equations number and endogenous variables belonging to this block.
There are five different types of blocks depending on the simulation method used:
EVALUATE FORWARD: in this case the block contains only equations where endogenous variable attributed to the equation appears currently on the left hand side and where no forward looking endogenous variables appear.
latex error! exitcode was 2 (signal 0), transscript follows: [Thu Sep 09 08:40:19.264493 2021] [wsgi:error] [pid 3360:tid 139902167504640] [client 192.168.1.1:36066] failed to exec() latex
.EVALUATE BACKWARD: the block contains only equations where endogenous variable attributed to the equation appears currently on the left hand side and where no backward looking endogenous variables appear.
latex error! exitcode was 2 (signal 0), transscript follows: [Thu Sep 09 08:40:19.304001 2021] [wsgi:error] [pid 3361:tid 139902167504640] [client 192.168.1.1:36066] failed to exec() latex
.SOLVE FORWARD x: the block contains only equations where endogenous variable attributed to the equation does not appear currently on the left hand side and where no forward looking endogenous variables appear.
latex error! exitcode was 2 (signal 0), transscript follows: [Thu Sep 09 08:40:19.351310 2021] [wsgi:error] [pid 3362:tid 139902167504640] [client 192.168.1.1:36066] failed to exec() latex
. x is equal to SIMPLE if the block has only one equation. If several equation appears in the block x is equal to COMPLETE.SOLVE FORWARD x: the block contains only equations where endogenous variable attributed to the equation does not appear currently on the left hand side and where no backward looking endogenous variables appear.
latex error! exitcode was 2 (signal 0), transscript follows: [Thu Sep 09 08:40:19.398996 2021] [wsgi:error] [pid 3363:tid 139902167504640] [client 192.168.1.1:36066] failed to exec() latex
. x is equal to SIMPLE if the block has only one equation. If several equation appears in the block x is equal to COMPLETE.SOLVE TWO BOUNDARIES x: the block contains equations depending on both forward and backward variables.
latex error! exitcode was 2 (signal 0), transscript follows: [Thu Sep 09 08:40:19.448125 2021] [wsgi:error] [pid 3364:tid 139902167504640] [client 192.168.1.1:36066] failed to exec() latex
. x is equal to SIMPLE if the block has only one equation. If several equation appears in the block x is equal to COMPLETE.
Synopsis:
model(block); ... end; model_info;
2. Bytecode representation of the model
By default, the Dynare preprocessor creates two M-files (one for the static model, one for the dynamic model) which are used by the MATLAB routines of Dynare. With big models, these M-files can become huge, and consume a lot of computing ressources.
The idea is to represent the model under another form: a bytecode, i.e. a binary file containing a compact representation of all the equations. This bytecode is then read and used for evaluations from MATLAB, using a dedicaded DLL.
You can activate the bytecode representation with the bytecode option of the model keyword:
model(block, bytecode); ... end;
In Dynare 4.1, bytecode without block is not possible. This restriction has been alleviated in Dynare 4.2.
3. New variants of Newton algorithm
3.1. Steady state computation
The steady option accepts a solve_algo option for choosing the nonlinear solver for the steady state. This option can take the following values:
solve_algo=0: uses fsolve
solve_algo=1: uses Dynare's own nonlinear equation solver
solve_algo=2: splits the model into recursive blocks and solves each block in turn
solve_algo=3: Chris Sims' solver
solve_algo=4: similar to value 2, except that it deals differently with nearly singular Jacobian
solve_algo=5: Newton algorithm with a sparse Gaussian elimination (SPE)
solve_algo=6: Newton algorithm with a sparse LU solver at each iteration
solve_algo=7: Newton algorithm with a Generalized Minimal Residual (GMRES) solver at each iteration
solve_algo=8: Newton algorithm with a Stabilized Bi-Conjugate Gradient (BICGSTAB) solver at each iteration
The possible combinations are the following:
3.1.1. In Dynare 4.1
solve_algo=... |
neither block nor bytecode |
block without bytecode |
bytecode without block |
block and bytecode |
0 |
OK (only under MATLAB with optim toolbox) |
N/A |
N/A |
N/A |
1 |
N/A |
OK |
N/A |
N/A |
2 |
N/A |
OK |
N/A |
N/A |
3 |
N/A |
OK |
N/A |
N/A |
4 |
N/A |
OK |
N/A |
N/A |
5 |
N/A |
N/A |
N/A |
OK |
6 |
N/A |
N/A |
N/A |
N/A |
7 |
N/A |
N/A |
N/A |
N/A |
8 |
N/A |
N/A |
N/A |
N/A |
3.1.2. In Dynare 4.2
solve_algo=... |
neither block nor bytecode |
block without bytecode |
bytecode without block |
block and bytecode |
0 |
OK (except under MATLAB without optim toolbox) |
OK |
OK |
OK |
1 |
OK |
OK |
OK |
OK |
2 |
OK |
OK |
OK |
OK |
3 |
OK |
OK |
OK |
OK |
4 |
OK |
OK |
OK |
OK |
5 |
N/A |
N/A |
OK |
OK |
6 |
N/A |
OK |
OK |
OK |
7 |
N/A |
OK (except under Octave) |
OK (except under Octave) |
OK (except under Octave) |
8 |
N/A |
OK |
OK |
OK |
3.2. Deterministic simulation
The simul command has a new option, stack_solve_algo, used to specify the resolution algorithm. This option can take integer values between 0 and 5:
stack_solve_algo=0 (default): use the historical simk.m or sim1.m solver which takes into account the sparse structure of the stacked time system according to Laffargue (1990) and Juillard (1996);
stack_solve_algo=1: use a Newton algorithm with a sparse LU solver at each iteration;
stack_solve_algo=2: use a Newton algorithm with a Generalized Minimal Residual (GMRES) solver at each iteration;
stack_solve_algo=3: use a Newton algorithm with a Stabilized Bi-Conjugate Gradient (BICGSTAB) solver at each iteration;
stack_solve_algo=4: use a Newton algorithm with a optimal path length at each iteration;
stack_solve_algo=5: use a Newton algorithm with a sparse Gaussian elimination (SPE) solver at each iteration (see below). In that case, the option minimal_solving_periods is used to specify the minimal number of periods where the model has to be solved, before using a constant set of operations for the remaining periods.
The possible combinations are the following:
3.2.1. In Dynare 4.1
stack_solve_algo=... |
neither block nor bytecode |
block without bytecode |
bytecode without block |
block and bytecode |
0 |
OK |
N/A |
N/A |
N/A |
1 |
N/A |
OK |
N/A |
N/A |
2 |
N/A |
OK |
N/A |
N/A |
3 |
N/A |
OK |
N/A |
N/A |
4 |
N/A |
OK |
N/A |
N/A |
5 |
N/A |
N/A |
N/A |
OK |
3.2.2. In Dynare 4.2
stack_solve_algo=... |
neither block nor bytecode |
block without bytecode |
bytecode without block |
block and bytecode |
0 |
OK |
OK |
OK |
OK |
1 |
N/A |
OK |
OK |
OK |
2 |
N/A |
OK (except under Octave) |
OK (except under Octave) |
OK (except under Octave) |
3 |
N/A |
OK |
OK |
OK |
4 |
N/A |
OK |
OK |
OK |
5 |
N/A |
N/A |
OK |
OK |
3.3. Sparse Gaussian Elimination
FILL IN DESCRIPTION HERE...
3.3.1. Markowitz criterion option
At each iteration of the deterministic simulation, if the linear approximation of the model is solved using a sparse gaussian elimination, two criteria could be used to select the variable to substitute:
- The maximum pivot to get the most accurate solution (quite standard in Gaussian Elimination or LU decomposition);
- The Markowitz criterion, to prevent an excessive sparsity reduction. The number of new non-zero elements created during the variable substitution is related to the number of non zero elements in its row. In this case we select the variable associated to the minimum non-zero elements in its row.
The pivot is selected according to the highest value among
latex error! exitcode was 2 (signal 0), transscript follows: [Thu Sep 09 08:40:19.575804 2021] [wsgi:error] [pid 3365:tid 139902167504640] [client 192.168.1.1:36066] failed to exec() latex(where
latex error! exitcode was 2 (signal 0), transscript follows: [Thu Sep 09 08:40:19.613465 2021] [wsgi:error] [pid 3366:tid 139902167504640] [client 192.168.1.1:36066] failed to exec() latexis the number of possible pivots) of the following criterion:
latex error! exitcode was 2 (signal 0), transscript follows: [Thu Sep 09 08:40:19.656263 2021] [wsgi:error] [pid 3367:tid 139902167504640] [client 192.168.1.1:36066] failed to exec() latex
With:
latex error! exitcode was 2 (signal 0), transscript follows: [Thu Sep 09 08:40:19.695378 2021] [wsgi:error] [pid 3368:tid 139902167504640] [client 192.168.1.1:36066] failed to exec() latex
: the value oflatex error! exitcode was 2 (signal 0), transscript follows: [Thu Sep 09 08:40:19.739169 2021] [wsgi:error] [pid 3369:tid 139902167504640] [client 192.168.1.1:36066] failed to exec() latex
th pivot;latex error! exitcode was 2 (signal 0), transscript follows: [Thu Sep 09 08:40:19.785364 2021] [wsgi:error] [pid 3370:tid 139902167504640] [client 192.168.1.1:36066] failed to exec() latex
: the highest absolute value of the pivot among thelatex error! exitcode was 2 (signal 0), transscript follows: [Thu Sep 09 08:40:19.827098 2021] [wsgi:error] [pid 3371:tid 139902167504640] [client 192.168.1.1:36066] failed to exec() latex
remaining pivots ;latex error! exitcode was 2 (signal 0), transscript follows: [Thu Sep 09 08:40:19.872141 2021] [wsgi:error] [pid 3372:tid 139902167504640] [client 192.168.1.1:36066] failed to exec() latex
: the number of non zeros elements in the row related to thelatex error! exitcode was 2 (signal 0), transscript follows: [Thu Sep 09 08:40:19.913047 2021] [wsgi:error] [pid 3373:tid 139902167504640] [client 192.168.1.1:36066] failed to exec() latex
th pivot ;latex error! exitcode was 2 (signal 0), transscript follows: [Thu Sep 09 08:40:19.954044 2021] [wsgi:error] [pid 3374:tid 139902167504640] [client 192.168.1.1:36066] failed to exec() latex
: the highest number of non zeros elements in the row related to remaining pivots ;latex error! exitcode was 2 (signal 0), transscript follows: [Thu Sep 09 08:40:19.996822 2021] [wsgi:error] [pid 3375:tid 139902167504640] [client 192.168.1.1:36066] failed to exec() latex
: the value of the Markowitz option.
As
latex error! exitcode was 2 (signal 0), transscript follows: [Thu Sep 09 08:40:20.046548 2021] [wsgi:error] [pid 3376:tid 139902167504640] [client 192.168.1.1:36066] failed to exec() latexthe Markowitz criterion prevails. At the opposite if
latex error! exitcode was 2 (signal 0), transscript follows: [Thu Sep 09 08:40:20.092376 2021] [wsgi:error] [pid 3377:tid 139902167504640] [client 192.168.1.1:36066] failed to exec() latexthe usual maximum pivot criterion prevails.
The default value for the Markowitz criterion is 0.5.
model(block, bytecode); ... end; steady(solve_algo=5, markowitz=2); simul(periods=80, stack_solve_algo=5, markowitz=2);
3.3.2. Datafile
If the variables of the model are not constant over time, their initial values, stored in a text file, could be loaded, using the datafile option, as initial values before a deteministic simulation.
model(block, bytecode); ... end; simul(periods=80, stack_solve_algo=5, datafile=mark3);