New order bounds in differential elimination algorithms

DOI10.1016/J.JSC.2017.07.006MaRDI QIDQ2409012zbMATH OpenOpenAlexFDO

Authors Richard Gustavson, Alexey Ovchinnikov, Gleb Pogudin

Publication date 10 October 2017

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.00246

zbMATH Keywords

computational complexitydifferential elimination algorithmspolynomial differential equations

Mathematics Subject Classification ID

Abstract differential equations (12H20) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Abstract: We present a new upper bound for the orders of derivatives in the Rosenfeld-Groebner 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.

Recommendations

• Bounds for Orders of Derivatives in Differential Elimination Algorithms
• A bound for the Rosenfeld-Gröbner algorithm
• Algorithms yield upper bounds in differential algebra
• An Improvement of Rosenfeld-Gröbner Algorithm
• Computing representations for radicals of finitely generated differential ideals

Cites work

• A bound for orders in differential Nullstellensatz
• A bound for the Rosenfeld-Gröbner algorithm
• A new lower bound construction for commutative Thue systems with applications
• Bounds for Orders of Derivatives in Differential Elimination Algorithms
• Computing representations for radicals of finitely generated differential ideals
• Effective differential Nullstellensatz for ordinary DAE systems with constant coefficients
• Effective uniform bounding in partial differential fields
• Fields with several commuting derivations
• scientific article; zbMATH DE number 1254247 (Why is no real title available?)
• scientific article; zbMATH DE number 1979252 (Why is no real title available?)
• scientific article; zbMATH DE number 5052246 (Why is no real title available?)
• scientific article; zbMATH DE number 3415973 (Why is no real title available?)
• New effective differential Nullstellensatz
• On bounds for the effective differential Nullstellensatz
• On the construction of Gröbner basis of a polynomial ideal based on Riquier-Janet theory

Cited in

(11)

• Effective bounds for the consistency of differential equations
• New bounds and an efficient algorithm for sparse difference resultants
• Computer-assisted proofs of congruences for multipartitions and divisor function convolutions, based on methods of differential algebra
• On the algorithmic linearizability of nonlinear ordinary differential equations
• Bounds for Orders of Derivatives in Differential Elimination Algorithms
• Orders of derivatives in decomposition of radical differential ideals
• scientific article; zbMATH DE number 7258828 (Why is no real title available?)
• Algorithms yield upper bounds in differential algebra
• Support bound for differential elimination in polynomial dynamical systems
• Differential elimination and algebraic invariants of polynomial dynamical systems
• A bound for the Rosenfeld-Gröbner algorithm

This page was built for publication: New order bounds in differential elimination algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2409012)