=ADD=
=reftype=
14
=number=
00-31
=url=
ftp://ftp.risc.uni-linz.ac.at/pub/techreports/2000/00-31.ps.gz
=year=
2000
=month=
11
=author=
Stadelmeyer; Peter
=title=
On the Computational Complexity of Resolving Curve Singularities and Related Problems
=abstract=
For a number of questions arising in the area of plane algebraic
geometry full analysis (resolution) of curve singularities is of
great importance. Examples for that are the determination of the
genus of a curve, the computation of the linear system of adjoint
curves of a curve, or the parametrization of a curve.

Constructive resolution methods are essentially based on repeated
applications of transformations, which transform the original curve
into a curve devoid of singularities. But not all of these methods
are equally well suited for practical use in computer algebra systems.
One of the main problems from an algorithmic point of view is the
possibly very high degree of intermediate results.

In the framework of this thesis it turned out, that the above
mentioned questions can be answered efficiently with the help of the
Newton--Puiseux algorithm for computing local parametrizations of
curve-branches. For this reason a considerable part of this thesis
is devoted to a thorough complexity analysis of the Newton--Puiseux
algorithm. There one sees that the determination low degree bounds
for the intermediate results is crucial for the efficiency of this
method.

We were able to show, that the resolution method described in this
thesis has a computational complexity w.r.t.\ to the number of
operations in the ground field of order $\mu^3$, where $\mu$ is the
Milnor number of the singularity.

This result serves as a basis for complexity statements about the
determination of the genus of plane curves and the computation of
the linear system of adjoint curves.
=note=
PhD Thesis
=sponsor=
FWF project number P11160-TEC ``HySaX'' and ``SFB -- Numerical and Symbolic Scientific Computing'' project number F013 04
=keywords=
algebraic geometry, plane curves, resolution, Puiseux series,
singularities, computational complexity