Benchmark Testing
Description
Accepted for publication in LBNL-45936Energy and BuildingsEFFICIENT SOLUTION STRATEGIES FOR BUILDINGENERGY SYSTEM SIMULATIONEdward F. SowellCalifornia State UniversityFullerton, CA 92834Philip HavesBuilding Technologies DepartmentEnvironmental Energy Technologies DivisionLawrence Berkeley National LaboratoryUniversity of CaliforniaBerkeley, CA 94720March 30, 2000This work was supported by the Assistant Secretary for Energy Efficiency and Renewable Energy,Office of Building Technology, State and Community Programs, Office of Building Systems of theU.S. Department of Energy under Contract No. DE-AC03-76SF00098. Portions of this work weresponsored by the Japan Ministry of Education and the United Kingdom Royal Academy ofEngineering Foresight Award Scheme.1EFFICIENT SOLUTION STRATEGIES FOR BUILDING ENERGY SYSTEM SIMULATIONEdward F. SowellCalifornia State UniversityFullerton, CA 92834Philip HavesLawrence Berkeley National LaboratoryBerkeley, CA 94720ABSTRACTThe efficiencies of methods employed in solution of building simulation models are considered andcompared by means of benchmark testing. Direct comparisons between the Simulation Problem Analysisand Research Kernel (SPARK) and the HVACSIM+ programs are presented, as are results for SPARKversus conventional and sparse matrix methods. An indirect comparison between SPARK and the IDAprogram is carried out by solving one of the benchmark test suite problems using the sparse methodsemployed in ...
Informations
| Publié par | Thiwyir |
| Nombre de lectures | 19 |
| Langue | English |
Extrait
Accepted for publication in Energy and Buildings
LBNL-45936
EFFICIENT SOLUTION STRATEGIES FOR BUILDING ENERGY SYSTEM SIMULATION
Edward F. Sowell California State University Fullerton, CA 92834 Philip Haves Building Technologies Department Environmental Energy Technologies Division Lawrence Berkeley National Laboratory University of California Berkeley, CA 94720
March 30, 2000
This work was supported by the Assistant Secretary for Energy Efficiency and Renewable Energy, Office of Building Technology, State and Community Programs, Office of Building Systems of the U.S. Department of Energy under Contract No. DE-AC03-76SF00098. Portions of this work were sponsored by the Japan Ministry of Education and the United Kingdom Royal Academy of Engineering Foresight Award Scheme.
1
E FFICIENT S OLUTION S TRATEGIES FOR B UILDING E NERGY S YSTEM S IMULATION Edward F. Sowell California State University Fullerton, CA 92834 Philip Haves Lawrence Berkeley National Laboratory Berkeley, CA 94720 A BSTRACT The efficiencies of methods employed in solution of building simulation models are considered and compared by means of benchmark testing. Direct comparisons between the Simulation Problem Analysis and Research Kernel (SPARK) and the HVACSIM+ programs are presented, as are results for SPARK versus conventional and sparse matrix methods. An indirect comparison between SPARK and the IDA program is carried out by solving one of the benchmark test suite problems using the sparse methods employed in that program. The test suite consisted of two problems chosen to span the range of expected performance advantage. SPARK execution times versus problem size are compared to those obtained with conventional and sparse matrix implementations of these problems. Then, to see if the results of these limiting cases extend to actual problems in building simulation, a detailed control system for a heating, ventilating and air conditioning (HVAC) system is simulated with and without the use of SPARK cut set reduction. Execution times for the reduced and non-reduced SPARK models are compared with those for an HVACSIM+ model of the same system. Results show that the graph-theoretic techniques employed in SPARK offer significant speed advantages over the other methods for significantly reducible problems, and that by using sparse methods in combination with graph theoretic methods even problem portions with little reduction potential can be solved efficiently. B ACKGROUND Detailed simulation of building energy systems involves the solution of large sets of nonlinear algebraic and differential equations. These equations emerge from component-based simulators such as TRNSYS [1] or HVACSIM+ [2], or equation based tools such as SPARK [3] or IDA [4]. Since each of these tools employs a different solution strategy, the question arises as to which strategy is most appropriate for the kinds of equations encountered in the building simulation domain. TRNSYS and HVACSIM+ are both based on subroutines containing algorithmic models of the underlying physics for the represented building system component. TRNSYS, the program with the longest and perhaps most wide spread usage, employs a fiblock iterative strategy, calling the component subroutines in a sequence largely determined by the order in which they appear in the user™s problem definition. Convergence is sought using successive substitution of calculated interface variables into the block inputs on the next iteration. If convergence is indeed obtained, solution is often fast since the number of iteration variables is small and there are no vector-matrix operations. However, the successive substitution method is unreliable in general, so convergence is often slow or not obtained at all. The HVACSIM+ program, which is much like TRNSYS at the problem definition level, assembles a vector of the interface variables throughout the model and employs a Newton-like solution strategy. The advantages sought with this approach are robustness and efficiency, since the information in the Jacobian allows calculation of a better next guess than the previous value alone. Indeed, provided that initial values of the interface variables are within the radius of convergence, the solution is approached quadratically. However, HVACSIM+ often is less efficient than TRNSYS in practice because of the need to calculate the Jacobian and solve the linear equation set that it represents at each iteration. Because no reduction is attempted, the size of this set is the total number of block interface variables, n i , and solving it is O ( n i 3 ) . Consequently, the more rapid and robust convergence can be overwhelmed, resulting in the longer runtimes often experienced relative to an equivalent TRANSYS model. The IDA and SPARK modeling environments represent a new departure in that they formulate the model, and its solution, in terms of equations rather than the algorithmic subroutines employed in TRNSYS and
2
HVACSIM+. One advantage of this approach is that the models of individual components are input/output free. That is, the same component model can be used for a variety of different input and output designations. This allows conceptual separation of the modelfrom the problem; the model is general, and a specific problem is defined only when a specific set of inputs is designated. Although the two modeling environments are similar in this important respect, the solution methods employed are radically different. In IDA, the equations are formed as residual formulas, e.g., R 1 f ( x , y , z ) , and R is forced to zero at the solution point. Residual equations comprising math models of individual physical component are grouped into component models, with variables relevant at the system level exposed to the interface. An IDA system model consists of a set of such component models together with set of coupling equations that, in effect, equate equivalent interface variables at different component models. The coupling equations are all linear, of the identification form p 1 % p 2 1 0 or the conservation form m 1 # m 2 % m 3 1 0 , but are large in number so that IDA equation sets tend to be quite large and sparse. For example, a simple example used in IDA reports [5] has 26 coupling equations augmenting 12 model equations. An innovative solution strategy employing sparse matrix methods in a Newton-like iterative process is used to solve the resulting large, sparse system. Because the size added by the coupling equation set is an obvious detriment to overall solution efficiency, the solver has a ficompact solution option for which the coupling variables and equations are, in some sense, removed. However, the expected theoretical performance improvement is not realized in the implementation, as it appears to in fact decrease solution speed [5]. Nonetheless, there is some anecdotal data (from informal discussions with users) to suggest that IDA may be somewhat faster than HVACSIM+ on some problems. Unfortunately, no benchmark testing results have been reported for IDA so the actual performance remains uncertain. Like IDA, SPARK [3], is equation based. However, SPARK relies upon the mathematical graph for model representation and solution rather than the matrix. To support the graph, rather than expressing equations as residuals, they are expressed in the form x 1 f ( y , z ) , where the functions are symbolic inverses of the user-supplied model equations. This allows graph algorithms to be used to determine a sequence of function evaluations that leads to the solution. This alone is an advantage, since it eliminates the need for coupling equations entirely. Further, it allows the problem to be decomposed into separately solvable (i.e., strongly connected) components. Within each strong component, if no direct sequence is possible, as evidenced by a cyclic problem graph, a small ficut set is determined so as to minimize the number of variables involved in the subsequent Newton-like iteration. As a result of these reductions, the size of the Jacobian matrix, and hence the linear set that must be solved at each Newton iteration, is reduced, often significantly. Consequently, as will be shown in this paper, solution speed is greatly reduced. While ideas from graph theory have been used in connection with equation system solving before [6-12], SPARK applies graph methods directly to the nonlinear equations. The graph, rather than the matrix, is the primary data structure for storing the problem structure and data and, as already noted, graph algorithms are employed to determine a solution sequence that operates directly on the nonlinear equations. Another distinctive attribute of the SPARK approach is that the model equations are stored individually, rather than packaged into modules, and are treated as equations rather than as formulae with assignment (algorithms). Symbolic methods are employed to find explicit inverses of the equations, when possible, to ensure computational efficiency. In these ways SPARK is unique. However, increasingly, simulation software is employing some of the ideas embodied in SPARK. For example, Klein, in collaboration with F. Alvarado, produced the Engineering Equation Solver [13], which employs decomposition using sparse matrix methods. This is conceptually the same as the strong component decomposition done in SPARK. However, reduction within blocks is not done in this software. In addition, TRNSYS has recently been modified to allow fireverse solving [1]. This is a move toward input/output free (non-algorithmic) modeling, another tenet of SPARK. Also in the building context, Tang has applied graph theoretic methods to improve matrix-based solution schemes [14, 15]. Although the SPARK methodology is well established, there has been relatively little systematic comparison of solution speed between SPARK and alternative methods available for solving large sets of
3
equations such as arise in building simulation. In order to begin to fill this gap, a simple benchmarking experiment was designed. Two problems sets were defined: (a) a replicated set of four nonlinear equations, and (b) the Laplacian equation, i.e., heat conduction, in a two dimensional grid of various sizes. These two problems, while somewhat removed from mainstream building system simulation, were selected to represent the endpoints in the degree to which problems are suited to the methods used in SPARK. To complement findings from these simple problems, the study was extended to include actual building HVAC systems models of considerable complexity. The system selected is one previously studied by Haves [16] using a different building simulation tool, thus providing opportunities for direct comparison. This work was reported at the Building Simulation ™99 conference [17] in Kyoto. Discussion at the Kyoto conference raised the question of how effective the SPARK graph-theoretic methods are when compared to state-of-the-art sparse matrix solution methods applied directly to the unreduced problem, as is done in IDA. Specifically, are the techniques routinely applied in sparse matrix packages fully equivalent to SPARK methods, thereby making it unnecessary to carryout graph theoretic reduction directly on the nonlinear problem? To address this question, one of the problems reported in the Kyoto paper was solved using the sparse matrix package used in IDA, SuperLU [18]. Because SuperLU appears to be one of the most advanced sparse matrix packages, it would seem that if the answer to the question is positive, then it should solve faster than the SPARK implementation. This is shown not to be the case. That is, the new results confirm that the SPARK methods, at least for problems with significant reduction potential, are significantly faster than sparse methods alone. In addition to these new results, more discussion is provided on the comparison to HVACSIM+. Otherwise, the results here are the same as in the Kyoto paper and are presented here for the convenience of the reader. N ONLINEAR EQUATION EXAMPLE The first benchmark problem derives from a problem in the SPARK Users™ Manual consisting of four highly nonlinear equations: 2 x 1 # x 3 # x 2 # x 2 1 c 1 x 1 x 2 1 x 1 e # # 3 x 1 x 4 x 3 x 4 x 4 1 c 2 x 1 x e % x 3 4 3 SPARK finds a solution to these equations by the calculation sequence: x 3 1 0.1 % x 1 x e x 3 4 3 x 1 1 ( c 2 % x 3 x 4 % x 43 ) / x 4 x 1 x e x 1 2 1 2 x 3 1 c 2 % x 1 % x 2 % x 2 Iterate on x 3 Using the default SPARK solution process, Newton-Raphson iteration is performed until the difference between two successive values of x 3 is less than a specified tolerance. Thus it is seen that reduction of 4:1 is achieved relative to conventional practice of iteration on all unknown variables. With c 1 =3000 and c 2 =1 the solution found is x 4 = 0.288576, x 1 2.9273, x 2 = 54.6738, and x 3 = 0.454716. = For the numerical experiments, this set of equations was implemented as a SPARK macro class called example which was then instantiated n/4 times to get a problem of size n. Obviously, every instance of example is in fact a separately solvable problem. SPARK is able to discern this structural regularity and partition the problem graph into n/4strongly connected components, each with a cut set of size one. Consequently, during the numeric phase of the solution, n/4single-variable iterative solutions are carried out. Most conventional, general solvers would instead solve a single equation set of size nby iteration on all n variables. If Newton-Raphson iteration were used, a linear set with an nby ncoefficient matrix would need to be solved at each iteration.
4
(1)
(2)
For comparison purposes, this equation set was also solved with three other methods. First, a handcrafted Newton-Raphson nonlinear solver (nlsolve) was written specifically for this equation set, with the problem size as an input parameter. In this solver, the four Eqs. (1) were coded in a single function that was called as needed for calculation of the residual functions and the Jacobian. The matrix functions from SPARK were used to calculate the Jacobian numerically and solve the linear set for new estimates of the iteration variables. Second, a sparse Newton-Raphson solver (spnlsolv) was written using the sparse LU solve function from the Meschach sparse matrix package [19]. The interface, function evaluation, Newton-Raphson loop, and output were basically the same as for nlsolve, with the only difference being the use of sparse storage date types and sparse matrix solver functions from Meschach. The same solution tolerance (1 ´ 10 -6 ) was used in both cases. Comparative run times with a 333MHz AMD K-6/2 processor are shown in Figure 1. NLSolve SPNLSolve SPARK
15 10 5 0
0 1000 2000 3000 4000 Number of Equations
Figure 1: Solution times for nonlinear benchmark, SPARK vs., Meschach. As would be expected, the experimental results show O ( n 3 ) performance for the full matrix solution. The solver based on the Meschach sparse matrix functions shows much better performance, approximately O ( n 2 ) . Also as expected, SPARK is much better than the sparse implementation, showing about O ( n ) . In order to confirm that these dramatic solution speed improvements are not attributable to the particular sparse package chosen, this problem was also coded for solution with the SuperLU sparse package [18]. This freely available software is the result of U.S. Government sponsored research at the University of California, Berkeley, and is currently supported by the National Energy Research Scientific Computing Center (NERSC) at the Lawrence Berkeley National Laboratory. If not the most advanced software in this category, it appears at least to be the most current. For these reasons, and also because it supports parallel computation models, it was chosen by the IDA development team for use in their program. The results of this substudy are presented in Figure 2. For comparison purposes, the SPARK and Meschach results are replotted in the figure. Thus the uppermost curve in the figure is for the Meschach solution, while the lowest one is for SPARK. The middle curve is for the SuperLU solution. The upshot is that, although SuperLU is somewhat faster than Meschach (15 seconds. versus 48 seconds for n= 2000), SPARK is much faster. More importantly, it is clear that SuperLU, like Meschach, is performing at
5
O ( n 2 ) as compared to O ( n ) for SPARK. In order to explore the full potential of the SuperLU package, several solution options were tried. In particular, each of the three column ordering options was tried and found to have no noticeable effect on run time. The option to reuse the factoring information from the initial iteration rather than factoring from scratch at each Newton iteration was also tried, again without significant effect. Finally, to see if initial equation ordering had an impact, the driver program was modified to randomize this ordering in constructing the Jacobian. Again, there was no significant effect. To demonstrate these findings, the results for the natural ordering and without refactorization and random ordering of the equations is overlaid with the case showing the greatest departure. The effects are so small as to be unnoticeable in the plot. The explanation for these findings is presented below (See D ISCUSSION ). Meschach SPARK sLUNatural sLURefactAxARand 15 10 5 0 0 500 1000 1500 2000 2500 3000 3500 Number of Equations Figure 2: Solution times for nonlinear benchmark, SPARK Vs, SuperLU. L APLACE S E QUATION E XAMPLE ™ The second benchmark problem, purposely chosen to be not well suited to the SPARK methodology, is Laplace™s equation in two dimensions. This equation models many physical phenomena, including heat transfer in a thin, square plate with uniformly distributed heat source and uniform boundary temperature. The problem is discretized by dividing the square into a uniform grid of specified size. Each cell in the grid is represented by a nodal temperature T i j and is governed by a heat balance equation , q 1 ( T % T # ) # ( T % T % ) 3 # si ( , T ji , j % T i , ij , j % 1 ) i # , j ( 1 T i , j % T i , ij # 1, j ) i 1, j ( ) where q si j is the heat source rate per unit surface area. As can be seen, the internodal conductance is , assumed to be 1.0. This problem is coded for sparse solution in the Meschach tutorial [19]. However, for this study, that implementation was modified to employ sparse LU factorization, since the use of Cholesky factorization and sparse conjugate gradient iteration in the original code applies only to symmetric positive definite matrices, a condition satisfied by the Laplacian but not often found in general simulation problems. For comparison, a program was written to generate SPARK problem and input files for the same equation system. The grid size was varied between 3 and 45, yielding equation set sizes between 9 and 2025. 6
Both SPARK and the Meschach-based solver were compiled with the same compiler and optimization options. In the initial SPARK implementation, each grid node was represented with a SPARK macro object called node constructed with atomic conductor and sum objects from the SPARK HVAC class library [20]. With this implementation and a grid size of 19 ´ 19, the SPARK solution time was about 60 times that of the Meschach solver. While a weak SPARK showing was anticipated for this problem, this huge difference was a surprise, calling for further investigation. The first reason for the long SPARK run times was found to be representation of the node as a macro object. This resulted in seven distinct equations for each node, four of the form q 1 u ( T 2 % T 1 ) and three of the form a 1 b # c , giving 2530 equations for the grid size of 19 x 19. Although the SPARK graph theoretic algorithms were able to find a cut set of 342, a reduction of 86%, the Meschach implementation was hand-crafted so that there were only 361 equations in the set to be solved. Moreover, the Meschach implementation assumed an inter-nodal conductance of unity, Eq. (3), so no multiplications were needed. Therefore, even after graph theoretic reduction brought the Jacobian size down to approximately the size seen by Meschach, the SPARK model required many more arithmetic operations in evaluation of each equation. In short, the numerical problems seen by the two solvers were not the same, even though they both represented the same physical problem. To try to get a more meaningful comparison, both models were changed in several ways. First, the SPARK implementation was revised to more closely approximate the problem as seen by Meschach. A specialized SPARK atomic object class was written to represent the node as a single heat balance equation with an assumed unit conductance, as in the Meschach implementation. With this revision there were only 361 objects in the SPARK model for the 19 x 19 grid, and the SPARK solution times improved considerably. Then, to see to what extent the presumably more efficient data handling methods in Meschach contribute to its speed advantage, the SPARK solver was modified to optionally use either sparse or non-sparse vector-matrix data structures and functions from Meschach when updating the solution vector. These changes both produced substantial speed-up, with the sparse handling option performing essentially as well as Meschach (See D ISCUSSION ). Another difference observed between the two approaches was that, because SPARK is a general nonlinear solver, it employs Newton-Raphson iteration, requiring numerical calculation of the Jacobian matrix at each iteration. In contrast, the handcrafted Meschach model is aware of the problem linearity and constant coefficients and consequently sets up the conduction matrix only once, directly from the given coefficients. Since this study was concerned principally with solving methods for nonlinear equation systems, it was of interest to see how much of the run time difference was due to extra work in SPARK associated with nonlinear solving. However, rather than changing SPARK, a second Meschach-based model was developed in which the system of equations was set up for solution as if they were nonlinear. That is, a Jacobian was formed numerically, as in SPARK, and Newton-Raphson iteration was performed to obtain a solution. A Meschach sparse solver and supporting vector-matrix routines were used to calculate the solution vector for each iteration. Note that, while this approach has the advantages of Meschach™s efficient data handling and sparse matrix operations, it does not share SPARK™s ability to reduce the Jacobian size. The performance of the various solution methods is summarized in Figure 3. The three solid curves show SPARK solution times versus total number of equations. The uppermost curve is for solution with the current, standard SPARK. The next lower curve was generated using the modified version of SPARK with the Meschach non-sparse handling of the Jacobian as mentioned above, while the lowest curve results from use of the sparse option. In all three cases, the graph theoretic matching and cutting were coerced by selecting input options so as to get the theoretical minimum cut set size while preserving diagonal dominance of the reduced Jacobian. This is an important qualification and is discussed further below.
7
The dash-line curve in Figure 3 is for solution using the Meschach based Newton-Raphson solver described previously. Performance is seen to be significantly better than the standard SPARK, and somewhat better than the modified SPARK using non-sparse methods. However, it is not as good as SPARK using sparse Jacobian handling. The final results in the figure are for the Meschach Tutorial program using sparse LU decomposition. These results overlay almost exactly those for the modified SPARK using sparse Jacobian handling, so a separate trend line is not plotted. However, this agreement is coincidental. Apparently, the reduced Jacobian size in SPARK offers a speed advantage that overcomes SPARK overhead costs such as function calls and numerical Jacobian evaluation, which are not done in Meschach. 1
SPARK Sparse LU 150
100
50
0
0
500
SPARK/Meschach Sparse Jacobian SPARK/Sparse
1000
1500 n
2000
ure 3:Solution times for the Laplace™s equation example.
2500
Fig
HVAC B ENCHMARKS Going beyond simple benchmark examples, the numerical methods used in SPARK were also evaluated by modeling an airflow system employing discrete-time controllers. The example used was a typical HVAC airflow network and its associated control loops, a problem involving significant computational burden [16].
1 In the current implementation, SPARK makes a call to a C++ function for every equation evaluation.
8
A number of steady state component models were implemented as SPARK objects, including variable speed centrifugal fans, flow diverters, flow mixers and control dampers. In modeling air flow, a square law dependence of total pressure drop on flow rate was used above a critical flow rate and a linear dependence was used below the critical flow rate to avoid known computational problems with air at low flow rates. Dynamic models included flow sensors, pressure sensors, rate limits, discrete-time proportional-plus-integral (PI) controllers and fan control strategies based on PI control. Figure 4 shows the system that was simulated. The positions of the mixing box dampers determine the proportions of outside and recirculated air that are filtered and cooled before being supplied to the six zones of the building. The positions of the terminal box dampers determine the air flow rates to the corresponding zones. The speed of the supply fan is determined by a PI controller that regulates the static pressure of the air in the supply duct. The speed of the return fan is determined by a PI controller that regulates the difference between the supply airflow rate and the return air flow rate. For the purposes of the benchmark tests, the various damper openings were treated as boundary conditions. In the airflow network used to model the duct system there were 28 flow rate variables and 30 pressure variables, three of which were boundary variables. In order to assess the benefits of using SPARK methods, a base case and two reference cases were constructed. The base case was modeled with SPARK in the normal manner, allowing the graph theoretic techniques to perform reduction of the problem graph. The two reference cases were:
Figure 4 HVAC system. · The system modeled using the HVACSIM+ program [2], as in the previous work [16]. · The system modeled using SPARK, but inhibiting the normal problem reduction techniques. The use of the two reference cases enables the benefits of the graph theoretic techniques to be separated from the effects of program architecture. For all three cases, the simulation problem was a series of set-point changes for each controller followed by a disturbance caused by progressive closing of the VAV terminal boxes. In addition to these comparisons directed at assessment of the importance of reduction, a side study was performed to determine whether fibreaking of control loops offers computational advantage. The interest in this derives both from the needs of proper models of discrete time sample-and-hold controllers, and from the introduction of artificial delays as a computational device to speed solution. Comparisons between HVACSIM+ and SPARK are shown in Table 1. In the first comparison, ‚Control loops Intact,™ the flow network equations and the controller equations are solved simultaneously. The
9
main result is that SPARK is 15 - 20 times faster than HVACSIM+. The obvious reason for the speedup is that SPARK achieves a 4:1 reduction in the number of variables in the iteration vector. Table 1 Comparison for HVACSIM+ and SPARK Time (s) Iteration Variables Control loops HVACSIM+ SPARK HVACSIM+ SPARK Intact 1135 48.8 62 15 Broken 785 52.7 55 15 In the second comparison, Control loops Broken, the set of simultaneous equations representing the airflow network and those representing the control system are solved sequentially. This corresponds to breaking the algebraic loops, such as by introduction of a sample-and-hold in the controller or an artificial delay. Whereas a significant benefit was gained from breaking the control loops when using HVACSIM+, there was no such benefit when using SPARK. The reason for this, as discussed in another paper [21], is that SPARK finds fan discharge pressures of the supply and return fans to be good choices for break variables, so the computation loops in question are broken regardless. In order to determine how much of the SPARK advantage can be attributed to the problem reduction, these techniques were disabled, producing the results shown in Table 2 for the Intact loops case. These results show that the effect of the problem reduction techniques in SPARK is to speed the benchmark problem up by a factor of 13. This is approximately what would be expected from the reduction in the number of equations.
Table 2 Effect of SPARK reduction HVACSIM+ SPARK unreduced SPARK reduced No. of eqns. 62 62 15 Exec. time (s) 1135 637 48.8 To investigate further the question of whether the reduction of ~4:1 in the number of problem variables in the iteration vector observed in this example is likely to be achieved in other HVAC simulation problems, a number of series/parallel network configurations representative of HVAC airflow networks were subjected to the SPARK problem reduction techniques. Twenty configurations were studied, with between two and twenty-four flow elements and up to eight parallel paths. In fifteen cases, the size of the cut set, and hence the number of iteration variables, was equal to the number of parallel flow paths. In four cases, the size of the cut set exceeded by one the number of parallel flow paths, and in the remaining case it exceeded it by two. The ratio of the numbers of equations in the unreduced and reduced problems ranged from 3.0:1 to 5.8;1, with a mean value of 4.4:1, a similar value to that found in the example case described above. The question of whether control loops typically add to the number of equations in the reduced problem was addressed by considering a further six configurations that each included one control loop. In five out of the six cases, adding the control loop did not increase the size of the cut set in the reduced problem, and in one case it increased the size of the cut set by one. The interpretation of these results is discussed in [21]. D ISCUSSION The above results confirm that the SPARK methodology offers significant reduction in solution times relative to both conventional and sparse matrix methods in the solution of certain kinds of nonlinear equation systems. This is borne out most dramatically by the contrived nonlinear benchmark problem, but is also quite clear from the HVAC control application. However, in the case of the example involving Laplace™s equation, we observe that without some user intervention, SPARK has difficulty competing with sparse methods. Understanding why this occurs is important in order to guide improvement of the SPARK methods and to delineate properly the class of problems amenable to SPARK methods.
10
To understand the observed differences in run times, it is important to note that at the heart of the Newton-Raphson nonlinear solution process is the solution of a linear problem. That is, during each iteration the solution vector must be updated by solution of the equations J ≅ 1 f ( x k ) (4) 1 x k # 1 x k #≅ where is the solution vector of size n, f is the vector of functions being solved, is the correction vector, and J is the Jacobian. Now, since J is nby n, calculation of its elements is O(n 2 ), whether done numerically by finite differenc 3 e) (the usual case), or from derivative formulae. Moreover, solution of linear systems is in general an O(n process. Since evaluation of the functions fis only of O(n), evaluation of the Jacobian and solving the linear set are the overriding factors in determining run time. Consequently, anything that can be done to reduce the size of the Jacobian has a powerful effect, especially for large problem size. SPARK gains its advantage over conventional methods by reducing the Jacobian size. It does this in two, separate ways: decomposition and cut set reduction. Decomposition is possible when the equation set is, in reality, a sequence of separately solvable problems. SPARK is able to detect this property automatically and carry out the decomposition without intervention. For example, the nonlinear benchmark problem with 100 equations and variables is decomposed into 25 sub-problems (or, in graph terms, strongly connected components) each of size 4. This alone would reduce the run time from O(100 3 ) to 25 ´ O(4 3 ), i.e., a factor of 625. Cut set reduction refers to reducing the sizes of the Jacobians of the sub-problems. This is done by an algorithm that finds a small set of nodes in the problem graph that breaks all cycles, called a cut set. The cut set variables then form the iteration vector for the Newton-Raphson process. Again, looking at the nonlinear benchmark problem, a cut set of size one was discovered in each component. Thus the 25 Jacobians are all 1 ´ 1, so the overall theoretical run time reduction is by a factor of 40,000. This efficiency gain is only partially realized due to the overhead associated with the SPARK implementation, but this analysis clearly explains the observed excellent performance for this example. A similar analysis shows why SPARK has difficulties with the Laplacian example. In this case, the problem graph, Figure 5, is more complex, with each node bi-connected to four neighbors. One consequence of this high degree of interconnectedness is that the problem does not decompose, so that it has to be solved as a single strongly connected component. Another is that a small cut set is hard to find. The normal SPARK cut set algorithm works on the principle of contraction, in which nodes with single incoming or outgoing edges are bypassed and removed, thereby producing progressively simpler graphs from which the cut set can be deduced. However, there are no such nodes in this graph, so the algorithm must revert to arbitrary removal of nodes into the cut set [22]. In many problems, arbitrary removal results in further opportunities for contraction. Such is not the case here, so the algorithm continues to do arbitrary removal, arriving at a relatively large cut set. For example, in the 45 ´ 45 grid case (2025 nodes) the discovered cut set is 1894. This is a reduction in Jacobian size of only 5%, hardly enough to overcome overhead costs. Indeed, with this cut set the SPARK run time was nearly 7 times that shown in Figure 3. However, it is not difficult to see that a much smaller cut set is possible for the Laplace™s equation example. Suppose that for oddrows in the grid, we mark with b (for break) every evencolumn node, and apply the reverse policy in evenrows. This creates a checkerboard pattern on the grid in which every marked node is surrounded by unmarked ones, as shown in Figure 5. Clearly, the marked nodes form a cut set, since every unmarked node can be calculated given temperature values at the marked ones. This policy can be implemented in a SPARK model using the break_level keyword, coercing the algorithm to choose the wanted breaks. When this is done, the cut set size is n/2, producing results shown in Figure 3. In a future version of SPARK it may be possible to improve the matching and cutting algorithms to detect regularities in the problem graph so as to automatically arrive at smaller cut sets in problems of this nature.
11
© 2010-2024 YouScribe