Solving Linear Rational Expectations Models: A Horse Race

Finance and Economics Discussion Series Divisions of Research & Statistics and Monetary Affairs Federal Reserve Board, Washington, D.C. Solving Linear Rational Expectations Models: A Horse Race Gary S. Anderson 2006-26 NOTE: Staff working papers in the Finance and Economics Discussion Series (FEDS) are preliminary materials circulated to stimulate discussion and critical comment. The analysis and conclusions set forth are those of the authors and do not indicate concurrence by other members of the research staff or the Board of Governors. References in publications to the Finance and Economics Discussion Series (other than acknowledgement) should be cleared with the author(s) to protect the tentative character of these papers.

Solving Linear Rational Expectations Models: A Horse Race Gary S. Anderson∗ Board of Governors of the Federal Reserve System May 24, 2006 Abstract This paper compares the functionality, accuracy, computational efficiency, and practicalities of alternative approaches to solving linear rational expectations models, including the procedures of (Sims, 1996), (Anderson and Moore, 1983), (Binder and Pesaran, 1994), (King and Watson, 1998), (Klein, 1999), and (Uhlig, 1999). While all six procedures yield similar results for models with a unique stationary solution, the AIM algorithm of (Anderson and Moore, 1983) provides the highest accuracy; furthermore,thisprocedureexhibitssignificantgainsincomputationalefficiencyforlarger-scalemodels. ∗IwouldliketothankRobertTetlow,AndrewLevinandBrianMadiganforusefuldiscussionsandsuggestions. Iwouldlike to thank Ed Yao for valuable help in obtaining and installing the MATLAB code. The views expressed in this document are myownanddonotnecessarilyreflectthepositionoftheFederalReserveBoardortheFederalReserveSystem. 1

May 24, 2006 2 1 Introduction and Summary Since (BlanchardandKahn,1980)anumberofalternativeapproachesforsolvinglinearrationalexpectations models have emerged. This paper describes, compares and contrasts the techniques of (Anderson, 1997; Anderson and Moore, 1983, 1985), (Binder and Pesaran, 1994), (King and Watson, 1998), (Klein, 1999), (Sims, 1996), and (Uhlig, 1999). All these authors provide MATLAB code implementing their algorithm.1 The paper compares the computational efficiency, functionality and accuracy of these MATLAB implementations. Thepaperusesnumericalexamplestocharacterizepracticaldifferencesinemployingthealternative procedures. Economistsusetheoutputoftheseproceduresforsimulatingmodels,estimatingmodels,computingimpulse response functions, calculating asymptotic covariance, solving infinite horizon linear quadratic control problems and constructing terminal constraints for nonlinear models. These applications benefit from the use of reliable, efficient and easy to use code. A comparison of the algorithms reveals that: • For models satisfying the Blanchard-Kahn conditions, the algorithms provide equivalent solutions.2 • The Anderson-Moore algorithm requires fewer floating point operations to achieve the same result. This computational advantage increases with the size of the model. • While the Anderson-Moore, Sims and Binder-Pesaran approaches provide matrix output for accommodating arbitrary exogenous processes, the King-Watson and Uhlig implementations only provide solutionsforVARexogenousprocess.3 Fortunately, therearestraightforwardformulaeforaugmenting the King-Watson Uhlig and Klein approaches with the matrices characterizing the impact of arbitrary shocks. • TheAnderson-Mooresuiteofprogramsprovidesasimplemodelinglanguagefordevelopingmodels. In addition, the Anderson-Moore implementation requires no special treatment for models with multiple lags and leads. To use each of the other algorithms, one must cast the model in a form with at most one lead or lag. This can be a tedious and error prone task for models with more than a couple of equations. • Using the Anderson-Moore algorithm to solve the quadratic matrix polynomial equation improves the performance of both Binder-Pesaran’s and Uhlig’s algorithms. Section2statestheproblemandintroducesnotation. Thispaperdividesthealgorithmsintothreecategories: eigensystem, QZ, and matrix polynomial methods. Section 3 describes the eigensystem methods. Section 4 describes applications of the QZ algorithm. Section 5 describes applications of the matrix polynomial approach. Section 6 compares the computational efficiency, functionality and accuracy of the algorithms. Section 7 concludes the paper. The appendices provide usage notes for each of the algorithms as well as information about how to compare inputs and outputs from each of the algorithms. 1 Although (Broze,Gouri´eroux,andSzafarz,1995)and (Zadrozny,1998)describealgorithms,Iwasunabletolocatecode implementingthealgorithms. 2 (BlanchardandKahn,1980)developedconditionsforexistenceanduniquenessoflinearrationalexpectationsmodels. In their setup, the solution of the rational expectations model is unique if the number of unstable eigenvectors of the system is exactlyequaltothenumberofforward-looking(control)variables. 3ImodifiedKlein’sMATLABversiontoincludethisfunctionalitybytranslatingtheapproachheusedinhisGaussversion.

May 24, 2006 3 2 Problem Statement and Notation These algorithms compute solutions for models of the form θ X H x =Ψz ,t=0,...,∞ (1) i t+i t i=−τ with initial conditions, if any, given by constraints of the form x =xdata,i=−τ,...,−1 (2) i i where both τ and θ are non-negative, and x is an L dimensional vector of endogenous variables with t lim kx k<∞ (3) t t→∞ and z is a k dimensional vector of exogenous variables. t (4) Solutions can be cast in the form −1 X (x −x∗)= B (x −x∗) t i t+i i=−τ GivenanyalgorithmthatcomputestheB ,onecaneasilycomputeotherquantitiesusefulforcharacterizing i the impact of exogenous variables. For models with τ =θ =1 the formulae are especially simple. Let Φ=(H +H B)−1 0 1 F =−ΦH B 1 We can write ∞ X (x −x∗)=B(x −x∗)+ Fsφψz t t−1 t+s s=0 and when z =Υz t+1 t vec(ϑ)=(I−ΥT ⊗F)−1vec(ΦΨ) (x −x∗)=B(x −x∗)+ϑz t t−1 t Consult (Anderson, 1997) for other useful formulae concerning rational expectations model solutions. IdownloadedtheMATLABcodeforeachimplementationinJuly,1999. Seethebibliographyfortherelevant URL’s.

May 24, 2006 4 3 Eigensystem Methods 3.1 The Anderson-Moore Algorithm (Anderson, 1997; Anderson and Moore, 1985) developed their algorithm in the mid 80’s for solving rational expectations models that arise in large scale macro models. Appendix B.1 on page 13 provides a synopsis of the model concepts and algorithm inputs and outputs. Appendix A presents pseudocode for the algorithm. Thealgorithmdetermineswhetherequation1hasauniquesolution,aninfinityofsolutionsornosolutionsat all. ThealgorithmproducesamatrixQcodifyingthelinearconstraintsguaranteeingasymptoticconvergence. The matrix Q provides a strategic point of departure for making many rational expectations computations. The uniqueness of solutions to system 1 requires that the transition matrix characterizing the linear system have appropriate numbers of explosive and stable eigenvalues (Blanchard and Kahn, 1980), and that the asymptotic linear constraints are linearly independent of explicit and implicit initial conditions (Anderson and Moore, 1985). The solution methodology entails 1. Manipulating equation 1 to compute a state space transition matrix. 2. Computing the eigenvalues and the invariant space associated with explosive eigenvalues 3. Combining the constraints provided by: (a) the initial conditions, (b) auxiliary initial conditions identified in the computation of the transition matrix and (c) the invariant space vectors The first phase of the algorithm computes a transition matrix, A, and auxiliary initial conditions, Z. The second phase combines left invariant space vectors associated with large eigenvalues of A with the auxiliary initial conditions to produce the matrix Q characterizing the saddle point solution. Provided the right hand half of Q is invertible, the algorithm computes the matrix B, an autoregressive representation of the unique saddle point solution. TheAnderson-Mooremethodologydoesnotexplicitlydistinguishbetweenpredeterminedandnon-predetermined variables. The algorithm assumes that history fixes the values of all variables dated prior to time t and that these initial conditions, the saddle point property terminal conditions, and the model equations determine all subsequent variable values. 3.2 King & Watson’s Canonical Variables/System Reduction Method (King and Watson, 1998) describe another method for solving rational expectations models. Appendix B.2 provides a synopsis of the model concepts and algorithm inputs and outputs. The algorithm consists of two parts: system reduction for efficiency and canonical variables solution for solving the saddle point problem. Although their paper describes how to accommodate arbitrary exogenous shocks, the MATLAB function does not return the relevant matrices. King-WatsonprovideaMATLABfunction,resolkw,thatcomputessolutions. TheMATLABfunctiontransforms the original system to facilitate the canonical variables calculations. The mdrkw program computes the solution assuming the exogenous variables follow a vector autoregressive process. Given: AE(y )=By +Cx t+1 t t

May 24, 2006 5 system reduction produces an equivalent model of the form 0=f +Kd +Ψ (F)E(x ) t t f t E(d )=Wd +Ψ (F)E(x ) t+1 t d t Where d are the “dynamic” variables and f are the “flow” variables in the y vector. t t t The mdrkw program takes the reduced system produced by redkw and the decomposition of its dynamic subsystem computed by dynkw and computes the rational expectations solution. The computation can use either eigenvalue-eigenvector decomposition or Schur decomposition. Appendix B.2.1 shows one way to compute the King-Watson solution using the Anderson-Moore algorithm. Appendix B.2.2 shows one way to compute the Anderson-Moore solution using the King-Watson algorithm. 4 Applications of the QZ Algorithm Several authors exploit the properties of the Generalized Schur Form (Golub and van Loan, 1989). Theorem 1 The Complex Generalized Schur Form – If A and B are in Cn×n, then there exist unitary Q and Z such that QHAZ =T and QHBZ =S are upper triangular. If for some k, t and s are both zero, kk kk then λ(A,B)=C. Otherwise, λ(A,B)={ s ti i i i :s ii 6=0} The algorithm uses the QZ decomposition to recast equation 5 in a canonical form that makes it possible to solve the transformed system “forward” for endogenous variables consistent with arbitrary values of the future exogenous variables. 4.1 Sims’ QZ Method (Sims, 1996) describes the QZ Method. His algorithm solves a linear rational expectations model of the form: Γ y =Γ y +C+Ψz +Πη (5) 0 t 1 t−1 t t where t = 1,2,3,··· ,∞ and C is a vector of constants, z is an exogenously evolving, possibly serially t correlated, random disturbance, and η is an expectational error, satisfying E η =0. t t t+1 Here, as with all the algorithms except the Anderson-Moore algorithm, one must cast the model in a form with one lag and no leads. This can be problematic for models with more than a couple of equations. Appendix B.3 summarizes the Sims’ QZ method model concepts and algorithm inputs and outputs. The Π designation of expectational errors identifies the “predetermined” variables. The Anderson-Moore technique does not explicitly require the identification of expectational errors. In applying the Anderson- Moore technique, one chooses the time subscript of the variables that appear in the equations. All predetermined variables have historical values available through time t−1. The evolution of the solution path can have no effect on any variables dated (t−1) or earlier. Future model values may influence time t values of any variable. AppendixB.3.1showsonewaytotransformtheproblemfromSims’formtoAnderson-Mooreformandhow toreconcilethesolutions. Forthesakeofcomparison,theAnderson-MooretransformationaddsLθvariables and the same number of equations, setting future expectation errors to zero. Appendix B.3.2 shows one way to transform the problem from Anderson-Moore form to Sims form.

May 24, 2006 6 4.2 Klein’s Approach (Klein, 1999) describes another method. Appendix B.4 summarizes the model concepts and algorithm inputs and outputs. ThealgorithmusestheGeneralizedSchurDecompositiontodecouplebackwardandforwardvariablesofthe transformed system. Although the MATLAB version does not provide solutions for autoregressive exogenous variables, one can solve the autoregressive exogenous variables problem by augmenting the system. The MATLAB program does not return matrices for computing the impact of arbitrary exogenous factors. Appendix B.4.1 describes one way to recast a model from a form suitable for Klein into a form for the Anderson-Moore algorithm. Appendix B.4.2 describes one way to recast a model from a form suitable for the Anderson-Moore methodology into a form for the Klein Algorithm. 5 Applications of the Matrix Polynomial Approach Several algorithms rely on determining a matrix C satisfying H C2+H C+H =0. (6) 1 0 −1 Theyemploylinearalgebraictechniquestosolvethisquadraticequation. Generallytherearemanysolutions. When the homogeneous linear system has a unique saddle-path solution, the Anderson-Moore algorithm constructs the unique matrix C =B that satisfies the quadratic matrix equation and has all roots inside AM the unit circle. H C2 +H C +H =0 1 AM 0 AM −1 5.1 Binder & Pesaran’s Method (Binder and Pesaran, 1994) describe another method. According to Binder & Pesaran(1994), under certain conditions, the unique stable solution, if it exists, is given by: ∞ X x =Cx + FiE(w ) t t−1 t+1 i=0 where F =(I−BC)−1B and C satisfies a quadratic equation like equation 6. Theiralgorithmconsistsofa“recursive”applicationofthelinearequationsdefiningtherelationshipsbetween C, H and F. Appendix B.5.1 describes one way to recast a model from a form suitable for Binder-Pesaran into a form for the Anderson-Moore algorithm. Appendix B.5.2 describes one way to recast a model from a form suitable for the Anderson-Moore methodology into a form for the Binder-Pesaran Algorithm. 5.2 Uhlig’s Technique (Uhlig, 1999) describes another method. The algorithm uses generalized eigenvalue calculations to obtain a solution for the matrix polynomial equation.

May 24, 2006 7 One can view the Uhlig technique as preprocessing of the input matrices to reduce the dimension of the quadratic matrix polynomial. It turns out that once the simplification has been done, the Anderson-Moore algorithm computes the solution to the matrix polynomial more efficiently than the approach adopted in Uhlig’s algorithm. Uhlig’s algorithm operates on matrices of the form: (cid:20) (cid:21) B 0 A C 0 0 H 0 G K F J Uhlig in effect pre-multiplies the equations by the matrix  C0 0   C+  −KC+ I where C0C =0,C+ =(CTC)−1CT to get  C0B 0 C0A 0 0 0   C+B 0 C+A I 0 0 H −KC+B 0 G−KC+A 0 F J one can imagine leading the second block of equations by one period and using them to annihilate J to get  0 0 C0B 0 C0A 0  H −KC+B 0 G−KC+A−JC+B 0 F −JC+A 0 0 0 C+B 0 C+A I This step in effect decouples the second set of equations making it possible to investigate the asymptotic properties by focusing on a smaller system. (cid:20) 0 C0B C0A (cid:21) H −KC+B G−KC+A−JC+B F −JC+A Uhlig’s algorithm undertakes the solution of a quadratic equation like equation 6 with (cid:20) C0A (cid:21) (cid:20) C0B (cid:21) (cid:20) 0 (cid:21) H = ,H = ,H = 1 F −JC+A 0 G−KC+A−JC+B −1 H −KC+B Appendix B.6.2 describes one way to recast a model from a form suitable for Uhlig into a form for the Anderson-Moore algorithm. Appendix B.6.1 describes one way to recast a model from a form suitable for the Anderson-Moore methodology into a form for the Uhlig Algorithm. 6 Comparisons Section2identifiedB,ϑ,φandF aspotentialoutputsofalinearrationalexpectationalgorithm. Mostofthe implementations do not compute each of the potential outputs. Only Anderson-Moore and Binder-Pesaran provide all four outputs (See Table 6). Generally, the implementations make restrictions on the form of the input. Most require the user to specify models with at most one lag or one lead. Only Anderson-Moore explicitly allows multiple lags and leads. EachoftheauthorsprovidessmallillustrativemodelsalongwiththeirMATLABcode. Thenexttwosections present results from applying all the algorithms to each of the example models.

May 24, 2006 8 Table 1: Modeling Features Technique B ϑ φ,F Usage Notes Anderson-Moore 4 4 4 Allows multiple lags and leads. Has modeling language. King & Watson 4 4 one lead, no lags Sims 4 4 one lag, no leads Klein 4 4 one lead, no lags Binder-Peseran 4 4 4 onelag,onelead;Cˆmustbenonsingular Uhlig 4 4 one lag, one lead; constraint involving choice of “jump” variables and rank condition on C. Note: • The Klein and Uhlig procedures compute ϑ by augmenting linear system • For the Uhlig procedure one must choose “jump” variables to guarantee that the C matrix has full rank. 6.1 Computational Efficiency Nearlyallthealgorithmssuccessfullycomputedsolutionsforalltheexamples. Eachofthealgorithms,except Binder-Pesaran’s, successfully computed solutions for all of Uhlig’s examples. Uhlig’s algorithm failed to provide a solution for the given parametrization of one of King’s examples. However, Binder-Pesaran’s and Uhlig’sroutineswouldlikelysolvealternativeparametrizationofthemodelsthathadconvergenceproblems. Tables 2-4 present the MATLAB-reported floating point operations (flops) counts for each of the algorithms applied to the example models. The first column of each table identifies the example model. The second column provides the flops required by the Anderson-Moore algorithm to compute B followed by the flops required to compute B, ϑ, φ, and F. Columns three through seven report the flops required by each algorithm divided by the flops required by the Anderson-Moore algorithm for a given example model. NotethattheAnderson-Moorealgorithmtypicallyrequiredafractionofthenumberofflopsrequiredbythe other algorithms. For example, King-Watson’s algorithm required more than three times the flops required by the Anderson-Moore algorithm for the first Uhlig example. In the first row, one observes that Uhlig’s algorithm required only 92% of the number of flops required by the Anderson-Moore algorithm, but this is the only instance where an alternative to the Anderson-Moore algorithm required fewer flops. In general, Anderson-Moore provides solutions with the least computational effort. There were only a few caseswheresomealternativehadapproximatelythesamenumberoffloatingpointoperations. Theefficiency advantage was especially pronounced for larger models. King-Watson generally used twice to three times the number of floating point operations. Sims generally used thirty times the number of floating point operations – never fewer than Anderson-Moore, King-Watson or Uhlig. It had about the same performance as Klein. Klein generally used thirty times the number of floating point operations. It never used fewer than Anderson-Moore, King-Watson or Uhlig. Binder-Pesaran was consistently the most computationally expensivealgorithm. Itgenerallyusedhundredsoftimesmorefloatingpointoperations. Inonecase,ittook asmanyas100,000timesthenumberoffloatingpointoperations. Uhliggenerallyusedabouttwicetheflops of Anderson-Moore even for small models and many more flops for larger models. Table 5 presents a comparison of the original Uhlig algorithm to a version using Anderson-Moore to solve thequadraticpolynomialequation. EmployingtheAnderson-Moorealgorithmspeedsthecomputation. The difference was most dramatic for larger models.

May 24, 2006 9 6.2 Numerical Accuracy Tables 6-11 presents the MATLAB relative errors. I have employed a symbolic algebra version of the Anderson-Moore algorithm to compute solutions to high precision4. Although ϑ and F are relatively simple lineartransformationsofB,eachoftheauthorsusesradicallydifferentmethodstocomputethesequantities. I then compare the matrices computed in MATLAB by each algorithm to the high precision solution. Anderson-Moorealwayscomputedthecorrectsolutionandinalmosteverycaseproducedthemostaccurate solution. Relativeerrorswereontheorderof10−16. King-Watsonalwayscomputedthecorrectsolution,but produced solutions with relative errors generally 3 times the size of the Anderson-Moore algorithm. Sims always computed correct solutions but produced solutions with relative errors generally 5 times the size of the Anderson-Moore algorithm. 5 Sim’s F calculation produced errors that were 20 times the size of the Anderson-Moore relative errors. Klein always computed the correct solution but produced solutions with relative errors generally 5 times the size of the Anderson-Moore algorithm. Uhlig provides accurate solutions with relative errors about twice the size of the Anderson-Moore algorithm for each case for which it converges. It cannot provide a solution for King’s example 3 for the particular parametrization I employed. I did not explore alternative parametrizations. For the ϑ computation, the results were similar. The algorithm was unable to compute ϑ for King example 3. Errors were generally 10 times the size of Anderson-Moore relative errors. Binder-PesaranconvergestoanincorrectvalueforthreeoftheUhligexamples: example3,6andexample7. Ineachcase, theresultingmatrixsolvesthequadraticmatrixpolynomial, buttheparticularsolutionhasan eigenvalue greaterthanone inmagnitude eventhoughanalternative matrixsolutionexists witheigenvalues less than unity. For Uhlig’s example 3, the algorithm diverges and produces a matrix with NaN’s. Even when the algorithm converges to approximate the correct solution, the errors are much larger than the other algorithms. One could tighten the convergence criterion at the expense of increasing computational time, but the algorithm is already the slowest of the algorithms evaluated. Binder-Pesaran’s algorithm does not converge for either of Sims’ examples. The algorithm provides accurate answers for King & Watson’s examples. Althoughtheconvergencedependsontheparticularparametrization,Ididnotexplorealternative parametrization when the algorithm’s did not converge. The ϑ and F results were similar to the B results. The algorithm was unable to compute H for Uhlig 3 in addition to Uhlig 7. It computed the wrong value for Uhlig 6. It was unable to compute values for either of Sims’s examples. 7 Conclusions A comparison of the algorithms reveals that: • For models satisfying the Blanchard-Kahn conditions, the algorithms provide equivalent solutions. • The Anderson-Moore algorithm proved to be the most accurate. • Using the Anderson-Moore algorithm to solve the quadratic matrix polynomial equation improves the performance of both Binder-Pesaran’s and Uhlig’s algorithms. • While the Anderson-Moore, Sims and Binder-Pesaran approaches provide matrix output for accommodating arbitrary exogenous processes, the King-Watson and Uhlig implementations only provide solutionsforVARexogenousprocess.6 Fortunately, therearestraightforwardformulaeforaugmenting 4Icomputedexactsolutionswhenthistooklessthan5minutesandsolutionscorrectto30decimalplacesinallothercases. 5TocompareF forSimsnotethat Ψ=IL F =(Θy.Θ f )Φ− ex 1 act 6ImodifiedKlein’sMATLABversiontoincludethisfunctionalitybytranslatingtheapproachheusedinhisGaussversion.

May 24, 2006 10 theKing-Watson,UhligandKleinapproacheswiththematricescharacterizingtheimpactofarbitrary shocks. • The Anderson-Moore algorithm requires fewer floating point operations to achieve the same result. This computational advantage increases with the size of the model. • TheAnderson-Mooresuiteofprogramsprovidesasimplemodelinglanguagefordevelopingmodels. In addition, the Anderson-Moore algorithm requires no special treatment for models with multiple lags and leads. To use each of the other algorithms, one must cast the model in a form with at most one leadorlag. Thiscanbetediousanderrorpronetaskformodelswithmorethanacoupleofequations.

May 24, 2006 11 8 Bibliography Gary Anderson. A reliable and computationally efficient algorithm for imposing the saddle point property in dynamic models. Unpublished Manuscript, Board of Governors of the Federal Reserve System. Downloadable copies of this and other related papers at http://www.federalreserve.gov/pubs/oss/oss4/aimindex.html, 1997. Gary Anderson and George Moore. An efficient procedure for solving linear perfect foresight models. 1983. Gary Anderson and George Moore. A linear algebraic procedure for solving linear perfect foresight models. Economics Letters, (3), 1985. URL http://www.federalreserve.gov/pubs/oss/oss4/aimindex.html. Michael Binder and M. Hashem Pesaran. Multivariate rational expectations models and macroeconometric modelling: A review and some new results. URL http://www.inform.umd.edu/EdRes/Colleges/BSOS/ Depts/Economics/mbinder/research/matlabresparse.html. Seminar Paper, May 1994. Olivier Jean Blanchard and C. Kahn. The solution of linear difference models under rational expectations. Econometrica, 48, 1980. Laurence Broze, Christian Gouri´eroux, and Ariane Szafarz. Solutions of multivariate rational expectations models. Econometric Theory, 11:229–257, 1995. Gene H. Golub and Charles F. van Loan. Matrix Computations. Johns Hopkins, 1989. Robert G. King and Mark W. Watson. The solution of singular linear difference systems under rational expectations. International Economic Review, 39(4):1015–1026, November 1998. URL http: //www.people.virginia.edu/~rgk4m/kwre/kwre.html. Paul Klein. Using the generalized schur form to solve a multivariate linear rational expectations model. Journal of Economic Dynamics and Control, 1999. URL http://www.iies.su.se/data/home/kleinp/ homepage.htm. ChristopherA.Sims.Solvinglinearrationalexpectationsmodels.URLhttp://www.econ.yale.edu/~sims/ #gensys. Seminar paper, 1996. Harald Uhlig. A toolkit for analyzing nonlinear dynamic stochastic models easily. URL http://cwis.kub. nl/~few5/center/STAFF/uhlig/toolkit.dir/toolkit.htm. User’s Guide, 1999. PeterA.Zadrozny. Aneigenvaluemethodofundeterminedcoefficientsforsolvinglinearrationalexpectations models. Journal of Economic Dynamics and Control, 22:1353–1373, 1998.

May 24, 2006 12 Appendix A The Anderson-Moore Algorithm(s) Algorithm 1 1 Given H, compute the unconstrained autoregression. 2 funct F 1 (H) ≡ 3 k :=0 4 Z0 :=∅ 5 H0 :=H 6 Γ:=∅ 7 while H θ k is singular ∩rows(Zk)<L(τ +θ) 8 do (cid:20) Uk(cid:21) 9 Uk = U Z k :=rowAnnihilator(H θ k) N(cid:20) 0 UkHk ... UkHk (cid:21) 10 Hk+1 := UkHk Z . τ .. U Z kH θ− k 1 (cid:20) N τ Qk (cid:21) N θ 11 Zk+1 := UkHk ... UkHk Z τ Z θ−1 12 k :=k+1 13 od 14 Γ=− (cid:20) H θ −1 (cid:21) (cid:2) H −τ ... H θ−1 (cid:3) 0 I 15 A= Γ 16 return{ (cid:2) H − kτ ... H θ k(cid:3) ,A,Zk} 17 . Algorithm 2 1 Given V,Z],∗, 2 funct F 2 (A,Z],∗) 3 Compute V, the vectors spanning the left 4 invariant space associated with eigenvalues 5 greater than one in magnitude (cid:20) Z],∗(cid:21) 6 Q:= V 7 return{Q} 8 . Algorithm 3 1 Given Q, 2 funct F 3 (Q) 3 cnt=noRows(Q)   { { Q Q , , ∞ 0} } c c n n t t < > L L θ θ 4 return  { { B Q, = ∞ − } Q− R 1Q L ,1} ( o Q th R e s r i w n i g s u e lar) 5 .

May 24, 2006 13 Appendix B Model Concepts The following sections present the inputs and outputs for each of the algorithms for the following simple example: V =(1+R)V −D t+1 t t+1 D =(1−δ)D t−1 Appendix B.1 Anderson-Moore Inputs θ X H x =Ψz i t+i t i=−τ Model Variable Description Dimensions x State Variables L(τ +θ)×1 t z Exogenous Variables M ×1 t θ Longest Lead 1×1 τ Longest Lag 1×1 H Structural Coefficients Matrix (L×L)(τ +θ+1) i Ψ Exogenous Shock Coefficients Matrix L×M Υ Optional Exogenous VAR Coefficients M ×M Matrix(z =Υz ) t+1 t Outputs   x t−τ ∞ (cid:20) (cid:21) x =B . . + (cid:2) 0 ...0 I (cid:3)X (Fs 0 ) t  .  ΦΨz t+s x s=0 t−1 Model Variable Description Dimensions B reduced form coefficients matrix L×L(τ +θ) Φ exogenous shock scaling matrix L×L F exogenous shock transfer matrix Lθ×Lθ ϑ autoregressive shock transfer matrix when L×M z =Υz the infinite sum simplifies to give t+1 t   x t−τ . x =B . +ϑz t  .  t x t−1

May 24, 2006 14 Anderson-Moore input: AIM Modeling Language Input 1 MODEL> FIRMVALUE 2 ENDOG> 3 V 4 DIV 5 EQUATION> VALUE 6 EQ> LEAD(V,1) = (1+R)*V - LEAD(DIV,1) 7 EQUATION> DIVIDEND 8 EQ> DIV = (1-DELTA)*LAG(DIV,1) 9 END Parameter File Input 1 DELTA=0.3; 2 R=0.1; 3 psi=[4. 1.;3. -2.]; 4 upsilon=[0.9 0.1;0.05 0.2]; (cid:20) (cid:21) (cid:20) (cid:21) (cid:20) (cid:21) 0 0 −1.1 0 1 1. 4. 1. 0.9 0.1 H = ,Ψ= ,Υ 0 −0.7 0 1 0 0 3. −2. 0.05 0.2 produces output: (cid:20) (cid:21) (cid:20) (cid:21) (cid:20) (cid:21) 0. 1.225 0.909091 0.909091 −0.909091 1.75 B = F = Φ= 0. 0.7 0. 0. 0. 1. (cid:20) (cid:21) (cid:20) (cid:21) 1.61364 −4.40909 21.0857 −3.15714 ΦΨ= ϑ= 3. −2. 3. −2. Usage Notes for Anderson-Moore Algorithm 1. “Align” model variables so that the data history (without applying model equations), completely determines all of x , but none of x . t−1 t 2. Develop a “model file” containing the model equations written in the “AIM modeling language” 3. Apply the model pre-processor to create MATLAB programs for initializing the algorithm’s input matrix,(H). Create Ψ and, optionally, Υ matrices. 4. Execute the MATLAB programs to generate B, φ, F and optionally ϑ Users can obtain code for the algorithm and the preprocessor from the author7 7 http://www.bog.frb.fed.us/pubs/oss/oss4/aimindex.htmlJuly,1999.

May 24, 2006 15 Appendix B.2 King-Watson Inputs θ X AE y =By + C E (x ) t t+1 t i t t+i i=0 x =Qδ t t δ =ρδ +G(cid:15) t t−1 t » – Λ y = t t k t Model Variable Description Dimensions θ longest lead 1×1 y Endogenous Variables m×1 t Λ Non-predetermined Endogenous Variables (m−p)×1 t k Predetermined Endogenous Variables p×1 t x Exogenous Variables n ×1 t x δ Exogenous Variables n ×1 t δ A Structural Coefficients Matrix associated with lead m×m endogenous variables, y t+1 B Structural Coefficients Matrix associated with con- m×m temporaneous endogenous variables, y t C Structural Coefficients Matrix associated with con- m×n i temporaneous and lead exogenous variables, x t Q Structural Coefficients Matrix associated with con- n ×n x δ temporaneous exogenous variables, x t ρ VectorAutoregressionmatrixforexogenousvariables n ×n δ δ G Matrix multiplying Exogenous Shock n ×1 δ Outputs y =Πs t t s =Ms +G¯(cid:15) t t−1 t » – k s = t t δ t Model Variable Description Dimensions s Exogenous Variables and predetermined variables (n +p)×1 t x Π Matrix relating endogenous variables to exogenous m×(p+n ) x and predetermined variables M (p+n )×(p+n ) x x G¯ Matrix multiplying Exogenous Shock (n +p)×l x

May 24, 2006 16 King-Watson input:       1 0 0 0 0 0 1 0 0 0 0 1 0 0  0 0 0 1 0 0  A= ,B = ,C = , 0 0 −1 −1. 0 0 −1.1 0 4. 1.  0 0 0 0 0 −0.7 0 1 3. −2. (cid:20) (cid:21) (cid:20) (cid:21) (cid:20) (cid:21) 1 0 0.9 0.1 0 Q= ,ρ= ,G= 0 1 0.05 0.2 0 produces output:     1. 0. 0. 0. 0. 1.225 −21.0857 3.15714 0. 1. 0. 0.  0. 0.7 −3. 2.  Π= ,M =  0. 1.225 −21.0857 3.15714 0. 0. 0.9 0.1  0. 0.7 −3. 2. 0. 0. 0.05 0.2 Usage Notes for King-Watson Algorithm 1. Identify predetermined variables 2. Cast the model in King-Watson form: endogenous variable must have at most one lead and no lag. 3. Create matlab “system” and “driver” programs generating the input matrices. “system” generates (A,B,C ,nx = n ,ny = m), and a matlab vector containing indices corresponding to predetermined i x variables. “driver” generates (Q,ρ,G). 4. Call resolkw with sytem and driver filenames as inputs to generate Π,M,G¯ Appendix B.2.1 King-Watson to Anderson-Moore Obtaining Anderson-Moore inputs from King-Watson inputs 2 3 Λ t 2 0 3 θ:=θ,x t := 6 6 4x k t t 7 7 5 ,z t :=4 (cid:15) 05, δ t t ˆ ˜ ˆ ˜ Ψ:= 0 0 G Υ:= 0 0 ρ ˆ ˜ ˆ ˜ B B :=B, A A :=A 1 2 1 2 2 0 −B 0 0 −B A −C 0 2 1 2 0 H :=40 0 0 0 0 0 −I Q ... 0 0 0 0 −ρ 0 0 I 3 A 0 −C 0 0 0 −C 0 1 1 θ 0 0 0 0 ... 0 0 0 05 −G 0 0 0 0 0 0 0

May 24, 2006 17 Obtaining King-Watson outputs from Anderson-Moore outputs 2 0 Πˆ 0 Πˆ 3 Λk Λδ 6 6 40 0 M Πˆ x k k k 0 0 M Πˆ x k δ δ7 7 5 :=B 0 0 0 ρ » – M M M := kk kδ 0 ρ Π:= ˆ Πˆ Πˆ ˜ M−1 Λk Λδ G¯ := ˆ 0 0 0 I ˜ ΦΨ Appendix B.2.2 Anderson-Moore to King-Watson Obtaining King-Watson inputs from Anderson-Moore inputs 2 x 3 2 x 3 2x 3 t−τ t t−τ . . . y :=6 . 7,Λ :=6 . 7k :=6 . 7,x :=z t 4 . 5 t 4 . 5 t 4 . 5 t t x x x t+θ−1 t+θ−1 t−1 2I 0 3 A:= 6 6 ... . . . 7 7 6 7 4 I 0 5 0 ... 0 −H θ 2 0 I 3 B:= 6 6 . . . ... 7 7 6 7 4 0 I 5 H H ... H −τ −τ+1 θ−1 » – 0 C := ,Q:=I,ρ:=0,G:=0,p:=Lτ,θ:=1,m:=L(τ +θ) Ψ Obtaining Anderson-Moore outputs from King-Watson outputs 2 I 0 3 » B ϑ – 6B 1 ϑ 7 :=M,6 . . 7:=Π 0 ρ 6 . . 7 4 . . 5 B B ϑ θ (θ−1)R

May 24, 2006 18 Appendix B.3 Sims Inputs Γ y =Γ y +C+Ψz +Πη 0 t 1 t−1 t t Model Variable Description Dimensions y State Variables L×1 t z Exogenous Variables M ×1 t 1 η Expectational Error M ×1 t 2 Γ Structural Coefficients Matrix L×L 0 Γ Structural Coefficients Matrix L×L 1 C Constants L×1 Ψ Structural Exogenous Variables Coefficients Ma- L×M 1 trix Π Structural Expectational Errors Coefficients Ma- L×M 2 trix Outputs ∞ X y =Θ y +Θ +Θ z +Θ Θs−1Θ E z t 1 t−1 c 0 t y f z t t+s s=1 Model Variable Description Dimensions Θ L×L 1 Θ L×1 c Θ L×M 0 1 Θ L×M y 2 Θ M ×M f 2 2 Θ M ×M z 2 1

May 24, 2006 19 Sims input:       1 0 0 0 0 0 1 0 0  0 1 0 0 0 0 0 1 0 Γ 0 = −1.1 0 1 1.   ,Γ 1 = 0 0 0 0   ,C = 0   , 0 1 0 0 0 0.7 0 0 0     0 0 1 0 0 0  0 1 Ψ= ,Π=  4. 1.  0 0 3. −2. 0 0 produces output:     0. 1.61364 −4.40909 (cid:20) (cid:21) 0.  3. −2.  0.909091 1.23405 Θ c 0.   ,Θ 0 =  3.675 −2.45   ,Θ f = 0. 0. , 0. 2.1 −1.4   1.28794 1.74832 −2.2204510−16 −1.1102210−16  (cid:20) −0.0796719 −2.29972 (cid:21) Θ y =  1.41673 0.702491   ,Θ z = 2.4577 −1.63846 −1.1102210−16 1.22066   4.19421 −5.82645 −2.5516810−16 6.9254610−16  Θ y Θ z =  1.61364 −4.40909   , 3. −2. Usage Notes for Sims Algorithm 1. Identify predetermined variables 2. Cast the model in Sims form: at most 1 lag and 0 leads of endogenous variables. 3. Create the input matrices Γ ,Γ ,C,Ψ, and Π 0 1 4. Call gensys to generate Θ ,Θ ,Θ ,Θ ,Θ ,Θ 1 c 0 y f z Appendix B.3.1 Sims to Anderson-Moore Obtaining Anderson-Moore inputs from Sims inputs » – » – » – y z Ψ C x := t+s −x∗,z := t ,Ψ:= t+s η t 1 0 0 t+s » – −Γ 0 Γ −Π 0 0 H := 1 0 0 0 0 0 0 I

May 24, 2006 20 Obtaining Sims outputs from Anderson-Moore outputs 20 I 3 L(τ−1)×L L(τ−1) 6 B 7 Θ 1 :=6 6 . . 0 L(τ+θ)×Lθ 7 7 4 . 5 B θ 20 3 L(τ−1)×L 6 I 7 ˆ Θ Θ ˜ := 6 6 B R 7 7ΦΨ 0 c 6 6 . . 7 7 4 . 5 B θR 20 3 L(τ−1)×L 6 xˆ t 7 ∃S 3Θ f =SFS−1,Θ y Θ z =6 6 . . 7 7 4 . 5 xˆ t+θ+1 where xˆ’s come from iterating equation Appendix B.1 forward θ+1 time periods with z =0,s6=1 t t+s and z =I t+1 Appendix B.3.2 Anderson-Moore to Sims Obtaining Sims inputs from Anderson-Moore inputs 2 x 3 t−τ . y :=6 . 7,z :=z t 4 . 5 t t x t+θ−1 2I 0 3 2 0 I 3 Γ := 6 6 ... . . . 7 7Γ := 6 6 . . . ... 7 7 0 6 7 1 6 7 4 I 0 5 4 0 I 5 0 H ... −H H ... H 0 0 0 θ −τ −1 2 3 0 L(τ−1)×Lθ » 0 – Π:=4 I Lθ 5Ψ:= Lτ Ψ ×Lθ 0 L×Lθ Obtaining Anderson-Moore outputs from Sims outputs ˆ ˜ ˆ ˜ B :=Θ , ΦΨ :=Θ Θ 1 y f

May 24, 2006 21 Appendix B.4 Klein Inputs AEx =Bx +Cz +Dz t+1 t t+1 t (cid:20) (cid:21) k z =φz +(cid:15) x = t t+1 t t t u t Model Variable Description Dimensions x Endogenous Variables L×1 t z Exogenous Variables M ×1 t n The number of state Variables M ×1 k k State Variables n ×1 t k u The Non-state Variables (L−n )×1 t k A Structural Coefficients Matrix for Future Vari- L×L ables B Structural Coefficient Matrix for contemporane- L×L ous Variables Outputs u =Fk t t k =Pk t t−1 Model Variable Description Dimensions F Decision Rule (L−n )×n k k P Law of Motion n ×n k k Klein input:       1 0 0 0 0 0 1 0 0 0 0 1 0 0  0 0 0 1 0 0  A= ,B = ,C = , 0 0 −1 −1. 0 0 −1.1 0 4. 1.  0 0 0 0 0 −0.7 0 1 3. −2. produces output: (cid:20) (cid:21) (cid:20) (cid:21) 0.9 0.1 −21.0857 3.15714 P = ,F = , 0.05 0.2 −3. 2. Usage Notes for Klein Algorithm 1. Identify predetermined variables. Order the system so that predetermined variables come last. 2. Create the input matrices A,B.a 3. Call solab with the input matrices and the number of predetermined variables to generate F and P aTheGaussversionallowsadditionalfunctionality.

May 24, 2006 22 Appendix B.4.1 Klein to Anderson-Moore Obtaining Anderson-Moore inputs from Klein inputs 2 3 θ:=θ,x t :=4u k t t5,z t := » z z t – Ψ:= ˆ D C ˜ ,Υ:= » φ φ – z t+1 t ˆ ˜ ˆ ˜ B B :=B, A A :=A 1 2 1 2 2 0 −B 0 0 −B A −C 0 2 1 2 0 H :=40 0 0 0 0 0 −I Q ... 0 0 0 0 −ρ 0 0 I 3 A 0 −C 0 0 0 −C 0 1 1 θ 0 0 0 0 ... 0 0 0 05 −G 0 0 0 0 0 0 0 Obtaining Klein outputs from Anderson-Moore outputs 2 0 Fˆ 0 Fˆ 3 Λk Λδ 6 6 4 0 0 F P ˆ x kk k 0 0 F P ˆ x kδ δ 7 7 5 :=B 0 0 0 ρ » – P P P := kk kδ 0 ρ F := ˆ Fˆ Fˆ ˜ P−1 Λk Λδ G¯ := ˆ 0 0 0 I ˜ ΦΨ Appendix B.4.2 Anderson-Moore to Klein Obtaining Klein inputs from Anderson-Moore inputs 2 x 3 2 x 3 2x 3 t−τ t t−τ . . . y :=6 . 7,Λ :=6 . 7k :=6 . 7 t 4 . 5 t 4 . 5 t 4 . 5 x x x t+θ−1 t+θ−1 t−1 2I 0 3 A:= 6 6 ... . . . 7 7 6 7 4 I 0 5 0 ... 0 −H θ 2 0 I 3 B:= 6 6 . . . ... 7 7 6 7 4 0 I 5 H H ... H −τ −τ+1 θ−1 » – 0 C := ,Q:=I,ρ:=0,G:=0 Ψ

May 24, 2006 23 Obtaining Anderson-Moore outputs from Klein outputs 2 I 0 3 2 3 0 I 0 6B 1L B 1R ΦΨ 7 4 B ΦΨ5:=P,6 6 . . . . . . 7 7 :=F 0 0 4 . . . 5 B B B ΦΨ θL θR (θ−1)R

May 24, 2006 24 Appendix B.5 Binder-Pesaran Inputs Cˆx =Aˆx +BˆEx +D w +D w t t−1 t+1 1 t 2 t+1 w =Γw t t−1 Model Variable Description Dimensions x State Variables L×1 t w Exogenous Variables M ×1 t Aˆ Structural Coefficients Matrix L×L Bˆ Exogenous Shock Coefficients Matrix L×L Cˆ Exogenous Shock Coefficients Matrix L×M D Exogenous Shock Coefficients Matrix L×M 1 D Exogenous Shock Coefficients Matrix L×M 2 Γ Exogenous Shock Coefficients Matrix L×M Outputs x =Cx +Hw t t−1 t ∞ X x =Cx + FiE(w ) t t−1 t+1 i=0 Model Variable Description Dimensions C reduced form codifying convergence constraints L×L(τ +θ) H exogenous shock scaling matrix L×M Binder-Peseran input: (cid:20) (cid:21) (cid:20) (cid:21) (cid:20) (cid:21) (cid:20) (cid:21) 0 0 −1 −1. −1.1 0 4. 1. A= B = C = D = 0 0.7 0 0 0 1 1 3. −2. (cid:20) (cid:21) (cid:20) (cid:21) 0 0 0.9 0.1 D = Γ= 2 0 0 0.05 0.2 produces output: (cid:20) (cid:21) (cid:20) (cid:21) 0. 1.225 21.0857 −3.15714 C = H = 0. 0.7 3. −2. Usage Notes for Binder-Pesaran Algorithm 1. CastmodelinBinder-Pesaranform: atmostoneleadandonelagofendogenousvariables. Thematrix Cˆ must be nonsingular. 2. Modify existing Matlab script implementing Binder-Pesaran’s Recursive Method to create the input matrices Aˆ,Bˆ,Cˆ,D ,D Γ and to update the appropriate matrices in the “while loop.”8 1 2 3. Call the modified script to generate C and H and F.

May 24, 2006 25 Appendix B.5.1 Binder-Pesaran to Anderson-Moore Obtaining Anderson-Moore inputs from Binder-Pesaran inputs » – w x :=x ,z := t t t t w t+1 H := ˆ −Aˆ Cˆ Bˆ˜ » – Γ ˆ ˜ Υ:= ,Ψ:= D D Γ 1 2 Obtaining Binder-Pesaran outputs from Anderson-Moore outputs C :=B,H :=ΦΨ Appendix B.5.2 Anderson-Moore to Binder-Pesaran Obtaining Binder-Pesaran inputs from Anderson-Moore inputs 2 3 −I 0 L(τ−1) L(τ−1)×L(θ−1) A:=4 0 L(θ−1) 0 L(θ−1)×L(θ−1)5 H 0 −τ L×L(τ+θ−2) 2 3 0 0 L(τ−1) L(τ−1)×L(θ−1) B:=4 I L(θ−1)×L 0 L(θ−1) 5 0 H L×L(θ+τ−2) θ 2 3 I 0 0 L(τ−1) L(τ−1)×L(θ−1) L(τ−1)×L C :=40 L(θ−1)×L 0 L(θ−1) I L(θ−1)×L(θ−1)5 H ... H −τ+1 θ−1 » – 0 D := ,D =0,Γ=0 1 Ψ 2 Obtaining Anderson-Moore outputs from Binder-Pesaran outputs 2 0 3 6 ΦΨ 7 6 6 B R ΦΨ 7 7:=H 6 6 . . 7 7 4 . 5 B ΦΨ (θ−1)R 20 I 03 6 B 07 6 . 7:=C 6 . 7 4 . 05 B 0 θ

May 24, 2006 26 Appendix B.6 Uhlig Inputs Ax +Bx +Cy +Dz =0 t t−1 t t E(Fx +Gx +Hx +Jy +Ky +Lz +Mz ) t+1 t t−1 t+1 t t+1 t z =Nz +(cid:15) t+1 t t+1 E(cid:15) =0 t+1 Model Variable Description Dimensions x State Variables m×1 t y Endogenous “jump” Variables n×1 t z Exogenous Variables k×1 t A,B Structural Coefficients Matrix l×m C Structural Coefficients Matrix l×n D Structural Coefficients Matrix l×k F,G,H Structural Coefficients Matrix (m+n−l)×m J,K Structural Coefficients Matrix (m+n−l)×n L,M Structural Coefficients Matrix m+n−l×k N Structural Coefficients Matrix k×k Outputs x =Px +Qz t t−1 t y =Rx +Sz t t−1 t Model Variable Description Dimensions P m×m Q m×k R n×m S n×k ForUhligcannotfindC withtheappropriaterankconditionwithoutaugmentingthesystemwitha“dummy variable” and equation like W =D +V . t t t Uhlig input: (cid:20) (cid:21) (cid:20) (cid:21) (cid:20) (cid:21) (cid:20) (cid:21) 1 0 −0.7 0 0 −3. 2. A= B = C = D = 1 −1 0 0 1 0 0 (cid:2) (cid:3) (cid:2) (cid:3) (cid:2) (cid:3) (cid:2) (cid:3) (cid:2) (cid:3) F = 1. 0 G= 0 0 H = 0 0 J = 1 K = −1.1 (cid:20) (cid:21) (cid:2) (cid:3) (cid:2) (cid:3) 0.9 0.1 L= 0 0 M = −4. −1. N = 0.05 0.2 produces output: (cid:20) (cid:21) (cid:20) (cid:21) 0.7 0. 3. −2. P = Q= 1.925 6.1629810−33 24.0857 −5.15714 R= (cid:2) 1.225 6.1629810−33(cid:3) S = (cid:2) 21.0857 −3.15714 (cid:3)

May 24, 2006 27 Usage Notes for Uhlig Algorithm 1. CastmodelinUhligForm. Onemustbecarefultochooseendogenous“jump”andand“nonjump”variablesto guaranteethattheC matrixisappropriaterank. Theranknullspacemustbe(l−n)wherelisthenumberof equations with no lead variables,(the row dimension of C) and n is the total number of “jump” variables(thee column dimension of C). 2. Create matrices A,B,C,D,F,G,H,J,K,L,M,N 3. Call the function do it to generate P,Q,R,S,W Appendix B.6.1 Uhlig to Anderson-Moore Obtaining Anderson-Moore inputs from Uhlig inputs » – » – x B 0 A C D 0 0 x := t H := t y H 0 G K F J 0 t Υ:=N,Ψ:=L, Obtaining Uhlig outputs from Anderson-Moore outputs » – » – R Q :=B, :=ΦΨ P S Appendix B.6.2 Anderson-Moore to Uhlig Obtaining Uhlig inputs from Anderson-Moore inputs 2 3 −I 0 L(τ−1) L(τ−1)×L(θ−1) A:=4 0 L(θ−1) 0 L(θ−1)×L(θ−1)5 H 0 −τ L×L(τ+θ−2) 2 3 0 0 L(τ−1) L(τ−1)×L(θ−1) B:=4 I L(θ−1)×L 0 L(θ−1) 5 0 H L×L(θ+τ−2) θ 2 3 I 0 0 L(τ−1) L(τ−1)×L(θ−1) L(τ−1)×L C :=40 L(θ−1)×L 0 L(θ−1) I L(θ−1)×L(θ−1)5 H ... H −τ+1 θ−1 find permutation matrices % ,% L R » – B 0 A C 0 0 =% H(I ⊗% ) H 0 G K F J L 3 R and such that with l row dimension of C and n the column dimension of C rank(nullSpace(CT))=l−n » – ˆ ˜ 0 DM = % Ψ L

May 24, 2006 28 Obtaining Anderson-Moore outputs from Uhlig outputs » – » – P Q B:= ΦΨ:= R S

May 24, 2006 29 Appendix C Computational Efficiency Table 2: Matlab Flop Counts: Uhlig Examples Model AIM KW Sims Klein BP Uhlig (L,τ,θ) (m,p) (L,M ) (L,n ) L (m,n) 2 k Computes (B,ϑ,φ,F) (B,ϑ) (B,φ,F) (B) (B,ϑ,φ,F) (B,ϑ) uhlig 0 (2514,4098) 3.38385 23.9387 28.8007 88.7832 0.922832 (4,1,1) (8,4) (8,4) (8,3) 4 (3,1) uhlig 1 (6878,9817) 3.81346 46.9301 29.1669 15347.3 1.88979 (6,1,1) (12,6) (12,6) (12,5) 6 (5,1) uhlig 2 (6798,9773) 3.292 52.2499 35.7318 6468.78 1.80494 (6,1,1) (12,6) (12,6) (12,5) 6 (5,1) uhlig 3 (112555,276912) 3.62782 40.5874 22.6611 205753. 16.7633 (14,1,1) (28,14) (28,14) (28,13) 14 (10,4) uhlig 4 (6850,9789) 3.58292 45.675 29.5441 16250.5 1.89752 (6,1,1) (12,6) (12,6) (12,5) 6 (5,1) uhlig 5 (6850,9789) 3.58292 45.675 29.5441 16250.5 1.89752 (6,1,1) (12,6) (12,6) (12,5) 6 (5,1) uhlig 6 (7809,26235) 2.53182 47.5947 46.3196 190.905 3.42169 (6,1,1) (12,6) (12,6) (12,4) 6 (4,2) uhlig 7 (82320,108000) 2.8447 48.1792 28.9946 131.785 2.60423 (13,1,1) (26,13) (26,13) (26,11) 13 (11,2) Note: L,τ,θ,B,ϑ,φ,F See Appendix B.1 m,p See Appendix B.2 L,M See Appendix B.3 2 L,n See Appendix B.4 k L See Appendix B.5 m,n See Appendix B.6 KW,Sims,Klein,BP,Uhligcolumnnormalized by dividing by comparable AIM value.

May 24, 2006 30 Table 3: Matlab Flop Counts: King & Watson, Klein, Binder & Peseran and Sims Examples Model AIM KW Sims Klein BP Uhlig (L,τ,θ) (m,p) (L,M ) (L,n ) L (m,n) 2 k Computes (B,ϑ,φ,F) (B,ϑ) (B,φ,F) (B) (B,ϑ,φ,F) (B,ϑ) king 2 (2288,2566) 2.36713 9.64904 20.7072 165.623 1.76311 (3,1,1) (6,3) (6,3) (6,1) 3 (2,1) king 3 (1028,2306) 2.81809 21.1284 77.1858 368.545 NA (3,1,1) (6,3) (6,3) (6,-1) 3 (2,1) king 4 (40967,146710) 5.2211 39.8819 30.493 185.299 14.2569 (9,1,1) (18,9) (18,9) (18,5) 9 (3,6) sims 0 (3501,5576) 4.70923 59.9526 59.2871 NA 5.72694 (5,1,1) (10,5) (10,5) (10,3) 5 (4,1) sims 1 (16662,39249) 4.20292 56.8375 48.4135 NA 9.2849 (8,1,1) (16,8) (16,8) (16,5) 8 (6,2) klein 1 (3610,15147) 2.13213 10.2756 16.7828 35555.2 2.30526 (3,1,1) (6,3) (6,3) (6,2) 3 (1,2) bp 1 (533,1586) 3.1257 13.8987 59.7749 613.814 2.88743 (2,1,1) (4,2) (4,2) (4,0) 2 (1,1) bp 2 (3510,5659) 3.5265 77.2456 67.7846 800.98 21.4259 (5,1,1) (10,5) (10,5) (10,1) 5 (4,1) Note: L,τ,θ,B,ϑ,φ,F See Appendix B.1 m,p See Appendix B.2 L,M See Appendix B.3 2 L,n See Appendix B.4 k L See Appendix B.5 m,n See Appendix B.6 KW,Sims,Klein,BP,Uhligcolumnnormalized by dividing by comparable AIM value.

May 24, 2006 31 Table 4: Matlab Flop Counts: General Examples Model AIM KW Sims Klein BP Uhlig (L,τ,θ) (m,p) (L,M ) (L,n ) L (m,n) 2 k Computes (B,ϑ,φ,F) (B,ϑ) (B,φ,F) (B) (B,ϑ,φ,F) (B,ϑ) firmValue 1 (535,1586) 2.90467 11.5252 92.9738 534.686 NA (2,1,1) (4,2) (4,2) (4,0) 2 (1,1) athan 1 (18475,70162) 3.75578 135.329 113.463 1385.73 196.251 (9,1,1) (18,9) (18,9) (18,1) 9 (8,1) fuhrer 1 (352283,1885325) NA 125.141 148.459 NA NA (12,1,4) (60,12) (60,48) (60,1) 48 (9,39) Note: L,τ,θ,B,ϑ,φ,F See Appendix B.1 m,p See Appendix B.2 L,M See Appendix B.3 2 L,n See Appendix B.4 k L See Appendix B.5 m,n See Appendix B.6 KW,Sims,Klein,BP,Uhligcolumnnormalized by dividing by comparable AIM value.

May 24, 2006 32 Table 5: Using Anderson-Moore to Improve Matrix Polynomial Methods Model(m,n) Uhlig AM/Uhlig uhlig 0(3,1) 2320 2053 uhlig 1(5,1) 12998 12731 uhlig 2(5,1) 12270 12003 uhlig 3(10,4) 1886798 304534 uhlig 4(5,1) 12998 12731 uhlig 5(5,1) 12998 12731 uhlig 6(4,2) 26720 24233 uhlig 7(11,2) 214380 213450 Note: m,n See Appendix B.6

May 24, 2006 33 Appendix D Accuracy Table 6: Matlab Relative Errors in B: Uhlig Examples kB −B k i exact kB k exact Model AIM KW Sims Klein BP Uhlig (L,τ,θ) (m,p) (L,M ) (L,n ) L (m,n) 2 k Computes (B,ϑ,φ,F) (B,ϑ) (B,φ,F) (B) (B,ϑ,φ,F) (B,ϑ) uhlig 0 1:=1.6944610−16 8. 40. 11. 134848. 49. (4,1,1) (8,4) (8,4) (8,3) 4 (3,1) uhlig 1 1:=3.8237510−15 0.518098 2.63371 0.617504 10217.1 3.32793 (6,1,1) (12,6) (12,6) (12,5) 6 (5,1) uhlig 2 1:=4.8878510−15 1. 2.00589 6.43964 9520.85 2.82951 (6,1,1) (12,6) (12,6) (12,5) 6 (5,1) uhlig 3 1:=1.1501510−15 2.65517 1.78046 1.45676 8.579941014 20.9358 (14,1,1) (28,14) (28,14) (28,13) 14 (10,4) uhlig 4 1:=1.1835710−15 2.2561 1.00348 14.7909 10673.4 34.6115 (6,1,1) (12,6) (12,6) (12,5) 6 (5,1) uhlig 5 1:=1.1835710−15 2.2561 1.00348 14.7909 10673.4 34.6115 (6,1,1) (12,6) (12,6) (12,5) 6 (5,1) uhlig 6 1:=1.6045810−15 7.32281 38.3459 13.4887 7.635241013 203.291 (6,1,1) (12,6) (12,6) (12,4) 6 (4,2) uhlig 7 1:=2.3333210−14 7.59657 4.15248 0.335751 NA 2.63499 (13,1,1) (26,13) (26,13) (26,11) 13 (11,2) Note: L,τ,θ,B,ϑ,φ,F See Appendix B.1 m,p See Appendix B.2 L,M See Appendix B.3 2 L,n See Appendix B.4 k L See Appendix B.5 m,n See Appendix B.6 KW,Sims,Klein,BP,Uhligcolumnnormalized by dividing by comparable AIM value.

May 24, 2006 34 Table 7: Matlab Relative Errors in B: King & Watson and Sims Examples kB −B k i exact kB k exact Model AIM KW Sims Klein BP Uhlig (L,τ,θ) (m,p) (L,M ) (L,n ) L (m,n) 2 k Computes (B,ϑ,φ,F) (B,ϑ) (B,φ,F) (B) (B,ϑ,φ,F) (B,ϑ) king 2 1:=0. 3.6516910−16 1.6164210−16 0. 0. 0 (3,1,1) (6,3) (6,3) (6,1) 3 (2,1) king 3 1:=0. 0. 2.2204510−16 2.4918310−15 0. NA (3,1,1) (6,3) (6,3) (6,1) 3 (2,1) king 4 1:=2.2510−15 3.9919910−15 1.4849210−15 2.055210−15 6.3833810−16 2.6396910−9 (9,1,1) (18,9) (18,9) (18,5) 9 (3,6) sims 0 1:=0. 8.8451610−17 3.5778810−16 2.3486410−16 NA 5.5511210−17 (5,1,1) (10,5) (10,5) (10,3) 5 (4,1) sims 1 1:=1.1860310−15 7.5808110−16 9.0868510−16 1.2829810−15 NA 8.1172910−16 (8,1,1) (16,8) (16,8) (16,6) 8 (6,2) klein 1 1:=1.2939810−14 3.225910−14 8.7211910−14 1.7695710−13 4.5474210−10 4.6152210−13 (3,1,1) (6,3) (6,3) (6,1) 3 (1,2) bp 1 1:=1.5460710−15 2.8232510−15 5.1087410−15 1.2368510−14 5.9544310−10 1.0620810−14 (2,1,1) (4,2) (4,2) (4,0) 2 (1,1) bp 2 1:=5.0076510−16 5.1510110−15 5.5205310−15 5.2176410−15 7.1480110−16 3.9814810−14 (5,1,1) (10,5) (10,5) (10,1) 5 (4,1) Note: L,τ,θ,B,ϑ,φ,F See Appendix B.1 m,p See Appendix B.2 L,M See Appendix B.3 2 L,n See Appendix B.4 k L See Appendix B.5 m,n See Appendix B.6 KW, Sims, Klein, BP, Uhlig column not normalizedbydividingbycomparableAIMvalue.

May 24, 2006 35 Table 8: Matlab Relative Errors in ϑ: Uhlig Examples kϑ −ϑ k i exact kϑ k exact Model AIM KW Sims Klein BP Uhlig (L,τ,θ) (m,p) (L,M ) (L,n ) L (m,n) 2 k Computes (B,ϑ,φ,F) (B,ϑ) (B,φ,F) (B) (B,ϑ,φ,F) (B,ϑ) uhlig 0 1:=9.6633110−16 0.532995 NA 1.34518 159728. 9.54822 (4,1,1) (8,4) (8,4) (8,3) 4 (3,1) uhlig 1 1:=2.2593810−15 3.78248 NA 2.32241 5.30459106 2.33909 (6,1,1) (12,6) (12,6) (12,5) 6 (5,1) uhlig 2 1:=5.0561410−15 0.43572 NA 2.62987 1.51637106 1. (6,1,1) (12,6) (12,6) (12,5) 6 (5,1) uhlig 3 1:=8.9310−16 2.08127 NA 1.39137 NA 14.3934 (14,1,1) (28,14) (28,14) (28,13) 14 (10,4) uhlig 4 1:=0.0114423 1. NA 1. 0.999999 1. (6,1,1) (12,6) (12,6) (12,5) 6 (5,1) uhlig 5 1:=1.3738810−15 3.79327 NA 9.97923 8.03937106 12.2245 (6,1,1) (12,6) (12,6) (12,5) 6 (5,1) uhlig 6 1:=6.9724710−14 1.00929 NA 1.83538 1.128991013 27.5959 (6,1,1) (12,6) (12,6) (12,4) 6 (4,2) uhlig 7 1:=7.4770810−14 1.67717 NA 0.131889 NA 0.665332 (13,1,1) (26,13) (26,13) (26,11) 13 (11,2) Note: L,τ,θ,B,ϑ,φ,F See Appendix B.1 m,p See Appendix B.2 L,M See Appendix B.3 2 L,n See Appendix B.4 k L See Appendix B.5 m,n See Appendix B.6 KW,Sims,Klein,BP,Uhligcolumnnormalized by dividing by comparable AIM value.

May 24, 2006 36 Table 9: Matlab Relative Errors in ϑ: King & Watson and Sims Examples kϑ −ϑ k i exact kϑ k exact Model AIM KW Sims Klein BP Uhlig (L,τ,θ) (m,p) (L,M ) (L,n ) L (m,n) 2 k Computes (B,ϑ,φ,F) (B,ϑ) (B,φ,F) (B) (B,ϑ,φ,F) (B,ϑ) king 2 1:=4.99610−16 4.99610−16 NA 4.99610−16 4.99610−16 4.99610−16 (3,1,1) (6,3) (6,3) (6,1) 3 (2,1) king 3 1:=2.5829710−15 5.0299910−15 NA 6.4234310−15 2.5829710−15 NA (3,1,1) (6,3) (6,3) (6,1) 3 (2,1) king 4 1:=3.4568810−16 1.1244510−15 NA 8.4011210−16 2.6581110−16 2.4735510−9 (9,1,1) (18,9) (18,9) (18,5) 9 (3,6) sims 0 1:=7.6663810−16 7.8533710−16 NA 9.5362310−16 NA 7.6663810−16 (5,1,1) (10,5) (10,5) (10,3) 5 (4,1) sims 1 1:=9.7329410−16 1.5767110−15 NA 4.2358910−15 NA 9.7329410−16 (8,1,1) (16,8) (16,8) (16,6) 8 (6,2) klein 1 1:=2.3377910−15 1.910710−14 NA 1.0726910−13 2.396710−9 2.6682310−13 (3,1,1) (6,3) (6,3) (6,1) 3 (1,2) bp 1 1:=1.480210−15 8.9103910−15 NA 1.2016910−14 5.5573710−9 1.1685810−14 (2,1,1) (4,2) (4,2) (4,0) 2 (1,1) bp 2 1:=6.180910−16 1.2534710−15 NA 1.326810−15 6.180910−16 8.902610−15 (5,1,1) (10,5) (10,5) (10,1) 5 (4,1) Note: L,τ,θ,B,ϑ,φ,F See Appendix B.1 m,p See Appendix B.2 L,M See Appendix B.3 2 L,n See Appendix B.4 k L See Appendix B.5 m,n See Appendix B.6 KW, Sims, Klein, BP, Uhlig column not normalizedbydividingbycomparableAIMvalue.

May 24, 2006 37 Table 10: Matlab Relative Errors in F: Uhlig Examples kF −F k i exact kF k exact Model AIM KW Sims Klein BP Uhlig (L,τ,θ) (m,p) (L,M ) (L,n ) L (m,n) 2 k Computes (B,ϑ,φ,F) (B,ϑ) (B,φ,F) (B) (B,ϑ,φ,F) (B,ϑ) uhlig 0 1:=4.6041110−16 NA 38.383 NA 6280.03 NA (4,1,1) (8,4) (8,4) (8,3) 4 (3,1) uhlig 1 1:=6.1262210−16 NA 4.25457 NA 3126.17 NA (6,1,1) (12,6) (12,6) (12,5) 6 (5,1) uhlig 2 1:=6.1324610−16 NA 3.58093 NA 3918.23 NA (6,1,1) (12,6) (12,6) (12,5) 6 (5,1) uhlig 3 1:=7.2884310−16 NA 12.9392 NA 1.409861015 NA (14,1,1) (28,14) (28,14) (28,13) 14 (10,4) uhlig 4 1:=6.0357310−16 NA 2.73637 NA 1028.17 NA (6,1,1) (12,6) (12,6) (12,5) 6 (5,1) uhlig 5 1:=6.0357310−16 NA 2.73637 NA 1028.17 NA (6,1,1) (12,6) (12,6) (12,5) 6 (5,1) uhlig 6 1:=6.049910−16 NA 308.153 NA 1.652921013 NA (6,1,1) (12,6) (12,6) (12,4) 6 (4,2) uhlig 7 1:=7.5242310−14 NA 1.72491 NA NA NA (13,1,1) (26,13) (26,13) (26,11) 13 (11,2) Note: L,τ,θ,B,ϑ,φ,F See Appendix B.1 m,p See Appendix B.2 L,M See Appendix B.3 2 L,n See Appendix B.4 k L See Appendix B.5 m,n See Appendix B.6 KW,Sims,Klein,BP,Uhligcolumnnormalized by dividing by comparable AIM value.

May 24, 2006 38 Table 11: Matlab Relative Errors in F: King & Watson and Sims Examples kF −F k i exact kF k exact Model AIM KW Sims Klein BP Uhlig (L,τ,θ) (m,p) (L,M ) (L,n ) L (m,n) 2 k Computes (B,ϑ,φ,F) (B,ϑ) (B,φ,F) (B) (B,ϑ,φ,F) (B,ϑ) king 2 1:=7.4940110−16 NA 1.3634910−15 NA 7.4940110−16 NA (3,1,1) (6,3) (6,3) (6,1) 3 (2,1) king 3 1:=3.996810−16 NA 6.5347210−15 NA 3.996810−16 NA (3,1,1) (6,3) (6,3) (6,1) 3 (2,1) king 4 1:=2.1388310−15 NA 2.5868610−15 NA 7.2945610−16 NA (9,1,1) (18,9) (18,9) (18,5) 9 (3,6) sims 0 1:=7.1371510−16 NA 1.191710−15 NA NA NA (5,1,1) (10,5) (10,5) (10,3) 5 (4,1) sims 1 1:=2.4165110−15 NA 2.9215210−15 NA NA NA (8,1,1) (16,8) (16,8) (16,6) 8 (6,2) klein 1 1:=1.2438710−15 NA 1.6691110−13 NA 3.7087310−10 NA (3,1,1) (6,3) (6,3) (6,1) 3 (1,2) bp 1 1:=4.4393710−16 NA 7.5127710−15 NA 5.0302510−11 NA (2,1,1) (4,2) (4,2) (4,0) 2 (1,1) bp 2 1:=5.8264510−16 NA 1.7128510−15 NA 5.8264510−16 NA (5,1,1) (10,5) (10,5) (10,1) 5 (4,1) Note: L,τ,θ,B,ϑ,φ,F See Appendix B.1 m,p See Appendix B.2 L,M See Appendix B.3 2 L,n See Appendix B.4 k L See Appendix B.5 m,n See Appendix B.6 KW, Sims, Klein, BP, Uhlig column not normalizedbydividingbycomparableAIMvalue.