More Web Proxy on the site http://driver.im/

research-article

Public Access

Effective Certification of Approximate Solutions to Systems of Equations Involving Analytic Functions

Authors:

Anton LeykinAuthors Info & Claims

ISSAC '19: Proceedings of the 2019 International Symposium on Symbolic and Algebraic Computation

Pages 267 - 274

https://doi.org/10.1145/3326229.3326235

Published: 08 July 2019 Publication History

Abstract

We develop algorithms for certifying an approximation to a nonsingular solution of a square system of equations built from univariate analytic functions. These algorithms are based on the existence of oracles for evaluating basic data about the input analytic functions. One approach for certification is based on α-theory while the other is based on the Krawczyk generalization of Newton's iteration. We show that the necessary oracles exist for \Dfinite\ functions and compare the two algorithmic approaches for this case using our software implementation in \sage.

References

[1]

Tulay Ayyildiz Akoglu, Jonathan D Hauenstein, and Agnes Szanto. 2018. Certifying solutions to overdetermined and singular polynomial systems over Q. J. Symbolic Comput, Vol. 84 (2018), 147--171.

[2]

Ruben Becker, Michael Sagraloff, Vikram Sharma, Juan Xu, and Chee Yap. 2016. Complexity Analysis of Root Clustering for a Complex Polynomial. In Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation (ISSAC '16). ACM, New York, NY, USA, 71--78.

Digital Library

[3]

A. Benoit, M. Joldecs, and M. Mezzarobba. 2017. Rigorous uniform approximation of D-finite functions using Chebyshev expansions. Math. Comp., Vol. 86, 305 (2017), 1303--1341.

[4]

L. Blum, F. Cucker, M. Shub, and S. Smale. 2012. Complexity and real computation .Springer Science & Business Media.

[5]

S. Bozóki, T. L. Lee, and L. Rónyai. 2015. Seven mutually touching infinite cylinders. Comput. Geom., Vol. 48, 2 (2015), 87--93.

Digital Library

[6]

D. V. Chudnovsky and G. V. Chudnovsky. 1990. Computer algebra in the service of mathematical physics and number theory. Computers in mathematics, Vol. 125 (1990), 109.

[7]

A. Gabrielov and N. Vorobjov. 2004. Complexity of computations with Pfaffian and Noetherian functions. Normal forms, bifurcations and finiteness problems in differential equations (2004), 211--250.

[8]

J. D. Hauenstein and V. Levandovskyy. 2017. Certifying solutions to square systems of polynomial-exponential equations. J. Symbolic Comput., Vol. 79 (2017), 575--593.

Digital Library

[9]

J. D. Hauenstein and F. Sottile. 2011. alphaCertified: Software for certifying numerical solutions to polynomial equations. Available at math.tamu.edu/ sottile/research/stories/alphaCertified (2011).

[10]

J. D. Hauenstein and F. Sottile. 2012. Algorithm 921: alphaCertified: certifying solutions to polynomial systems. ACM Trans. Math. Software, Vol. 38, 4 (2012), 28.

Digital Library

[11]

T. Hibi. 2014. Gröbner bases: Statistics and software systems .Springer Science & Business Media.

[12]

Wolfram Research, Inc. 2018. Mathematica, Version 11.3. Champaign, IL.

[13]

A. Khovanskii. 1991. Fewnomials. Vol. 88. American Mathematical Soc.

[14]

R. Krawczyk. 1969. Newton-algorithmen zur bestimmung von nullstellen mit fehlerschranken. Computing, Vol. 4, 3 (1969), 187--201.

[15]

S. Lang. 1983. Real analysis second ed.). Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA. xv

[16]

533 pages.

[17]

Kisun Lee, Nan Li, and Lihong Zhi. 2019. On isolation of singular zeros of multivariate analytic systems. arXiv preprint arXiv:1904.07937 (2019).

[18]

Nan Li and Lihong Zhi. 2014. Verified error bounds for isolated singular solutions of polynomial systems. SIAM J. Numer. Anal., Vol. 52, 4 (2014), 1623--1640.

Digital Library

[19]

J. Liouville. 1840. Mémoire sur les transcendantes élliptiques de première et de seconde espèce, considérées comme fonctions de leur module . 441--464 pages.

[20]

Angelos Mantzaflaris and Bernard Mourrain. 2011. Deflation and certified isolation of singular zeros of polynomial systems. In Proceedings of the 36th international symposium on Symbolic and algebraic computation. ACM, 249--256.

Digital Library

[21]

Maplesoft. 2018. Maple (2018). a division of Waterloo Maple Inc., Waterloo, Ontario (2018).

[22]

M. Mezzarobba. 2010. NumGfun: a package for numerical and analytic computation with D-finite functions. In Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation. ACM, 139--145.

Digital Library

[23]

M. Mezzarobba. 2016. Rigorous Multiple-Precision Evaluation of D-Finite Functions in SageMath . Technical Report 1607.01967. arXiv.

[24]

M. Mezzarobba and B. Salvy. 2010. Effective bounds for P-recursive sequences. J. Symbolic Comput., Vol. 45, 10 (2010), 1075--1096.

Digital Library

[25]

M. Mezzino and M. Pinsky. 1998. Leibniz's Formula, Cauchy Majorants, and Linear Differential Equations. Math. Mag., Vol. 71, 5 (1998), 360--368.

[26]

R. E. Moore, R. B. Kearfott, and M. J. Cloud. 2009. Introduction to interval analysis . Vol. 110. Siam.

Digital Library

[27]

R. E. Moore and J. B. Kioustelidis. 1980. A Simple Test for Accuracy of Approximate Solutions to Nonlinear (or Linear) Systems. SIAM J. Numer. Anal., Vol. 17, 4 (1980), 521--529.

Digital Library

[28]

H. Ratschek and J. Rokne. 1984. Computer Methods for the Range of Functions .Ellis Horwood Limited.

[29]

M. Shub and S. Smale. 2000. Complexity of Bezout's theorem. I: geometric aspects. In The Collected Papers of Stephen Smale: Volume 3. World Scientific, 1359--1401.

[30]

S. Smale. 1986. Newton's method estimates from data at one point. The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics (1986).

[31]

The Sage Developers. 2018. SageMath, the Sage Mathematics Software System (Version 8.3) . http://www.sagemath.org.

[32]

J. van der Hoeven. 1999. Fast evaluation of holonomic functions. Theoret. Comput. Sci., Vol. 210, 1 (1999), 199--215.

Digital Library

[33]

J. van der Hoeven. 2003. Majorants for formal power series . Technical Report 2003--15. Université Paris-Sud, Orsay, France.

Cited By

Duff TLee K(2024)Certified homotopy tracking using the Krawczyk methodProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3669699(274-282)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3666000.3669699
Lee K(2024)Effective Alpha Theory Certification Using Interval Arithmetic: Alpha Theory over RegionsMathematical Software – ICMS 202410.1007/978-3-031-64529-7_29(275-284)Online publication date: 17-Jul-2024
https://doi.org/10.1007/978-3-031-64529-7_29
Breiding PRose KTimme S(2023)Certifying Zeros of Polynomial Systems Using Interval ArithmeticACM Transactions on Mathematical Software10.1145/358027749:1(1-14)Online publication date: 21-Mar-2023
https://dl.acm.org/doi/10.1145/3580277
Show More Cited By

Recommendations

Method for Localizing the Zeros of Analytic Functions Based on the Krawczyk Operator

The problem of localizing the zeros of analytic functions using the Krawczyk operator is considered. Formulas are obtained for computing the image of the Krawczyk operator for analytic functions. Based on this, a new algorithm for localizing the zeros ...
Algorithmic Arithmetics with DD-Finite Functions
ISSAC '18: Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation

Many special functions as well as generating functions of combinatorial sequences that arise in applications are D-finite, i.e., they satisfy a linear differential equation with polynomial coefficients. These functions have been studied for centuries ...
CCNP BCMSN Exam Certification Guide (3rd Edition) (Exam Certification Guide)

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ISSAC '19: Proceedings of the 2019 International Symposium on Symbolic and Algebraic Computation

July 2019

418 pages

ISBN:9781450360845

DOI:10.1145/3326229

General Chairs:
James Davenport
University of Bath, UK
,
Dongming Wang
Beihang University, China; Guangxi University for Nationalities, China; Centre National de la Recherche Scientifique, France
,
Program Chair:
Manuel Kauers
Johannes Kepler University, Austria
,
Publications Chair:
Russell Bradford
University of Bath, UK

Copyright © 2019 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]

In-Cooperation

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

ISSAC '19

ISSAC '19: International Symposium on Symbolic and Algebraic Computation

July 15 - 18, 2019

Beijing, China

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
308
Total Downloads

Downloads (Last 12 months)93
Downloads (Last 6 weeks)14

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Duff TLee K(2024)Certified homotopy tracking using the Krawczyk methodProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3669699(274-282)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3666000.3669699
Lee K(2024)Effective Alpha Theory Certification Using Interval Arithmetic: Alpha Theory over RegionsMathematical Software – ICMS 202410.1007/978-3-031-64529-7_29(275-284)Online publication date: 17-Jul-2024
https://doi.org/10.1007/978-3-031-64529-7_29
Breiding PRose KTimme S(2023)Certifying Zeros of Polynomial Systems Using Interval ArithmeticACM Transactions on Mathematical Software10.1145/358027749:1(1-14)Online publication date: 21-Mar-2023
https://dl.acm.org/doi/10.1145/3580277
Lee K(2019)Certifying approximate solutions to polynomial systems on Macaulay2ACM Communications in Computer Algebra10.1145/3371991.337199553:2(45-48)Online publication date: 8-Nov-2019
https://dl.acm.org/doi/10.1145/3371991.3371995

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents