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....
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_00224049_v162_n2-3_p127_Almeida |
| Aporte de: |
| id |
todo:paper_00224049_v162_n2-3_p127_Almeida |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_00224049_v162_n2-3_p127_Almeida2023-10-03T14:32:37Z Computing bases of complete intersection rings in Noether position Almeida, M. Blaum, M. D'Alfonso, L. Solernó, P. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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 Almeida, M. Blaum, M. D'Alfonso, L. Solernó, P. 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. |
| format |
JOUR |
| author |
Almeida, M. Blaum, M. D'Alfonso, L. Solernó, P. |
| author_facet |
Almeida, M. Blaum, M. D'Alfonso, L. Solernó, P. |
| author_sort |
Almeida, M. |
| 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 |
| url |
http://hdl.handle.net/20.500.12110/paper_00224049_v162_n2-3_p127_Almeida |
| work_keys_str_mv |
AT almeidam computingbasesofcompleteintersectionringsinnoetherposition AT blaumm computingbasesofcompleteintersectionringsinnoetherposition AT dalfonsol computingbasesofcompleteintersectionringsinnoetherposition AT solernop computingbasesofcompleteintersectionringsinnoetherposition |
| _version_ |
1807318175520391168 |