Xavier Dahan
ABSTRACT
We study the triangular representation of zero-dimensional varieties defined over the rational field (resp. a rational function field). We prove polynomial bounds in terms of intrinsic quantities for the height (resp. degree) of the coefficients of such triangular sets, whereas previous bounds were exponential. We also introduce a rational form of triangular representation, for which our estimates become linear. Experiments show the practical interest of this new representation.
- M. E. Alonso, E. Becker, M.-F. Roy, and T. Wörmann. Zeroes, multiplicities and idempotents for zerodimensional systems. In MEGA'94, volume 142 of Prog. in Math., pages 1--15. Birkhäuser, 1996. Google Scholar
Digital Library
- P. Aubry, D. Lazard, and M. M. Maza. On the theories of triangular sets. J. Symb. Comp, 28(1,2):45--124, 1999. Google ScholarDigital Library
- P. Aubry and A. Valibouze. Using Galois ideals for computing relative resolvents. J. Symb. Comp, 30(6):635--651, 2000. Google ScholarDigital Library
- J.-B. Bost, H. Gillet, and C. Soulé. Heights of projective varieties and positive Green forms. J. Amer. Math. Soc., 7(4):903--1027, 1994.Google ScholarCross Ref
- X. Dahan. Bornes de hauteur pour la représentation triangulaire de variétés présentant des symétries. www.stix.polytechnique.fr/~dahan, 2003.Google Scholar
- G. Gallo and B. Mishra. Efficient algorithms and bounds for Wu-Ritt characteristic sets. In MEGA'90, volume~94 of Prog. in Math., pages 119--142. Birkhäuser, 1990.Google Scholar
- P. Gaudry and É. Schost. Construction of secure random curves of genus 2 over prime fields. 2003.Google Scholar
- M. Giusti, K. Hägele, J. Heintz, J. E. Morais, J. L. Montaña, and L. M. Pardo. Lower bounds for Diophantine approximations. J. Pure Appl. Algebra, 117--118:277--317, 1997.Google ScholarCross Ref
- M. Giusti, G. Lecerf, and B. Salvy. A Gröbner free alternative for polynomial system solving. J. Complexity, 17(1):154--211, 2001. Google ScholarDigital Library
- K. Hägele, J.-E. Morais, L.-M. Pardo, and M. Sombra. On the intrinsic complexity of the arithmetic Nullstellensatz. J. Pure. Appl. Alg., 146:103--183, 2000.Google ScholarCross Ref
- J. Heintz. Definability and fast quantifier elimination in algebraically closed fields. Theoret. Comput. Sci., 24(3):239--277, 1983.Google ScholarCross Ref
- É. Hubert. Notes on triangular sets and triangulation decomposition algorithms I: Polynomial systems. In Symbolic and Numerical Scientific Computations, volume 2630 of LNCS. Springer, 2003. Google ScholarDigital Library
- T. Krick, L.-M. Pardo, and M. Sombra. Sharp estimates for the arithmetic Nullstellensatz. Duke Math. J., 109(3):521--598, 2001.Google ScholarCross Ref
- S. Lang. Diophantine geometry. Tracts in Pure and Applied Mathematics, No. 11. Interscience, 1962.Google Scholar
- D. Lazard. Solving zero-dimensional algebraic systems. J. Symb. Comp, 13(2):117--133, 1992. Google ScholarDigital Library
- P. J. McCarthy. Algebraic extensions of fields. Dover Publications Inc., New York, 1991.Google Scholar
- P. Philippon. Sur des hauteurs alternatives. III. J. Math. Pures Appl. (9), 74(4):345--365, 1995.Google Scholar
- F. Rouillier. Solving zero-dimensional systems through the Rational Univariate Representation. Appl. Algebra Engrg. Comm. Comput., 9(5):433--461, 1999.Google ScholarCross Ref
- É. Schost. Sur la résolution des systèmes polynomiaux à paramètres. PhD thesis, École polytechnique, 2000.Google Scholar
- ÉE. Schost. Complexity results for triangular sets. J. Symb. Comp, 36(3--4):555--594, 2003. Google ScholarDigital Library
- ÉE. Schost. Computing parametric geometric resolutions. Appl. Algebra Engrg. Comm. Comput., 13(4):349--393, 2003.Google ScholarCross Ref
- M. Sombra. Estimaciones para el teorema de ceros de Hilbert. PhD thesis, U. de Buenos Aires, 1998.Google Scholar
- A. Szanto. Computation with polynomial systems. PhD thesis, Cornell Univ., 1999. Google ScholarDigital Library
- D. Wang. Elimination Methods, volume XIII of Texts and monographs in symbolic computation. Springer-Verlag, 2001.Google Scholar
Index Terms
- Sharp estimates for triangular sets
Recommendations
Lifting techniques for triangular decompositions
ISSAC '05: Proceedings of the 2005 international symposium on Symbolic and algebraic computationWe present lifting techniques for triangular decompositions of zero-dimensional varieties, that extend the range of the previous methods. We discuss complexity aspects, and report on a preliminary implementation. Our theoretical results are comforted by ...
Complexity results for triangular sets
Special issue: International symposium on symbolic and algebraic computation (ISSAC 2002)We study the representation of the solutions of a polynomial system by triangular sets, and concentrate on the positive-dimensional case. We reduce to dimension zero by placing the free variables in the base field, so the solutions can be represented by ...
Change of order for bivariate triangular sets
ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computationChanging the order of variables in bivariate triangular sets has applications in Trager's factorization algorithm, or in rational function integration. We discuss the complexity of this question, using baby steps / giant steps techniques and trace ...
Comments