research-article

Open access

Partial Evaluation of Automatic Differentiation for Differential-Algebraic Equations Solvers

Authors:

Oscar Eriksson,

Viktor Palmkvist,

David BromanAuthors Info & Claims

GPCE 2023: Proceedings of the 22nd ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences

Pages 57 - 71

https://doi.org/10.1145/3624007.3624054

Published: 22 October 2023 Publication History

Abstract

Differential-Algebraic Equations (DAEs) are the foundation of high-level equation-based languages for modeling physical dynamical systems. Simulating models in such languages requires a transformation known as index reduction that involves differentiating individual equations before numerical integration. Commercial and open-source implementations typically perform index reduction by symbolic differentiation (SD) and produce a Jacobian callback function with forward-mode automatic differentiation (AD). The former results in efficient runtime code, and the latter is asymptotically efficient in both runtime and code size. However, AD introduces runtime overhead caused by a non-standard representation of real numbers, and SD is not always applicable in models with general recursion. This work proposes a new approach that uses partial evaluation of AD in the context of numerical DAE solving to combine the strengths of the two differentiation methods while mitigating their weaknesses. Moreover, our approach selectively specializes partial derivatives of the Jacobian by exploiting structural knowledge while respecting a user-defined bound on the code size. Our evaluation shows that the new method both enables expressive modeling from AD and retains the efficiency of SD for many practical applications.

References

[1]

Martín Abadi and Gordon D. Plotkin. 2019. A simple differentiable programming language. Proceedings of the ACM on Programming Languages, 4, POPL (2019), Dec., 38:1–38:28. https://doi.org/10.1145/3371106

Digital Library

[2]

Joel Andersson, Johan Åkesson, and Moritz Diehl. 2012. CasADi: A symbolic package for automatic differentiation and optimal control. In Recent advances in algorithmic differentiation. 297–307. https://doi.org/10.1007/978-3-642-30023-3_27

[3]

Joel AE Andersson, Joris Gillis, Greg Horn, James B Rawlings, and Moritz Diehl. 2019. CasADi: a software framework for nonlinear optimization and optimal control. Mathematical Programming Computation, 11 (2019), 1–36. https://doi.org/10.1007/s12532-018-0139-4

[4]

Gordon C. Andrews. 1977. A General Re-Statement of the Laws of Dynamics Based on Graph Theory. In Problem Analysis in Science and Engineering, F.H. Branin and K. Huseyin (Eds.). Academic Press, 1–40. isbn:978-0-12-125550-3 https://doi.org/10.1016/B978-0-12-125550-3.50006-5

[5]

Martin Arnold. 2017. DAE Aspects of Multibody System Dynamics. Springer International Publishing, Cham. isbn:978-3-319-46618-7 https://doi.org/10.1007/978-3-319-46618-7_2

[6]

Peter J. Ashenden, Gregory D. Peterson, and Darrell A. Teegarden. 2002. The System Designer’s Guide to VHDL-AMS: Analog, Mixed-Signal, and Mixed-Technology Modeling. Morgan Kaufmann Publishers, USA. isbn:1558607498 https://doi.org/10.1016/B978-1-55860-749-1.X5000-2

[7]

Bernhard Bachmann, Peter Aronsson, and Peter Fritzson. 2007. Robust Initialization of Differential Algebraic Equations. In Equation-Based Object-Oriented Languages and Tools (EOOLT). 151–163.

[8]

Atilim Gunes Baydin, Barak A. Pearlmutter, Alexey Andreyevich Radul, and Jeffrey Mark Siskind. 2015. Automatic differentiation in machine learning: a survey. https://doi.org/10.48550/ARXIV.1502.05767

[9]

Atilim Gunes Baydin, Barak A Pearlmutter, Alexey Andreyevich Radul, and Jeffrey Mark Siskind. 2018. Automatic differentiation in machine learning: a survey. Journal of Marchine Learning Research, 18 (2018), 1–43.

Digital Library

[10]

Atılım Güneş Baydin, Barak A. Pearlmutter, and Jeffrey Mark Siskind. 2016. DiffSharp: An AD Library for .NET Languages. arxiv:1611.03423 arXiv:1611.03423 [cs]

[11]

Anders Bondorf. 1992. Improving Binding Times without Explicit CPS-Conversion. In Proceedings of the 1992 ACM Conference on LISP and Functional Programming (LFP ’92). Association for Computing Machinery, New York, NY, USA. 1–10. isbn:0897914813 https://doi.org/10.1145/141471.141483

Digital Library

[12]

Timothy Bourke, Jun Inoue, and Marc Pouzet. 2018. Sundials/ML: Connecting OCaml to the Sundials Numeric Solvers. In Proceedings ML Family Workshop / OCaml Users and Developers workshops, Nara, Japan, September 22-23, 2016, Kenichi Asai and Mark Shinwell (Eds.) (Electronic Proceedings in Theoretical Computer Science, Vol. 285). Open Publishing Association, 101–130. https://doi.org/10.4204/EPTCS.285.4

[13]

Willi Braun, Lennart Ochel, and Bernhard Bachmann. 2011. Symbolically derived Jacobians using automatic differentiation-enhancement of the OpenModelica compiler. In Proceedings of the 8th International Modelica Conference; March 20th-22nd; Technical Univeristy; Dresden; Germany. 495–501. https://doi.org/10.3384/ecp11063495

[14]

K. E. Brenan, S. L. Campbell, and L. R. Petzold. 1995. Numerical Solution of Initial-Value Problems in Differential-Algebraic Equations. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611971224

[15]

David Broman. 2010. Meta-Languages and Semantics for Equation-Based Modeling and Simulation. Ph. D. Dissertation. Department of Computer and Information Science, Linköping University. Sweden.

[16]

David Broman. 2019. A Vision of Miking: Interactive Programmatic Modeling, Sound Language Composition, and Self-Learning Compilation. In Proceedings of the 12th ACM SIGPLAN International Conference on Software Language Engineering (SLE 2019). Association for Computing Machinery, New York, NY, USA. 55–60. isbn:9781450369817 https://doi.org/10.1145/3357766.3359531

Digital Library

[17]

David Broman and Jeremy G. Siek. 2017. Gradually Typed Symbolic Expressions. In Proceedings of the ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (PEPM ’18). Association for Computing Machinery, New York, NY, USA. 15–29. isbn:9781450355872 https://doi.org/10.1145/3162068

Digital Library

[18]

Stephen L Campbell, R Hollenbeck, K Yeomans, and Yangchun Zhong. 1998. Mixed symbolic–numerical computations with general DAEs I: System properties. Numerical Algorithms, 19 (1998), 73–83. https://doi.org/10.1023/A:1019154423096

[19]

Stephen L Campbell and Wieslaw Marszalek. 1998. Mixed symbolic–numerical computations with general DAEs II: An applications case study. Numerical Algorithms, 19 (1998), 85–94. https://doi.org/10.1023/A:1019106507166

[20]

Dassault Systems. [n. d.]. DYMOLA Systems Engineering: Multi-Engineering Modeling and Simulation based on Modelica and FMI. http://www.dymola.com

[21]

Conal Elliott. 2009. Beautiful differentiation. In International Conference on Functional Programming (ICFP). http://conal.net/papers/beautiful-differentiation

Digital Library

[22]

Atiyah Elsheikh. 2015. An equation-based algorithmic differentiation technique for differential algebraic equations. J. Comput. Appl. Math., 281 (2015), June, 135–151. https://doi.org/10.1016/j.cam.2014.12.026

Digital Library

[23]

Martin Elsman, Fritz Henglein, Robin Kaarsgaard, Mikkel Kragh Mathiesen, and Robert Schenck. 2022. Combinatory Adjoints and Differentiation. In Proceedings Ninth Workshop on Mathematically Structured Functional Programming, Munich, Germany, 2nd April 2022, Jeremy Gibbons and Max S. New (Eds.) (Electronic Proceedings in Theoretical Computer Science, Vol. 360). Open Publishing Association, 1–26. https://doi.org/10.4204/EPTCS.360.1

[24]

Oscar Eriksson, Viktor Palmkvist, and David Broman. 2023. Partial Evaluation of Automatic Differentation for Differential-Algebraic Equations Solvers. https://doi.org/10.5281/zenodo.8347712

Digital Library

[25]

Cormac Flanagan, Amr Sabry, Bruce F. Duba, and Matthias Felleisen. 1993. The Essence of Compiling with Continuations. In Proceedings of the ACM SIGPLAN 1993 Conference on Programming Language Design and Implementation (PLDI ’93). Association for Computing Machinery, New York, NY, USA. 237–247. isbn:0897915984 https://doi.org/10.1145/155090.155113

Digital Library

[26]

Peter Fritzson, Peter Aronsson, Håkan Lundvall, Kaj Nyström, Adrian Pop, Levon Saldamli, and David Broman. 2005. The OpenModelica Modeling, Simulation, and Software Development Environment. Simulation News Europe, 15, 44/45 (2005), 8–16.

[27]

Assefaw Hadish Gebremedhin, Fredrik Manne, and Alex Pothen. 2005. What Color Is Your Jacobian? Graph Coloring for Computing Derivatives. SIAM Rev., 47, 4 (2005), 629–705. https://doi.org/10.1137/S0036144504444711 arxiv:https://doi.org/10.1137/S0036144504444711.

Digital Library

[28]

Narain Gehani and Krithi Ramamritham. 1991. Real-time concurrent C: A language for programming dynamic real-time systems. Real-Time Systems, 3, 4 (1991), 377–405. https://doi.org/10.1007/BF00365999

[29]

Andreas Griewank, Jean Utke, and Andrea Walther. 2000. Evaluating Higher Derivative Tensors by Forward Propagation of Univariate Taylor Series. Math. Comp., 69, 231 (2000), 1117–1130. issn:00255718, 10886842 http://www.jstor.org/stable/2585017

Digital Library

[30]

Andreas Griewank and Andrea Walther. 2004. On the Efficient Generation of Taylor Expansions for DAE Solutions by Automatic Differentiation. In Proceedings of the 7th International Conference on Applied Parallel Computing: State of the Art in Scientific Computing (PARA’04). Springer-Verlag, Berlin, Heidelberg. 1089–1098. isbn:3540290672 https://doi.org/10.1007/11558958_131

Digital Library

[31]

Benjamin Grégoire and Xavier Leroy. 2002. A Compiled Implementation of Strong Reduction. In Proceedings of the Seventh ACM SIGPLAN International Conference on Functional Programming (ICFP ’02). Association for Computing Machinery, New York, NY, USA. 235–246. isbn:1581134878 https://doi.org/10.1145/581478.581501

Digital Library

[32]

Laurent Hascoet and Valérie Pascual. 2013. The Tapenade Automatic Differentiation Tool: Principles, Model, and Specification. ACM Trans. Math. Softw., 39, 3 (2013), Article 20, may, 43 pages. issn:0098-3500 https://doi.org/10.1145/2450153.2450158

Digital Library

[33]

Alan C. Hindmarsh, Peter N. Brown, Keith E. Grant, Steven L. Lee, Radu Serban, Dan E. Shumaker, and Carol S. Woodward. 2005. SUNDIALS: Suite of Nonlinear and Differential/Algebraic Equation Solvers. ACM Trans. Math. Softw., 31, 3 (2005), sep, 363–396. issn:0098-3500 https://doi.org/10.1145/1089014.1089020

Digital Library

[34]

Robin J. Hogan. 2014. Fast Reverse-Mode Automatic Differentiation Using Expression Templates in C++. ACM Trans. Math. Software, 40, 4 (2014), jun, 26:1–26:24. http://doi.acm.org/10.1145/2560359

Digital Library

[35]

Neil D Jones, Carsten K Gomard, and Peter Sestoft. 1993. Partial evaluation and automatic program generation.

[36]

Jerzy Karczmarczuk. 1998. Functional Differentiation of Computer Programs. In Proceedings of the Third ACM SIGPLAN International Conference on Functional Programming (ICFP ’98). Association for Computing Machinery, New York, NY, USA. 195–203. isbn:1581130244 https://doi.org/10.1145/289423.289442

Digital Library

[37]

Faustyna Krawiec, Simon Peyton Jones, Neel Krishnaswami, Tom Ellis, Richard A. Eisenberg, and Andrew Fitzgibbon. 2022. Provably Correct, Asymptotically Efficient, Higher-Order Reverse-Mode Automatic Differentiation. Proc. ACM Program. Lang., 6, POPL (2022), Article 48, jan, 30 pages. https://doi.org/10.1145/3498710

Digital Library

[38]

Peter Kunkel and Volker Mehrmann. 2006. Differential-Algebraic Equations Analysis and Numerical Solution. European Mathematical Society. isbn:3-03719-017-5

[39]

Maplesoft. [n. d.]. Maple. https://www.maplesoft.com/products/Maple/

[40]

MathWorks. [n. d.]. Simscape - Model and simulate multidomain physical systems. https://www.mathworks.com/products/simscape

[41]

Sven Erik Mattsson and Gustaf Söderlind. 1993. Index reduction in differential-algebraic equations using dummy derivatives. SIAM Journal on Scientific Computing, 14, 3 (1993), 677–692. https://doi.org/10.1137/0914043

Digital Library

[42]

2017. Modelica - A Unified Object-Oriented Language for Physical Systems Modeling - Language Specification Version 3.4. Available from: http://www.modelica.org

[43]

Nedialko S Nedialkov and John D Pryce. 2005. Solving differential-algebraic equations by Taylor series (I): Computing Taylor coefficients. BIT-Numerical Mathematics, 45, 3 (2005), 561–592. https://doi.org/10.1007/s10543-005-0019-y

Digital Library

[44]

Nedialko S Nedialkov and John D Pryce. 2007. Solving differential-algebraic equations by Taylor series (II): Computing the System Jacobian. BIT Numerical Mathematics, 47 (2007), 121–135. https://doi.org/10.1007/s10543-006-0106-8

Digital Library

[45]

Nedialko S Nedialkov and John D Pryce. 2007. Solving differential-algebraic equations by Taylor series (III): the DAETS code. Journal of Numerical Analysis, Industrial and Applied Mathematics, 1, 1 (2007), 1–30.

[46]

Hans Olsson, Hubertus Tummescheit, Hilding Elmqvist, AB Dynasim, and AB Modelon. 2005. Using automatic differentiation for partial derivatives of functions in Modelica. In Proceedings of the 4th International Modelica Conference.

[47]

Martin Otter and Hilding Elmqvist. 2017. Transformation of differential algebraic array equations to index one form. In Proceedings of the 12th International Modelica Conference. https://doi.org/10.3384/ecp17132565

[48]

Viktor Palmkvist, Elias Castegren, Philipp Haller, and David Broman. 2023. Statically Resolvable Ambiguity. Proc. ACM Program. Lang., 7, POPL (2023), Article 58, jan, 27 pages. https://doi.org/10.1145/3571251

Digital Library

[49]

Constantinos C Pantelides. 1988. The consistent initialization of differential-algebraic systems. SIAM J. Sci. Statist. Comput., 9, 2 (1988), 213–231. https://doi.org/10.1137/0909014

[50]

David Peter. 2023. hyperfine. https://github.com/sharkdp/hyperfine

[51]

L. R. Petzold. 1982. Description of DASSL: a differential/algebraic system solver. Sandia National Labs., Livermore, CA (USA). https://www.osti.gov/biblio/5882821

[52]

J. D. Pryce. 1998. Numerical Algorithms, 19, 1/4 (1998), 195–211. https://doi.org/10.1023/a:1019150322187

[53]

J. D. Pryce. 2001. Bit Numerical Mathematics, 41, 2 (2001), 364–394. https://doi.org/10.1023/a:1021998624799

Digital Library

[54]

John D. Pryce, Nedialko S. Nedialkov, Guangning Tan, and Xiao Li. 2018. How AD can help solve differential-algebraic equations. Optimization Methods and Software, 33, 4-6 (2018), March, 729–749. https://doi.org/10.1080/10556788.2018.1428605

[55]

Amir Shaikhha, Andrew Fitzgibbon, Dimitrios Vytiniotis, and Simon Peyton Jones. 2019. Efficient Differentiable Programming in a Functional Array-Processing Language. Proc. ACM Program. Lang., 3, ICFP (2019), Article 97, jul, 30 pages. https://doi.org/10.1145/3341701

Digital Library

[56]

Amir Shaikhha, Mathieu Huot, and Shideh Hashemian. 2023. ∇ SD: Differentiable Programming for Sparse Tensors. arxiv:2303.07030.

[57]

Jeffrey M Siskind and Barak A Pearlmutter. 2008. Using Polyvariant Union-Free Flow Analysis to Compile a Higher-Order Functional-Programming Language with a First-Class Derivative Operator to Efficient Fortran-like Code. 12.

[58]

Ole Stauning and Claus Bendtsen. [n. d.]. FADBAD++. http://uning.dk/fadbad.html

[59]

Matthijs Vákár, Sam Staton, and Mathieu Huot. 2022. Higher order automatic differentiation of higher order functions. Logical Methods in Computer Science, 18 (2022), https://doi.org/10.46298/lmcs-18(1:41)2022

[60]

A. Walther and A. Griewank. 2012. Getting started with ADOL-C. 181–202 pages.

[61]

Fei Wang, Daniel Zheng, James Decker, Xilun Wu, Grégory M. Essertel, and Tiark Rompf. 2019. Demystifying differentiable programming: shift/reset the penultimate backpropagator. Proceedings of the ACM on Programming Languages, 3, ICFP (2019), July, 96:1–96:31. https://doi.org/10.1145/3341700

Digital Library

Cited By

Sowmith JDasari LMamidi NBelwal M(2024)Parsing Ambiguous Grammar-A Survey2024 15th International Conference on Computing Communication and Networking Technologies (ICCCNT)10.1109/ICCCNT61001.2024.10724711(1-7)Online publication date: 24-Jun-2024
https://doi.org/10.1109/ICCCNT61001.2024.10724711

Index Terms

Partial Evaluation of Automatic Differentiation for Differential-Algebraic Equations Solvers

Recommendations

Multiple shooting using a dichotomically stable integrator for solving differential-algebraic equations

In previous work by the first author, it has been established that a dichotomically stable discretization is needed when solving a stiff boundary-value problem in ordinary differential equations (ODEs), when sharp boundary layers may occur at each end ...
Regularization methods for solving differential-algebraic equations

In [M. Knorrenschild, SIAM J. Numer. Anal. 29 (1992) 1694-1715], a class of regularization methods for solving autonomous index-1 DAEs (differential-algebraic equations) has been proposed. In this paper, we generalize it to non-autonomous index-1 and ...
Adjoint pairs of differential-algebraic equations and Hamiltonian systems

We consider linear homogeneous differential-algebraic equations A(Dx)^'+Bx=0 and their adjoints -D^*(A^*x)^'+B^*x=0 with well-matched leading coefficients in parallel. Assuming that the equations are tractable with index less than or equal to 2, we give ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GPCE 2023: Proceedings of the 22nd ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences

October 2023

152 pages

ISBN:9798400704062

DOI:10.1145/3624007

General Chairs:
Coen De Roover
Vrije Universiteit Brussel, Belgium
,
Bernhard Rumpe
RWTH Aachen University, Germany
,
Program Chair:
Amir Shaikhha
University of Edinburgh, UK

Copyright © 2023 Owner/Author.

This work is licensed under a Creative Commons Attribution 4.0 International License.

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 October 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Artifacts Available / v1.1

Author Tags

Qualifiers

Research-article

Funding Sources

Swedish Research Council
Swedish Foundation for Strategic Research
Digital Futures (the DLL project)
Vinnova Competence Center for Trustworthy Edge Computing Sys- tems and Applications (TECoSA)

Conference

GPCE '23

Sponsor:

SIGPLAN

GPCE '23: 22nd ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences

October 22 - 23, 2023

Cascais, Portugal

Acceptance Rates

Overall Acceptance Rate 56 of 180 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
314
Total Downloads

Downloads (Last 12 months)199
Downloads (Last 6 weeks)32

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sowmith JDasari LMamidi NBelwal M(2024)Parsing Ambiguous Grammar-A Survey2024 15th International Conference on Computing Communication and Networking Technologies (ICCCNT)10.1109/ICCCNT61001.2024.10724711(1-7)Online publication date: 24-Jun-2024
https://doi.org/10.1109/ICCCNT61001.2024.10724711

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten