research-article

Power series composition and change of basis

Authors:

Éric SchostAuthors Info & Claims

ISSAC '08: Proceedings of the twenty-first international symposium on Symbolic and algebraic computation

Pages 269 - 276

https://doi.org/10.1145/1390768.1390806

Published: 20 July 2008 Publication History

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

[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]

B. K. Alpert and V. Rokhlin. A fast algorithm for the evaluation of Legendre expansions. SIAM J. Sci. Statist. Comp., 12(1):158--179, 1991.

Digital Library

[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]

D. J. Bernstein. Composing power series over a finite ring in essentially linear time. J. Symb. Comp., 26(3):339--341, 1998.

Digital Library

[6]

D. Bini and V. Y. Pan. Polynomial and matrix computations. Vol. 1. Birkhauser Boston Inc., 1994.

Digital Library

[7]

A. Bostan, G. Lecerf, and E. Schost. Tellegen's principle into practice. In ISSAC'03, pages 37--44. ACM, 2003.

Digital Library

[8]

A. Bostan, B. Salvy, and E. Schost. Fast algorithms for orthogonal polynomials. In preparation.

[9]

A. Bostan and E. Schost. Polynomial evaluation and interpolation on special sets of points. J. Complexity, 21(4):420--446, 2005.

Digital Library

[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 and H. T. Kung. Fast algorithms for manipulating formal power series. J. ACM, 25(4):581--595, 1978.

Digital Library

[12]

P. Burgisser, M. Clausen, and A. Shokrollahi. Algebraic complexity theory, volume 315 of GMW. Springer-Verlag, 1997.

Digital Library

[13]

J. Canny, E. Kaltofen, and Y. Lakshman. Solving systems of non-linear polynomial equations faster. In ISSAC'89, pages 121--128. ACM, 1989.

Digital Library

[14]

D. G. Cantor and E. Kaltofen. On fast multiplication of polynomials over arbitrary algebras. Acta Inform., 28(7):693--701, 1991.

Digital Library

[15]

J. R. Driscoll, J. D. M. Healy, and D. N. Rockmore. Fast discrete polynomial transforms with applications to data analysis for distance transitive graphs. SIAM J. Comp., 26(4):1066--1099, 1997.

Digital Library

[16]

M. Frumkin. A fast algorithm for expansion over spherical harmonics. Appl. Algebra Engrg. Comm. Comp., 6(6):333--343, 1995.

[17]

J. g. Gathen and J. Gerhard. Modern computer algebra. Cambridge University Press, 1999.

Digital Library

[18]

J. Gerhard. Modular algorithms for polynomial basis conversion and greatest factorial factorization. In RWCA'00, pages 125--141, 2000.

[19]

G. Hanrot, M. Quercia, and P. Zimmermann. The Middle Product Algorithm, I. Appl. Algebra Engrg. Comm. Comp., 14(6):415--438, 2004.

Digital Library

[20]

G. Hanrot and P. Zimmermann. Newton iteration revisited. http://www.loria.fr/ zimmerma/papers, 2002.

[21]

G. Heinig. Fast and superfast algorithms for Hankel-like matrices related to orthogonal polynomials. In NAA'00, volume 1988 of LNCS, pages 361--380. Springer-Verlag, 2001.

[22]

J. g. Hoeven. Relax, but don't be too lazy. J. Symb. Comput., 34(6):479--542, 2002.

Digital Library

[23]

E. Kaltofen. Challenges of symbolic computation: my favorite open problems. J. Symb. Comp., 29(6):891--919, 2000.

Digital Library

[24]

E. Kaltofen and Y. Lakshman. Improved sparse multivariate polynomial interpolation algorithms. In ISSAC'88, volume 358 of LNCS, pages 467--474. Springer Verlag, 1989.

[25]

J. Keiner. Computing with expansions in Gegenbauer polynomials. Preprint AMR07/10, U. New South Wales, 2007.

[26]

G. Leibon, D. Rockmore, and G. Chirikjian. A fast Hermite transform with applications to protein structure determination. In SNC'07, pages 117--124, New York, NY, USA, 2007. ACM.

Digital Library

[27]

Y.-M. Li and X.-Y. Zhang. Basis conversion among Bezier, Tchebyshev and Legendre. Comput. Aided Geom. Design, 15(6):637--642, 1998.

Digital Library

[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]

D. Potts, G. Steidl, and M. Tasche. Fast algorithms for discrete polynomial transforms. Math. Comp., 67(224):1577--1590, 1998.

Digital Library

[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]

V. Shoup. A new polynomial factorization algorithm and its implementation. J. Symb. Comp., 20(4):363--397, 1995.

Digital Library

Cited By

Neiger VSalvy BSchost ÉVillard G(2024)Faster Modular CompositionJournal of the ACM10.1145/363834971:2(1-79)Online publication date: 10-Apr-2024
https://dl.acm.org/doi/10.1145/3638349
Herath Mudiyanselage NMoroz GPouget MMaza MZhi L(2022)Fast High-Resolution Drawing of Algebraic CurvesProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation10.1145/3476446.3535483(449-458)Online publication date: 4-Jul-2022
https://dl.acm.org/doi/10.1145/3476446.3535483
Johansson F(2014)A fast algorithm for reversion of power seriesMathematics of Computation10.1090/S0025-5718-2014-02857-384:291(475-484)Online publication date: 6-May-2014
https://doi.org/10.1090/S0025-5718-2014-02857-3
Show More Cited By

Index Terms

Power series composition and change of basis
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Algebraic algorithms

Recommendations

Evaluation of the derivative of a polynomial in Bernstein form

In geometric modelling and computer-aided design a polynomial is usually represented in Bernstein form. Forward error analysis for the computation of the derivative of a polynomial in Bernstein form is performed. The corresponding running error is also ...
Fourier series of orthogonal polynomials
MATH'08: Proceedings of the American Conference on Applied Mathematics

Explicit formulas for the Fourier coeffcients of the Legendre polynomials can be found in the Bateman Manuscript Project. However, similar formulas for more general classes of orthogonal polynomials do not appear to have been worked out. Here we derive ...
Wronskian type determinants of orthogonal polynomials, Selberg type formulas and constant term identities

Let (p"n)"n be a sequence of orthogonal polynomials with respect to the measure @m. Let T be a linear operator acting in the linear space of polynomials P and satisfying deg(T(p))=deg(p)-1, for all polynomial p. We then construct a sequence of ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSAC '08: Proceedings of the twenty-first international symposium on Symbolic and algebraic computation

July 2008

348 pages

ISBN:9781595939043

DOI:10.1145/1390768

General Chair:
J. Rafael Sendra
Universidad de Alcalá, Spain
,
Program Chair:
Laureano Gonzalez-Vega
Universidad de Cantabria, Spain

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISSAC '08

Sponsor:

ISSAC '08: International Symposium on Symbolic and Algebraic Computation

July 20 - 23, 2008

Linz/Hagenberg, Austria

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
242
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)2

Reflects downloads up to 30 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Neiger VSalvy BSchost ÉVillard G(2024)Faster Modular CompositionJournal of the ACM10.1145/363834971:2(1-79)Online publication date: 10-Apr-2024
https://dl.acm.org/doi/10.1145/3638349
Herath Mudiyanselage NMoroz GPouget MMaza MZhi L(2022)Fast High-Resolution Drawing of Algebraic CurvesProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation10.1145/3476446.3535483(449-458)Online publication date: 4-Jul-2022
https://dl.acm.org/doi/10.1145/3476446.3535483
Johansson F(2014)A fast algorithm for reversion of power seriesMathematics of Computation10.1090/S0025-5718-2014-02857-384:291(475-484)Online publication date: 6-May-2014
https://doi.org/10.1090/S0025-5718-2014-02857-3
Zima E(2013)Accelerating Indefinite Summation: Simple Classes of SummandsMathematics in Computer Science10.1007/s11786-013-0170-97:4(455-472)Online publication date: 29-Dec-2013
https://doi.org/10.1007/s11786-013-0170-9
Bostan ASalvy BChowdhury MSchost ÉLebreton Rvan der Hoeven Jvan Hoeij M(2012)Power series solutions of singular (q)-differential equationsProceedings of the 37th International Symposium on Symbolic and Algebraic Computation10.1145/2442829.2442848(107-114)Online publication date: 22-Jul-2012
https://dl.acm.org/doi/10.1145/2442829.2442848
Giorgi P(2012)On Polynomial Multiplication in Chebyshev BasisIEEE Transactions on Computers10.1109/TC.2011.11061:6(780-789)Online publication date: 1-Jun-2012
https://dl.acm.org/doi/10.1109/TC.2011.110
Bostan ASalvy BSchost É(2010)Fast conversion algorithms for orthogonal polynomialsLinear Algebra and its Applications10.1016/j.laa.2009.08.002432:1(249-258)Online publication date: Jan-2010
https://doi.org/10.1016/j.laa.2009.08.002

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents