Go up to TopGo forward to About the Software Maple version, Singular version

# Introduction to the Problem

The problem of resolution of singularities shortly is:

Given an algebraic variety X, construct a proper, birational morphism Y-> X, where Y is a nonsingular variety.
The morphism is an isomorphism over an open dense subset of X. Along the same lines, the problem of embedded resolution of singularities is:
Given a nonsingular variety W and a variety X embedded into W; construct a proper, birational morphism p: W'-> W, where W' is nonsingular, such that p is an isomorphism outside the singular locus, Sing(X), of X, the proper transform of X (i.e. the closure of p-1(X-Sing(X))) is nonsingular and p-1(X) has normal crossings.
The most essential operation in the resolution of singularities is blowing up (also called as monoidal transformation, sigma-process, etc.). The blowing up of the affine plane at the origin is illustrated by the following figure:

Blowing up (A2, V(y2-x3-x2)) at the origin.

This problem has an impressive history. For curves, the existence of a resolution was already known in the 19th century. In the surface case, Walker gave an analytic proof [Walker1935], and Zariski gave an algebraic proof [Zariski1939]. Five years later, Zariski proved resolution of 3-folds [Zariski1944]. Then it took quite some time until Hironaka came up with his famous result of resolution for arbitrary dimension [Hironaka1964]. Hironaka's result holds only for the characteristic zero case. In positive characteristic, there are some partial results [Abhyankar1965,Lipman1978], but the general case is still open. For an account of the difficulties in positive characteristic, the reader should consult [Hauser1998].

Hironaka's existence proof is not constructive. Later, [Villamayor1989,Villamayor1996,Encinas and Villamayor2000] and [Bierstone and Milman1991,Bierstone and Milman1997] have come up with more explicit strategies to find a resolution. Still, the main interest of these authors was to prove the existence of resolutions with particular properties (equivariance) and not actual computation.

The algorithm is not new, since the main ideas are due to Villamayor; but this is the first time that a resolution algorithm has been formulated in such an explicit way. This is underlined by the fact that we could do a full implementation in Maple.

Even when taking the results of Villamayor and Bierstone-Milman into account, it is quite surprising that automated resolution is possible with nowadays means. We are not aware of any other implementations of resolution, even in the relatively easy case of surfaces, except a program for cyclic surfaces [Castellanos et al.1998] (see also [Eisenbud1993], where resolution of surfaces is considered as an open problem in constructive algebraic geometry). Only for curves, there are some implementations, e.g. in [Tran and Winkler1997] or in MapleV release 5 (in the package ``algcurves'' by M. van Hoeij).

One of the main difficulties in automated resolution is the following. The resolution is obtained by blowing up subvarieties in the singular locus. Now, it is quite easy to blowup a point. But for more complicated blowing up centers, the construction is not so trivial. There are implementations for performing blowing ups in various computer algebra systems like [Greuel et al.1998] and [Bayer et al.1993] (both are using Gröbner bases, by the way). But these computations are time consuming and the output can be much more complicated than the input. In the resolution algorithm, we need to apply blowing up repeatedly, which would be rather difficult when using these procedures. Gröbner bases [Buchberger1965,Buchberger1985,Winkler1988,] are, however, used in other places of the algorithm: testing whether a given ideal contains 1, solving linear equations over polynomials, computing quotient ideals.

By a new result in [Encinas and Villamayor2001] we were able to generalize the algorithm to the non hypersurface case in a straightforward manner. The package is also extended with adjoints computation facilities and it is able to compute the dual hypergraph of the exceptional divisors of a resolution.

This work was supported by the Austrian Science Fund FWF in the frame of the projects Computation of Adjoints for Surfaces and Proving and Solving over Reals. We are indebted to S. Encinas and O. Villamayor for their help in the clarification of details, and to H. Hauser for helpful remarks.