Optimal monomial quadratization for ODE systems: extended abstract

ACM Communications in Computer Algebra. 2021. Vol. 54. No. 3. P. 119–123.

Бычков А., Погудин Г. А.

Transformation of a polynomial ODE system to a special quadratic form has been successfully used recently as a preprocessing step for model order reduction methods. However, to the best of our knowledge, there has been no practical algorithm for performing this step automatically with any optimality guarantees.

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 of the original variables. The algorithm is guaranteed to produce an optimal transformation of this form. The algorithm is implemented, and we demonstrate it on examples from the literature.

Ключевые слова: graph algorithms, алгоритмы теории графов, symbolic computation, nonlinear differential equations, нелинейные дифференциальные уравнения, Алгоритмы для NP-трудных задач, Algorithms for NP-hard problems