Computing bases of complete intersection rings in Noether position

Let k be an effective infinite perfect field, k[x(l),...,x(n)] the polynomi al ring in n variables and F is an element of k[x(l),...,x(n)](MXM) a squar e polynomial matrix verifying F-2 = F. Suppose that the entries of F are po lynomials given by a straight-line program of size L and their total degree s are bounded by an integer D. We show that there exists a well paralleliza ble algorithm which computes bases of the kernel and the image of F in time (nL)(O(1))(MD)(O(n)). By means of this result we obtain a single exponenti al algorithm to compute a basis of a complete intersection ring in Noether position. More precisely, let fl,...,fn-r is an element of k[x(l),...,x(n)] be a regular sequence of polynomials given by a slp of size l, whose degre es are bounded by d. Let R:=k[x(l),...,x(r)] and such that S is integral ov er R; we show that there exists an algorithm running in time O (n)ld(O(n2)) which computes a basis of S over R. Also, as a consequence of our techniqu es, we show a single exponential well parallelizable algorithm which decide s the freeness of a finite k[x(l),...,x(n)]-module given by a presentation matrix, and in the affirmative case it computes a basis. (C) 2001 Elsevier Science B.V. All rights reserved.