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: |
| Sumario: | 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. |
|---|