C++ implementations of numerical methods for solving differential-algebraic equations: design and optimization considerations

ABSTRACT

Object-oriented programming can produce improved implementations of complex numerical methods, but it can also introduce a performance penalty. Since computational simulation often requires intricate and highly efficient codes, the performance penalty of high-level techniques must always be weighed against the improvements they enable. These issues are addressed in a general object-oriented (OO) toolkit for the numerical solution of differential-algebraic equations (DAEs). The toolkit can be configured in several different ways to solve DAE initial-value problems with an adaptive multistep method. It contains a wrapped version of the Fortran 77 code DASPK and a translation of this to C++. Two C++ constructs for assembling the tools are provided, as are two implementations an important DAE test problem. Multiple configurations of the toolkit for DAE test problems are compared in order to assess the performance penalties of C++. The mathematical methods and implementation techniques are discussed in detail in order to provide heuristics for efficient OO scientific programming and to demonstrate the effectiveness of OO techniques in managing complexity and producing better code. The codes were tested on a variety of problems using publicly available Fortran 77 and C++ compilers. Extensive effficiency comparisons are presented in order to isolate computationally inefficient OO techniques. Techniques that caused difficulty in implementation and maintenance are also highlighted. The comparisons demonstrate that the majority of C++'s built-in support for OO programming has a negligible effect on performance, when used at sufficiently high levels, and provides flexible and extensible software for numerical methods.

REFERENCES

• 1: E. Anderson , Z. Bai , C. Bischof , J. Demmel , J. Dongarra , J. Du Croz , A. Greenbaum , S. Hammarling , A. McKenney , S. Ostrouchov , D. Sorensen, LAPACK's user's guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 2: ARGE, E. ET AL. 1997. On the numerical efficiency of C++ in scientific computing. In Numerical Methods and Software Tools in Industrial Mathematics Birkh user Boston Inc., Cambridge, MA, 91-118.
• 3: John J. Barton , Lee R. Nackman, Scientific and Engineering C++: An Introduction with Advanced Techniques and Examples, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1994
• 4: BECK, R., ERDMANN, B., AND ROITZSCH, R. 1995. KASKADE 3.0: An object-oriented adaptive finite element model. Tech. Rep. TR 95-4. Konrad-Zuse-Zentrum fur Informationstechnik, Berlin, Germany.
• 5: BESSON, J. AND FOERCH, R. 1997. Large scale object-oriented finite element code design. Comput. Methods Appl. Mech. Eng. 142, 1-2, 165-187.
• 6: BRENAN, K., CAMPBELL, S., AND PETZOLD, L. 1996. Numerical Solution of Initial-Value Problems in Differential-Algebraic Equations. SIAM, Philadelphia, PA.
• 7: Peter N. Brown , Alan C. Hindmarsh , Linda R. Petzold, Using Krylov methods in the solution of large-scale differential-algebraic systems, SIAM Journal on Scientific Computing, v.15 n.6, p.1467-1488, Nov. 1994 [doi>10.1137/0915088]
• 8: Are Magnus Bruaset , Hans Petter Langtangen, Object-oriented design of preconditioned iterative methods in diffpack, ACM Transactions on Mathematical Software (TOMS), v.23 n.1, p.50-80, March 1997 [doi>10.1145/244768.244776]
• 9: CARY, J. R., SHASHARINA, S. G., CUMMINGS, J. C., REYNDERS, J. V., AND HINKER, P. J. 1997. Comparison of C++ and Fortran 90 for object-oriented scientific programming. Comput. Phys. Commun. 105, 1, 20-36.
• 10: Viktor K. Decyk , Charles D. Norton , Boleslaw K. Szymanski, Expressing object-oriented concepts in Fortran 90, ACM SIGPLAN Fortran Forum, v.16 n.1, p.13-18, April 1997 [doi>10.1145/263877.263880]
• 11: Pompiliu Donescu , Tod A. Laursen, A generalized object-oriented approach to solving ordinary and partial differential equations using finite elements, Finite Elements in Analysis and Design, v.22 n.1, p.93-107, May 1996 [doi>10.1016/0168-874X(95)00061-W]
• 12: DONGARRA, J., BUNCH, J., MOLER, C., AND STEWART, P. 1984. Linpack. (Software). http ://www.netlib. org/linpack
• 13: DONGARRA, J. J., LUMSDAINE, A., NIU, X., Pozo, R., AND REMINGTON, K. 1994. A sparse matrix library in C++ for high performance architectures. In Proceedings of the 2nd Annual Object-Oriented Numerics Conference (00N-SKI '94, Sun River, OR, Apr.), 214-218.
• 14: DONGARRA, J., LUMSDAINE, A., POZO, R., AND REMINGTON, K. 1996. Iml+ + version 1.2 iterative methods library reference guide.
• 15: R. Pozo , J. J. Dongarra , D. W. Walker, LAPACK++: a design overview of object-oriented extensions for high performance linear algebra, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.162-171, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169680]
• 16: DUBOIS-PELERIN, Y. AND PEGON, P. 1997. Improving modularity in object-oriented finite element programming. Commun. Numer. Methods Eng. 13, 3, 193-198.
• 17: Yves Dubois-Pèlerin , Thomas Zimmermann , Patricia Bomme, Object-oriented finite element in programming: II: A prototype program in Smalltalk, Computer Methods in Applied Mechanics and Engineering, v.98 n.3, p.361-397, Aug. 1992 [doi>10.1016/0045-7825(92)90004-4]
• 18: EYHERAMENDY, D. AND ZIMMERMANN, T. 1996. Object-oriented finite elements: II. A symbolic environment for automatic programming. Comput. Methods Appl. Mech. Eng. 132, 3-4, 277-304.
• 19: GEAR, C. 1971. The simultaneous numerical solution of differential-algebraic equations. IEEE Trans. Circuit Theory CT-18, 89-95.
• 20: GEAR, C.W. 1973. Asymptotic estimation of errors and derivatives for the numerical solution of ordinary differential equations. Tech. Rep. 598. Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL.
• 21: GEAR, C. 1986. Differential-algebraic equation index transformations. University of Illinois at Urbana-Champaign, Champaign, IL.
• 22: GEAR, C., LEIMKUHLER, B., AND GUPTA, G. 1985. Automatic integration of Euler-Lagrange equations with constraints. J. Comput. Appl. Math. 12/13 (May), 77-90.
• 23: K. R. Jackson , R. Sacks-Davis, An Alternative Implementation of Variable Step-Size Multistep Formulas for Stiff ODEs, ACM Transactions on Mathematical Software (TOMS), v.6 n.3, p.295-318, Sept. 1980 [doi>10.1145/355900.355903]
• 24: KARAMETE, B., TOKDEMIR, T., AND GER, M. 1997. Unstructured grid generation and a simple triangulation algorithm for arbitrary 2-D geometries using object-oriented programming. Int. J. Num. Methods Eng. 40, 2, 251-268.
• 25: KELLEY, C. 1995. Iterative Methods for Linear and Nonlinear Equations. SIAM, Philadelphia, PA.
• 26: C. T. Kelley , C. T. Miller , M. D. Tocci, Termination of Newton/Chord Iterations and the Method of Lines, SIAM Journal on Scientific Computing, v.19 n.1, p.280-290, Jan. 1998 [doi>10.1137/S1064827596303582]
• 27: Benedict Joseph Leimkuhler , William Gear, Approximation methods for the consistent initialization of differential-algebraic equations, 1988
• 28: LEWIS, R., MASTERS, I., AND CROSS, J. 1997. Automatic timestep selection for the super-timestepping acceleration on unstructured grids using object-oriented programming. Commun. Numer. Methods Eng. 13, 3, 249-260.
• 29: Jinn-Liang Liu , Ing-Jer Lin , Miin-Zhih Shih , Ren-Chuen Chen , Mao-Chung Hsieh, Object-oriented programming of adaptive finite element and finite volume methods, Applied Numerical Mathematics, v.21 n.4, p.439-467, Oct. 1996 [doi>10.1016/S0168-9274(96)00044-X]
• 30: MAIER, R. S. AND PETZOLD, L. R. 1993. User's guide to DASPKMP and DASPKF90. Army High Performance Computing Research Center, Minneapolis, MN.
• 31: Timothy Maly , Linda R. Petzold, Numerical methods and software for sensitivity analysis of differential-algebraic systems, Applied Numerical Mathematics, v.20 n.1-2, p.57-79, Feb. 1996 [doi>10.1016/0168-9274(95)00117-4]
• 32: NEWCOMB, R.W. 1981. The semistate description of nonlinear and time-variable circuits. IEEE Trans. Circ. Syst. 28, 1, 203-216.
• 33: PETZOLD, L. 1983. A Description of DASSL: A Differential/Algebraic System Solver. North-Holland Publishing Co., Amsterdam, The Netherlands.
• 34: Terry Quatrani, Visual modeling with Rational Rose and UML, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 35: Arch D. Robison, C++ gets faster for scientific computing, Computers in Physics, v.10 n.5, p.458-462, Sept./Oct. 1996
• 36: Bjarne Stroustrup, The C++ programming language (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 37: ToccI, M., KELLEY, C., AND MILLER, C. 1997. Accurate and economical solution of the pressure-head form of Richards' equation by the method of lines. Adv. Water Resour. 20, 1, 1-14.
• 38: ZIMMERMAN, T. AND EYHERAMENDY, D. 1996. Object-oriented finite elements I. Principles of symbolic derivations and automatic programming. Comput. Methods Appl. Mech. Eng. 132, 3-4, 259-276.
• 39: Thomas Zimmermann , Yves Dubois-Pèlerin , Patricia Bomme, Object-oriented finite element programming: I: Governing principles, Computer Methods in Applied Mechanics and Engineering, v.98 n.2, p.291-303, July 1992 [doi>10.1016/0045-7825(92)90180-R]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: C++

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.2 SOFTWARE ENGINEERING
      D.2.3 Coding Tools and Techniques
          Subjects: Object-oriented programming
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: FORTRAN 77

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.7 Ordinary Differential Equations
          Subjects: Differential-algebraic equations

General Terms:
Algorithms, Design, Experimentation, Languages, Performance

Keywords:
differential-algebraic equations