×

Exact hierarchical reductions of dynamical models via linear transformations. (English) Zbl 1531.34046

Summary: Dynamical models described by ordinary differential equations (ODEs) are a fundamental tool in the sciences and engineering. Exact reduction aims at producing a lower-dimensional model in which each macro-variable can be directly related to the original variables, and it is thus a natural step towards the model’s formal analysis and mechanistic understanding. We present an algorithm which, given a polynomial ODE model, computes a longest possible chain of exact linear reductions of the model such that each reduction refines the previous one, thus giving a user control of the level of detail preserved by the reduction. This significantly generalizes over the existing approaches which compute only the reduction of the lowest dimension subject to an approach-specific constraint. The algorithm reduces finding exact linear reductions to a question about representations of finite-dimensional algebras. We provide an implementation of the algorithm, demonstrate its performance on a set of benchmarks, and illustrate the applicability via case studies. Our implementation is freely available at https://github.com/x3042/ExactODEReduction.jl.

MSC:

34C20 Transformation and reduction of ordinary differential equations and systems, normal forms
34-04 Software, source code, etc. for problems pertaining to ordinary differential equations
16G10 Representations of associative Artinian rings
92E20 Classical flows, reactions, etc. in chemistry

References:

[1] Feret, J.; Danos, V.; Krivine, J.; Harmer, R.; Fontana, W., Internal coarse-graining of molecular systems, Proc Natl Acad Sci, 106, 16, 6453-6458, (2009)
[2] Feret, J.; Henzinger, T.; Koeppl, H.; Petrov, T., Lumpability abstractions of rule-based systems, Theoret Comput Sci, 431, 137-164, (2012) · Zbl 1267.68153
[3] Cardelli, L.; Tribastone, M.; Tschaikowski, M.; Vandin, A., ERODE: A tool for the evaluation and reduction of ordinary differential equations, (TACAS 2017. TACAS 2017, LNCS, vol. 10206, (2017))
[4] Cardelli, L.; Tribastone, M.; Tschaikowski, M.; Vandin, A., Maximal aggregation of polynomial dynamical systems, Proc Natl Acad Sci, 114, 38, 10029-10034, (2017), URL https://www.pnas.org/content/114/38/10029
[5] Ovchinnikov, A.; Verona, I. P.; Pogudin, G.; Tribastone, M., CLUE: exact maximal reduction of kinetic models by constrained lumping of differential equations, Bioinformatics, (2021)
[6] Antoulas, A., (Approximation of large-scale dynamical systems. Approximation of large-scale dynamical systems, Adv. in design and control, (2005), SIAM) · Zbl 1112.93002
[7] Hubert, E.; Labahn, G., Scaling invariants and symmetry reduction of dynamical systems, Found Comput Math, 13, 4, 479-516, (2013) · Zbl 1284.34045
[8] Camporesi, F.; Feret, J., Formal reduction for rule-based models, Electron Notes Theor Comput Sci, 276, 29-59, (2011) · Zbl 1342.68076
[9] Olver, P. J., Equivalence, invariants and symmetry, (1995), Cambridge University Press · Zbl 0837.58001
[10] Sankaranarayanan, S., Automatic abstraction of non-linear systems using change of bases transformations, (Proceedings of the 14th International Conference on Hybrid Systems: Computation and control, (2011)) · Zbl 1362.93033
[11] Faeder, J. R.; Blinov, M. L.; Hlavacek, W. S., Graphical rule-based representation of signal-transduction networks, (Proceedings of the 2005 ACM Symposium on Applied Computing, (2005))
[12] Danos, V.; Feret, J.; Fontana, W.; Harmer, R.; Krivine, J., Rule-based modelling of cellular signalling, (CONCUR 2007 - concurrency theory, (2007)), 17-41 · Zbl 1151.68723
[13] Camporesi, F.; Feret, J.; Hayman, J., Context-sensitive flow analyses: A hierarchy of model reductions, (Computational Methods in Systems Biology, (2013)), 220-233
[14] Camporesi, F.; Feret, J.; Lý, K. Q., KaDE: A tool to compile kappa rules into (reduced) ODEs models, (Fifteenth International Workshop on Static Analysis and Systems Biology. Fifteenth International Workshop on Static Analysis and Systems Biology, LNCS/LNBI, vol. 10545, (2017), springer)
[15] Cardelli, L.; Tribastone, M.; Tschaikowski, M.; Vandin, A., Symbolic computation of differential equivalences, Theoret Comput Sci, 777, 132-154, (2019) · Zbl 1425.68463
[16] Jiménez-Pastor, A.; Jacob, J. P.; Pogudin, G., Exact linear reduction for rational dynamical systems, (Computational Methods in Systems Biology, (2022), Springer International Publishing), 198-216 · Zbl 1505.92076
[17] Li, G.; Rabitz, H., A general analysis of exact lumping in chemical kinetics, Chem Eng Sci, 44, 6, 1413-1430, (1989)
[18] Rónyai, L., Computing the structure of finite algebras, J Symbolic Comput, 9, 3, 355-373, (1990) · Zbl 0721.16001
[19] Chistov, A.; Ivanyos, G.; Karpinski, M., Polynomial time algorithms for modules over finite dimensional algebras, (Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, (1997)), 68-74 · Zbl 0918.16001
[20] Speyer D. Response to “Is there a clean way to extract the subspaces invariant under a list of matrices?”, URL https://mathematica.stackexchange.com/questions/6519/is-there-a-clean-way-to-extract-the-subspaces-invariant-under-a-list-of-matrices/9442#9442.
[21] Malik-Sheriff, R. S.; Glont, M.; Nguyen, T. V.N.; Tiwari, K.; Roberts, M. G.; Xavier, A., BioModels — 15 years of sharing computational models in life science, Nucleic Acids Res, 48, D1, D407-D415, (2020)
[22] Pogudin, G.; Zhang, X., Interpretable exact linear reductions via positivity, (Cinquemani, E.; Paulevé, L., Computational Methods in Systems Biology, (2021)), 91-107 · Zbl 1489.92059
[23] Dunn, S.; Constantinides, A.; Moghe, P., Numerical methods in biomedical engineering, (2006), Academic Press
[24] Feinberg, M., Foundations of chemical reaction network theory, (2019), Springer Cham · Zbl 1420.92001
[25] Reineke, M., Every projective variety is a quiver grassmannian, Algebr Represent Theory, 16, 1313-1314, (2013) · Zbl 1284.16015
[26] Nijholt, E.; Rink, B. W.; Schwenker, S., Quiver representations and dimension reduction in dynamical systems, SIAM J Appl Dyn Syst, 19, 4, 2428-2468, (2020) · Zbl 1465.37040
[27] Drozd, Y. A.; Kirichenko, V. V., Finite dimensional algebras, (1994), Springer-Verlag · Zbl 0816.16001
[28] Bremner, M. R., How to compute the wedderburn decomposition of a finite-dimensional associative algebra, Groups, Complex, Cryptol, 3, 1, 47-66, (2011) · Zbl 1250.16018
[29] Klep, I.; Volčič, J., A note on group representations, determinantal hypersurfaces and their quantizations, (Bastos, M. A.; Castro, L.; Karlovich, A. Y., Operator theory, functional analysis and applications, (2021), Springer International Publishing), 393-402 · Zbl 1540.20018
[30] Cohen, S. D., The distribution of galois groups and Hilbert’s irreducibility theorem, Proc Lond Math Soc, s3-43, 2, 227-250, (1981) · Zbl 0484.12002
[31] Zippel, R., Effective polynomial computation, (1993), Springer · Zbl 0794.11048
[32] Axler, S., Linear algebra done right, (2015), Springer Cham · Zbl 1304.15001
[33] Bezanson, J.; Edelman, A.; Karpinski, S.; Shah, V. B., Julia: A fresh approach to numerical computing, SIAM Rev, 59, 1, 65-98, (2017) · Zbl 1356.68030
[34] Fieker, C.; Hart, W.; Hofmann, T.; Johansson, F., Nemo/hecke: Computer algebra and number theory packages for the julia programming language, (Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, (2017), ACM: ACM New York, NY, USA), 157-164, URL https://doi.acm.org/10.1145/3087604.3087611 · Zbl 1457.68325
[35] Hart, W. B., Fast library for number theory: An introduction, (Proceedings of the third International Congress on Mathematical Software, (2010), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 88-91, https://flintlib.org · Zbl 1273.11177
[36] Johansson, F., Calcium, (Proceedings of the 2021 on International Symposium on Symbolic and Algebraic Computation, (2021))
[37] Davis, T. A., Algorithm 1000: SuiteSparse:Graphblas: Graph algorithms in the language of sparse linear algebra, ACM Trans Math Software, 45, 4, (2019) · Zbl 1486.65044
[38] ERODE: Evaluation and reduction of stochastic reaction networks and differential equations, (2020), User’s manual, URL https://www.erode.eu/docs/ERODE-manual.pdf
[39] Pérez-Verona, I. C.; Tribastone, M.; Vandin, A., A large-scale assessment of exact model reduction in the BioModels repository, (Bortolussi, L.; Sanguinetti, G., Computational Methods in Systems Biology, (2019), Springer International Publishing), 248-265 · Zbl 1422.92072
[40] Assarf, B.; Gawrilow, E.; Herr, K.; Joswig, M.; Lorenz, B.; Paffenholz, A.; Rehn, T., Computing convex hulls and counting integer points with, Math Program Comput, 9, 1, 1-38, (2017) · Zbl 1370.90009
[41] Hockin, M. F.; Cawthern, K. M.; Kalafatis, M.; Mann, K. G., A model describing the inactivation of factor va by APC: Bond cleavage, fragment dissociation, and product inhibition, Biochemistry, 38, 21, 6918-6934, (1999)
[42] Ma, Y.; Gowda, S.; Anantharaman, R.; Laughman, C.; Shah, V.; Rackauckas, C., ModelingToolkit: A composable graph transformation system for equation-based modeling, (2021), arXiv:2103.05244
[43] Rackauckas, C.; Nie, Q., DifferentialEquations.jl-A performant and feature-rich ecosystem for solving differential equations in Julia, J Open Res Softw, 5, 1, (2017)
[44] Schliemann, M.; Bullinger, E.; Borchers, S.; Allgöwer, F.; Findeisen, R.; Scheurich, P., Heterogeneity reduces sensitivity of cell death for TNF-stimuli, BMC Syst Biol, 5, 204, (2011)
[45] Scott, J. K.; Barton, P. I., Bounds on the reachable sets of nonlinear control systems, Automatica, 49, 1, 93-100, (2013) · Zbl 1257.93015
[46] Tschaikowski, M.; Tribastone, M., Approximate reduction of heterogenous nonlinear models with differential hulls, IEEE Trans Automat Control, 61, 4, 1099-1104, (2016) · Zbl 1359.93084
[47] Girard, A.; Pappas, G. J., Approximate bisimulation: A bridge between computer science and control theory, Eur J Control, 17, 5, 568-578, (2011) · Zbl 1253.68241
[48] Soliman, S.; Fages, F.; Radulescu, O., A constraint solving approach to model reduction by tropical equilibration, Algorithms Mol Biol, 9, 1, (2014)
[49] Goyer, A., A sage package for the symbolic-numeric factorization of linear differential operators, ACM Commun Comput Algebra, 55, 2, 44-48, (2021) · Zbl 07581916
[50] Chyzak, F.; Goyer, A.; Mezzarobba, M., Symbolic-numeric factorization of differential operators, (Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation, (2022)), 73-82
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.