New bounds and an efficient algorithm for sparse difference resultants

DOI10.1016/J.JSC.2021.04.002MaRDI QIDQ2029018zbMATH OpenOpenAlexFDO

Authors Chunming Yuan, Zhi-Yong Zhang

Publication date 3 June 2021

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

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

zbMATH Keywords

complexitysparse resultantLaurent transformally essential systemsparse difference resultant

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Difference algebra (12H10) Solving polynomial systems; resultants (13P15) Numerical methods for difference and functional equations, recurrence relations (65Q99)

Abstract: The sparse difference resultant introduced in citep{gao-2015} is a basic concept in difference elimination theory. In this paper, we show that the sparse difference resultant of a generic Laurent transformally essential system can be computed via the sparse resultant of a simple algebraic system arising from the difference system. Moreover, new order bounds of sparse difference resultant are found. Then we propose an efficient algorithm to compute sparse difference resultant which is the quotient of two determinants whose elements are the coefficients of the polynomials in the algebraic system. The complexity of the algorithm is analyzed and experimental results show the efficiency of the algorithm.

Recommendations

• scientific article; zbMATH DE number 5302296
• scientific article; zbMATH DE number 503188
• scientific article; zbMATH DE number 1263319
• Efficient incremental algorithms for the sparse resultant and the mixed volume
• New order bounds in differential elimination algorithms
• Exploiting sparsity in difference-bound matrices
• On some computations on sparse polynomials
• A subdivision-based algorithm for the sparse resultant
• Sparse resultants and straight-line programs

Cites work

• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 575960 (Why is no real title available?)
• scientific article; zbMATH DE number 806917 (Why is no real title available?)
• scientific article; zbMATH DE number 3207354 (Why is no real title available?)
• A characteristic set method for ordinary difference polynomial systems
• A subdivision-based algorithm for the sparse resultant
• Coexistence of competing juvenile–adult structured populations
• Differential elimination with Dixon resultants
• Discrete May–Leonard Competition Models I
• Effective difference elimination and nullstellensatz
• Efficient incremental algorithms for the sparse resultant and the mixed volume
• Fast computation of GCDs
• How to generate as many Somos-like miracles as you wish^†
• Linear complete differential resultants and the implicitization of linear DPPEs
• Macaulay style formulas for sparse resultants
• On the Newton polytope of the resultant
• On von Neumann regular rings with an automorphism
• Sparse differential resultant for Laurent differential polynomials
• The Importance of Being Zero

Cited in

(4)

• Differential elimination by differential specialization of Sylvester style matrices
• Advances in elimination theory for algebraic differential and difference equations
• Sparse differential resultant for Laurent differential polynomials
• Sparse differential resultant

Describes a project that uses

Uses Software

• SparseResultants
• NesSomos

This page was built for publication: New bounds and an efficient algorithm for sparse difference resultants

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