Efficient syntax-Driven lumping of differential equations

Luca Cardelli*, Mirco Tribastone, Max Tschaikowski, Andrea Vandin

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


We present an algorithm to compute exact aggregations of a class of systems of ordinary differential equations (ODEs). Our approach consists in an extension of Paige and Tarjan’s seminal solution to the coarsest refinement problem by encoding an ODE system into a suitable discrete-state representation. In particular, we consider a simple extension of the syntax of elementary chemical reaction networks because (i) it can express ODEs with derivatives given by polynomials of degree at most two, which are relevant in many applications in natural sciences and engineering; and (ii) we can build on two recently introduced bisimulations, which yield two complementary notions of ODE lumping. Our algorithm computes the largest bisimulations in O(r·s·log s) time, where r is the number of monomials and s is the number of variables in the ODEs. Numerical experiments on real-world models from biochemistry, electrical engineering, and structural mechanics show that our prototype is able to handle ODEs with millions of variables and monomials, providing significant model reductions.

Original languageEnglish
Title of host publicationTools and Algorithms for the Construction and Analysis of Systems - 22nd International Conference, TACAS 2016 and Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2016, Proceedings
Number of pages19
PublisherSpringer Verlag
Publication date2016
ISBN (Print)9783662496732
Publication statusPublished - 2016
Externally publishedYes
Event22nd International Conference on Tools and Algorithms for the Construction and Analysis of Systems - Eindhoven, Netherlands
Duration: 2 Apr 20168 Apr 2016
Conference number: 22


Conference22nd International Conference on Tools and Algorithms for the Construction and Analysis of Systems
Internet address
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)


Dive into the research topics of 'Efficient syntax-Driven lumping of differential equations'. Together they form a unique fingerprint.

Cite this