An improved algorithm for the resolution of singularities

ABSTRACT

This paper contains several improvements of Villamayor's algorithm for the problem of resolution of the singularities of a hypersurface. The first improves the management of the charts which represent the blown up variety. The second improves the way how new resolution problems are created in the recursion, based on Hironaka's theory of idealistic exponents. The remaining two improve the way how discrete information is used, based on the adaption of Encinas and Villamayor of Abhyankar's theory of good points.

REFERENCES

• 1: Abhyankar, S. S. Resolution of singularities of arithmetical surfaces. In Arithmetical Algebraic Geometry. Harper and Row, 1965, pp. 111-152.
• 2: Abhyankar, S. S. Good points of a hypersurface. Adv. in Math. 68 (1988), 87-256.
• 3: Alonso, M. E., Luengo, I., and Raimondo, M. An algorithm on quasi-ordinary polynomials. Applicable Algebra in Engineering, Communication and Computing 6 (1988), 59-73.
• 4: Bayer, D., Stillman, M., and Stillman, M. Macaulay User Manual. Harvard University, 1993.
• 5: Thomas Becker , Volker Weispfenning , Heinz Kredel, Gro¨bner bases: a computational approach to commutative algebra, Springer-Verlag, London, 1993
• 6: Bierstone, E., and Milman, P. A simple constructive proof of canonical resolution of singularities. In Effective methods in algebraic geometry, T. Mora and C. Traverso, Eds. BirkhSuser, 1991, pp. 11-30.
• 7: Bierstone, E., and Milman, P. Canonical desingularization in characteristic zero by blowing up the maximum strata of a local invariant. Invent. math. 123 (1997), 207-302.
• 8: Bodn~r, G. Algorithmic Resolution of Singularities. PhD thesis, RISC-Linz, 2000. (Upcoming).
• 9: Gábor Bodnár , Josef Schicho, Automated resolution of singularities for hypersurfaces, Journal of Symbolic Computation, v.30 n.4, p.401-428, Oct. 2000 [doi>10.1006/jsco.1999.0414 ]
• 10: Bodn~r, G., and Schicho, J. A computer program for the resolution of singularities. In Resolution of Singularities (2000), H. Hauser, Ed., Birkh~iuser. to appear.
• 11: Bodn~r, G., and Schicho, J. Improvements of the algorithm for resolution of singularities. Tech. Rep. 00-03, RISC-Linz, Univ. Linz, A-4040 Linz, 2000.
• 12: Buchberger, B. An Algorithm for Finding a Basis for the Residue Class Ring of a Zero-Dimensional Polynomial Ideal. PhD thesis, UniversitSt Innsbruck, Institut ftir Mathematik, 1965. German.
• 13: Buchberger, B. GrSbner Bases: An Algorithmic Method in Polynomial Ideal Theory. In Recent Trends in Multidimensional Systems Theory, N. K. Bose, Ed. D. Riedel Publ. Comp., 1985, ch. 6.
• 14: Castellanos, A., Castellanos, J., Luengo, I., and Melle, A. Computing resolution invariants of a cyclic surface singularity with Maple. In EACA-98 (19 98), R. Sendra, Ed., Encuentro de Algebra Computacional y Aplicaciones.
• 15: Encinas, S., and Villamayor, O. Good points and constructive resolution of singularities. Acta Math. 131 (1998), 109-158.
• 16: Encinas, S., and Villamayor, O. Constructive desingularization and equivariance. In Resolution of Singularities (2000), H. Hauser, Ed., Birkhhuser. to appear.
• 17: Greuel, G.-M., Pfister, G., and Schoenemann, H. SING ULAR. http://www, singular, uni-kl, de/~ 1998.
• 18: Hauser, H. Seventeen obstacles for resolution of singularities. In Singularities, V. I. Arnold, G.-M. Greuel, and J. Steenbrink, Eds. Birkhhuser, 1998.
• 19: Hironaka, H. Resolution of singularities of an algebraic variety over a field of characteristic 0. Ann. Math. 79 (1964), 109-326.
• 20: Hironaka, H. Idealistic exponent of a singularity. In Algebraic Geometry. The John Hopkins centennial lectures. John Hopkins University Press, Baltimore, 1977, pp. 52-125.
• 21: Lipman, J. Desingularization of two-dimensional schemes. Ann. Math. 107 (1978), 151-207.
• 22: Josef Schicho, Rational parametrization of surfaces, Journal of Symbolic Computation, v.26 n.1, p.1-29, July 1998 [doi>10.1006/jsco.1997.0199 ]
• 23: Villamayor, O. Constructiveness of Hironaka's resolution. Ann. Scient. Ecole Norm. Sup. ~ 22 (1989), 1-32.
• 24: Villamayor, O. Introduction to the algorithm of resolution. In Algebraic geometry and singularities, La Rabida 1991 (1996), BirkhSuser, pp. 123-154.
• 25: Walker, R. J. Reduction of the singularities of an algebraic surface. Ann. Math. 36 (1935), 336-365.
• 26: Franz Winkler, A p-adic approach to the computation of Gro¨bner bases, Journal of Symbolic Computation, v.6 n.2-3, p.287-304, Oct./Dec. 1988 [doi>10.1016/S0747-7171(88)80049-X]
• 27: Zariski, O. The reduction of singularities of an algebraic surface. Ann. Math. JO (1939), 639-689.
• 28: Zariski, O. Reduction of the singularities of algebraic three-dimensional varieties. Ann. Math. J5 (1944), 472-542.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Performance, Theory, Verification