Efficient rational creative telescoping. (March 2022)

• Record Type: Journal Article
• Authors: Giesbrecht, Mark; Huang, Hui; Labahn, George; Zima, Eugene
• Is Part Of: Journal of symbolic computation. Volume 109(2022)
• Page Start: 57
• Page End: 87
• Publication Date: 2022-03
• Subjects: Rational function -- GGSZ reduction -- Left scalar division with remainder -- Telescoper; 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.07.005
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: We present a new algorithm to compute minimal telescopers for rational functions in two discrete variables. As with recent reduction-based approaches, our algorithm has the important feature that the computation of a telescoper is independent of its certificate. In addition, our algorithm uses a compact representation of the certificate, which allows it to be easily manipulated and analyzed without knowing the precise expanded form. This representation hides potential expression swell until the final (and optional) expansion, which can be accomplished in time polynomial in the size of the expanded certificate. A complexity analysis, along with a Maple implementation, indicates that our algorithm has better theoretical and practical performance than the reduction-based approach in the rational case.