New order bounds in differential elimination algorithms. (March 2018)

• Record Type: Journal Article
• Authors: Gustavson, Richard; Ovchinnikov, Alexey; Pogudin, Gleb
• Is Part Of: Journal of symbolic computation. Volume 85(2018)
• Page Start: 128
• Page End: 147
• Publication Date: 2018-03
• Subjects: Polynomial differential equations -- Differential elimination algorithms -- Computational complexity; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2017.07.006
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: We present a new upper bound for the orders of derivatives in the Rosenfeld–Gröbner algorithm under weighted rankings. 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. In the case of one derivation, such a bound was given byGolubitsky et al. (2008) . The only known bound in the case of several derivations was given by the authors of the present paper in 2016. The bound was achieved by associating to the algorithm antichain sequences whose lengths can be bounded using the results ofLeón Sánchez and Ovchinnikov (2016) . In the present paper, the above result by the current authors is generalized and significantly improved.