Evaluating geometric queries using few arithmetic operations
Let ℘ := (P1,..., Ps) be a given family of n-variate polynomials with integer coefficients and suppose that the degrees and logarithmic heights of these polynomials are bounded by d and h, respectively. Suppose furthermore that for each 1 ≤i ≤ s the polynomial Pi can be evaluated using L arithmetic...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_09381279_v23_n3-4_p179_Grimson |
| Aporte de: |
| id |
todo:paper_09381279_v23_n3-4_p179_Grimson |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_09381279_v23_n3-4_p179_Grimson2023-10-03T15:48:45Z Evaluating geometric queries using few arithmetic operations Grimson, R. Heintz, J. Kuijpers, B. Computational complexity Consistency of polynomial equation systems Constraint database Query evaluation Algebraic computations Arithmetic operations Constraint Databases Exponential numbers Geometric queries Integer coefficient Polynomial equation Polynomial equation system Query evaluation Real number Computational complexity Polynomials Trees (mathematics) Query processing Let ℘ := (P1,..., Ps) be a given family of n-variate polynomials with integer coefficients and suppose that the degrees and logarithmic heights of these polynomials are bounded by d and h, respectively. Suppose furthermore that for each 1 ≤i ≤ s the polynomial Pi can be evaluated using L arithmetic operations (additions, subtractions, multiplications and the constants 0 and 1). Assume that the family ℘ is in a suitable sense generic. We construct a database (script D sign), supported by an algebraic computation tree, such that for each x ∈ [0, 1]n the query for the signs of P1(x),..., Ps(x) can be answered using hd(script O sign)(n2) comparisons and nL arithmetic operations between real numbers. The arithmetic-geometric tools developed for the construction of (script D sign) are then employed to exhibit example classes of systems of n polynomial equations in n unknowns whose consistency may be checked using only few arithmetic operations, admitting, however, an exponential number of comparisons. © Springer-Verlag 2012. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_09381279_v23_n3-4_p179_Grimson |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-134 |
| collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
| topic |
Computational complexity Consistency of polynomial equation systems Constraint database Query evaluation Algebraic computations Arithmetic operations Constraint Databases Exponential numbers Geometric queries Integer coefficient Polynomial equation Polynomial equation system Query evaluation Real number Computational complexity Polynomials Trees (mathematics) Query processing |
| spellingShingle |
Computational complexity Consistency of polynomial equation systems Constraint database Query evaluation Algebraic computations Arithmetic operations Constraint Databases Exponential numbers Geometric queries Integer coefficient Polynomial equation Polynomial equation system Query evaluation Real number Computational complexity Polynomials Trees (mathematics) Query processing Grimson, R. Heintz, J. Kuijpers, B. Evaluating geometric queries using few arithmetic operations |
| topic_facet |
Computational complexity Consistency of polynomial equation systems Constraint database Query evaluation Algebraic computations Arithmetic operations Constraint Databases Exponential numbers Geometric queries Integer coefficient Polynomial equation Polynomial equation system Query evaluation Real number Computational complexity Polynomials Trees (mathematics) Query processing |
| description |
Let ℘ := (P1,..., Ps) be a given family of n-variate polynomials with integer coefficients and suppose that the degrees and logarithmic heights of these polynomials are bounded by d and h, respectively. Suppose furthermore that for each 1 ≤i ≤ s the polynomial Pi can be evaluated using L arithmetic operations (additions, subtractions, multiplications and the constants 0 and 1). Assume that the family ℘ is in a suitable sense generic. We construct a database (script D sign), supported by an algebraic computation tree, such that for each x ∈ [0, 1]n the query for the signs of P1(x),..., Ps(x) can be answered using hd(script O sign)(n2) comparisons and nL arithmetic operations between real numbers. The arithmetic-geometric tools developed for the construction of (script D sign) are then employed to exhibit example classes of systems of n polynomial equations in n unknowns whose consistency may be checked using only few arithmetic operations, admitting, however, an exponential number of comparisons. © Springer-Verlag 2012. |
| format |
JOUR |
| author |
Grimson, R. Heintz, J. Kuijpers, B. |
| author_facet |
Grimson, R. Heintz, J. Kuijpers, B. |
| author_sort |
Grimson, R. |
| title |
Evaluating geometric queries using few arithmetic operations |
| title_short |
Evaluating geometric queries using few arithmetic operations |
| title_full |
Evaluating geometric queries using few arithmetic operations |
| title_fullStr |
Evaluating geometric queries using few arithmetic operations |
| title_full_unstemmed |
Evaluating geometric queries using few arithmetic operations |
| title_sort |
evaluating geometric queries using few arithmetic operations |
| url |
http://hdl.handle.net/20.500.12110/paper_09381279_v23_n3-4_p179_Grimson |
| work_keys_str_mv |
AT grimsonr evaluatinggeometricqueriesusingfewarithmeticoperations AT heintzj evaluatinggeometricqueriesusingfewarithmeticoperations AT kuijpersb evaluatinggeometricqueriesusingfewarithmeticoperations |
| _version_ |
1807324485557157888 |