Shiftless decomposition and polynomial-time rational summation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Shiftless decomposition and polynomial-time rational summation

Full text

Pdf (274 KB)

Source

International Conference on Symbolic and Algebraic Computation archive
Proceedings of the 2003 international symposium on Symbolic and algebraic computation table of contents

Philadelphia, PA, USA

Pages: 119 - 126

Year of Publication: 2003

ISBN:1-58113-641-2

Authors

J. Gerhard	Maplesoft, Waterloo, ON, Canada
M. Giesbrecht	University of Waterloo, Waterloo, ON, Canada
A. Storjohann	University of Waterloo, Waterloo, ON, Canada
E. V. Zima	University of Waterloo, Waterloo, ON, Canada

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 10, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/860854.860887 What is a DOI?

ABSTRACT

New algorithms are presented for computing the dispersion set of two polynomials over Q and for shiftless factorization. Together with a summability criterion by Abramov, these are applied to get a polynomial-time algorithm for indefinite rational summation, using a sparse representation of the output.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	S.A. Abramov. On the summation of rational functions. U.S.S.R. Comput. Maths. Math. Phys. 11, pp. 324--330, 1971. Transl. from Zh. vychisl. mat. mat. fiz. 11, pp. 1071--1075, 1971.
	2	S.A. Abramov. The rational component of the solution of a first-order linear recurrence relation with a rational right-hand side. U.S.S.R. Comput. Maths. Math. Phys. 15, pp. 216--221, 1975. Transl. from Zh. vychisl. mat. mat. fiz. 15, pp. 1035--1039, 1975.
	3	S. A. Abramov, Indefinite sums of rational functions, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.303-308, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220386]
	4	Eric Bach , James Driscoll , Jeffrey Shallit, Factor refinement, Journal of Algorithms, v.15 n.2, p.199-222, Sept. 1993 [doi>10.1006/jagm.1993.1038]
	5	Eric Bach , Jeffrey Shallit, Algorithmic number theory, MIT Press, Cambridge, MA, 1996
	6	Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999
	7	J. Gerhard. Modular algorithms in symbolic summation and symbolic integration. PhD thesis, Universität Paderborn, Germany, 2001.
	8	R.W. Gosper. Decision procedures for indefinite hypergeometric summation. Proc. Natl. Acad. Sci. U.S.A. 75(1), pp. 40--42, 1978.
	9	Mark van Hoeij, Rational solutions of linear difference equations, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.120-123, August 13-15, 1998, Rostock, Germany [doi>10.1145/281508.281592]
	10	M. van Hoeij. Factoring polynomials and the knapsack problem. J. Number Theory. 95, pp. 167-189, 2002.
	11	Petr Lisoněk , Peter Paule , Volker Strehl, Improvement of the degree setting in Gosper's algorithm, Journal of Symbolic Computation, v.16 n.3, p.243-258, Sept. 1993 [doi>10.1006/jsco.1993.1043]
	12	Yiu-Kwong Man, On computing closed forms for indefinite summations, Journal of Symbolic Computation, v.16 n.4, p.355-376, Oct. 1993 [doi>10.1006/jsco.1993.1053]
	13	Yiu-Kwong Man , Francis J. Wright, Fast polynomial dispersion computation and its application to indefinite summation, Proceedings of the international symposium on Symbolic and algebraic computation, p.175-180, July 20-22, 1994, Oxford, United Kingdom [doi>10.1145/190347.190413]
	14	J.B. Rosser and L. Schoenfeld. Approximate formulas for some functions of prime numbers. Ill. J. Math. 6, pp. 64--94, 1962.
	15	Peter Paule, Greatest factorial factorization and symbolic summation, Journal of Symbolic Computation, v.20 n.3, p.235-268, Sept. 1995 [doi>10.1006/jsco.1995.1049]
	16	R. Pirastu. On combinatorial identities: symbolic summation and umbral calculus. PhD thesis, Johannes Kepler Universität Linz, Austria, July 1996.