Numerical and geometric properties of a method for finding points on real solution components
Authors: 
Wenyuan Wu, Greg Reid, Yong FengAuthors Info & Claims
Pages 111 - 117
Abstract
We consider a critical point method developed in our earlier work for finding certain solution (witness) points on real solution components of real polynomial systems of equations. The method finds points that are critical points of the distance from a plane to the component with the requirement that certain regularity conditions are satisfied. In this paper we analyze the numerical stability of the method. We aim to find at least one well conditioned witness point on each connected component by using perturbation, path tracking and projection techniques. An optimal-direction strategy and an adaptive step size control strategy for path following on high dimensional components are given.
References
[1]
S. Basu, R. Pollack and M-F Roy, Algorithms in real algebraic geometry. 2nd edition. Algorithms and Computation in Math., 10. Springer-Verlag, 2006.
[2]
D. J. Bates, J. D. Hauenstein, A. J. Sommese, and C. W. Wampler, Numerically Solving Polynomial Systems with the Software Package Bertini. In preparation. To be published by SIAM, 2013.
[3]
Carlos Beltran, Anton Leykin. Robust Certified Numerical Homotopy Tracking. Foundations of Computational Mathematics April 2013, Volume 13, Issue 2, pp 253--295.
[4]
L. Blum, F. Cucker, M. Shub, and S. Samle, Complexity and Real Computation. Springer-Verlag 1998.
[5]
G. M. Besana, S. DiRocco, J. D. Hauenstein, A. J. Sommese, and C. W. Wampler. Cell decomposition of almost smooth real algebraic surfaces. Num. Algorithms. (published online Sept 28, 2012).
[6]
C. Chen, J. H. Davenport, J. P. May, M. M. Maza, B. Xia and R. Xiao. Triangular decomposition of semi-algebraic systems Journal of Symbolic Computation Vol 49-0, pp 3--26, 2013.
[7]
G. Collins, Quantifier elimination for real closed fields by cylindrical algebraic decomposition. Springer Lec. Notes Comp. Sci. v 33. 515--532, 1975.
[8]
J. H. Davenport and J. Heintz, Real quantifier elimination is doubly exponential, J. Symbolic Comp., 5: 29--35, 1988.
[9]
Jean-Pierre Dedieu, Estimations for the Separation Number of a Polynomial System. J. Symbolic Comp., 24: 683--693, 1997.
[10]
J. Hauenstein, Numerically computing real points on algebraic sets. Acta Appl. Math. (published online September 27, 2012).
[11]
H. Hong. Improvement in CAD-Based Quantifer Elimination. Ph.D. thesis, the Ohio State University, Columbus, Ohio, 1990.
[12]
J. B. Lasserre, M. Laurent and P. Rostalski. A prolongation-projection algorithm for computing the finite real variety of an ideal. Theoret. Comput. Sci., 410(27--29), 2685--2700, 2009.
[13]
Y. Lu, Finding all real solutions of polynomial systems, Ph.D Thesis, University of Notre Dame, 2006. Results of this thesis appear in: (with D. J. Bates, A. J. Sommese, and C. W. Wampler), Finding all real points of a complex curve, Contemporary Mathematics 448, 183--205, 2007.
[14]
Y. Ma and L. Zhi. Computing Real Solutions of Polynomial Systems via Low-rank Moment Matrix Completion Proc. 2012 Internat. Symp. Symbolic Algebraic Comput. 249--256, 2012.
[15]
F. Rouillier, M.-F. Roy, and M. Safey El Din. Finding at least one point in each connected component of a real algebraic set defined by a single equation. J. Complexity, 16 (4), 716--750, 2000.
[16]
A. Seidenberg, A new decision method for elementary algebra, Ann. of Math. 60, 365--374, 1954.
[17]
A. J. Sommese and C. W. Wampler. The Numerical solution of systems of polynomials arising in engineering and science. World Scientific Press, 2005.
[18]
A. Tarski, A decision method for elementary algebra and geometry, Fund. Math. 17, 210--39, 1931.
[19]
G. W. Stewart. Perturbation Theory for the Singular Value Decomposition. In SVD and signal processing, II: Algorithms, analysys and applications, pp 99--109, Elsevier, 1990.
[20]
Wenyuan Wu and Greg Reid. Finding points on real solution components and applications to differential polynomial systems. ISSAC 2013: 339--346.
[21]
Zhengfeng Yang, Lihong Zhi, and Yijun Zhu. Verfied error bounds for real solutions of positive-dimensional polynomial systems In ISSAC'2013 Proc. 2013 Internat. Symp. Symbolic Algebraic Comput. pp. 371--378.
Index Terms
- Numerical and geometric properties of a method for finding points on real solution components
Recommendations
Finding points on real solution components and applications to differential polynomial systems
ISSAC '13: Proceedings of the 38th International Symposium on Symbolic and Algebraic ComputationIn this paper we extend complex homotopy methods to finding witness points on the irreducible components of real varieties. In particular we construct such witness points as the isolated real solutions of a constrained optimization problem.
First a ...
An approximate method for numerical solution of fractional differential equations
Fractional calculus applications in signals and systemsThis paper presents a numerical solution scheme for a class of fractional differential equations (FDEs). In this approach, the FDEs are expressed in terms of Caputo type fractional derivative. Properties of the Caputo derivative allow one to reduce the ...
A method for the numerical solution of the Painlevé equations
A numerical method for solving the Cauchy problem for all the six Painlevé equations is proposed. The difficulty of solving these equations is that the unknown functions can have movable (that is, dependent on the initial data) singular points of the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2014
154 pages
ISBN:9781450329637
DOI:10.1145/2631948
- Editors:
- Stephen M. Watt,
- Jan Verschelde,
- Lihong Zhi,
- General Chair:
- Lihong Zhi,
- Program Chair:
- Stephen M. Watt
Copyright © 2014 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]
Sponsors
- 973 Program: National Basic Research Program of China
- KLMM: Key Laboratory of Mathematics Mechanization
- MapleSoft
- ORCCA: Ontario Research Centre for Computer Algebra
- NSFC: Natural Science Foundation of China
- Chinese Academy of Engineering: Chinese Academy of Engineering
- NAG: Numerical Algorithms Group
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 28 July 2014
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Chinese Academy of Sciences
- Chongqing Key Laboratory of Automated Reasoning and Cognition
- Ministry of Science and Technology of the People's Republic of China
- Natural Sciences and Engineering Research Council of Canada
Conference
SNC '14
Sponsor:
- 973 Program
- KLMM
- ORCCA
- NSFC
- Chinese Academy of Engineering
- NAG
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 44Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 11 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in