Differences between revisions 6 and 7
⇤ ← Revision 6 as of 2009-09-02 16:41:31 →
Size: 7766
Editor: SébastienVillemot
Comment:
← Revision 7 as of 2009-09-03 08:54:49 → ⇥
Size: 13095
Editor: SébastienVillemot
Comment:
Deletions are marked like this. Additions are marked like this.
Line 1: Line 1:
## page was renamed from FastDeterministicSimulation
= Fast Deterministic Simulation =
This page documents the ~+{{{model}}} +~and ~+{{{simul}}}+~ options used to speed-up deterministic simulation in middle and large scale models. Two groups of options are considered:		 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 algorithms

Note that at this time it is not possible to combine all possible variants of these three families of algorithms; this is documented at the end of this page.

= Block decomposition of the model =

== Description of the steps of the algorithm ==

=== Model simplification ===

In a first step to get ride of nearly zero elements in the jacobian a threshold 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.
 
=== 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.

=== 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($x$)>> is assigned to the following equation: <<latex($y+0\cdot x=2z$)>>). 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.

=== Equations renormalization ===

Once the model has been normalized, the preprocessor tries to rewrite the equations in a normalized form: for the variable <<latex($x_i$)>> associated to the equation <<latex($i$)>>, the equation has of the following form <<latex($x_i = f(x_1, \ldots, x_{i-1}, x_{i+1}, \ldots, x_n)$)>>. 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.
  
=== 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.

=== 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 recursive set ordered in a recursive way;
 * Second the equations associated to variables belonging to feedback set.

== Dynare syntax ==

=== Computing block decomposition ===

The block decomposition of the model is triggered by the option {{{block}}} of the {{{model}}} keyword:
{{{
model(block);
...
end;
}}}

=== Controlling the normalization ===

To get ride of nearly zero elements in the jacobian a threshold 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 failed.

The default value of the cutoff is <<latex($10^{-15}$)>>.

Example:
{{{
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 have to set the cutoff to 0.

=== Controlling the set of feedback variables ===

Each block of the model can be rewritten in a quasi recursive form. The endogenous variables are split in two different groups: the recursive variables and the feedback variables. The recursive variables are simply evaluated conditional to the feedback variables. The system is solved only for the feedback variables. The set of feedback variables is determined according to the ~+{{{mfs}}}+~ option:
     * ~+{{{mfs = 0}}}+~: (default value) all the endogenous variables are considered as feedback variables;
     * ~+{{{mfs = 1}}}+~: the endogenous variables assigned to equation naturally normalized are potentially recursive variables. All the other variables are forced to belong to the set of feedback variables.
     * ~+{{{mfs = 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;
}}}

 Two groups of options are considered:
Line 8: Line 88:
=== sparse ===
Dynare performs a block-decomposition of the model and the preprocessor creates two m-files: ModFileName~+{{{_static}}}+~.m and ModFileName~+{{{_dynamic}}}+~.m containing the code for deterministic and stochastic simulation.
Line 11: Line 89:
{{{
model(sparse);
...
end;
}}}
Line 39: Line 112:
To get ride of nearly zero elements in the jacobian a threshold 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 failed.

The default value of the cutoff is 1e-15.

{{{
model(sparse,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 have to set the cutoff to 0.

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 algorithms

Note that at this time it is not possible to combine all possible variants of these three families of algorithms; this is documented at the end of this page.

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 ride of nearly zero elements in the jacobian a threshold 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 $x$ is assigned to the following equation: $y+0\cdot x=2z$). 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 $x_i$ associated to the equation $i$, the equation has of the following form $x_i = f(x_1, \ldots, x_{i-1}, x_{i+1}, \ldots, x_n)$. 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 recursive set ordered in a recursive way;
  • Second the equations associated to variables belonging to feedback set.

1.2. Dynare syntax

1.2.1. Computing block decomposition

The block decomposition of the model is triggered by the option block of the model keyword: 

model(block);
...
end;

1.2.2. Controlling the normalization

To get ride of nearly zero elements in the jacobian a threshold 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 failed.

The default value of the cutoff is $10^{-15}$.

Example: 

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 have to set the cutoff to 0.

1.2.3. Controlling the set of feedback variables

Each block of the model can be rewritten in a quasi recursive form. The endogenous variables are split in two different groups: the recursive variables and the feedback variables. The recursive variables are simply evaluated conditional to the feedback variables. The system is solved only for the feedback variables. The set of feedback variables is determined according to the mfs option:

  • mfs = 0: (default value) all the endogenous variables are considered as feedback variables;

  • mfs = 1: the endogenous variables assigned to equation naturally normalized are potentially recursive variables. All the other variables are forced to belong to the set of feedback variables.

  • mfs = 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;
  • Two groups of options are considered:
  • The options and command taking advantage of the sparsity of the model: block decomposition and fill-in;
  • The options indicating which algorithm is used to solve the model.

1.3. sparse model options and model_info command

1.3.1. sparse_dll

Dynare performs also a block-decomposition of the model and the preprocessor creates two C-files or a binary file containing the model code according to the "Compiler option" containing the code of the deterministic simulation. 

model(sparse_dll);
...
end;

/!\ in the current version of Dynare this option is not compatible with the check command.

1.3.2. Compiler options

These options have to be used in conjunction with sparse_dll option. Two values could be used GCC_compiler or NO_compiler (default value).

  • GCC_compiler: with the first option the preprocessor creates a C file containing the dynamic model which is compiled with the GCC compiler.

  • NO_compiler: a binary file containing the code of the dynamic model is created. During the simulation step binary code is evaluated by simulate.dll. 

model(sparse_dll,GCC_compiler);
...
end;

/!\ if you use GCC_compiler Gnumex has to be installed on your computer.

1.3.3. cutoff

1.3.4. markowitz

At each iteration of the deterministic simulation, if the linear approximation of the model is solve using a sparse gaussian elimination, two criterion 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.

Markowitz option

The pivot is selected according to the highest value among j=1,…,N (where N is the number of possible pivots) of the following criteria:

\[ \frac{\frac{\left | \lambda_j\right |}{Sup_{i} \left | \lambda_i\right |} }{\left ( \frac{ n_j }{ Sup_{i} n_i} \right )^\mu} \]

With:

  • $\lambda_j$: the value of jth pivot;

  • $Sup_{i} \left | \lambda_i\right |$: the highest absolute value of the pivot among the N remaining pivots ;

  • $n_j$: the number of non zeros elements in the row related to the jth pivot ;

  • $n_j$: the highest number of non zeros elements in the row related to remaining pivots ;

  • $\mu$ : the value of the Markowitz option.

As $\mu \rightarrow \infty $ the Markowitz criteria prevails. At the opposite if $\mu \rightarrow 0 $ the usual maximum pivot criteria prevails.

The default value is 0.5 

model(sparse_dll,markowitz=2);
...
end;

/!\ This option is only used in conjunction with sparse_dll option.

1.3.5. model_info command

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. $y_{j,t} = f_j \left (y_t, y_{t-1}, …, y_{t-k} \right) $.

  • 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. $y_{j,t} = f_j \left (y_t, y_{t+1}, …, y_{t+k} \right) $.

  • 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. $ g_j \left (y_{j,t}, y_t, y_{t-1}, …, y_{t-k} \right) =0 $. 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. $ g_j \left (y_{j,t}, y_t, y_{t+1}, …, y_{t+k} \right) =0 $. x is equal to SIMPLE if the block has only one equation. If several equation appears in the block x is equal to COMPLETE.

  • SOVE TWO BOUNDARIES x: the block contains equations depending on both forward and backward variables. $ g_j \left (y_{j,t}, y_t, y_{t-1}, …, y_{t-k} \ ,y_t, y_{t+1}, …, y_{t+k} \right) =0 $. x is equal to SIMPLE if the block has only one equation. If several equation appears in the block x is equal to COMPLETE. 

model(sparse);
...
end;

model_info;

1.4. simulate options

1.4.1. method

This option indicates which linear solver will be implemented at each step of the Newton simulation of the stacked systems formed by the simultaneous blocks containing leads and lags on the endogenous variables. There are three values for this option if the sparse option is used in model command:

  • LU: for the sparse LU decomposition (the default option);
  • GMRES: for the Generalized Minimal Residual method;
  • BICGSTAB: for the Stabilized Bi-Conjugate Gradient method.

When sparse_dll option is used only SGE (for Sparse Gaussian Elimination) is available. It is the unique and default value of method in this case.

1.4.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;
...
end;

simul(periods=80,datafile=mark3);

DynareWiki: FastDeterministicSimulationAndSteadyStateComputation (last edited 2011-03-18 09:04:48 by FerhatMihoubi)