Fast Algorithms for Manipulating Formal Power Series

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast Algorithms for Manipulating Formal Power Series

Full text

Pdf (907 KB)

Source

Journal of the ACM (JACM) archive
Volume 25 , Issue 4 (October 1978) table of contents

Pages: 581 - 595

Year of Publication: 1978

ISSN:0004-5411

Authors

R. P. Brent	Computer Science Department, Stanford University, Stanford, CA and Australian National University, Canberra, Australia
H. T. Kung	Department of Computer Science, Carnegie-Mellon University, Pittsburgh, PA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 71, Citation Count: 26

Additional Information:

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/322092.322099 What is a DOI?

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	ABRAMOWITZ, M., AND STEGUN, I A Handbook ofMathematlcal Functzons. Nat. Bur Stand., Washmgton, DC., 1964, chap 15
	2	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	3	BACHMAN, G Introduction to P-Adlc Numbers and Valuation Theory Academic Press, New York, 1964
	4	BORODIN, A. On the number of anthmetlcs to compute certain funcuons--Clrca May 1973. In Complemty of Sequenoal and Parallel Numerical Algorithms, J F Traub, Ed, Academic Press, New York, 1973, pp 149-180.
	5	BORODIN, A, AND MUNRO, l The Computatlonal Complemty of Algebraic and Numeric Problems American Elsevier, New York, 1975
	6	BURKtLL, j C The Theory of Ordmary Differential Equations Oliver and Boyd, London, 1962, Sec. 9.
	7	BRENT, R P The complexity of multlple-precmlon anthmeuc. In Complexity of Computational Problem Solving, R S Anderssen & R P Brent, Eds, U of Queensland Press, Brisbane, Austraha, 1975, pp. 126-165
	8	BRENT, R P Multiple-precision zero-finding methods and the complexity of elementary function evaluation In Analytic Computational Complexity, j F Traub, Ed., Academic Press, New York, 1975, pp. 151-176
	9	BRENT, R P, AND KUNO, H T. O((n log n)3/2) algorithms for composmon and reversion of power series (extended abstrac0 In Analytic Computational Complemty, j F. Traub, Ed, Academic Press, New York, 1976, pp 217-225
	10	BRENT, R P, AND KUNO, H.T. Fast algorithms for composiuon and reversion of multivariate power series Proc. Conf. Theoret Comptr Sct, U. of Waterloo, Waterloo, Ont., Canada, Aug 1977, pp 149-158
	11	BROCKWELL, P J The transient behaviour of the queuemg system GI/M/1 J Austral Math Soc 3 (1963), 249-256
	12	CHRYSTAL, G. Textbook of Algebra, Part H Chelsea, New York, 1964
	13	FATEMAN, R J Polynomial multiplication, powers and asymptotic analysis Some comments SIAM J Comptng 3 (1974), 196-213
	14	FERGUSON, H R P, NIELSEN, D E, AND COOK, G A partition formula for the integer coefficients of the theta funcuon home Math Comput 29 (1975), 851-855
	15	FINCH, P D The single server queuemg system with non-recurrent input-process and Erlang service time J Austral Math Soc 3 (1963), 220-236
	16	FINCH, P D On partial sums of Lagrange's series with application to theory of queues J Austral Math Soc 3 (1963), 488-490
	17	FISCHER, M J, AND STOCKMEYER, L J Fast on-hne integer multiplication J Comptr Syst Sci 9 (1974). 317-331
	18	GILBERT, E N Enumeration of labelled graphs Canadian J Math 8 (1956), 405-411
	19	HEINDEL, L E Computation of powers of multivariate polynomials over the integers J Comptr Syst Scl 6 (1971), 1-8
	20	Peter Henrici, Automatic Computations with Power Series, Journal of the ACM (JACM), v.3 n.1, p.10-15, Jan. 1956 [doi>10.1145/320815.320819]
	21	HENPaCi, P Apphed and Computational Complex Analysis, Vol 1 Wdey-lnterscience, New York, 1974, chap 1.
	22	HOPCROFT, J E Complexity of computer computations Information Processing 74, North-Holland Pub Co, Amsterdam, 1974, pp 620--626.
	23	Ellis Horowitz, On the substitution of polynomial forms, Proceedings of the annual conference, p.153-158, August 27-29, 1973, Atlanta, Georgia, United States [doi>10.1145/800192.805697]
	24	HogowlTz, E The efficient calculation of powers of polynomials J Comptr Syst Scz 7 (1973), 469-480
	25	JACKSON, D M, AND REILLY, J W The enumeration of homeomorphically irreducible labelled graphs J Combinatorial Theory, Set B, 19 (1975), 272-286
	26	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	27	KUNG, H T On computing reciprocals of power series Numer Math 22 (1974), 341-348
	28	KUNG, H.T, AND TRAUB, J F Computational complexity of one-point and multipomt iteration. In Complexity of Real Computation, R M Karp, Ed, SIAM-AMS Proc 7, Amer Math Soc, Providence, R I, 1974, pp 149-160
	29	H. T. Kung , J. F. Traub, All Algebraic Functions Can Be Computed Fast, Journal of the ACM (JACM), v.25 n.2, p.245-260, April 1978 [doi>10.1145/322063.322068]
	30	LEVY, H, AND LESSMAN, F Finite Dtfference Equattons Pitman and Sons, London, 1959.
	31	NIvEN, 1 Formal power series Amer Math Monthly 76 (1969), 871-889.
	32	A. C. Norman, Computing with Formal Power Series, ACM Transactions on Mathematical Software (TOMS), v.1 n.4, p.346-356, Dec. 1975 [doi>10.1145/355656.355660]
	33	PATERSON, M S, AND STOCKMEYER, L J On the number of nonscalar multlphcatlons necessary to evaluate polynomials SIAM J Comptng 2 (1973), 60-66
	34	RAt.L, L B Computattonal Solution of Nonhnear Operator Equattons Wiley, New York, 1969
	35	RIORDAN, J An Introductton to Combinatorial Analysts Wiley, New York, 1958
	36	SIEVEKING, M An algorithm for division of power series Computing 10 (1972), 153-156
	37	STRASSEN, V Gaussian ehmmatlon is not optimal Numer Math 13 (1969), 354-356
	38	TRAUB, J F Iteratlve Methods for the Solutton of Equattons Prentice-Hall, Englewood Chffs, N J, 1964, chap 5

CITED BY 26

	Tetsuro Fujise , Hirokazu Murao, Parallel distinct degree factorization algorithm, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.18-25, July 24-26, 1996, Zurich, Switzerland
	Victor Shoup, Efficient computation of minimal polynomials in algebraic extensions of finite fields, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.53-58, July 28-31, 1999, Vancouver, British Columbia, Canada
	K. Kalorkoti, Predicting zero coefficients in formal power series computations, Journal of Symbolic Computation, v.33 n.3, p.307-320, March 2002
	Erich Kaltofen , Victor Shoup, Fast polynomial factorization over high algebraic extensions of finite fields, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.184-188, July 21-23, 1997, Kihei, Maui, Hawaii, United States
	Daniel Richardson , Bruno Salvy , John Shackell , Joris Van der Hoeven, Asymptotic expansions of exp-log functions, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.309-313, July 24-26, 1996, Zurich, Switzerland
	Joachim von zur Gathen , Victor Shoup, Computing Frobenius maps and factoring polynomials, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.97-105, May 04-06, 1992, Victoria, British Columbia, Canada
	Alexandre Sedoglavic, A probabilistic algorithm to test local algebraic observability in polynomial time, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.309-317, July 2001, London, Ontario, Canada
	Robert M. Corless , Mark W. Giesbrecht , David J. Jeffrey, Approximate polynomial decomposition, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.213-219, July 28-31, 1999, Vancouver, British Columbia, Canada
	Joris Van der Hoeven, Relax, but don't be too lazy, Journal of Symbolic Computation, v.34 n.6, p.479-542, December 2002
	Erich Kaltofen , Victor Shoup, Subquadratic-time factoring of polynomials over finite fields, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.398-406, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Victor Shoup, Fast construction of irreducible polynomials over finite fields, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.484-492, January 25-27, 1993, Austin, Texas, United States
	Joris van der Hoeven, Lazy multiplication of formal power series, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.17-20, July 21-23, 1997, Kihei, Maui, Hawaii, United States
	Alexandre Sedoglavic, A probabilistic algorithm to test local algebraic observability in polynomial time, Journal of Symbolic Computation, v.33 n.5, p.735-755, May 2002
	Joris van der Hoeven, A new zero-test for formal power series, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.117-122, July 07-10, 2002, Lille, France
	E. Hubert , N. Le Roux, Computing power series solutions of a nonlinear PDE system, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.148-155, August 03-06, 2003, Philadelphia, PA, USA
	Bruce R. Fabijonas, Laplace's method on a computer algebra system with an application to the real valued modified Bessel functions, Journal of Computational and Applied Mathematics, v.146 n.2, p.323-342, September 2002
	Ronald I. Greenberg, The Fat-Pyramid and Universal Parallel Computation Independent of Wire Delay, IEEE Transactions on Computers, v.43 n.12, p.1358-1364, December 1994
	Berk Sunar, An Efficient Basis Conversion Algorithm for Composite Fields with Given Representations, IEEE Transactions on Computers, v.54 n.8, p.992-997, August 2005
	Christopher Umans, Fast polynomial factorization and modular composition in small characteristic, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Debra A. Lelewer , Daniel S. Hirschberg, Data compression, ACM Computing Surveys (CSUR), v.19 n.3, p.261-296, Sept. 1987
	A. Bostan , F. Chyzak , F. Ollivier , B. Salvy , É. Schost , A. Sedoglavic, Fast computation of power series solutions of systems of differential equations, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1012-1021, January 07-09, 2007, New Orleans, Louisiana
	P. Mihailescu , F. Morain , É. Schost, Computing the eigenvalue in the schoof-elkies-atkin algorithm using abelian lifts, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada
	Alin Bostan , Bruno Salvy , Éric Schost, Power series composition and change of basis, Proceedings of the twenty-first international symposium on Symbolic and algebraic computation, July 20-23, 2008, Linz/Hagenberg, Austria
	Joris van der Hoeven, New algorithms for relaxed multiplication, Journal of Symbolic Computation, v.42 n.8, p.792-802, August, 2007
	Alin Bostan , Éric Schost, A simple and fast algorithm for computing exponentials of power series, Information Processing Letters, v.109 n.13, p.754-756, June, 2009
	Alin Bostan , Éric Schost, Fast algorithms for differential equations in positive characteristic, Proceedings of the 2009 international symposium on Symbolic and algebraic computation, July 28-31, 2009, Seoul, Republic of Korea