PROCESSING LARGE SCALE SYSTEMS OF EQUATIONS IN FINANCIAL MODELS

Stuart J Nettleton, University of Technology Sydney

Abstract

This paper compares four approaches to solving a discrete cumulative financial model. These are using Solve, repeated replacement to form a single transfer function, an annual transformation function and spreadsheet emulation through the topological solution of an acyclic network. The use of a topological network for the numerical processing of optimization constraints is discussed.

Introduction: The Challenge of Large Scale Systems of Equations

General purpose algebraic modelling systems have not enjoyed the same ubiquity for financial modelling as spreadsheets. The exceptionally agile modelling capability of spreadsheets and their particular appropriateness for cumulative discrete time models quickly led to a celebrated reputation as the first "killer app" for corporate modelling. However it is well known that the flip-side of agility is later experienced as poorly documented models that become unwieldy and prone to errors.

Spreadsheets rely on models being acyclic with a unique pathway from cell to cell, starting at some assumption cell at the beginning  of the model and ending with the last calculation in the last period. This means that circular calculations must be identified and manually resolved to render the model acyclic. For example, an internal loop from net debt to interest paid to net debt needs to be eliminated using manual intervention or a new set of equations derived from an algebraic recursive solution.  Spreadsheets handle these equations well, notwithstanding their non-linearity and sometimes quite extended nature.

The Solve functions of an algebraic modelling systems approach have many advanced techniques for solving difficult equations. However, these techniques can be less suitable for resolving large sets of equations unless the equations happen to be amenable to linear techniques. If there are hundreds or thousands of equations, with some being non-linear, and there are a similar number of variables then finding a solution can become quite a lengthy process. Furthermore, if the financial model is used for constraints within an outer optimisation then the situation becomes even more demanding because this lengthy process is repeated perhaps thousands or hundreds of thousands of times.

Projected financial statements in financial modelling comprise the state, information and endogenous variables of a financial stocks and flows model arranged into a balance sheet and income and cash flow statements. Even though this stocks and flows model is a systems model of state variables and an annual transfer function, it is significantly more complicated than normal examples such as water into and out of a barrel. In a minority of cases, simple financial models might be able to make use of a transfer function. However, in the majority of cases this is not feasible because the transfer function is not a set of simple recursive functions for the corresponding variables. In addition, it may involve tests and switches, for example a negative net cash asset being switched to a positive overdraft liability. These frustrate efficient execution, which is the object of using a transfer function approach in the first place.

Another transfer function approach is to treat the whole intertemporal model as one single transfer function of the initial variables. The symbolic capability of algebraic modelling systems facilitates this approach for quite large models but is using sledge-hammer power to inelegantly crack a nut. The very long and cumbersome equations require increasingly large amounts of memory for each additional period and this eventually brings a limit to this approach. This is because each output variable is the cumulative symbolic solution to all of the equations that preceded it, which is analogous to each cell in a spreadsheet being the cumulative numerical solution of all the equations that preceded it. 

Four approaches to solving a traditional corporate financial model are evaluated in the Methodology. Each model is provided in an associated notebook.

Methodology

Part A of the Methodology outlines the conceptual elements of the four approaches to solving a discrete cumulative financial model. Part B of the Methodology demonstrates the use of topological processing in optimisation.

Four Approaches to Solving a Financial Model

Approach 1 Solve

All equations and all variables are submitted to Solve, which sorts out the whole model.

Solve[{all equations},{all variables}]

This method is attractive because it uses the power of the Solve function. However, when the number of variables and equations becomes very large then it may take a considerable time to compute the result.

Approach 2 Repeated Replace

Repeated Replace is a simple method that builds a single transfer function for the whole model,which at any time comprises  a partial set of cumulative symbolic equations for some variables in the model and numerical solutions for other variables. The left hand side of the equations are presumed to be the dependent variables. The right hand side of each equation is repeatedly substituted by the equations expressed as substitution rules.

solution to left hand side of equations  = right hand side of equations //. equations expressed as rules

While not particularly elegant, this method has a number of advantages. Equations may be in any order and there is no need for initial conditions to be specified for intermediate variables unless specifically required. It is useful for building small sets of symbolic equations for use in optimisation without requiring special arrangements .  Disadvantages are that the left hand side of the equations are presumed to be the dependent variables, larger sets of equations can take a long time to solve, the flow-through of numerical resolution is somewhat haphazard which can lead to messy cumulative equations that require extensive memory.

Approach 3 Annual Transformation

The Annual Transformation method prepares a generic transfer model that can be used repeatedly.  FoldList is used to process the transformations. It generates the variables {#1,#2}, which are respectively the accumulated list of solutions to the end of the previous stage and the index of the current stage to be processed.

transfer model rules = symbolic solution for a generic year
result = FoldList[right hand side of transfer model rules/.{t->#2}/.Thread[left hand side of transfer model rules/{t->#2-1}-> #1]&,initial values, range of periods}]

However, the disadvantages of this method are that the left hand side of the equations are assumed to be the dependent variables, a symbolic solution is required for the "annual transfer model", the set of initial conditions needs to be extended for all intermediate variables in the main set of equations. The original financial model can still be extraordinarily cumbersome unless it is simplified by removing discontinuous elements. Even then, the difficulties of making the "annual transfer model" standard and repeatable might offset its usefulness.

The annual transformation is applied using FoldList because processing techniques like RecurrenceTable (and RSolve) can only be used if the models are exceptionally simple with only linear and linear fractional recursive equations rather than non-linear equations. The only other way to approach this would be a diffeomorphism to map the nonlinear equations to a linear set at the point of interest.

Approach 4 Acyclic Topological Processing

The fourth is by the topological processing of an acyclic network, similar to a spreadsheet, which is achieved with the topoindex function. This function produces the index for equations to be processed . The Fold function is used to rapidly process the indexed equations and there is only a single variable to be determined at each step because the equations are acyclic.

eqnsindex=topoindex[eqns,initial variables]
results=Fold[Flatten[{#1,Solve[0==eqns2[[#2]]/.#1]}]&,initial variables,eqnsindex];

The advantages of this method are that equations may be in any order, there is no need to identify dependent variables in each equation, the method is exceptionally fast, uses low memory, and provides convenience in handling sub variables in vector notation and writing equations.

Results and Discussion

Four Approaches to Solving a Financial Model

The results from Part A of the Methodology are set out below (Note 1). It may be seen that  Methods 3 and 4, Repeated Replace and the Annual Transformation Function respectively, are very slow. This is attributable due to the long symbolic equations generated by the inclusion of the switch between cash and overdraft.

In contrast, Methods 1 and 4, respectively the Solve function and the Topological acyclic solver, are very fast with the latter showing distinct performance advantages.

data = {
   {1, "Solve Function", Round[0.0188016086*60, .1], Round[27.0942]},
   {2, "Repeated Replace", Round[0.8680816750*60], Round[2119.06]},
   {3, "Annual Transformation", Round[0.4002987369*60], Round[92.2695]},
   {4, "Topological Acyclic Solver", Round[0.0003370206*60, .01], Round[15.8432]}};
TableForm[data[[All, 1 ;; 4]], TableHeadings -> {None, {"Method","Description", Labeled["Execution", "Mins"], Labeled["Memory", "Mb"]}}]

Using a Topological Network in Optimisation

The first method above, using Solve, may also be used in optimisation. A large number of equations and variables can be submitted to the opitimising function and letting it sort it all out. This can work well for small problems but often overwhelms Solve in large scale problems.

Topological processing of acyclic networks facilitates optimisation where the objective function and constraints are functions of intermediate variables rather than only the initial state variables. It bears some similarity to the Repeated Replace method because a single transfer function is used for the whole model, however variables are sequentially resolved in a controlled manner.

In addition to the topological issues for the extended model network and parameterised objective function and constraints, special techniques are needed to interface the optimising function (Note 2). For example, FindMinimum can be used with numerically evaluated objective and constraints if each is managed individually rather than as a group [1]. This is shown below where αf[1] is a function for the objective, βf[1], βf[2] ... etc are functions for the inequality constraints and γf[1], γf[2] ... etc are functions for each equality constraint.

modelindex=topoindex[model equations,optimisation variables]
calcmodel[prevresult_,index_]:=Flatten[{prevresult,NSolve[(model equations[[index]]/.prevresult)==0]}]
model[variables_]:=model[variables_]=Fold[calcmodel,Thread[model equation variables->variables],modelindex]
αf[1][variables_]:=Chop[objective/.model[variables]]/;VectorQ[variables,NumberQ]
Scan[(βf[#][variables_]==Chop[inequality constraint[[#]]/.model[variables]]/;VectorQ[variables,NumberQ])&,Range[length inequality constraints]]
Scan[(γf[#][variables_]==Chop[equality constraint[[#]]/.model[variables]]/;VectorQ[variables,NumberQ])&,Range[length equality constraints]]
f0=Flatten[{αf[1][optimisation variables],Table[βf[i][optimisation variables]≤0,{i,length inequality constraints}],Table[γf[i][optimisation variables]==0,{i,length equality constraints}]}];
result=Block[{i=1,j=1,k=1,temp=""},FindMinimum[f0,optimisation variables,
StepMonitor:>(j++;k=1),
EvaluationMonitor:> (i++;k++;
If[Mod[i,100]==0,DownValues[model]=Last[DownValues[model]];
NotebookDelete[temp];temp=PrintTemporary["Step: "<>ToString[j]<>"; Sub "<>ToString[k]<>"; Cum "<>ToString[i]<>"; Curr Mem: "<>ToString[N[MemoryInUse[]/10^6]]<>"; Max: "<>ToString[N[MaxMemoryUsed[]/10^6]]<>" Mb"]])]]

Each time the objective function is evaluated, the model is calculated. This result is automatically stored as a DownValue for the function and available for each of the subsequent constraint evaluations. Therefore, the model is only calculated once per evaluation of the optimisation variables. To minimize unnecessary memory consumption, FindMinimum's EvaluationMonitor clears the DownValues of the model. StepMonitor and EvaluationMonitor are also used to monitor the progress of the optimisation, which can take many days. A simplified example of the use of this method is provided in an attached notebook.

Conclusion

Topological processing couples the efficiency of a spreadsheet with the robust declarative approach of a general algebraic modelling system. The technique may be a useful alternative for large scale optimisation where the constraints are functions of variables, other than the optimisation variables, present in an acyclic network of equations.

Notes

1. All tests conducted on 3.2Ghz 8MB L3 Cache Xeon W3570 (Quad Core) 6.4T/s QC with 6GB 1333MHz ECC DDR3-RAM
2. Private correspondence with Daniel Lichtblau 15 July 2010