The computational complexity of the resolution of plane curve singularities
HTML articles powered by AMS MathViewer
 by Jeremy Teitelbaum PDF
 Math. Comp. 54 (1990), 797837 Request permission
Abstract:
We present an algorithm which computes the resolution of a plane curve singularity at the origin defined by a power series with coefficients in a (not necessarily algebraically closed) field k of characteristic zero. We estimate the number of koperations necessary to compute the resolution and the conductor ideal of the singularity. We show that the number of koperations is polynomially bounded by the complexity of the singularity, as measured for example by the index of its conductor ideal. Our algorithm involves calculations over reduced rings with zero divisors, and employs methods of deformation theory to reduce the consideration of power series to the consideration of polynomials.References

M. Artin, Deformations of singularities, Tata Institute of Fundamental Research, Bombay, 1976.
D. Bayer, The division algorithm and the Hilbert scheme, Ph.D. thesis, Harvard University, 1982.
T. Berry, On Coates’ algorithm, SIGSAM Bull. 17 (1983), 1217.
 Egbert Brieskorn and Horst Knörrer, Ebene algebraische Kurven, Birkhäuser Verlag, BaselBoston, Mass., 1981 (German). MR 646612
 B. Buchberger, A criterion for detecting unnecessary reductions in the construction of Gröbnerbases, Symbolic and algebraic computation (EUROSAM ’79, Internat. Sympos., Marseille, 1979) Lecture Notes in Comput. Sci., vol. 72, Springer, BerlinNew York, 1979, pp. 3–21. MR 575678
 B. Buchberger, G. E. Collins, R. Loos, and R. Albrecht (eds.), Computer algebra, 2nd ed., SpringerVerlag, Vienna, 1983. Symbolic and algebraic computation. MR 728960, DOI 10.1007/9783709175514
 D. V. Chudnovsky and G. V. Chudnovsky, On expansion of algebraic functions in power and Puiseux series. I, J. Complexity 2 (1986), no. 4, 271–294. MR 923022, DOI 10.1016/0885064X(86)900063
 J. Coates, Construction of rational functions on a curve, Proc. Cambridge Philos. Soc. 68 (1970), 105–123. MR 258831, DOI 10.1017/s0305004100001110
 Claire Dicrescenzo and Dominique Duval, Computations on curves, EUROSAM 84 (Cambridge, 1984) Lecture Notes in Comput. Sci., vol. 174, Springer, Berlin, 1984, pp. 100–107. MR 779120, DOI 10.1007/BFb0032834 —, Algebraic computations on algebraic numbers, in Informatique et Calcul, WileyMasson, 1985, pp. 5461. D. Duval, Diverses questions relatives au calcul formel avec des nombres algébriques, Ph.D. thesis, L’Université Scientifique, Technologique, et Médicale de Grenoble, 1987. W. Fulton, Algebraic curves, Benjamin/Cummings, 1974. A. Galligo, Apropos du théorème de préparation de Weierstrass, Lecture Notes in Math., vol. 409, Springer, 1974, pp. 543579.
 Daniel Gorenstein, An arithmetic theory of adjoint plane curves, Trans. Amer. Math. Soc. 72 (1952), 414–436. MR 49591, DOI 10.1090/S00029947195200495918
 Heisuke Hironaka, Resolution of singularities of an algebraic variety over a field of characteristic zero. I, II, Ann. of Math. (2) 79 (1964), 109–203; ibid. (2) 79 (1964), 205–326. MR 0199184, DOI 10.2307/1970547
 Erich Kaltofen, Fast parallel absolute irreducibility testing, J. Symbolic Comput. 1 (1985), no. 1, 57–67. MR 810135, DOI 10.1016/S07477171(85)800298
 Donald E. Knuth, The art of computer programming, 2nd ed., AddisonWesley Series in Computer Science and Information Processing, AddisonWesley Publishing Co., Reading, Mass.LondonAmsterdam, 1975. Volume 1: Fundamental algorithms. MR 0378456
 H. T. Kung and J. F. Traub, All algebraic functions can be computed fast, J. Assoc. Comput. Mach. 25 (1978), no. 2, 245–260. MR 488306, DOI 10.1145/322063.322068
 Hideyuki Matsumura, Commutative algebra, 2nd ed., Mathematics Lecture Note Series, vol. 56, Benjamin/Cummings Publishing Co., Inc., Reading, Mass., 1980. MR 575344
 Ferdinando Mora, An algorithm to compute the equations of tangent cones, Computer algebra (Marseille, 1982) Lecture Notes in Comput. Sci., vol. 144, Springer, BerlinNew York, 1982, pp. 158–165. MR 680065 F. O. Schreyer, Ph.D. thesis, University of Hamburg, 1980.
 JeanPierre Serre, Groupes algébriques et corps de classes, Publications de l’Institut de Mathématique de l’Université de Nancago, VII, Hermann, Paris, 1959 (French). MR 0103191
Additional Information
 © Copyright 1990 American Mathematical Society
 Journal: Math. Comp. 54 (1990), 797837
 MSC: Primary 14B05; Secondary 1404, 14H20, 68Q25
 DOI: https://doi.org/10.1090/S00255718199010106021
 MathSciNet review: 1010602