Navegar

Colección

Datos Estadísticas

Artículo

Jeronimo, G.; Krick, T.; Sabia, J.; Sombra, M. "The Computational Complexity of the Chow Form" (2004) Foundations of Computational Mathematics. 4(1):41-117
Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We present a bounded probability algorithm for the computation of the Chow forms of the equidimensional components of an algebraic variety. In particular, this gives an alternative procedure for the effective equidimensional decomposition of the variety, since each equidimensional component is characterized by its Chow form. The expected complexity of the algorithm is polynomial in the size and the geometric degree of the input equation system defining the variety. Hence it improves (or meets in some special cases) the complexity of all previous algorithms for computing Chow forms. In addition to this, we clarify the probability and uniformity aspects, which constitutes a further contribution of the paper. The algorithm is based on elimination theory techniques, in line with the geometric resolution algorithm due to M. Giusti, J. Heintz, L. M. Pardo, and their collaborators. In fact, ours can be considered as an extension of their algorithm for zero-dimensional systems to the case of positive-dimensional varieties. The key element for dealing with positive-dimensional varieties is a new Poisson-type product formula. This formula allows us to compute the Chow form of an equidimensional variety from a suitable zero-dimensional fiber. As an application, we obtain an algorithm to compute a subclass of sparse resultants, whose complexity is polynomial in the dimension and the volume of the input set of exponents. As another application, we derive an algorithm for the computation of the (unique) solution of a generic overdetermined polynomial equation system.

Registro:

Documento: Artículo
Título:The Computational Complexity of the Chow Form
Autor:Jeronimo, G.; Krick, T.; Sabia, J.; Sombra, M.
Filiación:FCEyN, Departamento de Matemática, Ciudad Universitaria, 1428 Buenos Aires, Argentina
Université de Paris 7, UFR de Mathématiques, Equipe de Geometrie et Dynamique, 2 place Jussieu, 75251 Paris Cedex 05, France
Departamento de Matemática, Universidad Nacional de La Plata, Calle 50 y 115, 1900 La Plata, Argentina
Palabras clave:Chow form; Equidimensional decomposition of algebraic varieties; Overdetermined polynomial equation system; Sparse resultant; Symbolic Newton algorithm; Algorithms; Computational methods; Partial differential equations; Polynomials; Probability; Set theory; Bounded probability algorithm; Chow form; Computational complexity
Año:2004
Volumen:4
Número:1
Página de inicio:41
Página de fin:117
DOI: http://dx.doi.org/10.1007/s10208-002-0078-2
Título revista:Foundations of Computational Mathematics
Título revista abreviado:Found. Comput. Math.
ISSN:16153375
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_16153375_v4_n1_p41_Jeronimo

Referencias:

  • Abdeljaoued, J., (1997) Algorithmes Rapides Pour le Calcul du Polynôme Caractéristique, , Ph.D. dissertation, Univ. Franche-Comté, Besancon, France
  • Berkowitz, S.J., On computing the determinant in small parallel time using a small number of processors (1984) Inform. Process. Lett., 18, pp. 147-150
  • Baur, W., Strassen, W., The complexity of partial derivatives (1983) Theoret. Comput. Sci., 22, pp. 317-330
  • Blanco, C., Jeronimo, G., Solernó, P., (2003) Computing Generators of the Ideal of a Smooth Affine Algebraic Variety, , Preprint Univ. Buenos Aires
  • Blum, L., Cucker, F., Shub, M., Smale, S., (1998) Complexity and Real Computation, , Springer-Verlag, New York
  • Bourbaki, N., (1961) Éléments de Mathématique. Algèbre Commutative, , Hermann, Paris
  • Brown, W.S., Traub, J.F., On Euclid's algorithm and the theory of subresultants (1971) J. Assoc. Comput. Mach., 18, pp. 505-514
  • Bürgisser, P., Clausen, M., Shokrollahi, M.A., (1997) Algebraic Complexity Theory, , Springer-Verlag, New York
  • Caniglia, L., How to compute the Chow form of an unmixed ideal in single exponential time (1990) Appl. Algebra Engrg. Comm. Comput., 1, pp. 25-41
  • Canny, J.F., Emiris, I.Z., (1993) An Efficient Algorithm for the Sparse Mixed Resultant, 263, pp. 89-104. , Proceedings of the Tenth International Symposium on Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes, San Juan, Puerto Rico, 1993 (AAECC-10) (G. Cohen, et al., eds.), Lecture Notes in Comput. Sci
  • Canny, J.F., Emiris, I.Z., A subdivision-based algorithm for the sparse resultant (2000) J. Assoc. Comput. Mach., 47, pp. 417-451
  • Castro, D., Giusti, M., Heintz, J., Matera, G., Pardo, L.M., The hardness of polynomial equation solving (2003) Found. Comput. Math., 3, pp. 347-420
  • Chistov, A.L., Grigoriev, D.Y., (1983) Subexponential Time Solving Systems of Algebraic Equations, , LOMI preprint E-9-83, E-10-83, Steklov Institute, Leningrad
  • Collins, G.E., Subresultants and reduced polynomial remainder sequences (1967) J. Assoc. Comput. Mach., 14, pp. 128-142
  • Cox, D., Little, J., O'Shea, D., (1998) Using Algebraic Geometry, 185. , Graduate Texts in Mathematics, Springer-Verlag, New York
  • Dalbec, J., Sturmfels, B., Introduction to Chow forms (1995) Invariant Methods in Discrete and Computational Geometry, pp. 37-58. , Curaçao, 1994, Kluwer, Amsterdam
  • D'Andrea, C., Macaulay's style formulas for sparse resultants (2002) Trans. Amer. Math. Soc., 354, pp. 2595-2629
  • D'Andrea, C., Dickenstein, A., Explicit formulas for the multivariate resultant (2001) J. Pure Appl. Algebra, 164, pp. 59-86
  • Eisenbud, D., (1995) Commutative Algebra with a View Toward Algebraic Geometry, 150. , Graduate Texts in Mathematics, Springer-Verlag, New York
  • Elkadi, M., Mourrain, B., A new algorithm for the geometric decomposition of a variety (1999) Proc. ISSAC'1999, pp. 9-16. , ACM
  • Emiris, I., Mourrain, B., Matrices in elimination theory (1999) J. Symbolic Comput., 28, pp. 3-44
  • Gelfand, I.M., Kapranov, M.M., Zelevinsky, A.V., (1994) Discriminants, Resultants, and Multidimensional Determinants, , Birkhäuser, Boston
  • Giusti, M., Hägele, K., Heintz, J., Montana, J.L., Pardo, L.M., Morais, J.E., Lower bounds for Diophantine approximation (1997) J. Pure Appl. Algebra, 117-118, pp. 277-317
  • Giusti, M., Heintz, J., La détermination des points isolés et de la dimension d'une variété algébrique peut se faire en temps polynomial (1993) Computational Algebraic Geometry and Commutative Algebra, 34, pp. 216-256. , (D. Eisenbud and L. Robbiano, eds.), Sympos. Math
  • Giusti, M., Heintz, J., (1991) Algorithmes - Disons Rapides - Pour la Décomposition d'Une Varieté Algébrique en Composantes Irréductibles et Équidimensionelles, 94, pp. 164-194. , Proceedings of the International Conference on Effective Methods in Algebraic Geometry, Castiglioncello, Spain, 1990 (MEGA '90) (T. Mora and C. Traverse, eds.), Progress in Mathematics, Birkhäuser, Boston
  • Giusti, M., Heintz, J., Kronecker's smart, little black-boxes (2001) Proceedings of Foundations of Computational Mathematics, 284, pp. 69-104. , Oxford 1999 (FoCM'99) (A. Iserles and R. DeVore, eds.), Cambridge University Press, Cambridge
  • Giusti, M., Heintz, J., Morais, J.E., Morgenstern, J., Pardo, L.M., Straight-line programs in geometric elimination theory (1998) J. Pure Appl. Algebra, 124, pp. 101-146
  • Giusti, M., Heintz, J., Morais, J.E., Pardo, L.M., When polynomial equation systems can be "solved" fast? (1995) Proc. 11th International Symposium Applied Algebra, Algebraic Algorithms and Error-correcting Codes, 948, pp. 205-231. , AAECC-11, Paris 1995 (G. Cohen, M. Giusti and T. Mora, eds.), Lecture Notes in Comput. Sci., Springer-Verlag, Berlin
  • Giusti, M., Heintz, J., Sabia, J., On the efficiency of effective Nullstellensätze (1993) Comput. Complexity, 3, pp. 56-95
  • Giusti, M., Lecerf, G., Salvy, B., A Gröbner free alternative for polynomial system solving (2001) J. Complexity, 17, pp. 154-211
  • Harris, J., (1992) Algebraic Geometry, 133. , Graduate Texts in Mathematics, Springer-Verlag, New York
  • Heintz, J., Definability and fast quantifier elimination in algebraically closed fields (1983) Theoret. Comput. Sci., 24, pp. 239-277
  • Heintz, J., (1989) On the Computational Complexity of Polynomials and Bilinear Maps. A Survey, 356, pp. 269-300. , Lecture Notes in Comput. Sci., Springer-Verlag, Berlin
  • Heintz, J., Krick, T., Puddu, S., Sabia, J., Waissbein, A., Deformation techniques for efficient polynomial equation solving (2000) J. Complexity, 16, pp. 70-109
  • Heintz, J., Matera, G., Pardo, L.M., Wachenchauzer, R., The intrinsic complexity of parametric elimination methods (1998) Electronic J. SADIO, 1, pp. 37-51
  • Heintz, J., Matera, G., Waissbein, A., On the time-space complexity of geometric elimination procedures (2001) Appl. Algebra Engrg. Comm. Comput., 11, pp. 239-296
  • Jeronimo, G., Puddu, S., Sabia, J., Computing Chow forms and some applications (2001) J. Algorithms, 41, pp. 52-68
  • Jeronimo, G., Sabia, J., Effective equidimensional decomposition of affine varieties (2002) J. Pure Appl. Algebra, 169, pp. 229-248
  • Jouanolou, J.P., Formes d'inertie et résultant: Un formulaire (1997) Adv. in Math., 126, pp. 119-250
  • Kaltofen, E., Greatest common divisors of polynomials given by straight-line programs (1988) J. Assoc. Comput. Mach., 35, pp. 234-264
  • Krick, T., (1990) Complejidad Para Problemas de Geometría Elemental, , Ph.D. dissertation, Univ. Buenos Aires, Buenos Aires, Argentina
  • Krick, T., Pardo, L.M., (1996) A Computational Method for Diophantine Approximation, 143, pp. 193-253. , Proceedings of the International Conference on Effective Methods in Algebraic Geometry, Santander, Spain, (MEGA '94) (G.-V. Laureano et al., eds.), Progress in Mathematics, Birkhäuser, Boston
  • Krick, T., Pardo, L.M., Sombra, M., Sharp estimates for the arithmetic Nullstellensatz (2001) Duke Math. J., 109, pp. 521-598
  • Krick, T., Sabia, J., Solernó, P., On intrinsic bounds in the Nullstellensatz (1997) Appl. Algebra Engrg. Comm. Comput., 8, pp. 125-134
  • Lecerf, G., Kronecker, a Magma Package for Polynomial System Solving, , http://kronecker.medicis.polytechnique.fr/
  • Lecerf, G., Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions (2000) Proc. ISSAC'2000, pp. 209-216. , ACM
  • Lecerf, G., Quadratic Newton iteration for systems with multiplicity (2002) Found. Comput. Math., 2, pp. 247-293
  • Lecerf, G., Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers (2003) J. Complexity, 19, pp. 564-596
  • Macaulay, F., Some formulae in elimination (1902) Proc. London Math. Soc. Ser. 1, 33, pp. 3-27
  • Philippen, P., Critères pour l'indépendance algébrique (1986) Inst. Hautes Études Sci. Publ. Math., 64, pp. 5-52
  • Puddu, S., Sabia, J., An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs (1998) J. Pure Appl. Algebra, 129, pp. 173-200
  • Rojas, J.M., Toric laminations, sparse generalized characteristic polynomials, and a refinement of Hilbert's tenth problem (1997) Proc. FoCM'97, pp. 369-381. , Proceedings of Foundations of Computational Mathematics, Rio de Janeiro, 1997, Springer-Verlag, New York
  • Schwartz, J.T., Fast probabilistic algorithms for verification of polynomial identities (1980) J. Assoc. Comput. Mach., 27, pp. 701-717
  • Shafarevich, I., (1972) Basic Algebraic Geometry, , Springer-Verlag, New York
  • Strassen, V., Berechnung und Programm I, II (1972) Acta Inform., 1, pp. 320-355
  • (1973) Acta Inform., 2, pp. 64-79
  • Strassen, V., Vermeidung von Divisionen (1973) J. Reine Angew. Math., 264, pp. 182-202
  • Sturmfels, B., Sparse elimination theory (1993) Computational Algebraic Geometry and Commutative Algebra, pp. 377-396. , D. Eisenbud and L. Robbiano, eds., Cambridge University Press, Cambridge
  • Sturmfels, B., On the Newton polytope of the resultant (1994) J. Algebraic Combinatorics, 3, pp. 207-236
  • Szántó, A., (2001) Solving Over-determined Systems by Subresultant Method, , Preprint
  • Vogel, W., (1984) Lectures on Results on Bezout's Theorem, 74. , Tata Institute of Fundamental Research, Lectures on Mathematics and Physics, Springer-Verlag, Berlin
  • Zippel, R., Probabilistic algorithms for sparse polynomials (1979) Proceedings EUROSAM'79, 72, pp. 216-226. , Lecture Notes in Comput. Sci., Springer-Verlag, Berlin

Citas:

---------- APA ----------
Jeronimo, G., Krick, T., Sabia, J. & Sombra, M. (2004) . The Computational Complexity of the Chow Form. Foundations of Computational Mathematics, 4(1), 41-117.
http://dx.doi.org/10.1007/s10208-002-0078-2
---------- CHICAGO ----------
Jeronimo, G., Krick, T., Sabia, J., Sombra, M. "The Computational Complexity of the Chow Form" . Foundations of Computational Mathematics 4, no. 1 (2004) : 41-117.
http://dx.doi.org/10.1007/s10208-002-0078-2
---------- MLA ----------
Jeronimo, G., Krick, T., Sabia, J., Sombra, M. "The Computational Complexity of the Chow Form" . Foundations of Computational Mathematics, vol. 4, no. 1, 2004, pp. 41-117.
http://dx.doi.org/10.1007/s10208-002-0078-2
---------- VANCOUVER ----------
Jeronimo, G., Krick, T., Sabia, J., Sombra, M. The Computational Complexity of the Chow Form. Found. Comput. Math. 2004;4(1):41-117.
http://dx.doi.org/10.1007/s10208-002-0078-2