Algorithmic aspects of Suslin's proof of Serre's conjecture
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 [...
Guardado en:
| Publicado: |
1993
|
|---|---|
| Materias: | |
| Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_10163328_v3_n1_p31_Caniglia http://hdl.handle.net/20.500.12110/paper_10163328_v3_n1_p31_Caniglia |
| Aporte de: |
| id |
paper:paper_10163328_v3_n1_p31_Caniglia |
|---|---|
| record_format |
dspace |
| spelling |
paper:paper_10163328_v3_n1_p31_Caniglia2023-06-08T15:59:48Z Algorithmic aspects of Suslin's proof of Serre's conjecture complexity effective Nullstellensatz linear equation systems over polynomial rings Quillen-Suslin Theorem Serre's Conjecture Subject classifications: 68C25 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. 1993 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_10163328_v3_n1_p31_Caniglia http://hdl.handle.net/20.500.12110/paper_10163328_v3_n1_p31_Caniglia |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-134 |
| collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
| topic |
complexity effective Nullstellensatz linear equation systems over polynomial rings Quillen-Suslin Theorem Serre's Conjecture Subject classifications: 68C25 |
| spellingShingle |
complexity effective Nullstellensatz linear equation systems over polynomial rings Quillen-Suslin Theorem Serre's Conjecture Subject classifications: 68C25 Algorithmic aspects of Suslin's proof of Serre's conjecture |
| topic_facet |
complexity effective Nullstellensatz linear equation systems over polynomial rings Quillen-Suslin Theorem Serre's Conjecture Subject classifications: 68C25 |
| description |
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. |
| title |
Algorithmic aspects of Suslin's proof of Serre's conjecture |
| title_short |
Algorithmic aspects of Suslin's proof of Serre's conjecture |
| title_full |
Algorithmic aspects of Suslin's proof of Serre's conjecture |
| title_fullStr |
Algorithmic aspects of Suslin's proof of Serre's conjecture |
| title_full_unstemmed |
Algorithmic aspects of Suslin's proof of Serre's conjecture |
| title_sort |
algorithmic aspects of suslin's proof of serre's conjecture |
| publishDate |
1993 |
| url |
https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_10163328_v3_n1_p31_Caniglia http://hdl.handle.net/20.500.12110/paper_10163328_v3_n1_p31_Caniglia |
| _version_ |
1768541762225176576 |