TY - GEN
T1 - Bounds for orders of derivatives in differential elimination algorithms
AU - Gustavson, Richard
AU - Ovchinnikov, Alexey
AU - Pogudin, Gleb
N1 - Publisher Copyright:
© 2016 Copyright held by the owner/author(s).
PY - 2016/7/20
Y1 - 2016/7/20
N2 - We compute an upper bound for the orders of derivatives in the Rosenfeld-Gröbner algorithm. This algorithm computes a regular decomposition of a radical differential ideal in the ring of differential polynomials over a differential field of characteristic zero with an arbitrary number of commuting derivations. This decomposition can then be used to test for membership in the given radical differential ideal. In particular, this algorithm allows us to determine whether a system of polynomial PDEs is consistent. Previously, the only known order upper bound was given by Golubitsky, Kondratieva, Moreno Maza, and Ovchinnikov for the case of a single derivation. We achieve our bound by associating to the algorithm antichain sequences whose lengths can be bounded using the results of Leon Sanchez and Ovchinnikov.
AB - We compute an upper bound for the orders of derivatives in the Rosenfeld-Gröbner algorithm. This algorithm computes a regular decomposition of a radical differential ideal in the ring of differential polynomials over a differential field of characteristic zero with an arbitrary number of commuting derivations. This decomposition can then be used to test for membership in the given radical differential ideal. In particular, this algorithm allows us to determine whether a system of polynomial PDEs is consistent. Previously, the only known order upper bound was given by Golubitsky, Kondratieva, Moreno Maza, and Ovchinnikov for the case of a single derivation. We achieve our bound by associating to the algorithm antichain sequences whose lengths can be bounded using the results of Leon Sanchez and Ovchinnikov.
KW - Polynomial differential equations
KW - computational complexity
KW - differential elimination algorithms
U2 - 10.1145/2930889.2930922
DO - 10.1145/2930889.2930922
M3 - Conference contribution
AN - SCOPUS:84984647091
T3 - Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC
SP - 239
EP - 246
BT - ISSAC 2016 - Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation
A2 - Rosenkranz, Markus
PB - Association for Computing Machinery
T2 - 41st ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2016
Y2 - 20 July 2016 through 22 July 2016
ER -