Search

Your search keyword '"Rouillier, Fabrice"' showing total 209 results
Start Over Author "Rouillier, Fabrice"
209 results on '"Rouillier, Fabrice"'

53. PTOPO

Author

Katsamaki, Christina, primary, Rouillier, Fabrice, additional, Tsigaridas, Elias, additional, and Zafeirakopoulos, Zafeirakis, additional

Published
2020
Full Text
View/download PDF

56. Design of regular nonseparable bidimensional wavelets using Grobner basis techniques

Author

Faugere, Jean-Charles, de Saint-Martin, Francois Moreau, and Rouillier, Fabrice

Subjects
Signal processing -- Methods, Image coding -- Methods, Digital filters -- Usage, Polynomials -- Analysis, Filtering (Electronics) -- Methods, Business, Computers, Electronics, Electronics and electrical industries
Abstract

The Grobner basis computation and computer algebra techniques can be utilized in computing algebraic properties of multivariate polynomials involved in the design of two-dimensional filter banks. By using these techniques, the design of the filter banks yield optimum frequency characteristics such as orthogonality, linear phase features and wavelet bases. Such filter banks are necessary in enhanced signal processing applications.

Published
1998

60. Foreword

Author

Draisma, Jan, Ottaviani, Giorgio, Rouillier, Fabrice, and Discrete Mathematics

Subjects
Computational Mathematics, Algebra and Number Theory
Published
2017

62. Certified Non-conservative Tests for the Structural Stability of Multidimensional Systems

Author

Bouzidi, Yacine, Quadrat, Alban, Rouillier, Fabrice, Non-Asymptotic estimation for online systems (NON-A), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Université Pierre et Marie Curie - Paris 6 (UPMC), Institut de Mathématiques de Jussieu - Paris Rive Gauche (IMJ-PRG), Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), INRIA Lille - Nord Europe, INRIA Paris, ANR-13-BS03-0005,MSDOS,Systèmes multidimensionnels, digression sur la stabilité(2013), Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Université Pierre et Marie Curie - Paris 6 (UPMC), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Systèmes multidimensionnels, stabilité structurelle, analyse de stabilité, calcul formel, équations polynomiales, Multidimensional systems, structural stability, polynomial equations, stability analysis, computer algebra
Abstract

In this paper, we present new computer algebra based methods for testing the structural stability of n-D discrete linear systems (with n >= 2). More precisely, we show that the standard characterization of the structural stability of a multivariate rational transfer function (namely, the denominator of the transfer function does not have solutions in the unit polydisc of \C^n) is equivalent to the fact that a certain system of polynomials does not have real solutions. We then use state-of-the-art computer algebra algorithms to check this last condition, and thus the structural stability of multidimensional systems.; Nous présentons dans cet article de nouvelles méthodes, basées sur des techniques de calcul formel, pour tester la stabilité structurelle de systèmes n-D linéaires et discrets (avec n > 2). Plus précisément, nous montrons dans un premier temps que la condition classique de stabilité structurelle d'une fonction de transfert rationnelle multivariée (à savoir que le dénominateur de celle-ci n'a pas de zéros à l'intérieur du polydisque unité de \C^n) est équivalente au fait que des systèmes d'équations polynomiales, obtenus via certaines transformations, n'ont pas de zéros réels. Nous utilisons ensuite des algorithmes de résolutions de systèmes algébriques pour vérifier cette dernière condition et ainsi la stabilité structurelle de systèmes multidimensionnels.

Published
2017

63. Special Issue : MEGA 2015

Author

Draisma, Jan, Ottaviani, Giorgio, Rouillier, Fabrice, Mathematisches Institut [Bern], Universität Bern [Bern] (UNIBE), Dipartimento di Matematica e Informatica [Firenze] (DiMal), Università degli Studi di Firenze = University of Florence (UniFI), Université Pierre et Marie Curie - Paris 6 (UPMC), Institut de Mathématiques de Jussieu - Paris Rive Gauche (IMJ-PRG), Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), OUtils de Résolution Algébriques pour la Géométrie et ses ApplicatioNs (OURAGAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Universität Bern [Bern], Università degli Studi di Firenze = University of Florence [Firenze] (UNIFI), and Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Université Pierre et Marie Curie - Paris 6 (UPMC)

Subjects
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2017

64. Certified Algorithms for proving the structural stability of two dimensional systems possibly with parameters

Author

Bouzidi, Yacine, Rouillier, Fabrice, Non-Asymptotic estimation for online systems (NON-A), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), OUtils de Résolution Algébriques pour la Géométrie et ses ApplicatioNs (OURAGAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut de Mathématiques de Jussieu - Paris Rive Gauche (IMJ-PRG), Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Université Pierre et Marie Curie - Paris 6 (UPMC), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Université de Lille-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Université Pierre et Marie Curie - Paris 6 (UPMC), and Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe

Subjects
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], stability of multidimensional systems, computer algebra
Abstract

International audience; In [1], a new method for testing the structural stability of multidimensional systems has been presented. The key idea of this method is to reduce the problem of testing the structural stability to that of deciding if an algebraic set has real points. Following the same idea, we consider in this work the specific case of two-dimensional systems and focus on the practical efficiency aspect. For such systems, the problem of testing the stability is reduced to that of deciding if a bivariate algebraic system with finitely many solutions has real ones. Our first contribution is an algorithm that answers this question while achieving practical efficiency. Our second contribution concerns the stability of two dimensional systems with parameters. More precisely, given a two-dimensional system depending on a set of parameters, we present a new algorithm that computes regions of the parameter space in which the considered system is structurally stable.

Published
2016

65. Foreword of MEGA 2015

Author

Draisma, Jan, Ottaviani, Giorgio, Rouillier, Fabrice, Mathematisches Institut [Bern], Universität Bern [Bern] (UNIBE), Eindhoven University of Technology [Eindhoven] (TU/e), Dipartimento di Matematica e Informatica [Firenze] (DiMal), Università degli Studi di Firenze = University of Florence (UniFI), Institut de Mathématiques de Jussieu - Paris Rive Gauche (IMJ-PRG), Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), OUtils de Résolution Algébriques pour la Géométrie et ses ApplicatioNs (OURAGAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Universität Bern [Bern], Università degli Studi di Firenze = University of Florence [Firenze] (UNIFI), and Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Université Pierre et Marie Curie - Paris 6 (UPMC)

Subjects
[MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG]
Abstract

International audience; MEGA stands for Effective Methods in Algebraic Geometry, and its translations in various languages. It is a biennial series of conferences, which celebrated its 25th anniversary during the 2015 edition in Trento. Following the MEGA tradition, the conference was succeeded by a call for submissions to a standard issue of the Journal of Symbolic Computation on the occasion of MEGA 2015. Accepted contributors to the conference were encouraged to submit, but the call was open to everyone.

Published
2016

66. Character Varieties For SL(3,C): The Figure Eight Knot

Author

Falbel, Elisha, Guilloux, Antonin, Koseleff, Pierre-Vincent, Rouillier, Fabrice, Thistlethwaite, Morwen, Université Pierre et Marie Curie - Paris 6 (UPMC), Institut de Mathématiques de Jussieu - Paris Rive Gauche (IMJ-PRG), Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), OUtils de Résolution Algébriques pour la Géométrie et ses ApplicatioNs (OURAGAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), The University of Tennessee [Knoxville], and ANR-11-BS01-0018,SGT,Structures Géometriques et Triangulations(2011)

Subjects
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Mathematics - Geometric Topology, Mathematics - Algebraic Geometry, figure eight knot, character varieties, FOS: Mathematics, Geometric Topology (math.GT), Algebraic Geometry (math.AG), Mathematics::Geometric Topology, decorated representations
Abstract

We give a description of several representation varieties of the fundamental group of the complement of the figure eight knot in PGL(3,C) or SL(3,C). We moreover obtain an explicit parametrization of matrices generating the representation and a description of the projection of the representation variety into the character variety of the boundary torus into SL(3,C)., 29 pages, 3 figures

Published
2016

69. Representations of fundamental groups of 3-manifolds into PGL(3,C): Exact computations in low complexity

Author

Falbel, Elisha, Koseleff, Pierre-Vincent, Rouillier, Fabrice, Université Pierre et Marie Curie - Paris 6 (UPMC), Institut de Mathématiques de Jussieu (IMJ), Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), OUtils de Résolution Algébriques pour la Géométrie et ses ApplicatioNs (OURAGAN), Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and ANR-11-BS01-0018,SGT,Structures Géometriques et Triangulations(2011)

Subjects
Mathematics - Geometric Topology, [MATH.MATH-RT]Mathematics [math]/Representation Theory [math.RT], [MATH.MATH-GT]Mathematics [math]/Geometric Topology [math.GT], FOS: Mathematics, Geometric Topology (math.GT), Representation Theory (math.RT), Mathematics::Geometric Topology, Mathematics - Representation Theory
Abstract

International audience; In this paper we are interested in computing representations of the fundamental group of a 3-manifold into PSL(3;C) (in particular in PSL(2;C); PSL(3;R) and PU(2; 1)). The representations are obtained by gluing decorated tetrahedra of flags. We list complete computations (giving 0-dimensional or 1-dimensional solution sets) for the first complete hyperbolic non-compact manifolds with finite volume which are obtained gluing less than three tetrahedra with a description of the computer methods used to find them.

Published
2015

70. Improved algorithms for solving bivariate systems via Rational Univariate Representations

Author

Bouzidi, Yacine, Lazard, Sylvain, Moroz, Guillaume, Pouget, Marc, Rouillier, Fabrice, Sagraloff, Michael, Effective Geometric Algorithms for Surfaces and Visibility (VEGAS), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), OUtils de Résolution Algébriques pour la Géométrie et ses ApplicatioNs (OURAGAN), Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut de Mathématiques de Jussieu - Paris Rive Gauche (IMJ-PRG), Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft, Inria, Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Université Pierre et Marie Curie - Paris 6 (UPMC), Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Inria Nancy - Grand Est, and Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO]Computer Science [cs], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]
Abstract

Given two coprime polynomials $P$ and $Q$ in $\Z[x,y]$ of degree bounded by $d$ and bitsize bounded by $\tau$, we address the problem of solving the system $\{P,Q\}$. We are interested in certified numerical approximations or,more precisely, isolating boxes of the solutions. We are also interested in computing, as intermediate symbolic objects, rational parameterizations of he solutions, and in particular Rational Univariate Representations (RURs), which can easily turn many queries on the system into queries on univariate polynomials. Such representations require the computation of a separating form for the system, that is a linear combination of the variables that takes different values when evaluated at the distinct solutions of the system. We present new algorithms for computing linear separating forms, RUR decompositions and isolating boxes of the solutions. We show that these three algorithms have worst-case bit complexity $\widetilde{O}_B(d^6+d^5\tau)$, where $\widetilde{O}$ refers to the complexity where polylogarithmic factors are omitted and $O_B$ refers to thebit complexity. We also present probabilistic Las-Vegas variants of our two first algorithms, which have expected bit complecity $\widetilde{O}_B(d^5+d^4\tau)$. A key ingredient of our proofs of complexity is an amortized analysis of the triangular decomposition algorithm via subresultants, which is of independent interest.

Published
2015

71. Computing Chebyshev knots diagrams

Author

Koseleff, P-V., Pecker, D., Rouillier, Fabrice, Rouillier, Fabrice, and Université Pierre et Marie Curie - Paris 6 (UPMC)

Subjects
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], [INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC], ComputingMilieux_MISCELLANEOUS
Abstract

International audience; no abstract

Published
2011

73. Outils de calcul formel performants pour la résolution de certains problèmes en robotique

Author

Faugère, Jean-Charles, Rouillier, Fabrice, 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 Rouillier, Fabrice

Subjects
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], [INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC], ComputingMilieux_MISCELLANEOUS
Abstract

National audience

Published
2005

74. On the Rational Univariate Representation

Author

Rouillier, Fabrice, 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 Rouillier, Fabrice

Subjects
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], [INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2004

75. Computing sampling points in a semi-algebraic set defined by non-strict inequalities, Application to Pattern-Matching Problems

Author

Le Guernic, Colas, Rouillier, Fabrice, Safey El Din, Mohab, 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 Rouillier, Fabrice

Subjects
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], [INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2004

76. Local rigidity for SL (3,C) representations of 3-manifolds groups

Author

Bergeron, Nicolas, Guilloux, Antonin, Falbel, Elisha, Koseleff, Pierre-Vincent, Rouillier, Fabrice, Université Pierre et Marie Curie - Paris 6 (UPMC), Institut de Mathématiques de Jussieu (IMJ), Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), OUtils de Résolution Algébriques pour la Géométrie et ses ApplicatioNs (OURAGAN), Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and ANR-11-BS01-0018,SGT,Structures Géometriques et Triangulations(2011)

Subjects
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], [MATH.MATH-GT]Mathematics [math]/Geometric Topology [math.GT], Mathematics::Geometric Topology
Abstract

Let M be a non-compact hyperbolic 3-manifold that has a tri- angulation by positively oriented ideal tetraedra. We explain how to produce local coordinates for the variety defined by the gluing equations for SL(3, C)- representations. In particular we prove local rigidity of the "geometric" rep- resentation in SL(3, C), recovering a recent result of Menal-Ferrer and Porti. More generally we give a criterion for local rigidty of SL(3, C)-representations and provide detailed analysis of the figure eight knot sister manifold exhibiting the different possibilities that can occur.

Published
2013

77. New bivariate system solver and topology of algebraic curves

Author

Bouzidi, Yacine, Lazard, Sylvain, Pouget, Marc, Rouillier, Fabrice, Effective Geometric Algorithms for Surfaces and Visibility (VEGAS), 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), 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), Solvers for Algebraic Systems and Applications (SALSA), 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 Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), 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)-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)

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

International audience; We present a new approach for solving polynomial systems of two bivariate polynomials with rational coefficients. We first use González-Vega and Necula approach [3] based on sub-resultant sequences for decomposing a system into subsystems according to the number of roots (counted with multiplicities) in vertical lines. We then show how the resulting triangular subsystems can be efficiently solved by computing lexicographic Gröbner basis and Rational Univariate Representations (RURs) of these systems. We also show how this approach can be performed using modular arithmetic, while remaining deterministic. Finally we apply our solver to the problem of computing the topology of algebraic curves using the algorithm Isotop [2]. We show that our approach yields a substantial gain of a factor between 1 to 10 on curves of degree up to 28 compared to directly computing a Gröbner basis and RUR of the input system, and how it leads to a very competitive algorithm compared to the other state-of-the-art implementations.

Published
2011

78. Comments on a blind signal separation method for multiuser communications'

Author

Nong Gu, Yong Xiang, Rouillier, Fabrice, and Zhiqiang Cao

Subjects
Convergence (Mathematics) -- Analysis, Signal processing -- Analysis, Digital signal processor, Business, Computers, Electronics, Electronics and electrical industries
Abstract

The global convergence analysis of the method that is proposed is incomplete. A counter example to show that sufficient condition for global convergence is incorrect is provided.

Published
2007

81. On Using Triangular Decomposition for Solving Parametric Polynomial Systems

Author

Rouillier, Fabrice, Xiao, Rong, Solvers for Algebraic Systems and Applications (SALSA), 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 Paris-Rocquencourt, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
[INFO]Computer Science [cs], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2009

82. Explicit classification of the 9 first Haas parametric systems

Author

Moroz, Guillaume, Rouillier, Fabrice, Solvers for Algebraic Systems and Applications (SALSA), 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 Paris-Rocquencourt, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
[INFO]Computer Science [cs], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2008

83. Algorithmes pour l'étude des solutions réelles des systèmes polynomiaux

Author

Rouillier, Fabrice, Solvers for Algebraic Systems and Applications (SALSA), 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 Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Pierre & Marie Curie - Paris 6, and Jean-Daniel Boissonnat

Subjects
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Computer Algebra, Zéros Réels, Polynomial Systems, Calcul Formel, Real Roots, Systèmes Polynomiaux
Abstract

This presentation summarizes a set of general methods for solving systems of polynomial equations(with or without inequalities), mainly centered on the study of their real roots; The main subject isthe “resolution” of systems with an arbitrary number of solutions (finite or infinite), depending or noton parameters. Since the field is vast, one constrains it by imposing it that the algorithms are exact orcertified or, in other words, that the results are never ambiguous from the user’s point of view(number or structure of the solutions, numerical approximations when it makes sense, real characterof the solutions, etc.).The exposed work was carried out with two principal objectives: to progress in the development ofuseful effective methods in real geometry, but especially to propose some credible alternatives tothe standard tools for scientific computations, with the objective of answering to some openproblems (or considered difficult) in various applications.This assessment of several years of work is, in particular, the occasion to show the specific effortswhich seem to be necessary to obtain convincing results (efficient implementations, cost of thecertification/exactness, balance between theoretical and practical efficiency, etc.) and is articulatedaround some selected applications which justify the main theoretical, algorithmic but also technicalchoices.; Cette présentation résume un ensemble de méthodes générales pour la résolution des systèmesd’équations (et d’inéquations/inégalités) polynomiales, axées principalement sur l’étude de leursracines réelles ; Il s’agit essentiellement de « résoudre » des systèmes admettant ou non une infinitéde solutions, dépendant ou non de paramètres. Le sujet étant vaste, on le contraint en imposant queles algorithmes soient exacts ou certifiés, ou, en d’autres termes, que les résultats ne présententaucune ambigüité du point de vue de l’utilisateur (nombre ou structure des solutions,approximations numériques lorsque cela a un sens, caractère réel des solutions, etc.).Le travail exposé a été effectué avec deux objectifs principaux : progresser dans la mise au point deméthodes effectives utiles en géométrie réelle, mais surtout proposer quelques alternativescrédibles aux outils standards de calcul scientifique, avec pour objectif de répondre à quelquesproblèmes ouverts (ou réputés difficiles) dans divers domaines applicatifs.Ce bilan de plusieurs années de travail est, en particulier, l’occasion de montrer les effortsspécifiques a priori nécessaires pour arriver à quelques résultats probants (implantation efficace,coût de la certification, balance entre les efficacités théoriques et pratiques) et s’articule autour dequelques applications « fil rouge » ayant motivé les principaux choix théoriques, algorithmiques voirtechniques.

Published
2007

84. On solving the direct kinematics problem for parallel robots

Author

Faugère, Jean-Charles, Merlet, Jean-Pierre, Rouillier, Fabrice, Solvers for Algebraic Systems and Applications (SALSA), 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 Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Constraints solving, optimization and robust interval analysis (COPRIN), 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)-École des Ponts ParisTech (ENPC), INRIA, and Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)

Subjects
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract

In this paper, we propose efficient methods for solving the direct kinematics problem (DKP) for parallel manipulators. By solving, we mean computing all the real solutions in a certified way, without any assumption on the manipulator. For example, the precision and the real character of the solutions are guaranteed. The proposed algorithms use as black boxes several recent algorithms from computer algebra such as F4/F5 for computing Gröbner bases, recent methods for isolating the real roots by mean of intervals with rational bounds which are mixed with strategies coming from the interval arithmetics field. The resulting solutions are efficient for such kind of output since the running time never exceeds few seconds ( in fact about 1 second for non extreme but general examples) thanks to the algorithms but also to a well adapted translation of DKP problem into algebraic equations. As an example we give a new computational proof of the existence of a parallel robot with 40 real roots.

Published
2006

85. PoSSo-RealSolving (Simultaneous Inequalities)

Author

Rouillier, Fabrice, Trujillo, G., Institut de Recherche Mathématique de Rennes ( IRMAR ), Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -AGROCAMPUS OUEST-École normale supérieure - Rennes ( ENS Rennes ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National des Sciences Appliquées ( INSA ) -Université de Rennes 2 ( UR2 ), Université de Rennes ( UNIV-RENNES ) -Centre National de la Recherche Scientifique ( CNRS ), Rouillier, Fabrice, Institut de Recherche Mathématique de Rennes (IRMAR), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-École normale supérieure - Rennes (ENS Rennes)-Université de Rennes 2 (UR2)-Centre National de la Recherche Scientifique (CNRS)-INSTITUT AGRO Agrocampus Ouest, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro), AGROCAMPUS OUEST, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Université de Rennes 2 (UR2), Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)

Subjects
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], [INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC], ComputingMilieux_MISCELLANEOUS, [ INFO.INFO-SC ] Computer Science [cs]/Symbolic Computation [cs.SC]
Abstract

International audience; no abstract

Published
1995

86. PoSSo-RealSolving (zero-dimensional system of polynomials)

Author

Rouillier, Fabrice, Institut de Recherche Mathématique de Rennes ( IRMAR ), Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -AGROCAMPUS OUEST-École normale supérieure - Rennes ( ENS Rennes ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National des Sciences Appliquées ( INSA ) -Université de Rennes 2 ( UR2 ), Université de Rennes ( UNIV-RENNES ) -Centre National de la Recherche Scientifique ( CNRS ), Institut de Recherche Mathématique de Rennes (IRMAR), AGROCAMPUS OUEST, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Université de Rennes 2 (UR2), Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-École normale supérieure - Rennes (ENS Rennes)-Université de Rennes 2 (UR2)-Centre National de la Recherche Scientifique (CNRS)-INSTITUT AGRO Agrocampus Ouest, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro), and Rouillier, Fabrice

Subjects
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], [INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC], ComputingMilieux_MISCELLANEOUS, [ INFO.INFO-SC ] Computer Science [cs]/Symbolic Computation [cs.SC]
Abstract

International audience; no abstract

Published
1995

87. Des formules de Bareiss à la réduction des formes quadratiques

Author

Rouillier , Fabrice, Institut de Recherche Mathématique de Rennes ( IRMAR ), Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -AGROCAMPUS OUEST-École normale supérieure - Rennes ( ENS Rennes ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National des Sciences Appliquées ( INSA ) -Université de Rennes 2 ( UR2 ), Université de Rennes ( UNIV-RENNES ) -Centre National de la Recherche Scientifique ( CNRS ), Institut de Recherche Mathématique de Rennes (IRMAR), AGROCAMPUS OUEST, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Université de Rennes 2 (UR2), Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-École normale supérieure - Rennes (ENS Rennes)-Université de Rennes 2 (UR2)-Centre National de la Recherche Scientifique (CNRS)-INSTITUT AGRO Agrocampus Ouest, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro), and Rouillier, Fabrice

Subjects
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], [INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC], ComputingMilieux_MISCELLANEOUS, [ INFO.INFO-SC ] Computer Science [cs]/Symbolic Computation [cs.SC]
Abstract

International audience; no abstract

Published
1995

88. Polynomial System Solving for Industrial Problems

Author

Rouillier, Fabrice, Faugère, Jean-Charles, 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 Publications, Lip6

Subjects
[INFO]Computer Science [cs], [INFO] Computer Science [cs], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2005

89. The implicit structure of ridges of a smooth parametric surface

Author

Cazals, Frédéric, Faugère, Jean-Charles, Pouget, Marc, Rouillier, Fabrice, 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), Solvers for Algebraic Systems and Applications (SALSA), 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 Paris-Rocquencourt, Institut de Recherche Mathématique de Rennes (IRMAR), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-École normale supérieure - Rennes (ENS Rennes)-Université de Rennes 2 (UR2)-Centre National de la Recherche Scientifique (CNRS)-INSTITUT AGRO Agrocampus Ouest, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro), INRIA, 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 ), Solvers for Algebraic Systems and Applications ( SALSA ), 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 Paris-Rocquencourt, Institut de Recherche Mathématique de Rennes ( IRMAR ), Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -AGROCAMPUS OUEST-École normale supérieure - Rennes ( ENS Rennes ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National des Sciences Appliquées ( INSA ) -Université de Rennes 2 ( UR2 ), Université de Rennes ( UNIV-RENNES ) -Centre National de la Recherche Scientifique ( CNRS ), Université Pierre et Marie Curie - Paris 6 ( UPMC ) -Centre National de la Recherche Scientifique ( CNRS ), AGROCAMPUS OUEST, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Université de Rennes 2 (UR2), Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA), and Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)

Subjects
[INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], [ INFO.INFO-OH ] Computer Science [cs]/Other [cs.OH], RIDGES, UMBILICS, DIFFERENTIAL GEOMETRY
Abstract

Given a smooth surface, a blue (red) ridge is a curve along which the maximum (minimum) principal curvature has an extremum along its curvature line. Ridges are curves of extremal curvature and therefore encode important informations used in segmentation, registration, matching and surface analysis. State of the art methods for ridge extraction either report red and blue ridges simultaneously or separately in which case need a local orientation procedure of principal directions is needed, but no method developed so far topologically certifies the curves reported. On the way to developing certified algorithms independent from local orientation procedures, we make the following fundamental contribution. For any smooth parametric surface, we exhibit the implicit equation $P=0$ of the singular curve encoding all ridges of the surface (blue and red), and show how to recover the colors from factors of $P$. Exploiting $P=0$, we also derive a zero dimensional system coding the so-called turning points, from which elliptic and hyperbolic ridge sections of the two colors can be derived. Both contributions exploit properties of the Weingarten map of the surface and require computer algebra. Algorithms exploiting the structure of $P$ for algebraic surfaces are developed in a companion paper.

Published
2005

90. Topologically certified approximation of umbilics and ridges on polynomial parametric surface

Author

Cazals, Frédéric, Faugère, Jean-Charles, Pouget, Marc, Rouillier, Fabrice, 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), Solvers for Algebraic Systems and Applications (SALSA), 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 Paris-Rocquencourt, Institut de Recherche Mathématique de Rennes (IRMAR), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-École normale supérieure - Rennes (ENS Rennes)-Université de Rennes 2 (UR2)-Centre National de la Recherche Scientifique (CNRS)-INSTITUT AGRO Agrocampus Ouest, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro), INRIA, 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 ), Solvers for Algebraic Systems and Applications ( SALSA ), 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 Paris-Rocquencourt, Institut de Recherche Mathématique de Rennes ( IRMAR ), Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -AGROCAMPUS OUEST-École normale supérieure - Rennes ( ENS Rennes ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National des Sciences Appliquées ( INSA ) -Université de Rennes 2 ( UR2 ), Université de Rennes ( UNIV-RENNES ) -Centre National de la Recherche Scientifique ( CNRS ), Université Pierre et Marie Curie - Paris 6 ( UPMC ) -Centre National de la Recherche Scientifique ( CNRS ), AGROCAMPUS OUEST, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Université de Rennes 2 (UR2), Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA), and Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)

Subjects
[INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], [ INFO.INFO-OH ] Computer Science [cs]/Other [cs.OH], RIDGES, COMPUTER ALGEBRA, DIFFERENTIAL GEOMETRY
Abstract

Given a smooth surface, a blue (red) ridge is a curve along which the maximum (minimum) principal curvature has an extremum along its curvature line. Ridges are curves of extremal curvature and encode important informations used in surface analysis or segmentation. But reporting the ridges of a surface requires manipulating third and fourth order derivatives whence numerical difficulties. Additionally, ridges have self-intersections and complex interactions with the umbilics of the surface whence topological difficulties. In this context, we make two contributions for the computation of ridges of polynomial parametric surfaces. First, by instantiating to the polynomial setting a global structure theorem of ridge curves proved in a companion paper, we develop the first certified algorithm to produce a topological approximation of the curve P encoding all the ridges of the surface. The algorithm exploits the singular structure of P umbilics and purple points, and reduces the problem to solving zero dimensional systems using Gröbner basis. Second, for cases where the zero-dimensional systems cannot be practically solved, we develop a certified plot algorithm at any fixed resolution. These contributions are respectively illustrated for Bezier surfaces of degree four and five.

Published
2005

91. Exact Computations and Real Roots of Polynomial Systems

Author

Rouillier, Fabrice, Publications, Lip6, Systèmes Polynomiaux, Implantation, Résolution Algébrique (SPIRAL), Laboratoire d'Informatique de Paris 6 (LIP6), and 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)

Subjects
[INFO]Computer Science [cs], [INFO] Computer Science [cs], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2004

92. Real roots of parametric systems of polynomial equalities and inequalities

Author

Rouillier, Fabrice, Publications, Lip6, Systèmes Polynomiaux, Implantation, Résolution Algébrique (SPIRAL), Laboratoire d'Informatique de Paris 6 (LIP6), and 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)

Subjects
[INFO]Computer Science [cs], [INFO] Computer Science [cs], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2004

93. Real roots of parametric polynomial systems

Author

Rouillier, Fabrice, Publications, Lip6, Systèmes Polynomiaux, Implantation, Résolution Algébrique (SPIRAL), Laboratoire d'Informatique de Paris 6 (LIP6), and 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)

Subjects
[INFO]Computer Science [cs], [INFO] Computer Science [cs], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2004

94. Bernstein's basis and real root isolation

Author

Mourrain, Bernard, Rouillier, Fabrice, Roy, Marie-Françoise, 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), 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), INRIA, 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), Publications, Lip6, 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
TheoryofComputation_MISCELLANEOUS, REAL ROOTS, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], [INFO]Computer Science [cs], [INFO] Computer Science [cs], COMPUTER ALGEBRA, UNIVARIATE POLYNOMIALS
Abstract

International audience; In this mostly expository paper we explain how the Bernstein basis, widely used in computer-aided geometric design, provides an efficient method for real root isolation, using de Casteljau’s algorithm. We discuss the link between this approach and more classical methods for real root isolation. We also present a new improved method for isolating real roots in the Bernstein basis inspired by Roullier and Zimmerman.

Published
2004

97. Efficient real solutions and robotics

Author

Rouillier, Fabrice, 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 Publications, Lip6

Subjects
[INFO]Computer Science [cs], [INFO] Computer Science [cs], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2003

98. A library for arbitrary precision interval arithmetic

Author

Revol, Nathalie, Rouillier, Fabrice, 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), 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), and 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)

Subjects
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], ComputingMilieux_MISCELLANEOUS
Abstract

International audience; no abstract

Published
2002

99. Outils pour l'étude des zéros réels de systèmes algébriques

Author

Rouillier, Fabrice, 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), and 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)

Subjects
real roots, applications, zéros réels, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], algebraic systems, systèmes algébriques, computer algebra, calcul formel
Abstract

Colloque sur invitation. nationale.; National audience; Nous présentons quelques algorithmes performants, utilisant principalement du calcul exact, pour l'étude des zéros réels des systèmes algébriques. Ce type d'algorithmes, dont la sortie est complètement certifiée, permet d'obtenir des résultats souvant impossible à établir par des méthodes purement numériques : existance de zéros réels, nombre de zéros réels, isolation des coordonnées des solutions, multiplicités. Ceci sera présenté sur la base d'un ou deux exemples pratiques, issus de problèmes académiques ou industriels. Les outils (et rappels théoriques nécessaires) seront introduits un à un au cours de résolution de ces exemples.

Published
2002

100. Using computer algebra tools to classify serial cuspidal manipulators

Author

Corvez, Solen, Rouillier, Fabrice, 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), and INRIA

Subjects
Computer Science::Robotics, CYLINDRICAL ALGEBRAIC DECOMPOSITION, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], GRÖBNER BASIS, SERIAL MANIPULATORS, SEMIALGEBRAIC SETS, TRIANGULAR SETS, COMPUTER ALGEBRA
Abstract

In this paper we present a classification of 3-revolute-jointed manipulators based on the cuspidal behaviour. It was shown in a previous work that this ability to change posture without meeting a singularity is equivalent to the existence of a point in the workspace, such that a polynomial of degree four depending on the parameters of the manipulator and on the cartesian coordinates of the effector has a triple root. More precisely, from a partition of the parameters' space, such that in any connected component of this partition the number of triple roots is constant, we need to compute one sample point by cell, in order to have a full description, in terms of cuspidality, of the different possible configurations.

Published
2002

Catalog

Books, media, physical & digital resources
See catalog results