Navegar

Colección

Datos Estadísticas

Artículo

Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

Let V be a closed algebraic subvariety of the n-dimensional projective space over the complex or real numbers and suppose that V is non-empty and equidimensional. The classic notion of a polar variety of V associated with a given linear subvariety of the ambient space of V was generalized and motivated in Bank et al. (Kybernetika 40 (2004), to appear). As particular instances of this notion of a generalized polar variety one reobtains the classic one and an alternative type of a polar variety, called dual. As main result of the present paper we show that for a generic choice of their parameters the generalized polar varieties of V are empty or equidimensional and smooth in any regular point of V. In the case that the variety V is affine and smooth and has a complete intersection ideal of definition, we are able, for a generic parameter choice, to describe locally the generalized polar varieties of V by explicit equations. Finally, we indicate how this description may be used in order to design in the context of algorithmic elimination theory a highly efficient, probabilistic elimination procedure for the following task: In case, that the variety V is ℚ-definable and affine, having a complete intersection ideal of definition, and that the real trace of V is non-empty and smooth, find for each connected component of the real trace of V an algebraic sample point. © 2005 Elsevier Inc. All rights reserved.

Registro:

Documento: Artículo
Título:Generalized polar varieties: Geometry and algorithms
Autor:Bank, B.; Giusti, M.; Heintz, J.; Pardo, L.M.
Filiación:Humboldt-Universität zu Berlin, Institut für Mathematik, 10099 Berlin, Germany
Laboratoire STIX, École Polytechnique, 91228 Palaiseau Cedex, France
Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, 1428 Buenos Aires, Argentina
Departamento de Matemáticas, Estadística y Computación, Facultad de Ciencias, Universidad de Cantabria, 39071 Santander, Spain
Palabras clave:Arithmetic circuit; Arithmetic network; Complexity; Elimination procedure; Geometric degree; Geometry of polar varieties and its generalizations; Real polynomial equation solving; Algorithms; Computational complexity; Digital arithmetic; Matrix algebra; Polynomials; Probability; Theorem proving; Vectors; Arithmetic circuit; Arithmetic network; Elimination procedure; Geometric degree; Real polynomial equation solving; Computational geometry
Año:2005
Volumen:21
Número:4
Página de inicio:377
Página de fin:412
DOI: http://dx.doi.org/10.1016/j.jco.2004.10.001
Título revista:Festschrift for the 70th Birthday of Arnold Schonhage
Título revista abreviado:J. Complexity
ISSN:0885064X
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_0885064X_v21_n4_p377_Bank.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0885064X_v21_n4_p377_Bank

Referencias:

  • Aubry, P., Rouillier, F., Safey El Din, M., Real solving for positive dimensional systems (2002) J. Symbolic Comput., 34 (6), pp. 543-560
  • Bank, B., Giusti, M., Heintz, J., Mbakop, G.M., Polar varieties, real equation solving and data structures: The hypersurface case (1997) J. Complexity, 13 (1), pp. 5-27
  • Bank, B., Giusti, M., Heintz, J., Mbakop, G.M., Polar varieties and efficient real elimination (2001) Math. Z., 238, pp. 115-144
  • Bank, B., Giusti, M., Heintz, J., Pardo, L.M., Generalized polar varieties and an efficient real elimination procedure (2004) Kybernetika, 40 (5), pp. 519-550
  • Basu, S., Pollack, R., Roy, M.-F., On the combinatorial and algebraic complexity of quantifier elimination (1996) J. ACM, 43 (6), pp. 1002-1045
  • Basu, S., Pollack, R., Roy, M.-F., Complexity of computing semi-algebraic descriptions of the connected components of a semialgebraic set (1998) Proceedings, ISSAC '98, pp. 25-29. , O. Gloor Ed. Rostock, Germany, August 13-15, 1998 ACM Press New York, NY
  • Bochnak, J., Coste, M., Roy, M.-F., Géométrie algébrique réelle, Ergebnisse der Mathematik und ihrer Grenzgebiete (1987), Berlin, Heidelberg, New York: Springer; Bürgisser, P., Clausen, M., Shokrollahi, M.A., Algebraic complexity theory. With the collaboration of Thomas Lickteig (1997) Grundlehren Der Mathematischen Wissenschaften, 315. , Berlin, Springer
  • Canny, J.F., Some algebraic and geometric computations in PSPACE (1998) Proceedings of the 20th ACM Symposium on Theory of Computing, pp. 460-467
  • Canny, J.F., Emiris, I.Z., Efficient incremental algorithms for the sparse resultant and the mixed volume (1995) J. Symbolic Comput., 20 (2), pp. 117-149
  • Castro, D., Giusti, M., Heintz, J., Matera, G., Pardo, L.M., The hardness of polynomial solving (2003) Found. Comput. Math., 3 (4), pp. 347-420
  • Castro, D., Hägele, K., Morais, J.E., Pardo, L.M., Kronecker's and Newton's approaches to solving: A first comparison (2001) J. Complexity, 17 (1), pp. 212-303
  • Coste, M., Roy, M.-F., Thom's Lemma, the coding of real algebraic numbers and the computation of the topology of semialgebraic sets (1988) J. Symbolic Comput., 5, pp. 121-130
  • Cucker, F., Smale, S., Complexity estimates depending on condition and round-of error (1999) J. ACM, 46 (1), pp. 113-184
  • Demazure, M., (1989) Catastrophes Et Bifurcations, , Paris: Ellipses
  • Eagon, J.A., Hochster, M., R-sequences and indeterminates (1974) Osaka J. Math., Oxford II, 25, pp. 61-71
  • Eagon, J.A., Northcott, D.G., Ideals defined by matrices and a certain complex associated with them (1962) Proc. Roy. Soc. Lond. Ser. A, 269, pp. 188-204
  • Fulton, W., Intersection Theory (1984) Ergebnisse Der Mathematik Und Ihrer Grenzgebiete, (3). , Berlin: Springer
  • von zur Gathen, J., Parallel linear algebra (1993) Synthesis of Parallel Algorithms, , J. Reif Ed. Morgan Kaufmann Los Altos, CA
  • Giusti, M., Heintz, J., Kronecker's smart, little black boxes (2001) Foundations of Computational Mathematics, 284, pp. 69-104. , R.A. DeVore, A. Iserles, E.Süli (Eds.) Cambridge University Press, Cambridge
  • Giusti, M., Heintz, J., Hägele, K., Morais, J.E., Montaña, J.L., Pardo, L.M., Lower bounds for diophantine approximations (1997) J. Pure Appl. Algebra, 117-118, pp. 277-317
  • Giusti, M., Heintz, J., Morais, J.E., Morgenstern, J., Pardo, L.M., Straight-line programs in geometric elimination theory (1998) J. Pure Appl. Algebra, 124 (1-3), pp. 101-146
  • Giusti, M., Lecerf, G., Salvy, B., A Gröbner free alternative for polynomial system solving (2001) J. Complexity, 17 (1), pp. 154-211
  • Grigor'ev, D., Vorobjov, N., Solving systems of polynomial inequalities in subexponential time (1988) J. Symb. Comput., 5 (1-2), pp. 37-64
  • Heintz, J., Fast quantifier elimination over algebraically closed fields (1983) Theoret. Comp. Sci., 24, pp. 239-277
  • Heintz, J., Matera, G., Waissbein, A., On the time-space complexity of geometric elimination procedures (2001) Appl. Algebra Eng. Commun. Comput., 11 (4), pp. 239-296
  • Heintz, J., Roy, M.-F., Solernó, P., On the complexity of semialgebraic sets (1989) Proceedings of Information Processing '89 (IFIP '89), pp. 293-298. , G. Ritter Ed. San Francisco, 1989 North-Holland Amsterdam
  • Heintz, J., Roy, M.-F., Solernó, P., Complexité du principe de Tarski-Seidenberg (1989) Paris C. R. Acad. Sci. Sér. I, 309, pp. 825-830
  • Heintz, J., Roy, M.-F., Solernó, P., Sur la complexité du principe de Tarski-Seidenberg (1990) Bull. Soc. Math. France, 18, pp. 101-126
  • Heintz, J., Schnorr, C.P., Testing polynomials which are easy to compute (1980) Proceedings of the 12th Annual ACM Symposium on Computing, pp. 262-268
  • Heintz, J., Schnorr, C.P., (1982) Logic and Algorithmic: An International Symposium Held in Honour of Ernst Specker, pp. 237-254. , Monographie No.30 de l'Enseignement de Mathématiques, Genève
  • Kleiman, S.L., Transversality of the general translate (1973) Compos. Math., 28, pp. 287-297
  • Krick, T., Pardo, L.M., A computational method for diophantine approximation (1996) Proceedings of MEGA '94, Algorithms in Algebraic Geometry and Applications Progress in Mathematics, 143, pp. 193-254. , L. Gonzales-Vega, T. Recio (Eds.) Birkhäuser, Basel
  • Kunz, E., Kähler differentials (1986) Advanced Lectures in Mathematics, , Braunschweig: Wiesbaden Vieweg
  • Lê, D.T., Teissier, B., Variétés polaires locales et classes de Chern des variétés singulières (1981) Ann. Math., 114, pp. 457-491
  • Lecerf, G., Une alternative aux méthodes de réécriture pour la résolution des systèmes algébriques (2001), Thèse, École Polytechnique; Lecerf, G., Quadratic Newton iterations for systems with multiplicity (2002) Found. Comput. Math., 2 (3), pp. 247-293
  • Matera, G., Probabilistic algorithms for geometric elimination (1999) Appl. Algebra Eng. Commun. Comput., 9 (6), pp. 463-520
  • Matsumura, H., Commutative Ring Theory (1986) Cambridge Studies in Advanced Mathematics, 8. , Cambridge University Press, Cambridge, UK
  • Merle, M., Variétés polaires, stratifications de Whitney et classes de Chern des espaces analytiques complexes, d' après Lê-Teissier 35 (1982), (600). , Exposés du Séminaire Bourbaki; Piene, R., Polar classes of singular varieties (1978) Ann. Scient. Éc. Norm., 11 (SUPPL. 4), pp. 247-276
  • Renegar, J., A faster PSPACE algorithm for the existential theory of the reals (1988) Proceedings of the 29th Annual IEEE Symposium on the Foundation of Computer Science, pp. 291-295
  • Renegar, J., On the computational complexity and geometry of the first order theory of the reals (1992) J. Symbolic Comput., 13 (3), pp. 255-352
  • Safey El Din, M., Résolution réelle des systèmes polynomiaux en dimension positive (2001), Thèse, Université Paris VI; Safey El Din, M., Schost, E., Polar varieties and computation of one point in each connected component of a smooth real algebraic set (2003) ISSAC '03, , August 3-6 2003, Philadelphia, Pennsylvania, USA
  • Schoenhage, A., Grotefeld, A., Vetter, E., (1994) Fast Algorithms, , Mannheim: Bibl. Inst
  • Spivak, M., Calculus on manifolds (1965) A Modern Approach to Classical Theorems of Calculus, , New York, Amsterdam: W. A. Benjamin, Inc
  • Teissier, B., Variétés Polaires. II. Multiplicités polaires, sections planes et conditions de Whitney (1982) Algebraic Geometry (La Rábida, 1981), 961, pp. 314-491. , J.M. Aroca, R. Buchweitz, M. Giusti, M. Merle (Eds.) Lecture Notes in Mathematics, Springer, Berlin
  • Vogel, W., (1984) Lectures on Results on Bézout's Theorem, , Berlin: SpringerA4 -

Citas:

---------- APA ----------
Bank, B., Giusti, M., Heintz, J. & Pardo, L.M. (2005) . Generalized polar varieties: Geometry and algorithms. Festschrift for the 70th Birthday of Arnold Schonhage, 21(4), 377-412.
http://dx.doi.org/10.1016/j.jco.2004.10.001
---------- CHICAGO ----------
Bank, B., Giusti, M., Heintz, J., Pardo, L.M. "Generalized polar varieties: Geometry and algorithms" . Festschrift for the 70th Birthday of Arnold Schonhage 21, no. 4 (2005) : 377-412.
http://dx.doi.org/10.1016/j.jco.2004.10.001
---------- MLA ----------
Bank, B., Giusti, M., Heintz, J., Pardo, L.M. "Generalized polar varieties: Geometry and algorithms" . Festschrift for the 70th Birthday of Arnold Schonhage, vol. 21, no. 4, 2005, pp. 377-412.
http://dx.doi.org/10.1016/j.jco.2004.10.001
---------- VANCOUVER ----------
Bank, B., Giusti, M., Heintz, J., Pardo, L.M. Generalized polar varieties: Geometry and algorithms. J. Complexity. 2005;21(4):377-412.
http://dx.doi.org/10.1016/j.jco.2004.10.001