| Autor: |
Amir Hashemi, Benyamin M.-Alizadeh |
| Rok vydání: |
2020 |
| Předmět: |
|
| Zdroj: |
Theoretical Computer Science. 842:50-64 |
| ISSN: |
0304-3975 |
| DOI: |
10.1016/j.tcs.2020.07.025 |
| Popis: |
In this paper, we address the problem of transforming an ideal into normal position. We present a deterministic algorithm (based on linear algebra techniques) that finds a suitable linear change of variables to transform a given zero-dimensional (not necessarily radical) ideal into normal position. The main idea of this algorithm is to achieve this position via a sequence of elementary linear changes; i.e. each change involves only two variables. Furthermore we give complete complexity analysis of all the algorithms described in this paper based on a sharp upper bound for the maximal number of required elementary linear changes in the special case of the bi-variate polynomial ideal. As an application of this investigation, we conclude the paper by giving a sharper complexity bound for computing a primary decomposition for a zero-dimensional ideal. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect