Differential forms in computational algebraic geometry

ABSTRACT

We give a uniform method for the two problems #CC_C and #IC_C of counting connected and irreducible components of complex algebraic varieties, respectively. Our algorithms are purely algebraic, i.e., they use only the field structure of C. They work efficiently in parallel and can be implemented by algebraic circuits of polynomial depth, i.e., in parallel polynomial time. The design of our algorithms relies on the concept of algebraic differential forms. A further important building block is an algorithm of Sántó [40] computing a variant of characteristic sets. The crucial complexity parameter for #IC_C turns out to be the number of equations. We describe a randomised algorithm solving #IC_C for a fixed number of rational equations given by straight-line programs (slps), which runs in parallel polylogarithmic time in the length and the degree of the slps.

REFERENCES

• 1: Philippe Aubry , Daniel Lazard , Marc Moreno Maza, On the theories of triangular sets, Journal of Symbolic Computation, v.28 n.1-2, p.105-124, July/Aug. 1999 [doi>10.1006/jsco.1999.0269]
• 2: C. Bajaj , J. Canny , R. Garrity , J. Warren, Factoring rational polynomials over the complexes, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.81-90, July 17-19, 1989, Portland, Oregon, United States [doi>10.1145/74540.74551]
• 3: Saugata Basu , Richard Pollack , Marie-Françoise Roy, Algorithms in Real Algebraic Geometry (Algorithms and Computation in Mathematics), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 4: Stuart J. Berkowitz, On computing the determinant in small parallel time using a small number of processors, Information Processing Letters, v.18 n.3, p.147-150, March 1984 [doi>10.1016/0020-0190(84)90018-8]
• 5: L. Blum, M. Shub, and S. Smale. On a theory of computation and complexity over the real numbers. Bull. Amer. Math. Soc., 21:1--46, 1989.
• 6: A. Borodin. On relating time and space to size and depth. SIAM J. Comp., 6:733--744, 1977.
• 7: F. Boulier, F. Lemaire, and M. Moreno Maza. Well known theorems on triangular systems and the D5 principle. In Proc. of Transgressive Computing 2006, Granada, Spain, 2006.
• 8: P. Bürgisser and F. Cucker. Variations by complexity theorists on three themes of Euler, Bézout, Betti, and Poincaré. In J. Krajíček, editor, Complexity of computations and proofs, volume 13 of Quaderni di Matematica {Mathematics Series}, pages 73--152. Department of Mathematics, Seconda Università di Napoli, Caserta, 2004.
• 9: Peter Bürgisser , Felipe Cucker, Counting complexity classes for numeric computations II: algebraic and semialgebraic sets, Journal of Complexity, v.22 n.2, p.147-191, April 2006 [doi>10.1016/j.jco.2005.11.001]
• 10: Peter Bürgisser , Felipe Cucker , Paulin Jacobé Naurois, The complexity of semilinear problems in succinct representation, Computational Complexity, v.15 n.3, p.197-235, October 2006 [doi>10.1007/s00037-006-0213-6]
• 11: Peter Bürgisser , Felipe Cucker , Martin Lotz, Counting Complexity Classes for Numeric Computations. III: Complex Projective Sets, Foundations of Computational Mathematics, v.5 n.4, p.351-387, November 2005 [doi>10.1007/s10208-005-0146-x]
• 12: John Canny, Some algebraic and geometric computations in PSPACE, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.460-469, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62257]
• 13: A. Chistov. Algorithm of polynomial complexity for factoring polynomials, and finding the components of varieties in subexponential time. Theory of the complexity of computations, II., Zap. Nauchn. Sem. Leningrad Otdel. Mat. Inst. Steklov (LOMI), 137:124--188, 1984. English translation: J. Sov. Math. 34(1986).
• 14: D. Eisenbud. Commutative Algebra with a View Toward Algebraic Geometry, volume 150 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1995.
• 15: D. Eisenbud, C. Huneke, and W. Vasconcelos. Direct methods for primary decomposition. Invent. Math., 110:207--235, 1992.
• 16: G. Gallo and B. Mishra. Wu-Ritt characteristic sets and their complexity. In Discrete and Computational Geometry: Papers from the DIMACS Special Year, pages 111--136, 1991.
• 17: Shuhong Gao, Factoring multivariate polynomials via partial differential equations, Mathematics of Computation, v.72 n.242, p.801-822, 1 April 2003 [doi>10.1090/S0025-5718-02-01428-X]
• 18: Patrizia Gianni , Barry Trager , Gail Zacharias, Gro¨bner bases and primary decomposition of polynomial ideals, Journal of Symbolic Computation, v.6 n.2-3, p.149-167, Oct./Dec. 1988 [doi>10.1016/S0747-7171(88)80040-3]
• 19: M. Giusti and J. Heintz. Algorithmes -disons rapides-pour la décomposition d'une variété algébrique en composantes irréductibles etéquidimensionnelles. In T. M. C. Traverso, editor, Effective Methods in Algebraic Geometry (Proceedings of MEGA'90), volume 94 of Progress in Math., pages 169--193, New York, NY, USA, 1991. Birkhäuser.
• 20: D. Grigoriev. Factoring polynomials over a finite field and solution of systems of algebraic equations. Theory of the complexity of computations, II., Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov (LOMI), 137:20--79, 1984. English translation: J. Sov. Math. 34(1986).
• 21: J. Heintz. Definability and fast quantifier elimination in algebraically closed fields. Theoret. Comp. Sci., 24:239--277, 1983.
• 22: Joos Heintz , Malte Sieveking, Absolute Primality of Polynomials is Decidable in Random Polynomial Time in the Number of Variables, Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.16-28, July 13-17, 1981
• 23: Michael Kalkbrener, A generalized Euclidean algorithm for computing triangular representations of algebraic varieties, Journal of Symbolic Computation, v.15 n.2, p.143-167, Feb. 1993 [doi>10.1006/jsco.1993.1011]
• 24: Michael Kalkbrener, Prime decompositions of radicals in polynomial rings, Journal of Symbolic Computation, v.18 n.4, p.365-372, Oct. 1994 [doi>10.1006/jsco.1994.1052]
• 25: Michael Kalkbrener, Algorithmic properties of polynomial rings, Journal of Symbolic Computation, v.26 n.5, p.525-581, Nov. 1, 1998 [doi>10.1006/jsco.1998.0227]
• 26: Erich Kaltofen, Fast parallel absolute irreducibility testing, Journal of Symbolic Computation, v.1 n.1, p.57-68, March 1985 [doi>10.1016/S0747-7171(85)80029-8]
• 27: J. Kollár. Sharp effective Nullstellensatz. J. Amer. Math. Soc., 1(4):963--975, 1988.
• 28: E. Kunz. Einführung in die kommutative Algebra und algebraische Geometrie, volume 46 of Vieweg-Studium: Aufbaukurs Mathematik. Vieweg, Wiesbaden, 1979.
• 29: S. Lang. Algebra. Addison-Wesley, second edition, 1984.
• 30: D. Lazard, A new method for solving algebraic systems of positive dimension, Discrete Applied Mathematics, v.33 n.1-3, p.147-160, Nov. 1991 [doi>10.1016/0166-218X(91)90113-B]
• 31: Guillermo Matera , Jose Maria Turull Torres, The space complexity of elimination theory: upper bounds, Selected papers of a conference on Foundations of computational mathematics, p.267-276, September 1997, Rio de Janeiro, Brazil
• 32: Ernst W. Mayr, Some complexity results for polynomial ideals, Journal of Complexity, v.13 n.3, p.303-325, Sept. 1997 [doi>10.1006/jcom.1997.0447]
• 33: K. Mulmuley, A fast parallel algorithm to compute the rank of a matrix over an arbitrary field, Combinatorica, v.7 n.1, p.101-104, Jan. 1987 [doi>10.1007/BF02579205]
• 34: D. Mumford. Algebraic Geometry I: Complex Projective Varieties, volume 221 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag, Berlin Heidelberg New York, 1976.
• 35: D. A. Plaisted. Sparse complex polynomials and polynomial reducibility. JCSS, 14:210--221, 1977.
• 36: J. Ritt. Differential Algebra. Americal Mathematical Society, 1950.
• 37: W. Ruppert. Reduzibilität ebener Kurven. J. Reine Angew. Math., 369:167--191, 1986.
• 38: Peter Scheiblechner, On the complexity of deciding connectedness and computing Betti numbers of a complex algebraic variety, Journal of Complexity, v.23 n.3, p.359-379, June, 2007 [doi>10.1016/j.jco.2007.03.008]
• 39: I. R. Shafarevich. Basic Algebraic Geometry. Springer-Verlag, Berlin Heidelberg New York, 1972.
• 40: Ágnes Szántó, Complexity of the Wu-Ritt decomposition, Proceedings of the second international symposium on Parallel symbolic computation, p.139-149, July 20-22, 1997, Maui, Hawaii, United States [doi>10.1145/266670.266716]
• 41: Á. Szántó. Computation with polynomial systems. PhD Thesis, 1999.
• 42: J von zur Gathen, Parallel arithmetic computations: a survey, Proceedings of the 12th symposium on Mathematical foundations of computer science 1986, p.93-112, June 1986, Bratislava, Czechoslovakia
• 43: Dongming Wang, Irreducible decomposition of algebraic varieties via characteristic sets and Gro¨bner bases, Computer Aided Geometric Design, v.9 n.6, p.471-484, Dec. 1992 [doi>10.1016/0167-8396(92)90045-Q]
• 44: Wen-Tsun Wu, Basic principles of mechanical theorem proving in elementary geometrics, Journal of Automated Reasoning, v.2 n.3, p.221-252, Aug. 1987 [doi>10.1007/BF02328447]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
complexity, connected components, differential forms, irreducible components