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

On exact and approximate interpolation of sparse rational functions

Published: 29 July 2007 Publication History

Abstract

The black box algorithm for separating the numerator from the denominator of a multivariate rational function can be combined with sparse multivariate polynomial interpolation algorithms to interpolate a sparse rational function. domization and early termination strategies are exploited to minimize the number of black box evaluations. In addition, rational number coefficients are recovered from modular images by rational vector recovery. The need for separate numerator and denominator size bounds is avoided via correction, and the modulus is minimized by use of lattice basis reduction, a process that can be applied to sparse rational function vector recovery itself. Finally, one can deploy sparse rational function interpolation algorithm in the hybrid symbolic-numeric setting when the black box for the function returns real and complex values with noise. We present and analyze five new algorithms for the above problems and demonstrate their effectiveness on a mark implementation.

References

[1]
Becuwe, S., Cuyt, A., and Verdonk, B. Multivariate rational interpolation of scattered data. In Large-Scale Scientific Computing (Heidelberg, Germany, 2004), I. Lirkov, S. Margenov, J. Wasniewski, and Y. Plamen, Eds., vol. 2907 of Lect. Notes Comput. Sci., Springer Verlag, pp. 204--213.
[2]
Ben-Or, M., and Tiwari, P. A deterministic algorithm for sparse multivariate polynomial interpolation. In Proc. Twentieth Annual ACM Symp. Theory Comput.(New York, N.Y., 1988), ACM Press, pp. 301--309.
[3]
DeMillo, R.A., and Lipton, R.J. probabilistic remark on algebraic program testing. Information Process. Letters 7,4 (1978), 193--195.
[4]
Dílaz, A., and Kaltofen, E. FoxBox system for manipulating symbolic objects in black box representation. In Proc. 1998 Internat. Symp. Symbolic Algebraic Comput. (ISSAC'98) (New York, N.Y., 1998), O. Gloor, Ed., ACM Press, pp.30--37.
[5]
Dumas, J.-G. Ed. ISSAC MMVI Proc. 2006 Internat. Symp. Symbolic Algebraic Comput. (New York, N.Y., 2006), ACM Press.
[6]
von zur Gathen, J., and Gerhard, J. Modern Computer Algebra. Cambridge University Press, Cambridge, New York, Melbourne, 1999. Second edition 2003.
[7]
Giesbrecht, M., Labahn, G., and Lee, W. Symbolic-numeric sparse interpolation of multivariate polynomials. In Dumas {5}, pp.116--123.
[8]
Grigoriev, D. Y., Karpinski, M., and Singer, M. F. Computational complexity of sparse rational function interpolation. SIAM J. Comput. 23 (1994), 1--11.
[9]
Kai, H. Rational function approximation and its ill-conditioned property. In Wang and Zhi {26}, pp.47--53. Preliminary version in {25}, pp. 62--64.
[10]
Kaltofen, E. Greatest common divisors of polynomials given by straight-line programs. J. ACM 35,1 (1988), 231--264.
[11]
Kaltofen, E. Asymptotically fast solution of Toeplitz-like singular linear systems. In Proc. 1994 Internat. Symp. Symbolic Algebraic Comput.(ISSAC'94) (New York, N.Y., 1994), ACM Press, pp. 297--304. Journal version in {12}.
[12]
Kaltofen, E. Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems. Math. Comput. 64,210 (1995), 777--806.
[13]
Kaltofen, E., and Lee, W. Early termination in sparse interpolation algorithms. J. Symbolic Comput. 36,3-4 (2003), 365--400. Special issue Internat. Symp. Symbolic Algebraic Comput.(ISSAC 2002). Guest editors: M. Giusti & L.M. Pardo.
[14]
Kaltofen, E., Lee, W.-s., and Lobo, A. A. Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm. In Proc. 2000 Internat. Symp. Symbolic Algebraic Comput.(ISSAC'00)(New York, N.Y., 2000), C. Traverso, Ed., ACM Press, pp. 192--201.
[15]
Kaltofen, E., and Rolletschek, H. Computing greatest common divisors and factorizations in quadratic number fields. Math. Comput. 53,188 (1989), 697--720.
[16]
Kaltofen, E., and Trager, B. Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators. J. Symbolic Comput. 9,3 (1990), 301--320.
[17]
Kaltofen, E., Yang, Z., and Zhi, L. Approximate greatest common divisors of several polynomials with linearly constrained coefficients and singular polynomials. In Dumas {5}, pp.169--176. Full version, 21 pages. Submitted, December 2006.
[18]
Kaltofen, E., Yang, Z., and Zhi, L. On probabilistic analysis of randomization in hybrid symbolic-numeric algorithms, 2007. Manuscript in preparation.
[19]
Kaltofen, E., Yang, Z., and Zhi, L. Structured low rank approximation of a Sylvester matrix. In Wang and Zhi {26}, pp.69--83. Preliminary version in {25 }, pp. 188--201.
[20]
Lagarias, J. C. The computational complexity of simultaneous diophantine approximation problems. SIAM J. Comp. 14 (1985), 196--209.
[21]
Monagan, M. Maximal quotient rational reconstruction: An almost optimal algorithm for rational reconstruction. In ISSAC 2004 Proc. 2004 Internat. Symp. Symbolic Algebraic Comput.(New York, N.Y., 2004), J. Gutierrez, Ed., ACM Press, pp.243--249.
[22]
Olesh, Z., and Storjohann, A. The vector rational function reconstruction problem, Sept. 2006. Manuscript, 14 pages.
[23]
Park, H., Zhang, L., and Rosen, J. B. Low rank approximation of a Hankel matrix by structured total least norm. BIT 39,4 (1999), 757--779.
[24]
Schwartz, J. T. Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27 (1980), 701--717.
[25]
Wang, D., and Zhi, L. Eds. Internat. Workshop on Symbolic-Numeric Comput. SNC 2005 Proc.(2005). Distributed at the Workshop in Xi'an, China, July 19-21.
[26]
Wang, D., and Zhi, L. Eds. Symbolic-Numeric Computation. Trends in Mathematics. Birkhäuser Verlag, Basel, Switzerland, 2007.
[27]
Wang, P. S., Guy, M. J. T., and Davenport, J. H. P-adic reconstruction of rational numbers. SIGSAM Bulletin 16,2 (May 1982), 2--3.
[28]
Zippel, R. Probabilistic algorithms for sparse polynomials. In Symbolic and Algebraic Computation (Heidelberg, Germany, 1979), vol. 72 of Lect. Notes Comput. Sci., Springer Verlag, pp.216--226. Proc. EUROSAM '79.
[29]
Zippel, R. Interpolating polynomials from their values. J. Symbolic Computation 9,3 (1990), 375--403.

Cited By

View all
  • (2024)Fast interpolation and multiplication of unbalanced polynomialsProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3669717(437-446)Online publication date: 16-Jul-2024
  • (2023)Using monodromy to recover symmetries of polynomial systemsProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597106(251-259)Online publication date: 24-Jul-2023
  • (2022)Sparse Polynomial Interpolation and Division in Soft-linear TimeProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation10.1145/3476446.3536173(459-468)Online publication date: 4-Jul-2022
  • Show More Cited By

Index Terms

  1. On exact and approximate interpolation of sparse rational functions

    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. early termination
    2. hybrid symbolic-numeric computation
    3. lattice basis reduction
    4. rational vector recovery
    5. sparse rational function 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)8
    • Downloads (Last 6 weeks)1
    Reflects downloads up to 14 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Fast interpolation and multiplication of unbalanced polynomialsProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3669717(437-446)Online publication date: 16-Jul-2024
    • (2023)Using monodromy to recover symmetries of polynomial systemsProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597106(251-259)Online publication date: 24-Jul-2023
    • (2022)Sparse Polynomial Interpolation and Division in Soft-linear TimeProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation10.1145/3476446.3536173(459-468)Online publication date: 4-Jul-2022
    • (2020)The Fermat-Torricelli Problem of Triangles on the Sphere with Euclidean Metric: A Symbolic Solution with MapleMaple in Mathematics Education and Research10.1007/978-3-030-41258-6_20(263-278)Online publication date: 28-Feb-2020
    • (2018)What Can (and Can't) we Do with Sparse Polynomials?Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3208976.3209027(25-30)Online publication date: 11-Jul-2018
    • (2018)On rational functions without Froissart doubletsNumerische Mathematik10.1007/s00211-017-0917-3138:3(615-633)Online publication date: 1-Mar-2018
    • (2017)Sparse Rational Function Interpolation with Finitely Many Values for the CoefficientsMathematical Aspects of Computer and Information Sciences10.1007/978-3-319-72453-9_16(227-242)Online publication date: 21-Dec-2017
    • (2014)Sparse multivariate function recovery with a high error rate in the evaluationsProceedings of the 39th International Symposium on Symbolic and Algebraic Computation10.1145/2608628.2608637(280-287)Online publication date: 23-Jul-2014
    • (2013)Sparse multivariate function recovery from values with noise and outlier errorsProceedings of the 38th International Symposium on Symbolic and Algebraic Computation10.1145/2465506.2465524(219-226)Online publication date: 26-Jun-2013
    • (2011)Supersparse black box rational function interpolationProceedings of the 36th international symposium on Symbolic and algebraic computation10.1145/1993886.1993916(177-186)Online publication date: 8-Jun-2011
    • Show More Cited By

    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