TCS lab seminar: "Optimal monomial quadratization for ODE systems"
The laboratory will have the next seminar online on Wednesday, April 14, 18:10 via Zoom.
Speaker: Andrey Bychkov
Title: "Optimal monomial quadratization for ODE systems"
Please follow the link for registration: https://zoom.us/meeting/register/tJUqdeGvrzgtG9GAjc1oamWw_vmfZqqxoW3n
Consider a system of ODEs with polynomial right-hand side, for example, a scalar ODE: $x’ = x^5$. Introducing a new variable $y = x^4$ leads us to a system of two equations: $x’ = xy$ and $y’ = 4x^3 x’ = 4x^4 y = 4y^2$. The right-hand sides of the new system are of degree at most two, and every solution of the original system is the x-component of some solution of the new system. Such problem, given a system of ordinary differential equations (ODEs) with polynomial right-hand side, transform it into a system with quadratic right-hand side, is called a quadratization problem. The quadratization problem has emerged recently in such areas as model order reduction, numerical solutions of ODEs and chemical reaction networks. In 2011, Ch. Gu proved that it is always possible to perform quadratization with new variables being monomials in the original variables (like $x^4$ in the example above). We call such quadratization monomial. Later in 2020, M. Hemery, F. Fages, and S. Soliman, have showed that the problem of finding an optimal (i.e. of the smallest possible dimension) monomial quadratization is NP-hard. They also designed and implemented an algorithm for finding a monomial quadratization which is practical and yields an optimal monomial quadratization in many cases. In the talk, I will show the results of our recent preprint with G. Pogudin, in which we designed and implemented a practical algorithm that is guaranteed to find an optimal monomial quadratization. We will also discuss encoding the optimal monomial quadratization problem as APX-hard -sumset cover problem.