×

Cell decomposition of almost smooth real algebraic surfaces. (English) Zbl 1271.65031

Summary: Let \(Z\) be a two dimensional irreducible complex component of the solution set of a system of polynomial equations with real coefficients in \(N\) complex variables. This work presents a new numerical algorithm, based on homotopy continuation methods, that begins with a numerical witness set for \(Z\) and produces a decomposition into 2-cells of any almost smooth real algebraic surface contained in \(Z\). Each 2-cell (a face) has a generic interior point and a boundary consisting of 1-cells (edges). Similarly, the 1-cells have a generic interior point and a vertex at each end. Each 1-cell and each 2-cell has an associated homotopy for moving the generic interior point to any other point in the interior of the cell, defining an invertible map from the parameter space of the homotopy to the cell. This work draws on previous results for the curve case. Once the cell decomposition is in hand, one can sample the 2-cells and 1-cells to any resolution, limited only by the computational resources available.

MSC:

65D17 Computer-aided design (modeling of curves and surfaces)
14Q10 Computational aspects of algebraic surfaces
65H20 Global methods, including homotopy approaches to the numerical solution of nonlinear equations

Software:

PHCpack; Bertini; HOM4PS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alberti, L., Mourrain, B.: Regularity criteria for the topology of algebraic curves and surfaces. In: Mathematics of Surfaces XII, LNCS, vol. 4647, pp. 1-28 (2007) · Zbl 1163.68342
[2] Alberti, L., Mourrain, B., Técourt, J.P.: Isotopic triangulation of a real algebraic surface. J. Symb. Comput. 44(9), 1291-1310 (2009) · Zbl 1173.14344 · doi:10.1016/j.jsc.2008.02.007
[3] Andreotti, A., Frankel, T.: The Lefschetz theorem on hyperplane sections. Ann. Math. 69(2), 713-717 (1959) · Zbl 0115.38405 · doi:10.2307/1970034
[4] Arnon, D.S., Collins, G.E., McCallum, S.: An adjacency algorithm for cylindrical algebraic decompositions of three-dimensional space. J. Symb. Comput. 5(1-2), 163-187 (1988) · Zbl 0648.68055 · doi:10.1016/S0747-7171(88)80011-7
[5] Basu, S., Pollack, R., Roy, M.F.: Algorithms in Real Algebraic Geometry, vol. 10. Algorithms and Computation in Mathematics, 2nd edn. Springer, Berlin (2006) · Zbl 1102.14041
[6] Bates, D.J., Hauenstein, J.D., Peterson, C., Sommese, A.J.: A numerical local dimension test for points on the solution set of a system of polynomial equations. SIAM J. Numer. Anal. 47, 3608-3623 (2009) · Zbl 1211.14066 · doi:10.1137/08073264X
[7] Bates, D.J., Hauenstein, J.D., Sommese, A.J., Wampler, C.W.: Bertini: Software for numerical algebraic geometry. Available at http://www.nd.edu/ sommese/bertini (2012). Accessed 17 Sept 2012 · Zbl 1002.65060
[8] Berberich, E., Emeliyanenko, P., Kobel, A., Sagraloff, M.: Exact symbolic-numeric computation of planar algebraic curves. Preprint. Available at arXiv:1201.1548 (2012) · Zbl 1277.68300
[9] Berberich, E., Kerber, M., Sagraloff, M.: An efficient algorithm for the stratification and triangulation of an algebraic surface. Comput. Geom. 43(3), 257-278 (2010) · Zbl 1203.65037 · doi:10.1016/j.comgeo.2009.01.009
[10] Boissonnat, J.D., Cohen-Steiner, D., Vegter, G.: Isotopic implicit surface meshing. Discrete Comput. Geom. 39(1), 138-157 (2008) · Zbl 1170.65012 · doi:10.1007/s00454-007-9011-4
[11] Cheng, J.S., Gao, X.S., Li, M.: Determining the topology of real algebraic surfaces. In: Mathematics of Surfaces XI, LNCS, vol. 3604, pp. 121-146 (2005) · Zbl 1141.68628
[12] Collins, G.E.: Quantifier elimination for real closed fields by cylindrical algebraic decomposition. Springer Lect. Notes Comput. Sci. 33, 515-532 (1975)
[13] Drexler, F.J.: Eine Methode zur Berechnung sämtlicher Lösungen von Polynomgleichungssystemen. Numer. Math. 29(1), 45-58 (1977) · Zbl 0352.65023 · doi:10.1007/BF01389312
[14] Fortuna, E.; Gianni, P.; Parenti, P.; Traverso, C., Computing the topology of real algebraic surfaces, 92-100 (2002), New York · Zbl 1072.68666 · doi:10.1145/780506.780518
[15] Garcia, C.B., Zangwill, W.I.: Finding all solutions to polynomial systems and other systems of equations. Math. Program. 16(2), 159-176, (1979) · Zbl 0409.65026 · doi:10.1007/BF01582106
[16] Goresky, M.; MacPherson, R., Stratified Morse theory (1988), Berlin · Zbl 0639.14012
[17] Hauenstein, J.D., Sommese, A.J., Wampler, C.W.: Regeneration homotopies for solving systems of polynomials. Math. Comput. 80, 345-377 (2011) · Zbl 1221.65121
[18] Hauenstein, J.D., Sommese, A.J., Wampler, C.W.: Regenerative cascade homotopies for solving polynomial systems. Applied Math. Comput. 218(4), 1240-1246 (2011) · Zbl 1231.65190 · doi:10.1016/j.amc.2011.06.004
[19] Hauenstein, J.D., Wampler, C.W.: Isosingular sets and deflation. http://www4.ncsu.edu/ jdhauens/preprints/hwIsosingular.pdf. Accessed 23 Sept 2012 · Zbl 1276.65029
[20] Huber, B., Sturmfels, B.: A polyhedral method for solving sparse polynomial systems. Math. Comput. 64(212), 1541-1555 (1995) · Zbl 0849.65030 · doi:10.1090/S0025-5718-1995-1297471-4
[21] Lee, T.L., Li, T.Y., Tsai, C.H.: HOM4PS-2.0: a software package for solving polynomial systems by the polyhedral homotopy continuation method. Computing 83, 109-133 (2008) · Zbl 1167.65366 · doi:10.1007/s00607-008-0015-6
[22] Li, TY, Numerical solution of polynomial systems by homotopy continuation methods, 209-304 (2003), Amsterdam · Zbl 1059.65046 · doi:10.1016/S1570-8659(02)11004-0
[23] Lorensen, W.E., Cline, H.E.: Marching cubes: a high resolution 3d surface construction algorithm. Comput. Graph. 21(4), 163-170 (1987) · doi:10.1145/37402.37422
[24] Lu, Y., Bates, D.J., Sommese, A.J., Wampler, C.W.: Finding all real points of a complex curve. In: Proceedings of the Midwest Algebra, Geometry and its Interactions Conference, Contemporary Mathematics, vol. 448, pp. 183-205. AMS (2007) · Zbl 1136.65050
[25] Milnor, J.; Spivak, M. (ed.); Wells, R. (ed.), Morse theory (1963), Princeton
[26] Morgan, A.P.: A transformation to avoid solutions at infinity for polynomial systems. Appl. Math. Comput. 18(1), 77-86 (1986) · Zbl 0597.65045 · doi:10.1016/0096-3003(86)90029-9
[27] Morgan, A.P., Sommese, A.J.: A homotopy for solving general polynomial systems that respects m-homogeneous structures. Appl. Math. Comput. 24, 101-113 (1987) · Zbl 0635.65057 · doi:10.1016/0096-3003(87)90063-4
[28] Morgan, A.P., Sommese, A.J., Wampler, C.W.: Computing singular solutions to polynomial systems. Adv. Appl. Math. 13(3), 305-327 (1992) · Zbl 0764.65030 · doi:10.1016/0196-8858(92)90014-N
[29] Morgan, A.P., Sommese, A.J., Wampler, C.W.: A power series method for computing singular solutions to nonlinear analytic systems. Numer. Math. 63(3), 391-409 (1992) · Zbl 0756.65079 · doi:10.1007/BF01385867
[30] Myszka, D., Murray, A., Wampler, C.W.: Mechanism branches, turning curves, and critical points. In: Proc. IDETC Mechanisms & Robotics Conf. (CDROM) ASME. Chicago (2012) · Zbl 1211.14066
[31] Seong, J.K., Elber, G., Kim, M.S.: Contouring 1- and 2-manifolds in arbitrary dimensions. In: SMI 05, pp. 218-227 (2005) · Zbl 1203.65037
[32] Sommese, A.J., Verschelde, J.: Numerical homotopies to compute generic points on positive dimensional algebraic sets. J. Complex. 16(3), 572-602 (2000) · Zbl 0982.65070 · doi:10.1006/jcom.2000.0554
[33] Sommese, A.J., Verschelde, J., Wampler, C.W.: Numerical decomposition of the solution sets of polynomial systems into irreducible components. SIAM J. Numer. Anal. 38, 2022-2046 (2001) · Zbl 1002.65060 · doi:10.1137/S0036142900372549
[34] Sommese, AJ; Verschelde, J.; Wampler, CW, Using monodromy to decompose solution sets of polynomial systems into irreducible components, No. 36, 297-315 (2001), Dordrecht · Zbl 0990.65051 · doi:10.1007/978-94-010-1011-5_16
[35] Sommese, A.J., Verschelde, J., Wampler, C.W.: Symmetric functions applied to decomposing solution sets of polynomial systems. SIAM J. Numer. Anal. 40, 2026-2046 (2001) · Zbl 1034.65034 · doi:10.1137/S0036142901397101
[36] Sommese, A.J., Verschelde, J., Wampler, C.W.: Homotopies for intersecting solution components of polynomial systems. SIAM J. Numer. Anal. 42, 1552-1571 (2004) · Zbl 1108.13308 · doi:10.1137/S0036142903430463
[37] Sommese, A.J., and Wampler, C.W.: The Numerical Solution of Systems of Polynomials Arising in Engineering and Science. World Scientific, Singapore (2005) · Zbl 1091.65049 · doi:10.1142/9789812567727
[38] Verschelde, J.: Algorithm 795: PHCpack: a general-purpose solver for polynomial systems by homotopy continuation. ACM Trans. Math. Softw. 25(2), 251-276 (1999) · Zbl 0961.65047 · doi:10.1145/317275.317286
[39] Wampler, C.W., Sommese, A.J.: Numerical algebraic geometry and algebraic kinematics. Acta Numer. 20, 469-567 (2011) · Zbl 1254.13031 · doi:10.1017/S0962492911000067
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.