Article

Free access

Rational function decomposition

Author:

Richard ZippelAuthors Info & Claims

ISSAC '91: Proceedings of the 1991 international symposium on Symbolic and algebraic computation

Pages 1 - 6

https://doi.org/10.1145/120694.120695

Published: 01 June 1991 Publication History

PDF eReader

References

[1]

V. S. Alagar and M. Thanh. "Fast decomposition algorithms". In B. F. Caviness, editor, Proceedings of Eurocal '85. ~bl. {L volume 204 of Lecture Notes in Computer Science, pages 150-153, Berlin- Heidelberg-New York, 1985. Springer-Verlag.

Digital Library

Google Scholar

[2]

D. R. Barton and R. E. Zippel. "Polynomial decomposition". In Jenks {8}.

Digital Library

Google Scholar

[3]

~. "Polynomial decomposition algorithms". Journal of Symbolic Computation, 1(2):159-168, June 1985.

Digital Library

Google Scholar

[4]

M. Dickerson. The Functional Decomposition of Polynomials. PhD thesis, Cornell University, Ithaca, NY, August 1989.

Digital Library

Google Scholar

[5]

~. "The inverse of an automorphism in polynomial time". In 30th Symposium on Foundations of Compuler Science, pages 82-87. ACM, 1989.

Google Scholar

[6]

F. Dorey and G. Whaples. "Prime and composite polynomials". Journal of Algebra, 28:88101, 1974.

Crossref

Google Scholar

[7]

J. Guti6rrez, T. Recio, and C. Ruiz de Velasco. "Polynomial decomposition algorithm of almost quadratic complexity". In Proceedings of AAECC- 6, 1988. Springer-Verlag, 1989.

Google Scholar

[8]

R. Jenks, editor. Symbolic and Algebraic Compuration '76", New York, August 1976. ACM.

Google Scholar

[9]

E. Kaltofen. "Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorizations". SIAM Journal of Computing, 14:469-489, 1985.

Crossref

Google Scholar

[10]

D. E. Knuth. The Art of Computer Programming, volume II. Addison-Wesley, New York, NY, 1971.

Digital Library

Google Scholar

[11]

D. Kozen and S. Landau. "Polynomial decomposition algorithms". Journal of Symbolic Computation, 7:445456, 1989.

Digital Library

Google Scholar

[12]

H. T. Kung and J. F. Traub. "All algebraic functions can be computed fast". Journal of the ACM, 1978.

Digital Library

Google Scholar

[13]

S. Landau. "Factoring polynomials over algebraic number fields". SIAM Journal of Computing, 14( 1):184-195, 1985.

Google Scholar

[14]

S. Landau and G. L. Miller. "Solvability by radicals is in polynomial time". Journal of Computer and System Sciences, 30(2)'179-208, April 1985.

Crossref

Google Scholar

[15]

P. Lfiroth. "Beweis eines Satzes fiber rationale Curven". Mathematische Annalen, 9:163-165, 1876.

Google Scholar

[16]

R. J. McEliece and J. B. Shearer. "A property of Euclid's algorithm and an application to Pad6 approximation". SIAM Journal of Applied Mathematics, 34:611--615, 1978.

Crossref

Google Scholar

[17]

A. Schinze}. Selected Topics on Polynomials. llniversity of Michigan Press, Ann Arbor, MI, 1982.

Google Scholar

[18]

E. Steinitz. "Algebraische Theorie der KSrper". Journal fiir reine ~nd angewante Mathematik, 137:167-309, 1910.

Google Scholar

[19]

B. M. Trager. "Algebraic factoring and rational function integration". In Jenks {8}, pages 219-226.

Crossref

Google Scholar

[20]

B. L. van der Waerden. Modern Algebra. Fredrick Ungar, New York, NY, 1964.

Google Scholar

[21]

J. yon zur Gathen. "Functional decomposition of polynomials: the tame case". Journal of Symbolic CompuT~a~ion, ~)(~/):2~1-2~){}, March 1~0.

Digital Library

Google Scholar

[22]

--. "Functional decomposition of polynomials: the wild case". Journal of Symbolic Computation, 10(5):437-452, November 1990.

Digital Library

Google Scholar

[23]

J. von zur Gathen, D. Kozen, and S. Landau. "Functional decomposition of polynomials". In 28th Symposium on Foundations of Computer Science, pages 127-131. ACM, 1987.

Digital Library

Google Scholar

[24]

H. Weber. Lehrbuch der Algebra, volume II. Chelsea Publishing Co., New York, third edition, 1961.

Google Scholar

Cited By

View all

von zur Gathen JGiesbrecht MZiegler K(2020)Counting invariant subspaces and decompositions of additive polynomialsJournal of Symbolic Computation10.1016/j.jsc.2020.06.008Online publication date: Jun-2020
https://doi.org/10.1016/j.jsc.2020.06.008
Gómez-Torrecillas JLobillo FNavarro G(2019)Computing the bound of an Ore polynomial. Applications to factorizationJournal of Symbolic Computation10.1016/j.jsc.2018.04.01892(269-297)Online publication date: May-2019
https://doi.org/10.1016/j.jsc.2018.04.018
Shaik M(2018)Protecting Agents from Malicious Hosts using Trusted Platform Modules (TPM)2018 Second International Conference on Inventive Communication and Computational Technologies (ICICCT)10.1109/ICICCT.2018.8473278(559-564)Online publication date: Apr-2018
https://doi.org/10.1109/ICICCT.2018.8473278
Show More Cited By

Index Terms

Rational function decomposition

Recommendations

Partial fraction decomposition for rational Pythagorean hodograph curves
Abstract
All rational parametric curves with prescribed polynomial tangent direction form a vector space. Via tangent directions with rational norm, this includes the important case of rational Pythagorean hodograph curves. We study vector ...
Rational Biquartic Interpolating Surface Based on Function Values
Edutainment '08: Proceedings of the 3rd international conference on Technologies for E-Learning and Digital Entertainment

In this paper a bivariate rational biquartic interpolating spline based on function values with two parameters is constructed , and this spline is with biquartic numerator and bilinear denominator. The interpolating function has a simple and explicit ...
Rational Pythagorean-hodograph space curves

A method for constructing rational Pythagorean-hodograph (PH) curves in R^3 is proposed, based on prescribing a field of rational unit tangent vectors. This tangent field, together with its first derivative, defines the orientation of the curve ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ISSAC '91: Proceedings of the 1991 international symposium on Symbolic and algebraic computation

June 1991

468 pages

ISBN:0897914376

DOI:10.1145/120694

Editor:
Stephen M. Watt

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1991

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ISSAC 91

Sponsor:

German Comp Soc
GMD
SIGSAM

ISSAC 91: International Symposium on Symbolic Algebraic Computation

July 15 - 17, 1991

Bonn, West Germany

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

37
Total Citations
View Citations
795
Total Downloads

Downloads (Last 12 months)97
Downloads (Last 6 weeks)22

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

von zur Gathen JGiesbrecht MZiegler K(2020)Counting invariant subspaces and decompositions of additive polynomialsJournal of Symbolic Computation10.1016/j.jsc.2020.06.008Online publication date: Jun-2020
https://doi.org/10.1016/j.jsc.2020.06.008
Gómez-Torrecillas JLobillo FNavarro G(2019)Computing the bound of an Ore polynomial. Applications to factorizationJournal of Symbolic Computation10.1016/j.jsc.2018.04.01892(269-297)Online publication date: May-2019
https://doi.org/10.1016/j.jsc.2018.04.018
Shaik M(2018)Protecting Agents from Malicious Hosts using Trusted Platform Modules (TPM)2018 Second International Conference on Inventive Communication and Computational Technologies (ICICCT)10.1109/ICICCT.2018.8473278(559-564)Online publication date: Apr-2018
https://doi.org/10.1109/ICICCT.2018.8473278
Allem LCapaverde Jvan Hoeij MSzutkoski JYap CEl Din M(2017)Functional Decomposition Using Principal SubfieldsProceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3087604.3087608(421-428)Online publication date: 23-Jul-2017
https://dl.acm.org/doi/10.1145/3087604.3087608
Ziegler K(2016)Tame decompositions and collisionsJournal of Symbolic Computation10.1016/j.jsc.2015.11.01775:C(244-268)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1016/j.jsc.2015.11.017
Blankertz R(2014)A polynomial time algorithm for computing all minimal decompositions of a polynomialACM Communications in Computer Algebra10.1145/2644288.264429248:1/2(13-23)Online publication date: 10-Jul-2014
https://dl.acm.org/doi/10.1145/2644288.2644292
Stoutemyer D(2014)A computer algebra user interface manifestoACM Communications in Computer Algebra10.1145/2576802.257682747:3/4(130-165)Online publication date: 28-Jan-2014
https://dl.acm.org/doi/10.1145/2576802.2576827
Blankertz RVon Zur Gathen JZiegler K(2013)Compositions and collisions at degree p 2Journal of Symbolic Computation10.1016/j.jsc.2013.06.00159(113-145)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1016/j.jsc.2013.06.001
Von Zur Gathen J(2013)Lower bounds for decomposable univariate wild polynomialsJournal of Symbolic Computation10.1016/j.jsc.2011.01.00850(409-430)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1016/j.jsc.2011.01.008
Blankertz Rvon zur Gathen JZiegler Kvan der Hoeven Jvan Hoeij M(2012)Compositions and collisions at degree p2Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation10.1145/2442829.2442846(91-98)Online publication date: 22-Jul-2012
https://dl.acm.org/doi/10.1145/2442829.2442846
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Partial fraction decomposition for rational Pythagorean hodograph curves

Rational Biquartic Interpolating Surface Based on Function Values

Rational Pythagorean-hodograph space curves