Computing the topology of real algebraic surfaces

ABSTRACT

We present constructive algorithms to determine the topological type of a non-singular real algebraic projective surface S in the real projective space; we address this question when there exists a line in RP³ not intersecting the surface. Starting from a polynomial equation with rational coefficients for S, our algorithm computes the homology of the various connected components of the surface. We reconstruct the homology in a finite number of steps, using as a basic tool Morse theory. The entire procedure has been implemented in Axiom.

REFERENCES

• 1: Stefan Arnborg , Huichun Feng, Algebraic decomposition of regular curves, Journal of Symbolic Computation, v.5 n.1-2, p.131-140, February/April 1988 [doi>10.1016/S0747-7171(88)80009-9]
• 2: Dennis S. Arnon , Scott McCallum, A polynomical-time algorithm for the topological type of a real algebraic curve, Journal of Symbolic Computation, v.5 n.1-2, p.213-236, February/April 1988 [doi>10.1016/S0747-7171(88)80013-0]
• 3: Philippe Aubry , Daniel Lazard , Marc Moreno Maza, On the theories of triangular sets, Journal of Symbolic Computation, v.28 n.1-2, p.105-124, July/Aug. 1999 [doi>10.1006/jsco.1999.0269]
• 4: AUZINGER, W., AND STETTER, H. J. An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations. In Numerical mathematics, Singapore 1988. Birkhäuser, Basel, 1988, pp. 11-30.
• 5: BASU, S., POLLACK, R., AND ROY, M.-F. Computing roadmaps of semi-algebraic sets on a variety. J. Amer. Math. Soc. 13, 1 (2000), 55-82.
• 6: John F. Canny, The complexity of robot motion planning, MIT Press, Cambridge, MA, 1988
• 7: Paola Cellini , Patrizia M. Gianni , Carlo Traverso, Algorithms for the Shape of Semialgebraic Sets. A New Approach, Proceedings of the 9th International Symposium, on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.1-18, October 07-11, 1991
• 8: COHEN, A. M., CUYPERS, H., AND STERK, H., Eds. Some tapas of computer algebra. Springer-Verlag, Berlin, 1999.
• 9: CUCKER, F., GONZÁLEZ-VEGA, L., AND ROSSELLO, F. On algorithms for real algebraic plane curves. In Effective methods in algebraic geometry (Castiglioncello, 1990). Birkhäuser Boston, Boston, MA, 1991, pp. 63-87.
• 10: Patrizia Gianni , Barry Trager , Gail Zacharias, Gro¨bner bases and primary decomposition of polynomial ideals, Journal of Symbolic Computation, v.6 n.2-3, p.149-167, Oct./Dec. 1988 [doi>10.1016/S0747-7171(88)80040-3]
• 11: GIANNI, P., AND TRAVERSO, C. Shape determination for real curves and surfaces. Ann. Univ. Ferrara Sez. VII (N.S.) 29 (1983), 87-109.
• 12: GONZALEZ-VEGA, L., ROUILLIER, F., ROY, M.-F., AND TRUJILLO, G. Symbolic recipes for real solutions. In Some tapas of computer algebra. Springer, Berlin, 1999, pp. 121-167.
• 13: GOURNAY, L., AND RISLER, J.-J. Construction of roadmaps in semi-algebraic sets. Appl. Algebra Engrg. Comm. Comput. 4, 4 (1993), 239-252.
• 14: HEINTZ, J., ROY, M.-F., AND SOLERNÓ, P. Single exponential path finding in semi-algebraic sets. II. The general case. In Algebraic geometry and its applications (West Lafayette, IN, 1990). Springer, New York, 1994, pp. 449-465.
• 15: HIRSCH, M. W. Differential topology. Springer-Verlag, New York, 1976. Graduate Texts in Mathematics, No. 33.
• 16: MASSEY, W. S. Algebraic topology: an introduction. Springer-Verlag, New York, 1977. Reprint of the 1967 edition, Graduate Texts in Mathematics, Vol. 56.
• 17: MASSEY, W. S. A basic course in algebraic topology. Springer-Verlag, New York, 1991.
• 18: MILNOR, J. Morse theory. Princeton University Press, Princeton, N.J., 1963.
• 19: ROY, M.-F. Computation of the topology of a real curve. Astérisque, 192 (1990), 17-33. Algorithmique, topologie et géométrie algébriques (Seville, 1987 and Toulouse, 1988).
• 20: VIRO, O. Y. Achievements in the topology of real algebraic varieties in the last six years. Uspekhi Mat. Nauk 41, 3(249) (1986), 45-67, 240.
• 21: WILSON, G. Hilbert's sixteenth problem. Topology 17, 1 (1978), 53-73.
• 22: WINKLER, F. Advances and problems in algebraic computation. In Contributions to general algebra, 12 (Vienna, 1999). Heyn, Klagenfurt, 2000, pp. 51-70.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.7 Ordinary Differential Equations
          Subjects: Differential-algebraic equations

General Terms:
Algorithms, Experimentation, Standardization