A Triangular Decomposition Algorithm for Differential Polynomial Systems with Elementary Computation Complexity

2015/03/15 by Wei Zhu, Xiao-Shan Gao, Zhu, Wei +1
Computer Science · #Coding theory and cryptography #Formal Methods in Verification #Polynomial and algebraic computation #acm:12H05 #acm:14Q99 #cs.SC #msc:12H05 #msc:14Q99

paper · pdf · doi:10.48550/arxiv.1503.04380

arxiv created 2015/03/15 · arxiv updated 2015/03/17

Abstract

In this paper, a new triangular decomposition algorithm is proposed for ordinary differential polynomial systems, which has triple exponential computational complexity. The key idea is to eliminate one algebraic variable from a set of polynomials in one step using the theory of multivariate resultant. This seems to be the first differential triangular decomposition algorithm with elementary computation complexity.

Related

• Stability of Triangular Decomposition and Comprehensive Triangular Decomposition
• Decomposition of Differential Polynomials
• Algorithms for Computing Triangular Decompositions of Polynomial Systems
• Algorithmic Thomas Decomposition of Algebraic and Differential Systems
• On the chordality of polynomial sets in triangular decomposition in top-down style