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:
| Autores principales: | , , , , , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_10163328_v3_n1_p31_Caniglia |
| Aporte de: |
| id |
todo:paper_10163328_v3_n1_p31_Caniglia |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_10163328_v3_n1_p31_Caniglia2023-10-03T15:56:21Z Algorithmic aspects of Suslin's proof of Serre's conjecture Caniglia, L. Cortiñas, G. Danón, S. Heintz, J. Krick, T. Solernó, P. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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 Caniglia, L. Cortiñas, G. Danón, S. Heintz, J. Krick, T. Solernó, P. 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. |
| format |
JOUR |
| author |
Caniglia, L. Cortiñas, G. Danón, S. Heintz, J. Krick, T. Solernó, P. |
| author_facet |
Caniglia, L. Cortiñas, G. Danón, S. Heintz, J. Krick, T. Solernó, P. |
| author_sort |
Caniglia, L. |
| 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 |
| url |
http://hdl.handle.net/20.500.12110/paper_10163328_v3_n1_p31_Caniglia |
| work_keys_str_mv |
AT caniglial algorithmicaspectsofsuslinsproofofserresconjecture AT cortinasg algorithmicaspectsofsuslinsproofofserresconjecture AT danons algorithmicaspectsofsuslinsproofofserresconjecture AT heintzj algorithmicaspectsofsuslinsproofofserresconjecture AT krickt algorithmicaspectsofsuslinsproofofserresconjecture AT solernop algorithmicaspectsofsuslinsproofofserresconjecture |
| _version_ |
1807323067023622144 |