TY - GEN
T1 - Optimal Monomial Quadratization for ODE Systems
AU - Bychkov, Andrey
AU - Pogudin, Gleb
N1 - Publisher Copyright:
© 2021, Springer Nature Switzerland AG.
PY - 2021/1/1
Y1 - 2021/1/1
N2 - Quadratization is a transform of a system of ODEs with polynomial right-hand side into a system of ODEs with at most quadratic right-hand side via the introduction of new variables. Quadratization problem is, given a system of ODEs with polynomial right-hand side, transform the system to a system with quadratic right-hand side by introducing new variables. Such transformations have been used, for example, as a preprocessing step by model order reduction methods and for transforming chemical reaction networks. We present an algorithm that, given a system of polynomial ODEs, finds a transformation into a quadratic ODE system by introducing new variables which are monomials in the original variables. The algorithm is guaranteed to produce an optimal transformation of this form (that is, the number of new variables is as small as possible), and it is the first algorithm with such a guarantee we are aware of. Its performance compares favorably with the existing software, and it is capable to tackle problems that were out of reach before.
AB - Quadratization is a transform of a system of ODEs with polynomial right-hand side into a system of ODEs with at most quadratic right-hand side via the introduction of new variables. Quadratization problem is, given a system of ODEs with polynomial right-hand side, transform the system to a system with quadratic right-hand side by introducing new variables. Such transformations have been used, for example, as a preprocessing step by model order reduction methods and for transforming chemical reaction networks. We present an algorithm that, given a system of polynomial ODEs, finds a transformation into a quadratic ODE system by introducing new variables which are monomials in the original variables. The algorithm is guaranteed to produce an optimal transformation of this form (that is, the number of new variables is as small as possible), and it is the first algorithm with such a guarantee we are aware of. Its performance compares favorably with the existing software, and it is capable to tackle problems that were out of reach before.
KW - Branch-and-bound
KW - Differential equations
KW - Quadratization
U2 - 10.1007/978-3-030-79987-8_9
DO - 10.1007/978-3-030-79987-8_9
M3 - Conference contribution
AN - SCOPUS:85112004657
SN - 9783030799861
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 122
EP - 136
BT - Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Proceedings
A2 - Flocchini, Paola
A2 - Moura, Lucia
PB - Springer Science and Business Media Deutschland GmbH
T2 - 32nd International Workshop on Combinatorial Algorithms, IWOCA 2021
Y2 - 5 July 2021 through 7 July 2021
ER -