skip to main content
10.1145/1277548.1277575acmconferencesArticle/Chapter ViewAbstractPublication PagesissacConference Proceedingsconference-collections
Article

A sparse modular GCD algorithm for polynomials over algebraic function fields

Published: 29 July 2007 Publication History

Abstract

We present a first sparse modular algorithm for computing a greatest common divisor of two polynomials f1, f2 ε L[x] where L is an algebraic function field in k0 parameters with r0 field extensions. Our algorithm extends the dense algorithm of Monagan and van Hoeij from 2004 to support multiple field extensions and to be efficient when the gcd is sparse. Our algorithm is an output sensitive Las Vegas algorithm.
We have implemented our algorithm in Maple. We provide timings demonstrating the efficiency of our algorithm compared to that of Monagan and van Hoeij and with a primitive fraction-free Euclidean algorithm for both dense and sparse gcd problems.

References

[1]
W.S. Brown, On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors. J. ACM, ACM Press, 18 (4), 478--504, 1971.
[2]
X. Dahan, M. Moreno Maza, E. Schost, W. Wu and Y. Xie, Lifting Techniques for Triangular Decompositions. Proceedings of ISSAC '05, ACM Press, pp. 108--115, 2005.
[3]
Mark van Hoeij and Michael Monagan, A modular GCD algorithm over number fields presented with multiple extensions. Proceedings of ISSAC '02, ACM Press, pp. 109--116, 2002.
[4]
Mark van Hoeij and Michael Monagan. Algorithms for Polynomial GCD Computation over Algebraic Function Fields, Proceedings of ISSAC '04, ACM Press, pp. 297--304, 2004.
[5]
Sara Khodadad and Michael Monagan. Fast Rational Function Reconstruction. Proceedings of ISSAC '06, ACM Press, pp. 184--190, 2006.
[6]
J. de Kleine, M. Monagan and A. Wittkopf, Algorithms for the non-monic case of the sparse modular GCD algorithm. Proceedings of ISSAC '05, ACM Press, pp. 124--131, 2005.
[7]
Marc Moreno Maza and Renaud Rioboo. Polynomial Gcd Computations over Towers of Algebraic Extensions. Proceedings of AAECC-11, Springer-Verlag, pp. 365--382, 1995.
[8]
Michael Monagan, Maximal Quotient Rational Reconstruction: An Almost Optimal Algorithm for Rational Reconstruction. Proceedings of ISSAC'04, ACM Press, 243--249, 2004.
[9]
P. S. Wang, M. J. T. Guy, J. H. Davenport. Early detection of true factors in Univariate Polynomial Factorization. Proceedings of EUROCAL'83, Springer-Verlag LNCS 162, pp. 225--235.
[10]
Richard Zippel, Probabilistic algorithms for sparse polynomials. Proceedings of EUROSAM'79, Springer-Verlag LNCS 72, pp. 216--226, 1979.

Cited By

View all
  • (2021)Sparse polynomial interpolation based on diversificationScience China Mathematics10.1007/s11425-020-1791-565:6(1147-1162)Online publication date: 10-Apr-2021
  • (2017)Computing Sparse GCD of Multivariate Polynomials via Polynomial InterpolationJournal of Systems Science and Complexity10.1007/s11424-017-6332-031:2(552-568)Online publication date: 8-Dec-2017
  • (2016)Polynomial GCDs by Syzygies2016 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC)10.1109/SYNASC.2016.021(53-59)Online publication date: Sep-2016
  • Show More Cited By

Index Terms

  1. A sparse modular GCD algorithm for polynomials over algebraic function fields

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    ISSAC '07: Proceedings of the 2007 international symposium on Symbolic and algebraic computation
    July 2007
    406 pages
    ISBN:9781595937438
    DOI:10.1145/1277548
    • General Chair:
    • Dongming Wang
    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: 29 July 2007

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. GCD algorithms
    2. algebraic function fields
    3. sparse interpolation

    Qualifiers

    • Article

    Conference

    ISSAC07
    Sponsor:
    ISSAC07: International Symposium on Symbolic and Algebraic Computation
    July 29 - August 1, 2007
    Ontario, Waterloo, Canada

    Acceptance Rates

    Overall Acceptance Rate 395 of 838 submissions, 47%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)2
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 14 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2021)Sparse polynomial interpolation based on diversificationScience China Mathematics10.1007/s11425-020-1791-565:6(1147-1162)Online publication date: 10-Apr-2021
    • (2017)Computing Sparse GCD of Multivariate Polynomials via Polynomial InterpolationJournal of Systems Science and Complexity10.1007/s11424-017-6332-031:2(552-568)Online publication date: 8-Dec-2017
    • (2016)Polynomial GCDs by Syzygies2016 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC)10.1109/SYNASC.2016.021(53-59)Online publication date: Sep-2016
    • (2011)Diversification improves interpolationProceedings of the 36th international symposium on Symbolic and algebraic computation10.1145/1993886.1993909(123-130)Online publication date: 8-Jun-2011
    • (2011)On sparse interpolation over finite fieldsACM Communications in Computer Algebra10.1145/1940475.194049344:3/4(116-117)Online publication date: 28-Jan-2011
    • (2010)Parallel sparse polynomial interpolation over finite fieldsProceedings of the 4th International Workshop on Parallel and Symbolic Computation10.1145/1837210.1837233(160-168)Online publication date: 21-Jul-2010
    • (2009)On factorization of multivariate polynomials over algebraic number and function fieldsProceedings of the 2009 international symposium on Symbolic and algebraic computation10.1145/1576702.1576731(199-206)Online publication date: 28-Jul-2009

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media