Abstract:
In this paper we present a probabilistic algorithm which computes, from a finite set of polynomials defining an algebraic variety V, the decomposition of V into equidimensional components. If V is defined by s polynomials in n variables of degrees bounded by an integer d ≥ n and V = ∪l=0 r Vℓ is the equidimensional decomposition of V, the algorithm obtains in sequential time bounded by sO(1)dO(n), for each 0 ≤ ℓ ≤r, a set of n + 1 polynomials of degrees bounded by deg(Vℓ) which define Vℓ. © 2002 Elsevier Science B.V. All rights reserved.
Referencias:
- Chistov, A.L., Grigor'ev, D.Y., Subexponential time solving systems of algebraic equations (1983), LOMI preprint E-9-83, E-10-83, Steklov Institute, Leningrad; Elkadi, M., Mourrain, B., A new algorithm for the geometric decomposition of a variety (1999), Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation; Giusti, M., Heintz, J., Algorithmes -disons rapides- pour la décomposition d'une variété algébrique en composantes irréductibles et équidimensionnelles (1991) Effective Methods in Algebraic Geometry, Progress in Mathematics, 94, pp. 169-193. , T. Mora, C. Traverso (Eds.), Birkhäuser, Basel
- 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), 34, pp. 216-256. , Proceedings of the Cortona Conference on Computational Algebraic Geometry and Commutative Algebra, Symposia Matematica; 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., Sabia, J., On the efficiency of effective Nullstellensätze (1993) Comput. Complexity, 3, pp. 56-95
- Heintz, J., Definability and fast quantifier elimination in algebraically closed fields (1983) Theoret. Comput. Sci, 24, pp. 239-277
- Heintz, J., On the computational complexity of polynomials and bilinear mappings, a survey (1989) Lecture Notes in Computer Science, 356, pp. 269-300. , L. Huguet, A. Poli (Eds.), Proceedings of the Fifth International Conference AAECC 5, Springer, Berlin
- Heintz, J., Schnorr, C.P., Testing polynomials which are easy to compute (1982) Monographie 30 de l'Enseignement Mathématique, pp. 237-254
- Jeronimo, G., Sabia, J., Probabilistic equidimensional decomposition (2000) C.R. Acad. Sci. Paris, 331 I, pp. 485-490
- Krick, T., Pardo, L.M., A computational method for diophantine aproximation (1996) Prog. Math, 143, pp. 193-253
- Krick, T., Pardo, L.M., Sombra, M., Sharp estimates for the arithmetic Nullstellensatz Duke Math. J, , to appear
- Lecerf, G., Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions (2000), Proceedings of the ISSAC 2000 Conference, ACM; Sabia, J., Solernó, P., Bounds for traces in complete intersections and degrees in the Nullstellensatz (1995) AAECC J, 6, pp. 353-376
- Schwartz, J.T., Fast probabilistic algorithms for verification of polynomial identities (1980) J. ACM, 27, pp. 701-717
- Strassen, V., Vermeidung von Divisionen (1973) Crelle J. Reine Angew. Math, 264, pp. 184-202
- von zur Gathen, I., Parallel algorithms for algebraic problems (1986) Lecture Notes in Computer Science, 233, pp. 93-112. , Proceedings of the 13th Conference on MFCS, Springer, Berlin
Citas:
---------- APA ----------
Jeronimo, G. & Sabia, J.
(2002)
. Effective equidimensional decomposition of affine varieties. Journal of Pure and Applied Algebra, 169(2-3), 229-248.
http://dx.doi.org/10.1016/S0022-4049(01)00083-4---------- CHICAGO ----------
Jeronimo, G., Sabia, J.
"Effective equidimensional decomposition of affine varieties"
. Journal of Pure and Applied Algebra 169, no. 2-3
(2002) : 229-248.
http://dx.doi.org/10.1016/S0022-4049(01)00083-4---------- MLA ----------
Jeronimo, G., Sabia, J.
"Effective equidimensional decomposition of affine varieties"
. Journal of Pure and Applied Algebra, vol. 169, no. 2-3, 2002, pp. 229-248.
http://dx.doi.org/10.1016/S0022-4049(01)00083-4---------- VANCOUVER ----------
Jeronimo, G., Sabia, J. Effective equidimensional decomposition of affine varieties. J. Pure Appl. Algebra. 2002;169(2-3):229-248.
http://dx.doi.org/10.1016/S0022-4049(01)00083-4