Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



The computational complexity of the resolution of plane curve singularities

Author: Jeremy Teitelbaum
Journal: Math. Comp. 54 (1990), 797-837
MSC: Primary 14B05; Secondary 14-04, 14H20, 68Q25
MathSciNet review: 1010602
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 k-operations necessary to compute the resolution and the conductor ideal of the singularity. We show that the number of k-operations 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 [Enhancements On Off] (What's this?)

  • [1] M. Artin, Deformations of singularities, Tata Institute of Fundamental Research, Bombay, 1976.
  • [2] D. Bayer, The division algorithm and the Hilbert scheme, Ph.D. thesis, Harvard University, 1982.
  • [3] T. Berry, On Coates' algorithm, SIGSAM Bull. 17 (1983), 12-17.
  • [4] E. Brieskorn and H. Knorrer, Ebene algebraische Kurven, Birkhäuser, Boston, 1981. MR 646612 (83i:14001)
  • [5] B. Buchberger, A criterion for detecting unnecessary reductions in the construction of Gröbner bases, Lecture Notes in Comput. Sci., vol. 72, Springer, 1979, pp. 3-21. MR 575678 (82e:14004)
  • [6] B. Buchberger, G. E. Collins, and R. Loos (editors), Computer algebra: Symbolic and algebraic computation, Springer, 1983. MR 728960 (87a:68024)
  • [7] D. V. Chudnovsky and G. V. Chudnovsky, On expansion of algebraic functions in power and Puiseux series. I, J. Complexity 2 (1986), 271-294. MR 923022 (90d:68031a)
  • [8] J. Coates, Construction of rational functions on a curve, Proc. Cambridge Philos. Soc. 68 (1970), 105-123. MR 0258831 (41:3477)
  • [9] C. Dicrescenzo and D. Duval, Computations on curves, Lecture Notes in Comput. Sci., vol. 174, Springer, 1984, pp. 100-107. MR 779120 (86d:14001)
  • [10] -, Algebraic computations on algebraic numbers, in Informatique et Calcul, Wiley-Masson, 1985, pp. 54-61.
  • [11] 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.
  • [12] W. Fulton, Algebraic curves, Benjamin/Cummings, 1974.
  • [13] A. Galligo, Apropos du théorème de préparation de Weierstrass, Lecture Notes in Math., vol. 409, Springer, 1974, pp. 543-579.
  • [14] D. Gorenstein, An arithmetic theory of adjoint plane curves, Trans. Amer. Math. Soc. 72 (1952), 414-436. MR 0049591 (14:198h)
  • [15] H. Hironaka, Resolution of singularities of an algebraic variety over a field of characteristic zero, Ann. of Math. (2) 79 (1964), 109-326. MR 0199184 (33:7333)
  • [16] E. Kaltofen, Fast parallel absolute irreducibility testing, J. Symbolic Comput. 1 (1985), 57-67. MR 810135 (87b:12002)
  • [17] D. Knuth, The art of computer programming: Seminumerical algorithms, Addison-Wesley, 1971. MR 0378456 (51:14624)
  • [18] H. T. Kung and J. F. Traub, All algebraic functions can be computed fast, J. Assoc. Comput. Mach. 25 (1978), 245-260. MR 488306 (80a:68042)
  • [19] H. Matsumura, Commutative algebra, Benjamin/Cummings, 1980. MR 575344 (82i:13003)
  • [20] F. Mora, An algorithm to compute the equations of tangent cones, Lecture Notes in Comput. Sci., vol. 144, Springer, 1982, pp. 158-165. MR 680065 (84c:13012)
  • [21] F. O. Schreyer, Ph.D. thesis, University of Hamburg, 1980.
  • [22] J.-P. Serre, Groupes algébriques et corps de classes, Hermann, Paris, 1959. MR 0103191 (21:1973)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 14B05, 14-04, 14H20, 68Q25

Retrieve articles in all journals with MSC: 14B05, 14-04, 14H20, 68Q25

Additional Information

Article copyright: © Copyright 1990 American Mathematical Society

American Mathematical Society