New bounds and an efficient algorithm for sparse difference resultants. (November 2021)

• Record Type: Journal Article
• Authors: Yuan, Chun-Ming; Zhang, Zhi-Yong
• Is Part Of: Journal of symbolic computation. Volume 107(2021)
• Page Start: 279
• Page End: 298
• Publication Date: 2021-11
• Subjects: Sparse difference resultant -- Laurent transformally essential system -- Sparse resultant -- 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.2021.04.002
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: The sparse difference resultant introduced in Li et al. (2015b) 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.