Algorithmic Algebraic Geometry

The most famous algorithms in algebraic geometry are the three big engines of

1. Gröbner bases,
2. characteristic sets,
3. cylindric algebraic decomposition.

Each of them is the topic of several courses and text books (see [5][9][10] for Gröbner bases, [37][36][22] for characteristic sets, [3][4][11] for cylindric algebraic decomposition).

However, to get a flavour of the fruitful interplay between algebra, geometry, and computing science, it is more enlightning to study several smaller ideas/algorithms/problems. We will study the problems of

1. counting roots with Bernshtein's method
2. counting roots with Hermite's method
3. the Lüroth problem
4. rational parameterization of curves
5. polynomial parametrization of curves
6. trigonometric parametrization of curves
7. rational parametrization of surfaces

For each of the problems, some material is distributed, and there will be a talk/several talks by course participants.

An essential part of the talks will be computing examples. The computations can be facilitated by computer, eg by the general purpose systems like AXIOM, Macsyma, MAGMA, Maple, Mathematica, REDUCE, or by special purpose systems devoted to algebraic geometry, such as CALI, CASA, CoCoA, FELIX, Macaulay, Singular.

References

 [1]

Abhyankar, S. S. Algebraic Geometry for Scientists and Engineers. No. 35 in Mathematical Surveys and Monographs. American Mathematical Society, Providence, Rhode Island, 1990.

 [2]

Abhyankar, S. S., and Bajaj, B. Automatic parametrization of curves and surfaces III. Computer Aided Geometric Design 5-4 (1987), 309-323.

 [3]

Arnon, D. S., Collins, G. E., and McCallum, S. Cylindrical algebraic decomposition I: The basic algorithm. SIAM J. Comp. 13 (1984), 865-877.

 [4]

Arnon, D. S., and McCallum, S. Cylindrical algebraic decomposition by quantifier elimination. In Proceedings of the European Computer Algebra Conference (EUROCAM '82) (1982), vol. 144 of Lecture Notes Comp. Science., pp. 215-222.

 [5]

Becker, T., and Weispfenning, V. Gröbner bases - a computational approach to commutative algebra. Graduate Texts in Mathematics. Springer Verlag, 1993.

 [6]

Bernshtein, D. The number of roots of a system of equations. Funct. Anal. Appl. (1975), 183-185.

 [7]

Binder, F. Polynomial Decomposition. Master's thesis, University of Linz, 1995.

 [8]

Binder, F. Fast Computations in the Lattice of Polynomial Rational Function Fields. In ISSAC-96 (1996), ACM Press, pp. 43-48.

 [9]

Buchberger, B. An Algorithm for Finding a Basis for the Residue Class Ring of a Zero-Dimensional Polynomial Ideal. PhD thesis, Universitat Innsbruck, Institut fur Mathematik, 1965. German.

 [10]

Buchberger, B. Groebner 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.

 [11]

Collins, G. E. Quantifier elimination for the elementary theory of real closed fields by cylindrical algebraic decomposition. In Lecture Notes In Computer Science (1975), Springer, pp. 134-183. Vol. 33.

 [12]

der Waerden, B. L. V. Modern Algebra Vols. I and II. Fredrick Ungar Publishing Co., New York, 1966.

 [13]

Hong, H., and Schicho, J. Algorithms for trigonometric curves. Journal of Symbolic Computation (1997). submitted as # 1629.

 [14]

Hong, H., and Stöcher, W. Implementing Real Root Count with Polynomial Constraints for the Multivariate Case with one Constraint Polynomial. RISC-report 95-50 (1995).

 [15]

Khovanskii, A. Newton polyhedra and toric varieties. Funct. Anal. Appl. (1977), 289-296.

 [16]

Kushnirenko, A. Newton polytopes and the bezout theorem. Funkt. Anal. Appl. (1976), 82-83.

 [17]

Lausch, H., and Nöbauer, W. Algebra of polynomials. North-Holland, 1973.

 [18]

Li, T. Y., Rojas, J. M., and Wang, X. Counting affine roots of polynomial systems via pointed newton polytopes. Unpublished, 1994.

 [19]

Mñuk, M. Algebraic parametrization of rational curves. PhD thesis, RISC Linz, 1996.

 [20]

Mñuk, M., Sendra, J. R., and Winkler, F. On the complexity of parametrizing curves. Beitr. Algebra und Geometrie 37/2 (1996).

 [21]

Manocha, D., and Canny, J. Rational curves with polynomial parametrization. Computer Aided Geometric Design (1991), 12-19.

 [22]

Mishra, B. Algorithmic Algebra. Springer, New York, 1993.

 [23]

Pedersen, P., Roy, M.-F., and Szpirglas, A. Counting real zeroes in the multivariate case. In Proceedings MEGA'92: Computational Algebraic Geometry (1993), Eyssette and Galligo, Eds., vol. 109 of Progress in Math., Birkhäuser, pp. 203-224.

 [24]

Peternell, M. Rational parametrizations for envelopes of quadric families. PhD thesis, Techn. Univ. Vienna, 1997.

 [25]

Rojas, J. M. A convex geometric approach to counting the roots of a polynomial system. Theoretical Computer Science 133 (1994), 105-140.

 [26]

Schicho, J. On the choice of pencils in the parametrization of curves. Journal of Symbolic Computation 14, 6 (1992), 557-576.

 [27]

Schicho, J. On algorithmic parametrization methods in algebraic geometry. In Automated practical reasoning, J. Pfalzgraf and D. Wang, Eds. Springer, 1995, pp. 81-90.

 [28]

Schicho, J. Inversion of rational maps with gröbner bases. In Gröbner bases and applications (1998), B. Buchberger and F. Winkler, Eds., Cambridge Univ. Press.

 [29]

Schicho, J. Rational parameterization of real algebraic surfaces. In ISSAC-98 (1998), ACM Press.

 [30]

Schicho, J. Rational parameterization of surfaces. Journal of Symbolic Computation 21 (1998). to appear.

 [31]

Sendra, J., and Winkler, F. Symbolic parametrization of curves. Journal of Symbolic Computation 12, 6 (1991), 607-632.

 [32]

Sendra, J., and Winkler, F. Parametrization of algebraic curves over optimal field extensions. Journal of Symbolic Computation 23, 2/3 (1997), 191-208.

 [33]

van Hoeij, M. Computing parametrizations of rational algebraic curves. In ISSAC-94 (1994), ACM Press, pp. 187-190.

 [34]

van Hoeij, M. Rational parametrizations of algebraic curves using canonical divisors. Journal of Symbolic Computation 23 (1997). to appear.

 [35]

Walker, R. J. Algebraic Curves. Springer, 1978.

 [36]

Wang, D. Solving polynomial equations: Characteristic sets and triangular systems. Tech. Rep. 93-39, RISC-Linz, 1993.

 [37]

Wu, W. T. Basic principles of mechianical theorem proving in elementary geometries. Journal of Automated Reasoning 2 (1986), 221-252.