Search

Your search keyword '"Trebuchet, Philippe"' showing total 22 results
Start Over Author "Trebuchet, Philippe"
22 results on '"Trebuchet, Philippe"'

1. Toric Border Bases

Author

Mourrain, Bernard and Trebuchet, Philippe

Subjects
Mathematics - Algebraic Geometry
Abstract

We extend the theory and the algorithms of Border Bases to systems of Laurent polynomial equations, defining "toric" roots. Instead of introducing new variables and new relations to saturate by the variable inverses, we propose a more efficient approach which works directly with the variables and their inverse. We show that the commutation relations and the inversion relations characterize toric border bases. We explicitly describe the first syzygy module associated to a toric border basis in terms of these relations. Finally, a new border basis algorithm for Laurent polynomials is described and a proof of its termination is given for zero-dimensional toric ideals.

Published
2014
Full Text
View/download PDF

2. Unconstraint global polynomial optimization via Gradient Ideal

Author

Bucero, Marta Abril, Mourrain, Bernard, and Trebuchet, Philippe

Subjects
Mathematics - Algebraic Geometry
Abstract

In this paper, we describe a new method to compute the minimum of a real polynomial function and the ideal defining the points which minimize this polynomial function, assuming that the minimizer ideal is zero-dimensional. Our method is a generalization of Lasserre relaxation method and stops in a finite number of steps. The proposed algorithm combines Border Basis, Moment Matrices and Semidefinite Programming. In the case where the minimum is reached at a finite number of points, it provides a border basis of the minimizer ideal., Comment: arXiv admin note: text overlap with arXiv:1112.3197

Published
2013

3. Moment Matrices, Border Bases and Real Radical Computation

Author

Lasserre, Jean-Bernard, Laurent, Monique, Mourrain, Bernard, Rostalski, Philipp, and Trébuchet, Philippe

Subjects
Mathematics - Algebraic Geometry
Abstract

In this paper, we describe new methods to compute the radical (resp. real radical) of an ideal, assuming it complex (resp. real) variety is finite. The aim is to combine approaches for solving a system of polynomial equations with dual methods which involve moment matrices and semi-definite programming. While the border basis algorithms of [17] are efficient and numerically stable for computing complex roots, algorithms based on moment matrices [12] allow the incorporation of additional polynomials, e.g., to re- strict the computation to real roots or to eliminate multiple solutions. The proposed algorithm can be used to compute a border basis of the input ideal and, as opposed to other approaches, it can also compute the quotient structure of the (real) radical ideal directly, i.e., without prior algebraic techniques such as Gr\"obner bases. It thus combines the strength of existing algorithms and provides a unified treatment for the computation of border bases for the ideal, the radical ideal and the real radical ideal.

Published
2011

4. Stable normal forms for polynomial system solving

Author

Mourrain, Bernard and Trébuchet, Philippe

Subjects
Computer Science - Symbolic Computation
Abstract

This paper describes and analyzes a method for computing border bases of a zero-dimensional ideal $I$. The criterion used in the computation involves specific commutation polynomials and leads to an algorithm and an implementation extending the one provided in [MT'05]. This general border basis algorithm weakens the monomial ordering requirement for \grob bases computations. It is up to date the most general setting for representing quotient algebras, embedding into a single formalism Gr\"obner bases, Macaulay bases and new representation that do not fit into the previous categories. With this formalism we show how the syzygies of the border basis are generated by commutation relations. We also show that our construction of normal form is stable under small perturbations of the ideal, if the number of solutions remains constant. This new feature for a symbolic algorithm has a huge impact on the practical efficiency as it is illustrated by the experiments on classical benchmark polynomial systems, at the end of the paper.

Published
2008
Full Text
View/download PDF

5. Strong bi-homogeneous B\'{e}zout theorem and its use in effective real algebraic geometry

Author

Din, Mohab Safey El and Trebuchet, Philippe

Subjects
Computer Science - Symbolic Computation
Abstract

Let f1, ..., fs be a polynomial family in Q[X1,..., Xn] (with s less than n) of degree bounded by D. Suppose that f1, ..., fs generates a radical ideal, and defines a smooth algebraic variety V. Consider a projection P. We prove that the degree of the critical locus of P restricted to V is bounded by D^s(D-1)^(n-s) times binomial of n and n-s. This result is obtained in two steps. First the critical points of P restricted to V are characterized as projections of the solutions of Lagrange's system for which a bi-homogeneous structure is exhibited. Secondly we prove a bi-homogeneous B\'ezout Theorem, which bounds the sum of the degrees of the equidimensional components of the radical of an ideal generated by a bi-homogeneous polynomial family. This result is improved when f1,..., fs is a regular sequence. Moreover, we use Lagrange's system to design an algorithm computing at least one point in each connected component of a smooth real algebraic set. This algorithm generalizes, to the non equidimensional case, the one of Safey El Din and Schost. The evaluation of the output size of this algorithm gives new upper bounds on the first Betti number of a smooth real algebraic set. Finally, we estimate its arithmetic complexity and prove that in the worst cases it is polynomial in n, s, D^s(D-1)^(n-s) and the binomial of n and n-s, and the complexity of evaluation of f1,..., fs.

Published
2006

6. Border Basis for Polynomial System Solving and Optimization

Author

Trébuchet, Philippe, Mourrain, Bernard, Bucero, Marta Abril, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Greuel, Gert-Martin, editor, Koch, Thorsten, editor, Paule, Peter, editor, and Sommese, Andrew, editor

Published
2016
Full Text
View/download PDF

9. Anion-exchange displacement centrifugal partition chromatography

Author

Maciuk, Alexandre, Renault, Jean-Hugues, Margraff, Rodolphe, Trebuchet, Philippe, Zeches-Hanrot, Monique, and Nuzillard, Jean-Marc

Subjects
Chromatography -- Methods, Ion exchange, Chemistry
Abstract

Ion-exchange displacement chromatography has been adapted to centrifugal partition chromatography. The use of an ionic liquid, benzalkonium chloride, as a strong anion-exchanger has proven to be efficient for the preparative separation of phenolic acid regioisomers. Multigram quantities of a mixture of three hydroxycinnamic acid isomers were separated using iodide as a displacer. The displacement process was characterized by a trapezoidal profile of analyte concentration in the eluate with narrow transition zones. By taking advantage of the partition rules involved in support-free liquid-liquid chromatography, a numerical separation model is proposed as a tool for preliminary process validation and further optimization.

Published
2004

11. Analytical blind channel identification

Author

Grellier, Olivier, Comon, Pierre, Mourrain, Bernard, and Trebuchet, Philippe

Subjects
Signal processing -- Research, Digital signal processor, Business, Computers, Electronics, Electronics and electrical industries
Abstract

A blind identification approach is described and discussed. It is based on second-order statistics of the obswervation, and it is shown that it is not necessary to employ higher order statistics.

Published
2002

13. WooKey

Author

Benadjila, Ryad, primary, Michelizza, Arnauld, additional, Renard, Mathieu, additional, Thierry, Philippe, additional, and Trebuchet, Philippe, additional

Published
2019
Full Text
View/download PDF

15. Mathemagix

Author

van Der Hoeven, Joris, Lecerf, Grégoire, Mourrain, Bernard, Trebuchet, Philippe, Berthomieu, Jérémy, Diatta, Daouda Niang, Mantzaflaris, Angelos, Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Geometry, algebra, algorithms (GALAAD), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS), Algorithmes, Programmes et Résolution (APR), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), African Institute for Mathematical Sciences (AIMS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Nice Sophia Antipolis (... - 2019) (UNS)

Subjects
ComputingMilieux_MISCELLANEOUS, [INFO.INFO-MS]Computer Science [cs]/Mathematical Software [cs.MS]
Abstract

International audience

Published
2012
Full Text
View/download PDF

16. Strong bi-homogeneous Bézout theorem and its use in effective real algebraic geometry

Author

Safey El Din, Mohab, Trebuchet, Philippe, Systèmes Polynomiaux, Implantation, Résolution Algébrique (SPIRAL), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), and INRIA

Subjects
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Bihomogeneous Bezout Bound, Real Algebraic Geometry, ACM: F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY/F.2.2: Nonnumerical Algorithms and Problems/F.2.2.2: Geometrical problems and computations, ACM: G.: Mathematics of Computing
Abstract

Let f1, ..., fs be a polynomial family in Q[X1,..., Xn] (with s less than n) of degree bounded by D. Suppose that f1, ..., fs generates a radical ideal, and defines a smooth algebraic variety V. Consider a projection P. We prove that the degree of the critical locus of P restricted to V is bounded by D^s(D-1)^(n-s) times binomial of n and n-s. This result is obtained in two steps. First the critical points of P restricted to V are characterized as projections of the solutions of Lagrange's system for which a bi-homogeneous structure is exhibited. Secondly we prove a bi-homogeneous Bézout Theorem, which bounds the sum of the degrees of the equidimensional components of the radical of an ideal generated by a bi-homogeneous polynomial family. This result is improved when f1,..., fs is a regular sequence. Moreover, we use Lagrange's system to design an algorithm computing at least one point in each connected component of a smooth real algebraic set. This algorithm generalizes, to the non equidimensional case, the one of Safey El Din and Schost. The evaluation of the output size of this algorithm gives new upper bounds on the first Betti number of a smooth real algebraic set. Finally, we estimate its arithmetic complexity and prove that in the worst cases it is polynomial in n, s, D^s(D-1)^(n-s) and the binomial of n and n-s, and the complexity of evaluation of f1,..., fs.

Published
2006

17. Strong Bi-homogeneous Bézout's Theorem and degree bounds for algebraic optimization

Author

Safey El Din, Mohab, Trebuchet, Philippe, Solving problems through algebraic computation and efficient software (SPACES), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Systèmes Polynomiaux, Implantation, Résolution Algébrique (SPIRAL), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), INRIA, Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP), and Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)

Subjects
REAL SOLUTIONS, Mathematics::Commutative Algebra, POLYNOMIAL SYSTEMS, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], Computer Science::Symbolic Computation
Abstract

Let $(f_1, \ldots, f_s)$ be a polynomial family in $\Q[X_1, \ldots, X_n]$ (with $s\leq n-1$) of degree bounded by $D$, generating a radical ideal, and defining a smooth algebraic variety $\mathcal{V}\subset\C Consider a {\em generic} projection $\pi:\Cightarrow\Cts restriction to $\mathcal{V}$ and its critical locus which is supposed to be zero-dimensional. We state that the number of critical points of $\pi$ restricted to $\mathcal{V}$ is bounded by $D^s(D-1)^{n-s}{{n}\choose{n-s}}$. This result is obtained in two steps. First the critical points of $\pi$ restricted to $\mathcal{V}$ are characterized as projections of the solutions of the Lagrange system for which a bi-homogeneous structure is exhibited. Secondly we apply a bi-homogeneous Bézout Theorem, for which we give a proof and which bounds the sum of the degrees of the isolated primary components of an ideal generated by a bi-homogeneous family for which we give a proof. This result is improved in the case where $(f_1, \ldots, f_s)$ is a regular sequence. Moreover, we use Lagrange's system to generalize the algorithm due to Safey El Din and Schost for computing at least one point in each connected component of a smooth real algebraic set to the non equidimensional case. Then, evaluating the size of the output of this algorithm gives new upper bounds on the first Betti number of a smooth real algebraic set.

Published
2004

18. Circular Cylinders by Four or Five Points in Space

Author

Devillers, Olivier, Mourrain, Bernard, Preparata, Franco, Trebuchet, Philippe, Geometric computing (GEOMETRICA), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Geometry, algebra, algorithms (GALAAD), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science (Brown University), Brown University, Calcul formel (CALFOR), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Nice Sophia Antipolis (... - 2019) (UNS)

Subjects
[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]
Abstract

International audience; We are interested in computing effectively cylinders through 5 points, and in other problems involved in metrology. In particular, we consider the cylinders through 4 points with a fix radius and with extremal radius. For these different problems, we give bounds on the number of solutions and exemples show that these bounds are optimal. Finally, we describe two algebraic methods which can be used here to solve efficiently these problems and some experimentation results.

Published
2002
Full Text
View/download PDF

19. On circular Cylinders by Four or Five Points in Space

Author

Devillers, Olivier, Mourrain, Bernard, Preparata, Franco, Trebuchet, Philippe, Geometry, Algorithms and Robotics (PRISME), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Algebraic Systems, Geometry and Applications (SAGA), and INRIA

Subjects
RESOLUTION, GEOMETRY, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], METROLOGY, CYLINDER, ALGEBRA
Abstract

We are interested in computing effectively cylinders through 5 points, and in other problems involved in metrology. In particular, we consider the cylinders through 4 points with a fix radius and with extremal radius. For these different problems, we give bounds on the number of solutions and exemples show that these bounds are optimal. Finally, we describe two algebraic methods which can be used here to solve efficiently these problems and some experimentation results.

Published
2001

Catalog

Books, media, physical & digital resources
See catalog results