Computing bases of complete intersection rings in Noether position

Let k be an effective infinite perfect field, k[x1,...,xn] the polynomial ring in n variables and F∈k[x1,...,xn]M×M a square polynomial matrix verifying F2=F. Suppose that the entries of F are polynomials given by a straight-line program of size L and their total degrees are bounded by an integer D....

Descripción completa

Guardado en:
Detalles Bibliográficos
Publicado: 2001
Materias:
13C10
13P10
68Q40
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00224049_v162_n2-3_p127_Almeida
http://hdl.handle.net/20.500.12110/paper_00224049_v162_n2-3_p127_Almeida
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_00224049_v162_n2-3_p127_Almeida
record_format dspace
spelling paper:paper_00224049_v162_n2-3_p127_Almeida2023-06-08T14:50:35Z Computing bases of complete intersection rings in Noether position 13C10 13P10 68Q40 Let k be an effective infinite perfect field, k[x1,...,xn] the polynomial ring in n variables and F∈k[x1,...,xn]M×M a square polynomial matrix verifying F2=F. Suppose that the entries of F are polynomials given by a straight-line program of size L and their total degrees are bounded by an integer D. We show that there exists a well parallelizable 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 exponential algorithm to compute a basis of a complete intersection ring in Noether position. More precisely, let f1,...,fn-r∈k[x1,...,xn] be a regular sequence of polynomials given by a slp of size ℓ, whose degrees are bounded by d. Let Rk[x1,...,xr] and Sk[x1,...,xn]/(f1,...,fn-r) such that S is integral over R; we show that there exists an algorithm running in time O(n)ℓdO(n2) which computes a basis of S over R. Also, as a consequence of our techniques, we show a single exponential well parallelizable algorithm which decides the freeness of a finite k[x1,...,xn]-module given by a presentation matrix, and in the affirmative case it computes a basis. © 2001 Elsevier Science B.V. 2001 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00224049_v162_n2-3_p127_Almeida http://hdl.handle.net/20.500.12110/paper_00224049_v162_n2-3_p127_Almeida
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic 13C10
13P10
68Q40
spellingShingle 13C10
13P10
68Q40
Computing bases of complete intersection rings in Noether position
topic_facet 13C10
13P10
68Q40
description Let k be an effective infinite perfect field, k[x1,...,xn] the polynomial ring in n variables and F∈k[x1,...,xn]M×M a square polynomial matrix verifying F2=F. Suppose that the entries of F are polynomials given by a straight-line program of size L and their total degrees are bounded by an integer D. We show that there exists a well parallelizable 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 exponential algorithm to compute a basis of a complete intersection ring in Noether position. More precisely, let f1,...,fn-r∈k[x1,...,xn] be a regular sequence of polynomials given by a slp of size ℓ, whose degrees are bounded by d. Let Rk[x1,...,xr] and Sk[x1,...,xn]/(f1,...,fn-r) such that S is integral over R; we show that there exists an algorithm running in time O(n)ℓdO(n2) which computes a basis of S over R. Also, as a consequence of our techniques, we show a single exponential well parallelizable algorithm which decides the freeness of a finite k[x1,...,xn]-module given by a presentation matrix, and in the affirmative case it computes a basis. © 2001 Elsevier Science B.V.
title Computing bases of complete intersection rings in Noether position
title_short Computing bases of complete intersection rings in Noether position
title_full Computing bases of complete intersection rings in Noether position
title_fullStr Computing bases of complete intersection rings in Noether position
title_full_unstemmed Computing bases of complete intersection rings in Noether position
title_sort computing bases of complete intersection rings in noether position
publishDate 2001
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00224049_v162_n2-3_p127_Almeida
http://hdl.handle.net/20.500.12110/paper_00224049_v162_n2-3_p127_Almeida
_version_ 1768543933942464512

Ejemplares similares