×

A regularization approach for estimating the type of a plane curve singularity. (English) Zbl 1298.14066

The paper addresses the problem of analyzing the local topology of each singularity of a plane complex algebraic curve defined by a squarefree polynomial. The local topology is computed by means of a symbolic-numeric algorithm that uses tools from knot theory, namely the Alexander polynomial and the delta-invariant of the singularity. As a novelty, the paper deals not only with the exact case, but also with the case when the coefficients of the polynomial defining the curve are known up to a finite tolerance. In this case, the computation of the local topology is an ill-posed problem, in the sense that tiny changes in the input may result in qualitative changes in the output. In the inexact case, the paper also provides a parameter choice rule that satisfies the convergence for noisy data property. This implies that as the noise in the data reduces to zero, the output provided by the algorithm converges to the exact answer. Furthermore, the algorithm is implemented in a new software package called CENOM3CK, written in the Axel free algebraic geometric modeler and in the Mathemagix free computer algebra system. A potential application of the algorithm is the computation of the genus of an implicit algebraic curve, whose coefficients are known up to a fixed tolerance.

MSC:

14Q05 Computational aspects of algebraic curves
14B05 Singularities in algebraic geometry
68W30 Symbolic computation and algebraic computation
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alexander, J. W., Topological invariant of knots and links, Transactions of the American Mathematical Society, 30, 275-306 (1928) · JFM 54.0603.03
[2] Bates, D. J.; Peterson, C.; Sommese, A. J.; Wampler, C. W., Numerical computation of the genus of an irreducible curve within an algebraic set, Journal of Pure and Applied Algebra, 215, 8, 1844-1851 (2011) · Zbl 1211.14062
[3] Blanchette, J.; Summerfield, M., \(C+ +\) GUI Programming with Qt 4 (2008), Prentice Hall US
[4] Bochnak, J.; Coste, M.; Roy, M.-F., Real Algebraic Geometry (1998), Ergebnisse der Math. Springer Verlag: Ergebnisse der Math. Springer Verlag Germany · Zbl 0633.14016
[5] Cimasoni, D., Studying the multivariable Alexander polynomial by means of Seifert surfaces, Sociedad Matemática Mexicana. Boletín. Tercera Serie. Soc. Mat. Mexican, 10, 3, 107-115 (2004) · Zbl 1097.57008
[6] Corless, R. M.; Kaltofen, E.; Watt, S. M., Hybrid methods, (Grabmeier, J.; Kaltofen, E.; Weispfenning, V., Computer Algebra Handbook (2003), Springer Verlag: Springer Verlag Heidelberg, Germany), 112-125
[7] de Berg, M.; Krefeld, M.; Overmars, M.; Schwarzkopf, O., Computational Geometry: Algorithms and Applications (2008), Springer: Springer Berlin
[8] Engl, H. W.; Hanke, M.; Neubauer, A., Regularization of Inverse Problems (1996), Kluwer Academic Publishers Group: Kluwer Academic Publishers Group Dordrecht, Netherlands · Zbl 0859.65054
[11] Hodorog, M.; Mourrain, B.; Schicho, J., An adapted version of the Bentley-Ottmann algorithm for invariants of plane curve singularities, (Murgante, B.; Gervasi, O.; Iglesias, A.; Taniar, D.; Apduhan, B. O., Proceedings of 11th International Conference on Computational Science and Its Applications, Session: Computational Geometry and Applications. Proceedings of 11th International Conference on Computational Science and Its Applications, Session: Computational Geometry and Applications, Lecture Notes in Computer Science, vol. 6784 (2011), Springer), 121-131
[12] Hodorog, M.; Schicho, J., A regularization method for computing approximate invariants of plane curves singularities, (SNC 2011, Proceedings of the 2011 International Workshop on Symbolic-Numeric Computation (2011), Association for Computing Machinery New York: Association for Computing Machinery New York New York, USA), 44-53 · Zbl 1346.14073
[13] Hodorog, M.; Schicho, J., A symbolic-numeric algorithm for genus computation, (Langer, U.; Paule, P., Numerical and Symbolic Scientific Computing: Progress and Prospects (2011), Springer Wien: Springer Wien Austria), 65-95 · Zbl 1250.65037
[15] Kaltofen, E.; Yang, Z.; Zhi, L., Structured low rank approximation of a Sylvester matrix, (Wang, D.; Zhi, L., Symbolic-Numeric Computation. Symbolic-Numeric Computation, Texts and Monographs in Symbolic Computation (2007), Birkhäuser Verlag: Birkhäuser Verlag Basel, Switzerland), 69-83 · Zbl 1117.65060
[16] Li, C.; Pion, S.; Yap, C., Recent progress in exact geometric computation, Practical Development of Exact Real Number Computation. Practical Development of Exact Real Number Computation, Journal of Logic and Algebraic Programming, 64, 1, 85-111 (2004), (special issue) · Zbl 1080.68106
[17] Liang, C.; Mourrain, B.; Pavone, J., Subdivision methods for the topology of 2d and 3d implicit curves, (Jüttler, B.; Piene, R., Geometric Modeling and Algebraic Geometry (2008), Springer: Springer Berlin Heidelberg), 199-214 · Zbl 1132.14335
[18] Livingston, C., Knot Theory (1993), Mathematical Association of America: Mathematical Association of America U.S.A · Zbl 0887.57008
[19] Marker, D., (Model Theory: An Introduction. Model Theory: An Introduction, Graduate Texts in Mathematics (2002), Springer: Springer New York, United States of America) · Zbl 1003.03034
[20] Milnor, J., Singular Points of Complex Hypersurfaces (1968), Princeton University Press and the University of Tokyo Press: Princeton University Press and the University of Tokyo Press New Jersey · Zbl 0184.48405
[21] Mourrain, B.; Pavone, J., Subdivision methods for solving polynomial equations, Symbolic Computation, 44, 292-306 (2009) · Zbl 1158.13010
[22] Munkres, J. R., Topology (1996), Prentice Hall: Prentice Hall Upper Saddle River, New Jersey, United States of America
[23] Neumann, W., Topology of hypersurface singularities, (Kähler, E., Mathematische Werke (Mathematical Works) (2003), Walter de Gruyter GmbH: Walter de Gruyter GmbH Berlin, Germany), 727-737 · Zbl 1365.14053
[24] Pérez-Díaz, S.; Sendra, J. R.; Rueda, S. L.; Sendra, J., Approximate parametrization of plane algebraic curves by linear systems of curves, Computer Aided Geometric Design, 27, 2, 212-231 (2010) · Zbl 1225.65024
[25] (Robbiano, L.; Abbott, J., Approximate Commutative Algebra. Approximate Commutative Algebra, Texts and Monographs in Symbolic Computation (2009), Springer Verlag: Springer Verlag Wien) · Zbl 1176.13001
[27] Sendra, J. R.; Winkler, F.; Pérez-Díaz, S., Rational Algebraic Curves. A Computer Algebra Approach (2008), Springer-Verlag: Springer-Verlag Berlin Heidelberg, Germany · Zbl 1129.14083
[28] Sommese, A. J.; Wampler, C. W., Numerical Solution of Polynomial Systems Arising in Engineering and Science (2005), World Scientific: World Scientific Singapore · Zbl 1091.65049
[29] Stetter, H. J., Numerical Polynomial Algebra (2004), SIAM: SIAM Philadelphia · Zbl 1058.65054
[30] Tikhonov, A. N.; Arsenin, V. A., Solution of Ill-posed Problems (1977), V. H. Winston & Sons: V. H. Winston & Sons Washington, D.C · Zbl 0499.65030
[31] Walker, R. J., Algebraic Curves (1978), Springer-Verlag: Springer-Verlag New York, United States of America
[32] Winkler, F., Polynomial Algorithms in Computer Algebra (1996), Springer-Verlag: Springer-Verlag Wien, New York · Zbl 0853.12003
[34] Wolfram, S., The Mathematica Book (2000), Wolfram Research Inc.
[35] Yamamoto, M., Classification of isolated algebraic singularities by their Alexander polynomials, Topology, 23, 277-287 (1984) · Zbl 0581.57002
[36] Zeng, Z., A method computing multiple roots of inexact polynomials, (Proceedings of ISSAC ’03 International Symposium of Symbolic and Algebraic Computation. Proceedings of ISSAC ’03 International Symposium of Symbolic and Algebraic Computation, Philadelphia, Pennsylvania, August 3-6, 2003 (2003), ACM Press: ACM Press New York), 266-272 · Zbl 1072.68704
[37] Zeng, Z., Regularization and matrix computation in numerical polynomial algebra, (Robbiano, L.; Abbott, J., Approximate Commutative Algebra. Approximate Commutative Algebra, Texts and Monographs in Symbolic Computation (2010), Springer Vienna: Springer Vienna Austria), 125-162 · Zbl 1191.65036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.