×
Duff, Timothy; Ruddy, Michael

Signatures of algebraic curves via numerical algebraic geometry. (English) Zbl 1507.14047

J. Symb. Comput. 115, 452-477 (2023).
The topic of this paper is to decide whether two plane algebraic curves are equal up to action of the group of rigid body motions or other subgroups of the projective group. Problems of this type can be studied via differential invariants. For example in the case of rigid body motions the curves’ arclength and curvature must match. It is, however, conceptually simpler, also for implementation, to merge suitable differential invariants into a “signature curve”. An alternative approach uses “joint signatures” which rely only on invariants of order zero and are considered to be more robust against noise. The thus obtained theory is not only capable of detecting symmetries between two curves, it can also report the size of the symmetry group. Details of definition and precise statements on the information value to be extracted are too technical to be reported here.
Besides improving theoretical underpinnings, this article introduces for the first time numerical algebraic geometry to signature based symmetry detection between curves. The curves are represented by witness sets or sampling oracles, respectively and membership tests are performed via homotopy continuation. This leads to a probabilistic algorithm that is both feasible for curves of degree \(d \le 6\) (the paper also reports successful runs for \(d \le 10\)) and robust against noise. The theory comes with an implementation in Macaulay2 that is publicly available. It is described in Section 4 together with particular examples and experimental results.
Reviewer: Hans-Peter Schröcker (Innsbruck)

Cited in 1 Document

MSC:

14H50 Plane and space curves
65H20 Global methods, including homotopy approaches to the numerical solution of nonlinear equations
14Q05 Computational aspects of algebraic curves
53A55 Differential invariants (local theory), geometric objects

Keywords:

differential invariants; invariant theory; numerical algebraic geometry; Euclidean group; computer algebra; homotopy continuation

Software:

MonodromySolver; Macaulay2; NumericalAlgebraicGeometry; Bertini; LearningAlgebraicVarieties
PDFBibTeX XMLCite
\textit{T. Duff} and \textit{M. Ruddy}, J. Symb. Comput. 115, 452--477 (2023; Zbl 1507.14047)
Full Text: DOI arXiv

References:

[1] Allgower, E. L.; Georg, K., Numerical Continuation Methods: An Introduction, vol. 13 (1990), Springer Science & Business Media · Zbl 0717.65030
[2] Améndola, C.; Lindberg, J.; Rodriguez, J. I., Solving parameterized polynomial systems with decomposable projections (2021), arXiv preprint
[3] Bates, D. J.; Hauenstein, J. D.; Sommese, A. J.; Wampler, C. W., Numerically Solving Polynomial Systems with Bertini (2013), SIAM · Zbl 1295.65057
[4] Berchenko (Kogan), I. A.; Olver, P. J., Symmetries of polynomials, J. Symb. Comput., 29, 485-514 (2000) · Zbl 0970.15023
[5] Breiding, P.; Kališnik, S.; Sturmfels, B.; Weinstein, M., Learning algebraic varieties from samples, Rev. Mat. Complut., 31, 3, 545-593 (2018) · Zbl 1481.13040
[6] Brysiewicz, T., Numerical software to compute Newton polytopes and tropical membership, (International Congress on Mathematical Software (2018), Springer), 80-88 · Zbl 1397.65341
[7] Burdis, J. M.; Kogan, I. A.; Hong, H., Object-image correspondence for algebraic curves under projections, SIGMA, 9, Article 023 pp. (2013) · Zbl 1278.14044
[8] Calabi, E.; Olver, P. J.; Shakiban, C.; Tannenbaum, A.; Haker, S., Differential and numerically invariant signatures curves applied to object recognition, Int. J. Comput. Vis., 26, 2, 107-135 (1998)
[9] Chen, J.; Kileel, J., Numerical implicitization, J. Softw. Algebra Geom., 9, 55-65 (2019) · Zbl 1430.14112
[10] Derksen, H.; Kemper, G., Computational Invariant Theory, Encyclopaedia of Mathematical Sciences, vol. 130 (2015), Springer: Springer Heidelberg · Zbl 1332.13001
[11] Duff, T.; Hill, C.; Jensen, A.; Lee, K.; Leykin, A.; Sommars, J., Solving polynomial systems via homotopy continuation and monodromy, IMA J. Numer. Anal., 39, 3, 1421-1446 (2019) · Zbl 1462.65055
[12] Duff, T.; Ruddy, M., Numerical equality tests for rational maps and signatures of curves, (Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation (July 2020), ACM) · Zbl 07300066
[13] Fels, M.; Olver, P. J., Moving coframes. II. Regularization and theoretical foundations, Acta Appl. Math., 55, 2, 127-208 (1999) · Zbl 0937.53013
[14] Grayson, D., Stillman, M., 1997. Macaulay2—a system for computation in algebraic geometry and commutative algebra.
[15] Grim, A.; Shakiban, C., Applications of signature curves to characterize melanomas and moles, (Applications of Computer Algebra. Applications of Computer Algebra, Springer Proc. Math. Stat., vol. 198 (2017), Springer: Springer Cham), 171-189 · Zbl 1383.92035
[16] Guggenheimer, H. W., Differential Geometry (1963), McGraw-Hill Book Co., Inc.: McGraw-Hill Book Co., Inc. New York-San Francisco-Toronto-London · Zbl 0116.13402
[17] Harris, J., Algebraic Geometry: A First Course, vol. 133 (2013), Springer Science & Business Media
[18] Hauenstein, J. D.; Leykin, A.; Rodriguez, J. I.; Sottile, F., A numerical toolkit for multiprojective varieties, Math. Comput., 90, 327, 413-440 (2022) · Zbl 1451.65065
[19] Hauenstein, J. D.; Regan, M. H., Evaluating and differentiating a polynomial using a pseudo-witness set, (International Congress on Mathematical Software (2020), Springer), 61-69 · Zbl 1503.65111
[20] Hauenstein, J. D.; Rodriguez, J. I., Multiprojective witness sets and a trace test, Adv. Geom., 20, 3, 297-318 (2020) · Zbl 1448.65054
[21] Hauenstein, J. D.; Sommese, A. J., Witness sets of projections, Appl. Math. Comput., 217, 7, 3349-3354 (2010) · Zbl 1203.14072
[22] Hauenstein, J. D.; Sommese, A. J., Membership tests for images of algebraic sets by linear projections, Appl. Math. Comput., 219, 12, 6809-6818 (2013) · Zbl 1285.14066
[23] Hauenstein, J. D.; Sottile, F., Newton polytopes and witness sets, Math. Comput. Sci., 8, 2, 235-251 (2014) · Zbl 1304.14077
[24] Hoff, D. J.; Olver, P. J., Extensions of invariant signatures for object recognition, J. Math. Imaging Vis., 45, 2, 176-185 (2013) · Zbl 1276.68137
[25] Hoff, D. J.; Olver, P. J., Automatic solution of jigsaw puzzles, J. Math. Imaging Vis., 49, 1, 234-250 (2014) · Zbl 1361.68291
[26] Hubert, E.; Kogan, I. A., Smooth and algebraic invariants of a group action: local and global construction, Found. Comput. Math. J., 7, 4, 345-383 (2007)
[27] Kogan, I. A.; Moreno Maza, M., Computation of canonical forms for ternary cubics, (Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation (2002), ACM: ACM New York), 151-160 · Zbl 1072.68629
[28] Kogan, I. A.; Ruddy, M.; Vinzant, C., Differential signatures of algebraic curves, SIAM J. Appl. Algebra Geom., 4, 1, 185-226 (2020) · Zbl 1445.14051
[29] Leykin, A., Numerical algebraic geometry, J. Softw. Algebra Geom., 3, 1, 5-10 (2011) · Zbl 1311.14057
[30] Leykin, A., Homotopy continuation in Macaulay2, (International Congress on Mathematical Software (2018), Springer), 328-334 · Zbl 1395.13028
[31] Leykin, A.; Rodriguez, J. I.; Sottile, F., Trace test, Arnold Math. J., 4, 1, 113-125 (2018) · Zbl 1408.14192
[32] Monagan, M.; Pearce, R., Rational simplification modulo a polynomial ideal, (ISSAC 2006 (2006), ACM: ACM New York), 239-245 · Zbl 1356.13037
[33] Morgan, A., Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems, vol. 57 (2009), SIAM · Zbl 1170.65316
[34] Morgan, A. P.; Sommese, A. J., Coefficient-parameter polynomial continuation, Appl. Math. Comput., 29, 2, 123-160 (1989) · Zbl 0664.65049
[35] (Mundy, J. L.; Zisserman, A.; Forsyth, D., Applications of Invariance in Computer Vision (1994), Springer: Springer Berlin, Heidelberg) · Zbl 0825.00107
[36] Olver, P. J., Equivalence, Invariants and Symmetry (1995), Cambridge University Press · Zbl 0837.58001
[37] Olver, P. J., Classical Invariant Theory, London Mathematical Society Student Texts, vol. 44 (1999), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0971.13004
[38] Olver, P. J., Joint invariant signatures, Found. Comput. Math., 1, 1, 3-67 (2001) · Zbl 1001.53004
[39] Ruddy, M., The Equivalence Problem and Signatures of Algebraic Curves (2019), North Carolina State University, PhD thesis
[40] Shafarevich, I., Basic Algebraic Geometry, vol. 2 (1994), Springer · Zbl 0797.14001
[41] Sommese, A. J.; Verschelde, J.; Wampler, C. W., Introduction to numerical algebraic geometry, (Solving Polynomial Equations (2005), Springer), 301-337 · Zbl 1152.14313
[42] Sturmfels, B., Algorithms in Invariant Theory (2008), Springer: Springer Vienna · Zbl 1154.13003
[43] Wampler, I. C.W., The Numerical Solution of Systems of Polynomials Arising in Engineering and Science (2005), World Scientific · Zbl 1091.65049
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.