Compact Formulae in Sparse Elimination

Ioannis Emiris 1, 2
2 AROMATH - AlgebRe, geOmetrie, Modelisation et AlgoriTHmes
CRISAM - Inria Sophia Antipolis - Méditerranée , UoA - University of Athens
Abstract : It has by now become a standard approach to use the theory of sparse (or toric) elimination, based on the Newton polytope of a polynomial, in order to reveal and exploit the structure of algebraic systems. This talk surveys compact formulae, including older and recent results, in sparse elimination. We start with root bounds and juxtapose two recent formulae: a generating function of the m-Bézout bound and a closed-form expression for the mixed volume by means of a matrix permanent. For the sparse resultant, a bevy of results have established determinantal or rational formulae for a large class of systems, starting with Macaulay. The discriminant is closely related to the resultant but admits no compact formula except for very simple cases. We offer a new determinantal formula for the discriminant of a sparse multilinear system arising in computing Nash equilibria. We introduce an alternative notion of compact formula, namely the Newton polytope of the unknown polynomial. It is possible to compute it efficiently for sparse resultants, discriminants, as well as the implicit equation of a parameterized variety. This leads us to consider implicit matrix representations of geometric objects.
Type de document :
Communication dans un congrès
ISSAC 2016 - International Symposium on Symbolic and Algebraic Computation, Jul 2016, Waterloo, Canada. pp.1 - 8, 2016, ISSAC '16 - Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation. 〈10.1145/2930889.2930943〉
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01401132
Contributeur : Ioannis Emiris <>
Soumis le : vendredi 13 octobre 2017 - 11:19:52
Dernière modification le : mercredi 18 octobre 2017 - 15:07:26

Fichiers

emiris2016.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité - Pas d'utilisation commerciale 4.0 International License

Identifiants

Collections

Citation

Ioannis Emiris. Compact Formulae in Sparse Elimination. ISSAC 2016 - International Symposium on Symbolic and Algebraic Computation, Jul 2016, Waterloo, Canada. pp.1 - 8, 2016, ISSAC '16 - Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation. 〈10.1145/2930889.2930943〉. 〈hal-01401132〉

Partager

Métriques

Consultations de la notice

146

Téléchargements de fichiers

9