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: |
| Sumario: | 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. |
|---|