Algorithmic aspects of Suslin's proof of Serre's conjecture

LetF be a unimodularr×s matrix with entries beingn-variate polynomials over an infinite fieldK. Denote by deg(F) the maximum of the degrees of the entries ofF and letd=1+deg(F). We describe an algorithm which computes a unimodulars×s matrixM with deg(M)=(rd) ^O(n) such thatFM=I _r ,O], where I _r ,O] denotes ther×s matrix obtained by adding to ther×r unit matrixI _r s–r zero columns.We present the algorithm as an arithmetic network with inputs fromK, and we count field operations and comparisons as unit cost.The sequential complexity of our algorithm amounts to field operations and comparisons inK whereas its parallel complexity isO(n ⁴ r ⁴log²(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.