Power series composition and change of basis

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Power series composition and change of basis

Full text

Pdf (310 KB)

Source

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

Linz/Hagenberg, Austria

SESSION: Contributed papers table of contents

Pages 269-276

Year of Publication: 2008

ISBN:978-1-59593-904-3

Authors

Alin Bostan	INRIA, Rocquencourt, France
Bruno Salvy	INRIA, Rocquencourt, France
Éric Schost	University of Western Ontario, London, 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): 4, Downloads (12 Months): 50, Citation Count: 0

Additional Information:

abstract references 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/1390768.1390806 What is a DOI?

ABSTRACT

Efficient algorithms are known for many operations on truncated power series (multiplication, powering, exponential, ...). Composition is a more complex task. We isolate a large class of power series for which composition can be performed efficiently. We deduce fast algorithms for converting polynomials between various bases, including Euler, Bernoulli, Fibonacci, and the orthogonal Laguerre, Hermite, Jacobi, Krawtchouk, Meixner and Meixner-Pollaczek.

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	A. V. Aho, K. Steiglitz, and J. D. Ullman. Evaluating polynomials at fixed sets of points. SIAM J. Comp., 4(4):533--539, 1975.
	2	Bradley K. Alpert , Vladimir Rokhlin, A fast algorithm for the evaluation of Legendre expansions, SIAM Journal on Scientific and Statistical Computing, v.12 n.1, p.158-179, Jan. 1991 [doi>10.1137/0912009]
	3	G. Andrews, R. Askey, and R. Roy. Special functions. Cambridge University Press, 1999.
	4	R. Barrio and J. Pena. Basis conversions among univariate polynomial representations. C. R. Math. Acad. Sci. Paris, 339(4):293--298, 2004.
	5	Daniel J. Bernstein, Composing power series over a finite ring in essentially linear time, Journal of Symbolic Computation, v.26 n.3, p.339-341, Sept. 1998 [doi>10.1006/jsco.1998.0216]
	6	Dario Bini , Victor Y. Pan, Polynomial and matrix computations (vol. 1): fundamental algorithms, Birkhauser Verlag, Basel, Switzerland, 1994
	7	A. Bostan , G. Lecerf , É. Schost, Tellegen's principle into practice, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.37-44, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860870]
	8	A. Bostan, B. Salvy, and E. Schost. Fast algorithms for orthogonal polynomials. In preparation.
	9	Alin Bostan , Éric Schost, Polynomial evaluation and interpolation on special sets of points, Journal of Complexity, v.21 n.4, p.420-446, August 2005 [doi>10.1016/j.jco.2004.09.009]
	10	R. P. Brent. Multiple-precision zero-finding methods and the complexity of elementary function evaluation. In Analytic Computational Complexity, pages 151--176. Acad. Press, 1975.
	11	R. P. Brent , H. T. Kung, Fast Algorithms for Manipulating Formal Power Series, Journal of the ACM (JACM), v.25 n.4, p.581-595, Oct. 1978 [doi>10.1145/322092.322099]
	12	P. Burgisser, M. Clausen, and A. Shokrollahi. Algebraic complexity theory, volume 315 of GMW. Springer-Verlag, 1997.
	13	J. F. Canny , E. Kaltofen , L. Yagati, Solving systems of nonlinear polynomial equations faster, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.121-128, July 17-19, 1989, Portland, Oregon, United States [doi>10.1145/74540.74556]
	14	David G. Cantor , Erich Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Informatica, v.28 n.7, p.693-701, Oct. 1991 [doi>10.1007/BF01178683]
	15	J. R. Driscoll , D. M. Healy, Jr. , D. N. Rockmore, Fast Discrete Polynomial Transforms with Applications to Data Analysis for Distance Transitive Graphs, SIAM Journal on Computing, v.26 n.4, p.1066-1099, Aug. 1997 [doi>10.1137/S0097539792240121]
	16	M. Frumkin. A fast algorithm for expansion over spherical harmonics. Appl. Algebra Engrg. Comm. Comp., 6(6):333--343, 1995.
	17	Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999
	18	J. Gerhard. Modular algorithms for polynomial basis conversion and greatest factorial factorization. In RWCA'00, pages 125--141, 2000.
	19	Guillaume Hanrot , Michel Quercia , Paul Zimmermann, The Middle Product Algorithm I, Applicable Algebra in Engineering, Communication and Computing, v.14 n.6, p.415-438, March 2004 [doi>10.1007/s00200-003-0144-2]
	20	G. Hanrot and P. Zimmermann. Newton iteration revisited. http://www.loria.fr/ zimmerma/papers, 2002.
	21	Georg Heinig, Fast and Superfast Algorithms for Hankel-Like Matrices Related to Orthogonal Polynominals, Revised Papers from the Second International Conference on Numerical Analysis and Its Applications, p.385-392, June 11-15, 2000
	22	Joris Van der Hoeven, Relax, but don't be too lazy, Journal of Symbolic Computation, v.34 n.6, p.479-542, December 2002 [doi>10.1006/jsco.2002.0562]
	23	Erich Kaltofen , Robert M. Corless , David J. Jeffrey, Challenges of symbolic computation: my favorite open problems, Journal of Symbolic Computation, v.29 n.6, p.891-919, June 2000 [doi>10.1006/jsco.2000.0370]
	24	Erich Kaltofen , Yagati N. Lakshman, Improved Sparse Multivariate Polynomial Interpolation Algorithms, Proceedings of the International Symposium ISSAC'88 on Symbolic and Algebraic Computation, p.467-474, July 04-08, 1988
	25	J. Keiner. Computing with expansions in Gegenbauer polynomials. Preprint AMR07/10, U. New South Wales, 2007.
	26	Greg Leibon , Daniel Rockmore , Gregory Chirikjian, A fast hermite transform with applications to protein structure determination, Proceedings of the 2007 international workshop on Symbolic-numeric computation, July 25-27, 2007, London, Ontario, Canada [doi>10.1145/1277500.1277519]
	27	Yong-Ming Li , Xiao-Ying Zhang, Basis conversion among Be´zier, Tchebyshev and Legendre, Computer Aided Geometric Design, v.15 n.6, p.637-642, June 1, 1998 [doi>10.1016/S0167-8396(98)00009-0]
	28	V. Y. Pan. New fast algorithms for polynomial interpolation and evaluation on the Chebyshev node set. Computers and Mathematics with Applications, 35(3):125--129, 1998.
	29	Daniel Potts , Gabriele Steidl , Manfred Tasche, Fast algorithms for discrete polynomial transforms, Mathematics of Computation, v.67 n.224, p.1577-1590, Oct. 1998 [doi>10.1090/S0025-5718-98-00975-2]
	30	S. Roman. The umbral calculus. Dover publications, 2005.
	31	A. Schonhage and V. Strassen. Schnelle Multiplikation gross er Zahlen. Computing, 7:281--292, 1971.
	32	Victor Shoup, A new polynomial factorization algorithm and its implementation, Journal of Symbolic Computation, v.20 n.4, p.363-397, October 1995 [doi>10.1006/jsco.1995.1055]