Computing bases of complete intersection rings in Noether position

DOI10.1016/S0022-4049(00)00135-3MaRDI QIDQ5946450zbMATH OpenFDO

Authors Marcela Almeida, Manuela Blaum, Lisi D'Alfonso, Pablo Solernó

Publication date 3 February 2004

Published in Journal of Pure and Applied Algebra (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0022-4049(00)00135-3

computing bases for complete intersection rings computing bases of free modules Noether position Quillen-Suslin theorem

Software, source code, etc. for problems pertaining to commutative algebra (13-04) Projective and free modules and ideals in commutative rings (13C10) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Parallel algorithms in computer science (68W10)

Review text

Assume that \(k\) is an effective infinite perfect field. The aim of the paper is to compute bases of certain free modules over the ring of polynomials \(k[x_1,\dots, x_n]\) and to give a uniform setting to the solution of the problems (which, in some cases, can already be found in the literature). Among the results of the paper we have: Let \(F\) be an \(M \times M\) matrix with polynomial entries such that \(F^2=F\) (i.e. \(F\) is a linear projection), assume that the degrees of the entries of \(F\) are bounded by an integer \(D\) and are given by a straight-line program of size \(L\). Then there exists a well parallelizable algorithm which computes (in sequential time \((nL)^{O(1)}(MD)^{O(n)})\) two subsets of \(k[x_1,\dots,x_n]^M\): \(\{v_1,\dots,v_s\}\) and \(\{v_{s+1}, \dots,v_M\}\) such that: (1) \(\{v_1,\dots,v_M\}\) is a basis of \(k[x_1,\dots,x_n]^M\); (2) \(\{v_1,\dots,v_s\}\) is a basis of \(\text{Im}(F)\) and \(\{v_{s+1},\dots,v_M\}\) is a basis of \(\text{Ker}(F)\). Moreover the entries of \(v_1,\dots,v_M\) are bounded in degree by \((MD)^{O(n)}\). Furthermore, given a finitely generated module \(P\) over the polynomial ring, the authors show that there exists a single exponential algorithm which decides if \(P\) is free and in the affirmative case, computes a free basis of it. The above result can be used to compute bases for complete intersection rings in Noether position. More precisely: Let \(f_1,\dots, f_{n-r} \in k[x_1,\dots,x_n]\) be a regular sequence of polynomials of degrees bounded by an integer \(d\) and given by a straight-line program of size \(l\), such that the canonical morphism \( k[x_1,\dots,x_r] \rightarrow S:=k[x_1,\dots,x_n]/( f_1,\dots,f_{n-r})\) is injective and integral, then there exists a single exponential algorithm which computes a basis of \(S\) as a free \( k[x_1,\dots,x_r]\)-module. The proposed algorithm is well parallelizable.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Computing bases of complete intersection rings in Noether position

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5946450)