Artículo

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:

Let k be an effective infinite perfect field, k[x1,...,xn] the polynomial ring in n variables and F∈k[x1,...,xn]M×M a square polynomial matrix verifying F2=F. Suppose that the entries of F are polynomials given by a straight-line program of size L and their total degrees are bounded by an integer D. We show that there exists a well parallelizable algorithm which computes bases of the kernel and the image of F in time (nL)O(1)(MD)O(n). By means of this result we obtain a single exponential algorithm to compute a basis of a complete intersection ring in Noether position. More precisely, let f1,...,fn-r∈k[x1,...,xn] be a regular sequence of polynomials given by a slp of size ℓ, whose degrees are bounded by d. Let Rk[x1,...,xr] and Sk[x1,...,xn]/(f1,...,fn-r) such that S is integral over R; we show that there exists an algorithm running in time O(n)ℓdO(n2) which computes a basis of S over R. Also, as a consequence of our techniques, we show a single exponential well parallelizable algorithm which decides the freeness of a finite k[x1,...,xn]-module given by a presentation matrix, and in the affirmative case it computes a basis. © 2001 Elsevier Science B.V.

Registro:

Documento: Artículo
Título:Computing bases of complete intersection rings in Noether position
Autor:Almeida, M.; Blaum, M.; D'Alfonso, L.; Solernó, P.
Filiación:Departamento de Matemática, Fac. Cie. Exact. y Nat., Univ. B., Buenos Aires, Argentina
Universidad de San Andrés, Depto. Matemat., Vito D., Victoria, Argentina
Palabras clave:13C10; 13P10; 68Q40
Año:2001
Volumen:162
Número:2-3
Página de inicio:127
Página de fin:170
DOI: http://dx.doi.org/10.1016/S0022-4049(00)00135-3
Título revista:Journal of Pure and Applied Algebra
Título revista abreviado:J. Pure Appl. Algebra
ISSN:00224049
CODEN:JPAAA
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00224049_v162_n2-3_p127_Almeida

Referencias:

  • Almeida, M., D'Alfonso, L., Solernó, P., On the degrees of bases of free modules over a polynomial ring (1999) Math. Z., 231, pp. 679-706
  • Armendáriz, I., Solernó, P., On the computation of the radical of polynomial complete intersection ideals (1995) Lecture Notes in Computer Science, 948, pp. 106-119. , in: G. Cohen, M. Giusti, T. Mora (Eds.), Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-11, Paris, 1995, Springer, Berlin
  • Berenstein, C., Struppa, D., Recent improvements in the complexity of the effective Nullstellensatz (1991) Linear Algebra Appl., 157, pp. 203-215
  • Berenstein, C., Yger, A., Bounds for the degrees in the division problem (1990) Mich. Math. J., 37, pp. 25-43
  • Berkowitz, S., On computing the determinant in small parallel time using a small number of processors (1984) Inform. Process. Lett., 18, pp. 147-150
  • Brownawell, D., Bounds for the degrees in the Nullstellensatz (1987) Ann. Math. Second Ser., 126 (3), pp. 577-591
  • Bürguisser, P., Clausen, M., Amin Shokrollahi, M., Algebraic Complexity Theory Grundlehren der Mathematischen Wissenschaften, 315, p. 1997. , Springer, Berlin
  • Caniglia, L., Cortiñas, G., Danón, S., Heintz, J., Krick, T., Solernó, P., Algorithmic aspects of Suslin's proof of Serre's Conjecture (1993) Comput. Complexity, 3, pp. 31-55
  • Caniglia, L., Galligo, A., Heintz, J., Some new effectivity bounds in computational geometry (1988) Lecture Notes Computer Science, 357, pp. 131-151. , Proceedings of 6th International Conference on Applied Algebra, Algebraic Algorithms and Error Correcting Codes, AAECC-6, Roma, Springer, Berlin
  • Caniglia, L., Guccione, J.A., Guccione, J.J., Local membership problems for polynomial ideals (1991) Effective Methods in Algebraic Geometry, MEGA 90, Progress in Mathematics, Vol. 94, pp. 31-45. , T. Mora, & C. Traverso. Basel: Birkhäuser
  • Coleff, N., Herrera, M., Les Courants Residuels Associés à une Forme Meromorphe (1978) Lecture Notes in Mathematics, 633. , Springer, Berlin
  • Demazure, M., Le monoïde de Mayr et Meyer (1984) Notes Informelles de Calcul Formel, , Ecole Polytechnique, Palaiseau
  • Dickenstein, A., Fitchas, N., Giusti, M., Sessa, C., The membership problem for unmixed polynomial ideals is solvable in single exponential time (1991) Discrete Appl. Math., 33, pp. 73-94
  • Dickenstein, A., Sessa, C., Duality methods for the membership problem (1990) Effective Methods in Algebraic Geometry, MEGA '90, Progress in Mathematics, Vol. 94, pp. 89-103. , T. Mora, & C. Traverso. Basel: Birkhäuser
  • Eisenbud, D., (1994) Commutative Algebra with a View Toward Algebraic Geometry, Graduate Texts in Mathematics, Vol. 150, , Berlin: Springer
  • Fitchas, N., Galligo, A., Nullstellensatz effectif et Conjecture de Serre (théorème de Quillen-Suslin) pour le Calcul Formel (1990) Math. Nachr., 149, pp. 231-253
  • Fitchas, N., Galligo, A., Morgenstern, J., Precise sequential and parallel bounds for quantifier elimination over algebraically closed fields (1990) J. Pure Appl. Algebra, 67, pp. 1-14
  • Fitchas, N., Giusti, M., Smietanski, F., Sur la complexité du théorème de zéros (1995) Proceedings of Second International Conference on Non-Linear Optimization and Approximation, Approximation and Optimization, 8, pp. 247-329. , in: J. Guddat et al. (Eds.), Approximation and Optimization in the Caribbean II, Peter Lange Verlag
  • Giusti, M., Heintz, J., Morais, J., Pardo, L., When polynomial equation systems can be "solved" fast? (1995) Lecture Notes in Computer Science, 948, pp. 205-231. , in: G. Cohen, M. Giusti, T. Mora (Eds.), Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-11, Paris, 1995, Springer, Berlin
  • Giusti, M., Heintz, J., Morais, J., Morgenstern, J., Pardo, L., Straight-line programs in geometric elimination theory (1998) J. Pure Applied Algebra, 124, pp. 101-146
  • Giusti, M., Heintz, J., Sabia, J., On the efficiency of effective Nullstellensatz (1993) Comput. Complexity, 3, pp. 56-95
  • Hägele, K., Morais, J.E., Pardo, L.M., Sombra, M., On the intrinsic complexity of the arithmetic Nullstellensatz (2000) J. Pure Appl. Algebra, 146, pp. 103-183
  • Hartshorne, R., (1966) Residues and Duality, Lecture Notes in Mathematics, Vol. 20, , Berlin: Springer
  • Heintz, J., Definability and fast quantifier elimination in algebraically closed fields (1983) Theoret. Comput. Sci., 24 (3), pp. 239-277
  • Heintz, J., Schnorr, C., Testing polynomials which are easy to compute (1982) Monographie de l'Enseignement Mathématique, 30, pp. 237-254. , in: Logic and Algorithmic, an International Symposium held in Honour of E. Specker, Genève
  • Iversen, B., Generic Local Structure in Commutative Algebra (1973) Lecture Notes in Mathmatics, 310. , Springer, Berlin
  • Kollár, J., Sharp effective Nullstellensatz (1988) J. Amer. Math. Soc., 1, pp. 963-975
  • Krick, T., Pardo, L., A computational method for diophantine approximation (1996) Progress in Mathematics, 143, pp. 193-253. , in: Effective Methods in Algebraic Geometry, MEGA '94 Birkhäuser, Basel
  • Kunz, E., (1985) Introduction to Commutative Algebra and Algebraic Geometry, , Basel: Birkhäuser
  • Kunz, E., (1986) Kähler Differentials, Adv. Lect. in Math., , Braunschweig: Vieweg
  • Logar, A., Sturmfels, B., Algorithms for Quillen-Suslin Theorem (1992) J. Algebra, 145, pp. 231-239
  • Lam, T., Serre's Conjecture (1978) Lecture Notes in Mathmatics, 635. , Springer, Berlin
  • Laudenbacher, R., Woodburn, C., An algorithm for the Quillen-Suslin theorem for monoid rings (1997) J. Pure Appl. Algebra, 117-118, pp. 395-429
  • Laudenbacher, R., Schlauch, K., (1999) An Algorithm for the Quillen-Suslin Theorem for Quotients of Polynomial Rings by Monomial Ideals, , Preprint
  • Matera, G., Probabilistic algorithms for geometric elimination (1999) Appl. Algebra in Eng., Communication and Comput. (AAECC J.), 9, pp. 463-520
  • Mayr, E., Meyer, A., The complexity of the word problem for commutative semigroups and polynomial ideals (1982) Adv. in Math., 46, pp. 305-329
  • Mulmuley, K., A fast parallel algorithm to compute the rank of a matrix over an arbitrary field (1986) Proceedings of 18th Annual ACM Symposium on Theory of Computing, pp. 338-339
  • Mumford, D., (1995) Algebraic Geometry I: Complex Projective Varieties, Class. in Mathematics, , Berlin: Springer
  • Philippon, P., Dénominateurs dans le théorème des zéros de Hilbert (1991) Acta. Arith., 58, pp. 1-25
  • 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
  • Rossi, F., Spangher, W., Some effective methods in the openness of loci for Cohen-Macaulay and Gorenstein properties (1990) Effective Methods in Algebraic Geometry, MEGA '90, Progress in Mathematics, Vol. 94, pp. 441-455. , T. Mora, & C. Traverso. Basel: Birkhäuser
  • Sabia, J., Solernó, P., Bounds for traces in complete intersections and degrees in the Nullstellensatz (1995) AAECC J., 6 (6), pp. 353-376
  • Shiffman, B., Degree bounds for the division problem in polynomial ideals (1989) Michigan Math. J., 36, pp. 163-171
  • Sombra, A., Bounds for the Hilbert function of polynomial ideal and for the degrees in the Nullstellensatz (1997) J. Pure Appl. Algebra, 117-118, pp. 565-599
  • Teissier, B., Résultats récents d'algèbre commutative effective (1991) Astérisque, 189-190, pp. 107-131. , Séminaire Bourbaki 1989-1990
  • Vasconcelos, W., (1998) Computational Methods in Commutative Algebra and Algebraic Geometry, Algorithms and Computations in Mathmatics, Vol. 2, , Berlin: Springer
  • Von Zur Gathen, J., Parallel arithmetic computations: A survey (1986) Lecture Notes in Computer Science, 233, pp. 93-112. , Proceedings of 13th Symposium on MFCS 1986 Springer, Berlin

Citas:

---------- APA ----------
Almeida, M., Blaum, M., D'Alfonso, L. & Solernó, P. (2001) . Computing bases of complete intersection rings in Noether position. Journal of Pure and Applied Algebra, 162(2-3), 127-170.
http://dx.doi.org/10.1016/S0022-4049(00)00135-3
---------- CHICAGO ----------
Almeida, M., Blaum, M., D'Alfonso, L., Solernó, P. "Computing bases of complete intersection rings in Noether position" . Journal of Pure and Applied Algebra 162, no. 2-3 (2001) : 127-170.
http://dx.doi.org/10.1016/S0022-4049(00)00135-3
---------- MLA ----------
Almeida, M., Blaum, M., D'Alfonso, L., Solernó, P. "Computing bases of complete intersection rings in Noether position" . Journal of Pure and Applied Algebra, vol. 162, no. 2-3, 2001, pp. 127-170.
http://dx.doi.org/10.1016/S0022-4049(00)00135-3
---------- VANCOUVER ----------
Almeida, M., Blaum, M., D'Alfonso, L., Solernó, P. Computing bases of complete intersection rings in Noether position. J. Pure Appl. Algebra. 2001;162(2-3):127-170.
http://dx.doi.org/10.1016/S0022-4049(00)00135-3