Navegar

Colección

Datos Estadísticas

Artículo

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) Computational Complexity. 3(1):31-55
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 F be a unimodular r×s matrix with entries being n-variate polynomials over an infinite field K. Denote by deg(F) the maximum of the degrees of the entries of F and let d=1+deg(F). We describe an algorithm which computes a unimodular s×s matrix M with deg(M)=(rd)O(n) such that FM=[Ir, O], where [Ir, O] denotes the r×s matrix obtained by adding to the r×r unit matrix Irs-r zero columns. We present the algorithm as an arithmetic network with inputs from K, and we count field operations and comparisons as unit cost. The sequential complexity of our algorithm amounts to {Mathematical expression} field operations and comparisons in K whereas its parallel complexity is O(n4r4log2(srd)). The complexity bounds and the degree bound for deg(M) mentioned above are optimal in order. Our algorithm is inspired by Suslin's proof of Serre's Conjecture. © 1993 Birkhäuser Verlag.

Registro:

Documento: Artículo
Título:Algorithmic aspects of Suslin's proof of Serre's conjecture
Autor:Caniglia, L.; Cortiñas, G.; Danón, S.; Heintz, J.; Krick, T.; Solernó, P.
Filiación:Departmento de Matemáticas, Fac. de Ciencias Exactas. Univ. de Buenos Aires, Buenos Aires, 1428, Argentina
Palabras clave:complexity; effective Nullstellensatz; linear equation systems over polynomial rings; Quillen-Suslin Theorem; Serre's Conjecture; Subject classifications: 68C25
Año:1993
Volumen:3
Número:1
Página de inicio:31
Página de fin:55
DOI: http://dx.doi.org/10.1007/BF01200406
Título revista:Computational Complexity
Título revista abreviado:Comput Complexity
ISSN:10163328
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_10163328_v3_n1_p31_Caniglia

Referencias:

  • Bayer, D., Stillman, M., On the complexity of computing syzygies (1988) Journal of Symbolic Computation, 6, pp. 135-147
  • Berkowitz, S., On computing the determinant in small parallel time using a small number of processors (1984) Inform. Processing Letters, 18, pp. 147-150
  • Brownawell, W.D., Bounds for the degree in the Nullstellensatz (1987) The Annals of Mathematics, 126 (3), pp. 577-591
  • Buchberger, B., Gröbner-Bases: an algorithmic method in polynomial ideal theory (1985) Multidimensional Systems Theory, pp. 184-232. , N. K., Bose, Reidel Publishing Company, Dordrecht
  • L. Caniglia, A. Galligo, and J. Heintz, Some new effectivity bounds in computational geometry, in Proc. 6-th Int. Conf. Applied Algebra, Algebraic Algorithmic and Error Correcting Codes (AAECC-6), T. Mora, ed., Springer LN Comp. Sci. 357 (1989), 131–151; L. Caniglia, J. A. Guccione, and J. J. Guccione, Local Membership Problems for Polynomial Ideals, in Effective Methods in Algebraic Geometry, T. Mora and C. Traverso, eds., Progress in Math. 94, Birkhäuser (1991), 31–45; F. Chaqui, Algorithme de calcul d'une base pour les modules projectifs sur K[X,Y] et ℤ[X], Thèse 3ème Cycle, Université Paris-Sud, Centre d'Orsay (1983); A. Chistov, Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic, in Proc. Int. Conf. FCT 1985, Springer LN Comp. Sci. 199 (1985), 63–69; Fitchas, N., Galligo, A., Nullstellensatz effectif et Conjecture de Serre (Théorème de Quillen-Suslin) pour le Calcul Formel (1990) Mathematische Nachrichten, 149, pp. 231-253
  • N. Fitchas, A. Galligo and J. Morgenstern, Algorithmes rapides en séquentiel et en parallèle pour l'élimination des quantificateurs en géométrie élémentaire, in F. Delon, M. Dickmann, D. Gondard (eds.), Séminaire Structures Algébriques Ordonnées: Sélection d'exposés 1986–1987. Publ. Université Paris VII 32 (1990), 103–145; Gantmacher, F.R., (1977) Teorya matrits. English version: The theory of matrices, Volume I, , Chelsea Publishing Company, New York
  • von zur Gathen, J., Parallel arithmetic computations: a survey (1986) Proc. 13-th Symp. MFCS 1986, Springer LN Comp. Sci., 233, pp. 93-112
  • Hermann, G., Die Frage der endlich vielen Schritte in der Theorie der Polynomideale (1926) Math. Ann., 95, pp. 736-788
  • Kollár, J., Sharp effective Nullstellensatz (1988) Journal of the American Mathematical Society, 1, pp. 963-975
  • E. Kunz, Einführnug in die kommutative Algebra und algebraische Geometrie, F. Vieweg und Söhne, Braunschweig-Wiesbaden (1980); T. Y. Lam, Serre's Conjecture, Springer LN Math. 635 Springer-Verlag (1978); Logar, A., Sturmfels, B., Algorithms for Quillen-Suslin Theorem (1992) J. Algebra, 145, pp. 231-239
  • Mayr, E., Meyer, A., The complexity of the word problem for commutative semigroups and polynomial ideals (1982) Advances in Math., 46, pp. 305-329
  • K. Mulmuley, A fast parallel algorithm to compute the rank of a matrix over an arbitrary field, Proc. 18-th Ann. ACM Symp. Theory of Comput. (1986), 338–339; P. Philippon, Théorème des zéros effectif d'après J.Kollár, Probl. Dioph. 1988–89, Publ. Math. Univ. Paris VI 88 (1988); Seidenberg, S., Constructions in Algebra (1974) Transactions of the American Mathematical Society, 197, pp. 273-313
  • Serre, J.P., Faisceaux algébriques cohérents (1955) Amer. Math., 61, pp. 191-274
  • Teissier, B., Résultats récents d'algèbre commutative effective (1991) Séminaire Bourbaki, 189-190, pp. 107-131

Citas:

---------- APA ----------
Caniglia, L., Cortiñas, G., Danón, S., Heintz, J., Krick, T. & Solernó, P. (1993) . Algorithmic aspects of Suslin's proof of Serre's conjecture. Computational Complexity, 3(1), 31-55.
http://dx.doi.org/10.1007/BF01200406
---------- CHICAGO ----------
Caniglia, L., Cortiñas, G., Danón, S., Heintz, J., Krick, T., Solernó, P. "Algorithmic aspects of Suslin's proof of Serre's conjecture" . Computational Complexity 3, no. 1 (1993) : 31-55.
http://dx.doi.org/10.1007/BF01200406
---------- MLA ----------
Caniglia, L., Cortiñas, G., Danón, S., Heintz, J., Krick, T., Solernó, P. "Algorithmic aspects of Suslin's proof of Serre's conjecture" . Computational Complexity, vol. 3, no. 1, 1993, pp. 31-55.
http://dx.doi.org/10.1007/BF01200406
---------- VANCOUVER ----------
Caniglia, L., Cortiñas, G., Danón, S., Heintz, J., Krick, T., Solernó, P. Algorithmic aspects of Suslin's proof of Serre's conjecture. Comput Complexity. 1993;3(1):31-55.
http://dx.doi.org/10.1007/BF01200406