May 2009 - Dev - dynare.org

stochastic steady state/Kalman filter
by Michel Juillard 11 May '09

11 May '09

Dear Andrea, I met with Pablo last week and we made some progress. He is going to go ahead with his algorithm taking approximation around the unconditional mean. He will present it in an intermediary report that is due at the end of this week. Please check it for typos and other mistakes when it is ready and, if possible, send him remarks by Thursday. I'm still thinking about an alternative approach around the steady sate, but I need to finish writing it before showing it to you. I would like you to start another project around the multiplication with quasi-triangular matrices. We are in the process of coding the Kalman filter in C++ hoping to accelerate this part of estimation. George is in charge of the overall project. However, when we estimate with non-stationary variables, we are forced to transform the transition equation of the state space representation and we have a transition matrix that is quasi-triangular. As it turns out, we could always used this transformation, even for models with only stationary variables. I expect some speed gain from taking into account the special structure of the transition matrix. I'm attaching a brief outline of the Kalman filte So I would like you to write a code (+, C or Fortran) for the two operations involving the transition matrix T. 1) T and P have the same dimensions. When they are large 100x100 and larger, I imagine there is a gain from using a block algorithm for T*P*T' as in BLAS/LAPACK dgemm and to optimize the size of a block so as to keep it in fast cache memory the same way as ATLAS is doing. 2) For smaller matrices, it may be better to simply inline the loops. The optimal size for both approaches should be determined empirically by testing. 3) Currently, in the Matlab code, for lage models, most of the time is spent in computing T*P*T' For this project, I would like you to consult with Marco. He has agreed to help and JRC has much experience with Kalman filter computations.

1 0

Re: [DynareDev] Extracting rules for deterministic exogenous vars
by Michel Juillard 11 May '09

11 May '09

One more thing. We realized that when we are estimating models with non-stationary variables (diffuse_filter option) it is necessary to transform the transition equation so that the transition matrix is quasi-upper diagonal. This transformation of the transition matrix is indeed available in all cases (even for models with stationary variables only) because it is a by-product of the algorithm for solving the Lyapunov equation. This equation is used for computing the unconditional variance of the endogenous variables used to initialize the matrix of forecast error variance in the Kalman filter (P matrix usually). Using a quasi-triangular transition matrix should permit speed gains in matrix multiplication where this matrix is involved. I'm planning to ask Andrea to look into writing a block algorithm for matrix multiplication specialized for the case where one of the two matrices is quasi-triangular. For the time being, you can use DGEMM for these matrix multiplications. Best, Michel G. Perendia wrote: > Deara Michel > > Thanks. > > As you already pointed out, the KF software from SVN is highly > over-modularised and difficult to grasp and modify. But we may not have to > modify much as it has some of the functionalities we expect already built-in > such as univariate and multivariate filtering, smoother and diffuse priors. > Also, as mentioned earlier, it should integrate well with other Dynare > applications around dynarelib (it uses sylvester code too). So far the > only two package that uses LAPACK/BLAS (either the optimised one , or, if > customised, the bespoke ports to various parallel hardware platforms) are > dynarelib/KF and a smaller of the two Bayesian filter libraries ( C++ > Bayesian Filtering Classes by Michael Stevens, see enclosed draft analysis). > > The most of other internet KF packages either rely on BOOST/uBLAS or their > own > matrix calculation implementations. And, contrary to my initial assumptions, > uBLAS, as the most of the BOOST libraries it is part of, is a self-contained > "header" library that implements most of important basic algebra > functionality in header (.hpp) files. It therefore does not use (or > interface) any external libraries such as LAPACK/BLAS and, all compiling and > optimisation is done at application compilation time. This is one of reasons > our SVN KF still scores high among the alternatives. > > Smoothing, however, is also present in one of the Bayesian filtering > packages (Orocos ), and though that one relies on BOOST/uBLAS header > libraries, the Orocos BFL is probably best (i.e. functionally richest) > alternative. > > Altogether it is still difficult to derive single recommendation and I am > still working on analysing the available packages - The latest draft > analysis is enclosed . > > Best regards > > George > > ----- Original Message ----- > From: "Michel Juillard" <michel.juillard(a)ens.fr> > To: "G. Perendia" <george(a)perendia.orangehome.co.uk> > Sent: Sunday, May 10, 2009 1:28 PM > Subject: Re: Extracting rules for deterministic exogenous vars > > > >> There should be no problem if we want ot use it. This was developed for >> the Dynare project. What do you think of the code? >> >> best >> >> Michel >> >> G. Perendia wrote: >> >>> Dear Michel >>> I wandered also if we are allowed to use it. >>> Best regards >>> >>> George >>> >>> ----- Original Message ----- >>> From: "Michel Juillard" <michel.juillard(a)ens.fr> >>> To: "G. Perendia" <george(a)perendia.orangehome.co.uk> >>> Sent: Tuesday, May 05, 2009 1:49 PM >>> Subject: Re: Extracting rules for deterministic exogenous vars >>> >>> >>> >>> >>>> Hi George, >>>> >>>> my memory that it was too modular in conception and hard to understand, >>>> but I will fish it back and send it to you. >>>> >>>> All the best, >>>> >>>> Michel >>>> >>>> G. Perendia wrote: >>>> >>>> >>>>> Dear Michel >>>>> >>>>> I started looking into Kalman Filter DLL - Can we still re-use the >>>>> (existing?) Kalman Filter code that was/is (??) in SVN for the new >>>>> > KF? > >>>>> PS: I.e., I can not see, find or access the Kalman_Filter SVN repo any >>>>> more - i.e. since the move- - but browsing inside the current repo did >>>>> >>>>> >>> not >>> >>> >>>>> find Kalman-Filter." >>>>> >>>>> Best regards >>>>> >>>>> George >>>>> Mob. +44(0)7951415480 >>>>> artilogica(a)btconnect.com >>>>> >>>>> ----- Original Message ----- >>>>> From: "Michel Juillard" <michel.juillard(a)ens.fr> >>>>> To: "G. Perendia" <george(a)perendia.orangehome.co.uk>; "List for Dynare >>>>> developers" <dev(a)dynare.org> >>>>> Sent: Monday, April 27, 2009 8:33 PM >>>>> Subject: Re: Extracting rules for deterministic exogenous vars >>>>> >>>>> >>>>> >>>>> >>>>> >>>>>> Hi George, >>>>>> >>>>>> I have completely forgotten about dr.fuu, I don't see at the moment >>>>>> >>>>>> >>> what >>> >>> >>>>>> it is useful for. >>>>>> Porting the varexo_det stuff to C++ isn't a priority, far from it. >>>>>> I would rather that you clean-up existing k_order_perturbation code. >>>>>> When that is done, I would like you to turn to the Kalman filter, but >>>>>> >>>>>> >>> we >>> >>> >>>>>> will need to do a careful analysis before starting to code. >>>>>> One question will be which matrix implementation to use in the Kalman >>>>>> filter code? Shall we keep using Ondra's TwoD matrices? Shall we >>>>>> > build > >>>>>> our own (doubtful)? Should we use something like Boost? >>>>>> >>>>>> Best >>>>>> >>>>>> Michel >>>>>> >>>>>> >>>>>> G. Perendia wrote: >>>>>> >>>>>> >>>>>> >>>>>>> Dear Michel >>>>>>> >>>>>>> I was thinking of re-using some of the existing 2nd order dr1.m code >>>>>>> >>>>>>> >>> to >>> >>> >>>>>>> determine dr.fuu and the rules for, if any, deterministic exogenous >>>>>>> >>>>>>> >>> vars >>> >>> >>>>>>> (dr.gh??d). >>>>>>> >>>>>>> Looking at the code in dr1.m, for both dr.fuu and deterministic >>>>>>> >>>>>>> >>>>>>> >>>>> exogenous >>>>> >>>>> >>>>> >>>>>>> vars, we need hessian and, for the former, jacobian. Shall I >>>>>>> > retrieve > >>>>>>> >>>>> them >>>>> >>>>> >>>>> >>>>>>> from k-order-perturbation or is there a more elegant way to get >>>>>>> > those > >>>>>>> >>>>> rules >>>>> >>>>> >>>>> >>>>>>> that you can think of? Perhaps we can determine fuu from ghs2 (if >>>>>>> > not > >>> 0) >>> >>> >>>>>>> more elegantly but I can not see it as yet. >>>>>>> >>>>>>> I however could not find where dr.fuu is used other than internally >>>>>>> >>>>>>> >>>>>>> >>>>> within >>>>> >>>>> >>>>> >>>>>>> dr1.m (and dr11_sparse.m). That could mean that we only need hessian >>>>>>> >>>>>>> >>> and >>> >>> >>>>>>> only infrequently when if we have deterministic exogenous vars. >>>>>>> >>>>>>> Best regards >>>>>>> >>>>>>> George >>>>>>> Mob. +44(0)7951415480 >>>>>>> artilogica(a)btconnect.com >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>> >>>>> >>>> >>> >>> >>> >>

1 0

Re: [DynareDev] Extracting rules for deterministic exogenous vars
by Michel Juillard 11 May '09

11 May '09

Thanks George, this is very useful. I suggest the following. 1) Use matrix implementation in dynare++/tl/cc, and develop the interface to BLAS/LAPACK if additional such functions are needed 2) Start with the code developed by Ondra Kamenik, but try to redesign the code in a less complicated implementation and get rid of the cweb part. You will just mention the ancestry of this new code. Please, send me the classes and functions that you think would be optimal to implement before actually writing code. We have two preoccupations: * the code must be numerically robust for the type of models that we are handling (we will need tests ex-post) * speed because of the Metropolis algorithm that will call this function millions of times per run. 3) Look at OROCOS implementation when in doubt about algorithm details 4) For the moment, we are only concerned with filtering and log-likelihood computation, we will worry about the smoother (and which smoothers we need) later. All the best, Michel G. Perendia wrote: > Deara Michel > > Thanks. > > As you already pointed out, the KF software from SVN is highly > over-modularised and difficult to grasp and modify. But we may not have to > modify much as it has some of the functionalities we expect already built-in > such as univariate and multivariate filtering, smoother and diffuse priors. > Also, as mentioned earlier, it should integrate well with other Dynare > applications around dynarelib (it uses sylvester code too). So far the > only two package that uses LAPACK/BLAS (either the optimised one , or, if > customised, the bespoke ports to various parallel hardware platforms) are > dynarelib/KF and a smaller of the two Bayesian filter libraries ( C++ > Bayesian Filtering Classes by Michael Stevens, see enclosed draft analysis). > > The most of other internet KF packages either rely on BOOST/uBLAS or their > own > matrix calculation implementations. And, contrary to my initial assumptions, > uBLAS, as the most of the BOOST libraries it is part of, is a self-contained > "header" library that implements most of important basic algebra > functionality in header (.hpp) files. It therefore does not use (or > interface) any external libraries such as LAPACK/BLAS and, all compiling and > optimisation is done at application compilation time. This is one of reasons > our SVN KF still scores high among the alternatives. > > Smoothing, however, is also present in one of the Bayesian filtering > packages (Orocos ), and though that one relies on BOOST/uBLAS header > libraries, the Orocos BFL is probably best (i.e. functionally richest) > alternative. > > Altogether it is still difficult to derive single recommendation and I am > still working on analysing the available packages - The latest draft > analysis is enclosed . > > Best regards > > George > > ----- Original Message ----- > From: "Michel Juillard" <michel.juillard(a)ens.fr> > To: "G. Perendia" <george(a)perendia.orangehome.co.uk> > Sent: Sunday, May 10, 2009 1:28 PM > Subject: Re: Extracting rules for deterministic exogenous vars > > > >> There should be no problem if we want ot use it. This was developed for >> the Dynare project. What do you think of the code? >> >> best >> >> Michel >> >> G. Perendia wrote: >> >>> Dear Michel >>> I wandered also if we are allowed to use it. >>> Best regards >>> >>> George >>> >>> ----- Original Message ----- >>> From: "Michel Juillard" <michel.juillard(a)ens.fr> >>> To: "G. Perendia" <george(a)perendia.orangehome.co.uk> >>> Sent: Tuesday, May 05, 2009 1:49 PM >>> Subject: Re: Extracting rules for deterministic exogenous vars >>> >>> >>> >>> >>>> Hi George, >>>> >>>> my memory that it was too modular in conception and hard to understand, >>>> but I will fish it back and send it to you. >>>> >>>> All the best, >>>> >>>> Michel >>>> >>>> G. Perendia wrote: >>>> >>>> >>>>> Dear Michel >>>>> >>>>> I started looking into Kalman Filter DLL - Can we still re-use the >>>>> (existing?) Kalman Filter code that was/is (??) in SVN for the new >>>>> > KF? > >>>>> PS: I.e., I can not see, find or access the Kalman_Filter SVN repo any >>>>> more - i.e. since the move- - but browsing inside the current repo did >>>>> >>>>> >>> not >>> >>> >>>>> find Kalman-Filter." >>>>> >>>>> Best regards >>>>> >>>>> George >>>>> Mob. +44(0)7951415480 >>>>> artilogica(a)btconnect.com >>>>> >>>>> ----- Original Message ----- >>>>> From: "Michel Juillard" <michel.juillard(a)ens.fr> >>>>> To: "G. Perendia" <george(a)perendia.orangehome.co.uk>; "List for Dynare >>>>> developers" <dev(a)dynare.org> >>>>> Sent: Monday, April 27, 2009 8:33 PM >>>>> Subject: Re: Extracting rules for deterministic exogenous vars >>>>> >>>>> >>>>> >>>>> >>>>> >>>>>> Hi George, >>>>>> >>>>>> I have completely forgotten about dr.fuu, I don't see at the moment >>>>>> >>>>>> >>> what >>> >>> >>>>>> it is useful for. >>>>>> Porting the varexo_det stuff to C++ isn't a priority, far from it. >>>>>> I would rather that you clean-up existing k_order_perturbation code. >>>>>> When that is done, I would like you to turn to the Kalman filter, but >>>>>> >>>>>> >>> we >>> >>> >>>>>> will need to do a careful analysis before starting to code. >>>>>> One question will be which matrix implementation to use in the Kalman >>>>>> filter code? Shall we keep using Ondra's TwoD matrices? Shall we >>>>>> > build > >>>>>> our own (doubtful)? Should we use something like Boost? >>>>>> >>>>>> Best >>>>>> >>>>>> Michel >>>>>> >>>>>> >>>>>> G. Perendia wrote: >>>>>> >>>>>> >>>>>> >>>>>>> Dear Michel >>>>>>> >>>>>>> I was thinking of re-using some of the existing 2nd order dr1.m code >>>>>>> >>>>>>> >>> to >>> >>> >>>>>>> determine dr.fuu and the rules for, if any, deterministic exogenous >>>>>>> >>>>>>> >>> vars >>> >>> >>>>>>> (dr.gh??d). >>>>>>> >>>>>>> Looking at the code in dr1.m, for both dr.fuu and deterministic >>>>>>> >>>>>>> >>>>>>> >>>>> exogenous >>>>> >>>>> >>>>> >>>>>>> vars, we need hessian and, for the former, jacobian. Shall I >>>>>>> > retrieve > >>>>>>> >>>>> them >>>>> >>>>> >>>>> >>>>>>> from k-order-perturbation or is there a more elegant way to get >>>>>>> > those > >>>>>>> >>>>> rules >>>>> >>>>> >>>>> >>>>>>> that you can think of? Perhaps we can determine fuu from ghs2 (if >>>>>>> > not > >>> 0) >>> >>> >>>>>>> more elegantly but I can not see it as yet. >>>>>>> >>>>>>> I however could not find where dr.fuu is used other than internally >>>>>>> >>>>>>> >>>>>>> >>>>> within >>>>> >>>>> >>>>> >>>>>>> dr1.m (and dr11_sparse.m). That could mean that we only need hessian >>>>>>> >>>>>>> >>> and >>> >>> >>>>>>> only infrequently when if we have deterministic exogenous vars. >>>>>>> >>>>>>> Best regards >>>>>>> >>>>>>> George >>>>>>> Mob. +44(0)7951415480 >>>>>>> artilogica(a)btconnect.com >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>> >>>>> >>>> >>> >>> >>> >>

1 0

Re: [DynareDev] cleaning up korderpert
by Michel Juillard 06 May '09

06 May '09

Thanks George. I guess that we will have to live with *.cpp and .hpp in some directories. Best Michel Quoting "G. Perendia" <george(a)perendia.orangehome.co.uk>: > Dear Michel > > I filtered out DOS ^Ms and replaced tabs with 2 spaces. My editors (MSVC and > Matlab) do not provide support for .cc and .hh file extensions but only the > more standard .cpp and .hpp. Shall then I also rename those files in the > SVN to fully match Dynare coding standards (though there is gensylv code > that does not follow that rule)?. > > Best regards > > George > > ----- Original Message ----- > From: "Michel Juillard" <michel.juillard(a)ens.fr> > To: "G. Perendia" <george(a)perendia.orangehome.co.uk> > Sent: Tuesday, May 05, 2009 2:26 PM > Subject: cleaning up korderpert > > > > > > Hi George, > > > > when you clean-up the code of korderpert, could you please follow the > > coding standards in > > http://www.dynare.org/DynareWiki/CodingStandards, including an > > indentation of 2 spaces, > > and remove all the lines of code that were commented out because we > > preferred another alternative. > > Many thanks in advance > > All the best, > > > > Michel > > > > > > > > --

1 0