On the time-space complexity of geometric elimination procedures
In [25] and [22] a new algorithmic concept was introduced for the symbolic solution of a zero dimensional complete intersection polynomial equation system satisfying a certain generic smoothness condition. The main innovative point of this algorithmic concept consists in the introduction of a new ge...
Guardado en:
| Autor principal: | |
|---|---|
| Publicado: |
2001
|
| Materias: | |
| Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_09381279_v11_n4_p239_Heintz http://hdl.handle.net/20.500.12110/paper_09381279_v11_n4_p239_Heintz |
| Aporte de: |
| id |
paper:paper_09381279_v11_n4_p239_Heintz |
|---|---|
| record_format |
dspace |
| spelling |
paper:paper_09381279_v11_n4_p239_Heintz2023-06-08T15:53:21Z On the time-space complexity of geometric elimination procedures Matera, Guillermo Algebraic complexity theory Algorithmic elimination theory Computation tree Polynomial equation solving Straight-line program Symbolic computation Time-space complexity Algorithms Computational complexity Mathematical models Mathematical programming Matrix algebra Polynomials Theorem proving Trees (mathematics) Algebraic complexity theory Algorithmic elimination theory Computation tree Geometric elimination procedures Straight line program Symbolic computation Time space complexity Geometry In [25] and [22] a new algorithmic concept was introduced for the symbolic solution of a zero dimensional complete intersection polynomial equation system satisfying a certain generic smoothness condition. The main innovative point of this algorithmic concept consists in the introduction of a new geometric invariant, called the degree of the input system, and the proof that the most common elimination problems have time complexity which is polynomial in this degree and the length of the input. In this paper we apply this algorithmic concept in order to exhibit an elimination procedure whose space complexity is only quadratic and its time complexity is only cubic in the degree of the input system. Fil:Matera, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2001 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_09381279_v11_n4_p239_Heintz http://hdl.handle.net/20.500.12110/paper_09381279_v11_n4_p239_Heintz |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-134 |
| collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
| topic |
Algebraic complexity theory Algorithmic elimination theory Computation tree Polynomial equation solving Straight-line program Symbolic computation Time-space complexity Algorithms Computational complexity Mathematical models Mathematical programming Matrix algebra Polynomials Theorem proving Trees (mathematics) Algebraic complexity theory Algorithmic elimination theory Computation tree Geometric elimination procedures Straight line program Symbolic computation Time space complexity Geometry |
| spellingShingle |
Algebraic complexity theory Algorithmic elimination theory Computation tree Polynomial equation solving Straight-line program Symbolic computation Time-space complexity Algorithms Computational complexity Mathematical models Mathematical programming Matrix algebra Polynomials Theorem proving Trees (mathematics) Algebraic complexity theory Algorithmic elimination theory Computation tree Geometric elimination procedures Straight line program Symbolic computation Time space complexity Geometry Matera, Guillermo On the time-space complexity of geometric elimination procedures |
| topic_facet |
Algebraic complexity theory Algorithmic elimination theory Computation tree Polynomial equation solving Straight-line program Symbolic computation Time-space complexity Algorithms Computational complexity Mathematical models Mathematical programming Matrix algebra Polynomials Theorem proving Trees (mathematics) Algebraic complexity theory Algorithmic elimination theory Computation tree Geometric elimination procedures Straight line program Symbolic computation Time space complexity Geometry |
| description |
In [25] and [22] a new algorithmic concept was introduced for the symbolic solution of a zero dimensional complete intersection polynomial equation system satisfying a certain generic smoothness condition. The main innovative point of this algorithmic concept consists in the introduction of a new geometric invariant, called the degree of the input system, and the proof that the most common elimination problems have time complexity which is polynomial in this degree and the length of the input. In this paper we apply this algorithmic concept in order to exhibit an elimination procedure whose space complexity is only quadratic and its time complexity is only cubic in the degree of the input system. |
| author |
Matera, Guillermo |
| author_facet |
Matera, Guillermo |
| author_sort |
Matera, Guillermo |
| title |
On the time-space complexity of geometric elimination procedures |
| title_short |
On the time-space complexity of geometric elimination procedures |
| title_full |
On the time-space complexity of geometric elimination procedures |
| title_fullStr |
On the time-space complexity of geometric elimination procedures |
| title_full_unstemmed |
On the time-space complexity of geometric elimination procedures |
| title_sort |
on the time-space complexity of geometric elimination procedures |
| publishDate |
2001 |
| url |
https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_09381279_v11_n4_p239_Heintz http://hdl.handle.net/20.500.12110/paper_09381279_v11_n4_p239_Heintz |
| work_keys_str_mv |
AT materaguillermo onthetimespacecomplexityofgeometriceliminationprocedures |
| _version_ |
1768543759876751360 |