Navegar

Colección

Datos Estadísticas

Artículo

Grimson, R.; Heintz, J.; Kuijpers, B. "Evaluating geometric queries using few arithmetic operations" (2012) Applicable Algebra in Engineering, Communications and Computing. 23(3-4):179-193
Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

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.

Registro:

Documento: Artículo
Título:Evaluating geometric queries using few arithmetic operations
Autor:Grimson, R.; Heintz, J.; Kuijpers, B.
Filiación:Departamento de Matemática, Universidad de Buenos Aires, CONICET, Ciudad Universitaria, Pab. I, 1428 Buenos Aires, Argentina
Departamento de Computación, Universidad de Buenos Aires, CONICET, Ciudad Universitaria, Pab. I, 1428 Buenos Aires, Argentina
Departamento de Matemáticas, Estadística y Computacíon, Facultad de Ciencias, Universidad de Cantabria, Avda. de los Castros s/n, 39005 Santander, Spain
Database and Theoretical Computer Science Research Group, Hasselt University, Agoralaan, Gebouw D, 3590 Diepenbeek, Belgium
Palabras clave: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
Año:2012
Volumen:23
Número:3-4
Página de inicio:179
Página de fin:193
DOI: http://dx.doi.org/10.1007/s00200-012-0172-x
Título revista:Applicable Algebra in Engineering, Communications and Computing
Título revista abreviado:Appl Algebra Eng Commun Comput
ISSN:09381279
CODEN:AAECE
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_09381279_v23_n3-4_p179_Grimson

Referencias:

  • Basu, S., Pollack, R., Roy, M.F., On the combinatorial and algebraic complexity of quantifier elimination (1994) IEEE Symposium on Foundations of Computer Science, pp. 632-641
  • Basu, S., Pollack, R., Roy, M.F., Algorithms in real algebraic geometry (2006) Algorithms and Computation in Mathematics, 10. , 2nd edn. Springer, Secaucus, NJ, USA
  • Bost, J.B., Gillet, H., Soulé, C., Heights of projective varieties and positive Green forms (1994) J. Am.Math. Soc., 7, pp. 903-1027
  • Bürgisser, P., Clausen, M., Shokrollahi, M.A., (1997) Algebraic Complexity Theory Grundlehren der Mathematischen Wissenschaften, , Springer, New York
  • Charbit, P., Jeandel, E., Koiran, P., Perifel, S., Thomasse, S., Finding a vector orthogonal to roughly half a collection of vectors (2008) Journal of Complexity, 24 (1), pp. 39-53. , DOI 10.1016/j.jco.2006.09.005, PII S0885064X0700057X
  • Dickenstein, A., Fitchas, N., Giusti, M., Sessa, C., The membership problem for unmixed polynomial ideals is solvable in single exponential time (1991) Discret. Appl. Math., 33, pp. 73-94
  • Fulton, W., Intersection theory (1984) Ergebnisse der Mathematik, (3). , 2nd edn., Springer, New York
  • Grigoriev, D., Topological complexity of the range searching (2000) J. Complex., 16 (1), pp. 50-53
  • Grimson, R., Heintz, J., Kuijpers, B., Efficient evaluation of specific queries in constraint databases (2011) Inf. Process. Lett., 111 (19), pp. 941-944
  • Heintz, J., Definability and fast quantifier elimination over algebraically closed fields (1983) Theor. Comput. Sci., 24, pp. 239-277
  • Heintz, J., Kuijpers, B., Rojas Paredes, A., Software engineering and complexity in effective algebraic geometry (2012) J. Complex., , doi:10.1016/j.jco.2012.04.005
  • Knuth, D.E., (1998) Art of Computer Programming, Vol. 3: Sorting and Searching, , 2nd edn. Addison-Wesley Professional, New York
  • Koiran, P., Perifel, S., VPSPACE and a transfer theorem over the reals (2009) Comput. Complex., 18 (4), pp. 551-575
  • Krick, T., Pardo, L.M., A computational method for diophantine approximation, algorithms in algebraic geometry and applications (1996) Progress in Mathematics, 143, pp. 193-254. , González-Vega, L., Recio, T. (eds.) Proceedings of MEGA'94. Birkhäuser Verlag, Basel
  • Kuper, G., Libkin, L., Paredaens, J., (2000) Constraint Databases, , Springer, New York
  • Meiser, S., Point location in arrangements of hyperplanes (1993) Inf. Comput., 106 (2), pp. 286-303
  • Meyerauf Der Heide, F., A polynomial linear search algorithm for the n-dimensional knapsack problem (1984) J. ACM, 31 (3), pp. 668-676
  • Meyerauf Der Heide, F., Fast algorithms for n-dimensional restrictions of hard problems (1988) J. ACM, 35 (3), pp. 740-747
  • Mignotte, M., (1992) Mathematics for Computer Algebra, , Springer, New York
  • Philippon, P., Sur des hauteurs alternatives, I (1991) Math. Ann., 289, pp. 255-283
  • Philippon, P., Sur des hauteurs alternatives, II (1994) Ann. Inst. Fourier, 44 (2), pp. 1043-1065. , Grenoble
  • Philippon, P., Sur des hauteurs alternatives, III (1995) J. Math. Pures Appl., 74, pp. 345-365
  • Shafarevich, I.R., (1974) Basic Algebraic Geometry, , Springer, New York
  • Strassen, V., Algebraic complexity theory Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A), pp. 633-672
  • Vogel, W., (1984) Results on Bézout's Theorem Tata Institute of Fundamental Research, , Springer, New York

Citas:

---------- APA ----------
Grimson, R., Heintz, J. & Kuijpers, B. (2012) . Evaluating geometric queries using few arithmetic operations. Applicable Algebra in Engineering, Communications and Computing, 23(3-4), 179-193.
http://dx.doi.org/10.1007/s00200-012-0172-x
---------- CHICAGO ----------
Grimson, R., Heintz, J., Kuijpers, B. "Evaluating geometric queries using few arithmetic operations" . Applicable Algebra in Engineering, Communications and Computing 23, no. 3-4 (2012) : 179-193.
http://dx.doi.org/10.1007/s00200-012-0172-x
---------- MLA ----------
Grimson, R., Heintz, J., Kuijpers, B. "Evaluating geometric queries using few arithmetic operations" . Applicable Algebra in Engineering, Communications and Computing, vol. 23, no. 3-4, 2012, pp. 179-193.
http://dx.doi.org/10.1007/s00200-012-0172-x
---------- VANCOUVER ----------
Grimson, R., Heintz, J., Kuijpers, B. Evaluating geometric queries using few arithmetic operations. Appl Algebra Eng Commun Comput. 2012;23(3-4):179-193.
http://dx.doi.org/10.1007/s00200-012-0172-x