Ioannis Z. Emiris, George M. Tzoumas
in the plane: incremental algorithm, bottleneck is predicate InCircle. • High algebraic complexity: 184 complex tritangent circles. How many are real?
Algebraic methods for counting Euclidean embeddings of rigid graphs (2009)
Emiris, Ioannis Z., Tsigaridas, Elias P., Varvitsiotis, Antonios
The study of (minimally) rigid graphs is motivated by numerous applications, mostly in robotics and bioinformatics. A major open problem concerns the number of embeddings of such graphs, up to rigid...
Multihomogeneous Resultant Formulae for Systems with Scaled Support (2009)
Emiris, Ioannis Z., Mantzaflaris, Angelos
Constructive methods for matrices of multihomogeneous resultants for unmixed systems have been studied by Weyman, Zelevinsky, Sturmfels, Dickenstein and Emiris. We generalize these constructions to...
2.3 Gaussian Elimination Algorithm.......................... 7 (2009)
Angel D Az, Ioannis Z. Emiris, Erich Kaltofen, Victor Y. Pan
1
The DMM bound: multivariate (aggregate) separation bounds (2009)
Emiris, Ioannis Z., Mourrain, Bernard, Tsigaridas, Elias
In this paper we present aggregate separation bounds for polynomials systems. We call the bounds Davenport-Mahler-Mignotte (\dmm), and we prove that in most of the cases are close to optimal. The...
The DMM bound: multivariate (aggregate) separation bounds (2009)
Emiris, Ioannis Z., Mourrain, Bernard, Tsigaridas, Elias P.
In this paper we present aggregate separation bounds for polynomials systems. We call the bounds Davenport-Mahler-Mignotte (\dmm), and we prove that in most of the cases are close to optimal. The...
The DMM bound: multivariate (aggregate) separation bounds (2009)
Emiris, Ioannis Z., Mourrain, Bernard, Tsigaridas, Elias P.
In this paper we present aggregate separation bounds for polynomials systems. We call the bounds Davenport-Mahler-Mignotte (\dmm), and we prove that in most of the cases are close to optimal. The...
Computing the Newton polygon of the implicit equation (2008)
Emiris, Ioannis Z., Konaxis, Christos, Palios, Leonidas
We consider polynomially and rationally parameterized curves, where the polynomials in the parameterization have fixed supports and generic coefficients. We apply sparse (or toric) elimination theory...
ALGEBRAIC AND NUMERICAL ALGORITHMS 1 (2008)
Ioannis Z. Emiris, Elias P. Tsigaridas
Arithmetic manipulation with matrices and polynomials is a common subject for algebraic (or symbolic) and numerical computing. Typical computational problems in these areas include the solution of a...
Maximizing the Guarded Interior of an Art Gallery (2008)
Ioannis Z. Emiris, Christodoulos Fragoudakis, Euripides Markou
In the Art Gallery problem a polygon is given and the goal is to place as few guards as possible so that the entire area of the polygon is covered. We address a closely related problem: how to place...
Computing the Newton polytope of specialized resultants (2008)
Ioannis Z. Emiris, Christos Konaxis, Leonidas Palios
We consider sparse (or toric) elimination theory in order to describe, by combinatorial means, the monomials appearing in the (sparse) resultant of a given overconstrained algebraic system. A...
Thème Sym, Elias P. Tsigaridas, Ioannis Z. Emiris, Projet Geometrica
apport de recherche SN 0249-6399 ISRN INRIA/RR--6059--FR+ENG
Thème Sym, Elias P. Tsigaridas, Ioannis Z. Emiris, Projet Geometrica
apport de recherche SN 0249-6399 ISRN INRIA/RR--????--FR+ENG
Comparing real algebraic numbers of small (2008)
Ioannis Z. Emiris, Elias P. Tsigaridas
Abstract. We study polynomials of degree up to 4 over the rationals or a computable real subfield. Our motivation comes from the need to evaluate predicates in nonlinear computational geometry...
Distributed Routing in Tree Networks with Few Landmarks (2008)
Ioannis Z. Emiris, Euripides Markou, Aris Pagourtzis
Abstract. We consider the problem of finding a short path between any two nodes of a network when no global information is available, nor any oracle to help in routing. A mobile agent, situated in a...
Real algebraic numbers and polynomial systems of small degree ⋆ (2008)
Ioannis Z. Emiris, Elias P. Tsigaridas
We present exact and complete algorithms based on precomputed Sturm-Habicht sequences, discriminants and invariants, that classify, isolate with rational points and compare the real roots of...
Distributed Routing in Tree Networks with Few Landmarks (2008)
Ioannis Z. Emiris, Euripides Markou, Aris Pagourtzis
European Social Fund (75%) and national resources (25%). Abstract. We consider the problem of finding a short path between any two nodes of a network when no global information is available, nor any...
Computations with one and two real algebraic numbers (2008)
Ioannis Z. Emiris, Elias P. Tsigaridas
We present algorithmic and complexity results concerning computations with one and two real algebraic numbers, as well as real solving of univariate polynomials and bivariate polynomial systems with...
Abstract The Predicates for the Voronoi Diagram of Ellipses ∗ (2008)
Ioannis Z. Emiris, Elias P. Tsigaridas, George M. Tzoumas
This paper examines the computation of the Voronoi diagram of a set of ellipses in the Euclidean plane. We propose the first complete algorithms, under the exact computation paradigm, for the...
ACS Algorithms for Complex Shapes with Certified Numerics and Topology (2008)
Dimitrios I, Ioannis Z. Emiris, Bernard Mourrain, Elias P. Tsigaridas, Elias P. Tsigaridas
Experimental implementation of more operations on algebraic numbers, possibly with the addition of numeric filters, and of robust operations on small polynomial systems
Abstract The structure of sparse resultant matrices (2008)
Ioannis Z. Emiris, Victor Y. Pan
Resultants characterize the existence of roots of systems of multivariate nonlinear polynomial equations, while their matrices reduce the computation of all common zeros to a problem in linear...
2.3 Gaussian Elimination Algorithm.......................... 7 (2008)
Angel D Az, Ioannis Z. Emiris, Erich Kaltofen, Victor Y. Pan
1
Sparseness in the implicit equation of rational parametric curves and surfaces (2008)
Ioannis Z. Emiris, Ilias S. Kotsireas
In [6] we used various tools from toric (or sparse) elimination theory, in order to predict the support of the implicit equation of a parametric curve or (hyper)surface. The problem of switching from...
Predicates for the Planar Additively Weighted Voronoi Diagram (2008)
Menelaos I. Karavelas, Ioannis Z. Emiris
We consider the geometric predicates involved in an incremental algorithm for computing the additively weighted Voronoi diagram in the plane. These predicates correspond to certain algebraic...
Experimental evaluation and cross-benchmarking of univariate real solvers (2008)
Emiris, Ioannis Z., Hemmer, Michael, Karavelas, Menelaos, Mourrain, Bernard, Tsigaridas, Elias P., Zafeirakopoulos, Zafeirakis
Real solving of univariate polynomials is a fundamental problem with several important applications. This paper focuses on the efficient and generic black-box implementations of state-of-the-art...
Experimental evaluation and cross-benchmarking of univariate real solvers (2008)
Emiris, Ioannis Z., Hemmer, Michael, Karavelas, Menelaos, Mourrain, Bernard, Tsigaridas, Elias P., Zafeirakopoulos, Zafeirakis
Real solving of univariate polynomials is a fundamental problem with several important applications. This paper focuses on the efficient and generic black-box implementations of state-of-the-art...
Experimental evaluation and cross-benchmarking of univariate real solvers (2008)
Emiris, Ioannis Z., Hemmer, Michael, Karavelas, Menelaos, Mourrain, Bernard, Tsigaridas, Elias P., Zafeirakopoulos, Zafeirakis
Real solving of univariate polynomials is a fundamental problem with several important applications. This paper focuses on the efficient and generic black-box implementations of state-of-the-art...
Experimental evaluation and cross-benchmarking of univariate real solvers (2008)
Emiris, Ioannis Z., Hemmer, Michael, Karavelas, Menelaos, Mourrain, Bernard, Tsigaridas, Elias P., Zafeirakopoulos, Zafeirakis
Real solving of univariate polynomials is a fundamental problem with several important applications. This paper focuses on the efficient and generic black-box implementations of state-of-the-art...
Notes creuses sur le r#sultant creux (2007)
La th#orie d'#limination creuse utilise plusieurs notions g#om#triques dans l'#tude de polyn#mes et de syst#mes alg#briques. Avant d'examiner le passage de l'alg#bre # la...
Matrix Methods for Solving Algebraic Systems (2007)
The problem of computing all common zeros of a system of polynomials is of fundamental importance in a wide variety of scientic and engineering applications. This article surveys eOEcient methods...
Computing Exact Geometric Predicates Using Modular Arithmetic with Single Precision (2007)
Hervé Brönnimann, Herv Br#nnimann, Ioannis Z. Emiris, Sylvain Pion, Victor Y. Pan
We propose an efficient method that determines the sign of a multivariate polynomial expression with integer coefficients. This is a central operation on which the robustness of many geometric...
Angel Díaz, Ioannis Z. Emiris, Erich Kaltofen, Victor Y. Pan
This article, along with [Elkadi and Mourrain 1996], explain the correlation between residue theory and the Dixon matrix, which yields an alternative method for studying and approximating all common...
Computing Exact Geometric Predicates Using Modular Arithmetic With Single Precision (2007)
Herv Brnnimann Ioannis, Herv Br#nnimann, Ioannis Z. Emiris, Victor Y. Pan
: We propose an eOEcient method that determines the sign of a multivariate polynomial expression with integer coeOEcients. This is a central operation on which the robustness of many geometric...
Monomial Bases and Polynomial System Solving (2007)
Extend Ed, Ioannis Z. Emiris, Ashutosh Rege
) Ioannis Z. Emiris Ashutosh Rege Abstract This paper addresses the problem of efficient construction of monomial bases for the coordinate rings of zerodimensional varieties. Existing approaches rely...
La Cinématique Des Molécules (2007)
6> i par des relations entre les angles OE i , ` i et les longueurs L i . Exercice 1 : Un nouveau type D#velopper des fonctions Maple d'apr#s le typage du cours de mercredi matin sur le...
Ioannis Z. Emiris, Erich Kaltofen, Victor Y. Pan
1 Supported by NSF grant No. CCR-9319776 and by GTE under a Graduate Computer Science Fellowship. 2 Supported by the European Union under ESPRIT FRISCO project LTR 21.024. 3 Supported by NSF grant...
A comparative application of convex hull algorithms in (2007)
Kyriakos Zervoudakis, Ioannis Z. Emiris
two and three dimensions
Apport De Recherche, Mihail N. Vrahatis, Ioannis Z. Emiris, Ioannis Z. Emiris, Bernard Mourrain, Bernard Mourrain, ...
In this report, we implement the concept of topological degree to isolate and compute all zeros of systems of nonlinear algebraic equations when the only computable information required is the...
Ioannis Z. Emiris, Ioannis Z. Emiris, Bernard Mourrain, Bernard Mourrain, Thème Génie Logiciel, Projet Safir
apport de recherche Polynomial system solving: the case of a six-atom molecule
On the complexity of real solving bivariate systems (2007)
Diochnos, Dimitrios, Emiris, Ioannis Z., Tsigaridas, Elias
This paper is concerned with exact real solving of well-constrained, bivariate algebraic systems. The main problem is to isolate all common real roots in rational rectangles, and to determine their...
On the complexity of real solving bivariate systems (2007)
Diochnos, Dimitrios, Emiris, Ioannis Z., Tsigaridas, Elias
This paper is concerned with exact real solving of well-constrained, bivariate algebraic systems. The main problem is to isolate all common real roots in rational rectangles, and to determine their...
Ioannis Z. Emiris, George M. Tzoumas, Elias P. Tsigaridas
We present a C++ open-source implementation of an incremental algorithm for the computation of the Voronoi diagram of ellipses in the Euclidean plane. This is the first complete implementation, under...
Real Algebraic Numbers: Complexity Analysis and Experimentations (2006)
Emiris, Ioannis Z., Mourrain, Bernard, Tsigaridas, Elias P.
We present algorithmic, complexity and implementation results concerning real root isolation of a polynomial of degree $d$, with integer coefficients of bit size $\le\tau$, using Sturm (-Habicht)...
Real Algebraic Numbers: Complexity Analysis and Experimentations (2006)
Emiris, Ioannis Z., Mourrain, Bernard, Tsigaridas, Elias P.
We present algorithmic, complexity and implementation results concerning real root isolation of a polynomial of degree $d$, with integer coefficients of bit size $\le\tau$, using Sturm (-Habicht)...
The predicates for the Voronoi diagram of ellipses (2006)
Ioannis Z. Emiris, George M. Tzoumas, Elias Tsigaridas
This paper examines the computation of the Voronoi diagram of a set of ellipses in the Euclidean plane. We propose the first complete algorithms, under the exact computation paradigm, for the...
Ioannis Z. Emiris, Elias P. Tsigaridas, Ioannis Z. Emiris, Elias P. Tsigaridas
Project co-funded by the European Commission within FP6 (2002–2006) under contract nr. IST-006413 Robust operations on small polynomial systems
Tsigaridas. Real Algebraic Numbers: Complexity Analysis and Experimentation (2006)
Ioannis Z. Emiris, Bernard Mourrain, Elias P. Tsigaridas
Abstract. We present algorithmic, complexity and implementation results concerning real root isolation of a polynomial of degree d, with integer coefficients of bit size ≤ τ, using Sturm...
On the complexity of real root isolation using Continued Fractions (2006)
Elias P. Tsigaridas, Ioannis Z. Emiris
We present algorithmic, complexity and implementation results concerning real root isolation of integer univariate polynomials using the continued fraction expansion of real algebraic numbers. One...
Alcalá De Henares, M. J. Chávez, A. Quintero, M. T. Villar, Cornelia Dangelmayr, Stefan Felsner, ...
The structure of flag sphere triangulations
The Offset to an Algebraic Curve and an Application to Conics (2005)
Anton, François, Emiris, Ioannis Z., Mourrain, Bernard, Teillaud, Monique
Curve offsets are important objects in computer-aided design. We study the algebraic properties of the offset to an algebraic curve, thus obtaining a general formula for its degree. This is applied...
The Offset to an Algebraic Curve and an Application to Conics (2005)
Anton, François, Emiris, Ioannis Z., Mourrain, Bernard, Teillaud, Monique
Curve offsets are important objects in computer-aided design. We study the algebraic properties of the offset to an algebraic curve, thus obtaining a general formula for its degree. This is applied...
Tsigaridas. Minkowski decomposition of convex lattice polygons (2005)
Ioannis Z. Emiris, Elias P. Tsigaridas
Summary. A relatively recent area of study in geometric modelling concerns toric Bézier patches. In this line of work, several questions reduce to testing whether a given convex lattice polygon can...
Real solving of bivariate polynomial systems (2005)
Ioannis Z. Emiris, Elias P. Tsigaridas
Abstract. We propose exact, complete and efficient methods for 2 problems: First, the real solving of systems of two bivariate rational polynomials of arbitrary degree. This means isolating all...
Computations with real algebraic numbers of degree up to 4 (2004)
Elias P. Tsigaridas, Ioannis Z. Emiris
up to 4
Towards an open curved kernel (2004)
Ioannis Z. Emiris, Monique Teillaud, Sophia Antipolis, Athanasios Kakargias
Our work goes towards answering the growing need for the robust and efficient manipulation of curved objects in numerous applications. The kernel of the cgal library provides several functionalities...
Molecular Conformation Search by Matrix Perturbations,” preprint (2003)
Theodore G. Nikitopoulos, Ioannis Z. Emiris
Abstract. Three-dimensional structure information is fundamental in drug design and discovery, docking, and chemical function identication. Enumeration of all possible conformations provides a...
Computing Sparse Projection Operators (2001)
Carlos D'Andrea, Ioannis Z. Emiris
: We produce a new family of projection operators applying linear perturbations on sparse (or toric) resultants. These operators are not identically zero but vanish on all proper components of the...
A Subdivision-Based Algorithm for the Sparse Resultant (2000)
John F. Canny, Ioannis Z. Emiris
Multivariate resultants generalize the Sylvester resultantoftwo polynomials and characterize the solvability of a polynomial system. They also reduce the computation of all common roots to a problem...
Mixed Volume Implementation (2000)
This report outlines the implemented algorithm and the usage of the program. For further information, including proofs, alternative algorithms, and a time and randomization complexity analysis,...
Enumerating a subset of the integer points inside a Minkowski sum (2000)
The relatively recent theory of sparse variable elimination exploits the structure of algebraic equations in order to relate it, on the one hand, to the bounds on the number of roots and, on the...
Computing integer points in Minkowski sums (2000)
The relatively recent theory of sparse variable elimination exploits the structure in polynomial equations in order to define tighter bounds on the number of common roots and faster methods for...
Comparison Of Fourth-Degree Algebraic Numbers And Applications To Geometric Predicates (2000)
Ioannis Z. Emiris, Ioannis Z. Emiris, Elias P. Tsigaridas, Elias P. Tsigaridas
We present algorithms for the exact comparison of the real roots of two polynomials of degree 4. The algorithm precomputes Sturm sequences and isolating intervals for the representation of the roots...
Sign Methods for Counting and Computing Real Roots of Algebraic Systems (1999)
Emiris, Ioannis Z., Mourrain, Bernard, Vrahatis, Mihail N.
In this report, we implement the concept of topological degree to isolate and compute all zeros of systems of nonlinear algebraic equations when the only computable information required is the...
Sign Methods for Counting and Computing Real Roots of Algebraic Systems (1999)
Emiris, Ioannis Z., Mourrain, Bernard, Vrahatis, Mihail N.
In this report, we implement the concept of topological degree to isolate and compute all zeros of systems of nonlinear algebraic equations when the only computable information required is the...
Sign Methods for Counting and Computing Real Roots of Algebraic Systems (1999)
Unit Inria, Sophia Antipolis, Ioannis Z. Emiris, Ioannis Z. Emiris, Bernard Mourrain, Bernard Mourrain, ...
In this report, we implement the concept of topological degree to isolate and compute all zeros of systems of nonlinear algebraic equations when the only computable information required is the...
Computing integer points in Minkowski sums (1999)
: The relatively recent theory of sparse variable elimination exploits the structure in polynomial equations in order to dene tighter bounds on the number of common roots and faster methods for...
A Subdivision-Based Algorithm for the Sparse Resultant (1999)
John F. Canny, Ioannis Z. Emiris
Multivariate resultants generalize the Sylvester resultant of two polynomials and characterize the solvability of a polynomial system. They also reduce the computation of all common roots to a...
Sign Determination in Residue Number Systems (1999)
Herv Brnnimann Ioannis, Herv Br#nnimann, Ioannis Z. Emiris, Victor Y. Pan
Sign determination is a fundamental problem in algebraic as well as geometric computing. It is the critical operation when using real algebraic numbers and exact geometric predicates. We propose an...
Matrices in Elimination Theory (1999)
Ioannis Z. Emiris, Bernard Mourrain
The last decade has witnessed the rebirth of resultant methods as a powerful computational tool for variable elimination and polynomial system solving. In particular, the advent of sparse elimination...
Sign Determination in Residue Number Systems (1999)
Hervé Brönnimann, Herv Br#nnimann, Ioannis Z. Emiris, Sylvain Pion, Victor Y. Pan
Sign determination is a fundamental problem in algebraic as well as geometric computing. It is the critical operation when using real algebraic numbers and exact geometric predicates. We propose an...
Ioannis Z. Emiris, Victor Y. Pan
Introduction The subject of this chapter lies in the area of theoretical computer science, though it borrows certain results from computational mathematics, and is fundamental to the theory and...
Sign determination in residue number systems (1999)
Hervé Brönnimann, Ioannis Z. Emiris, Victor Y. Pan
Sign determination is a fundamental problem in algebraic as well as geometric computing. It is the critical operation when using real algebraic numbers and exact geometric predicates. We propose an...
Modular Arithmetic for Linear Algebra Computations in the Real Field (1998)
Ioannis Z. Emiris, Yanqiang Yu, Victor Y. Pan
The aim of this work is to decrease the bit precision required in communications without affecting the precision of the answer...
MARS: A Maple/Matlab/C Resultant-based Solver (1998)
Aaron Wallack, Ioannis Z. Emiris, D. Manocha, Dinesh Manocha
The problem of computing zeros of a system of polynomial equations has been well studied in the computational literature. A number of algorithms have been proposed and many computer algebra and...
Matrices in Elimination Theory (1998)
Ioannis Z. Emiris, Bernard Mourrain
The last decade has witnessed the rebirth of resultant methods as a powerful computational tool for variable elimination and polynomial system solving. In particular, the advent of sparse elimination...
How to Count Efficiently All Affine Roots of a Polynomial System (1998)
Polynomials are ubiquitous in a variety of applications. A relatively recent theory exploits their sparse structure by associating a point configuration to each polynomial system; however, it has so...
Modular arithmetic for linear algebra computations (1998)
Ioannis Z. Emiris, Y. Pan, Yanqiang Yu
The aim of this work is to decrease the bit precision required in computations without a ecting the precision of the answer, whether this is computed exactly or within some tolerance. By precision we...
How to Count Efficiently all Affine Roots of a Polynomial System (1997)
Emiris, Ioannis Z., Verschelde, Jan
Polynomials are ubiquitous in a variety of applications. A relatively recent theory exploits their sparse structure by associating a point configuration to each polynomial system; however, it has so...
Computing Exact Geometric Predicates Using Modular Arithmetic with Single Precision (1997)
Brönnimann, Hervé, Emiris, Ioannis Z., Pan, Victor Y., Pion, Sylvain
We propose an efficient method that determines the sign of a multivariate polynomial expression with integer coefficients. This is a central operation on which the robustness of many geometric...
A General Solver Based on Sparse Resultants: Numerical Issues and Kinematic Applications (1997)
Sparse elimination and the sparse resultant exploit the structure of polynomials by measuring their complexity in terms of Newton polytopes instead of total degree. % The sparse, or Newton, resultant...
How to Count Efficiently all Affine Roots of a Polynomial System (1997)
Emiris, Ioannis Z., Verschelde, Jan
Polynomials are ubiquitous in a variety of applications. A relatively recent theory exploits their sparse structure by associating a point configuration to each polynomial system; however, it has so...
Computing Exact Geometric Predicates Using Modular Arithmetic with Single Precision (1997)
Brönnimann, Hervé, Emiris, Ioannis Z., Pan, Victor Y., Pion, Sylvain
We propose an efficient method that determines the sign of a multivariate polynomial expression with integer coefficients. This is a central operation on which the robustness of many geometric...
A General Solver Based on Sparse Resultants: Numerical Issues and Kinematic Applications (1997)
Sparse elimination and the sparse resultant exploit the structure of polynomials by measuring their complexity in terms of Newton polytopes instead of total degree. % The sparse, or Newton, resultant...
Efficient perturbations for handling geometric degeneracies (1997)
Ioannis Z. Emiris, John F. Canny, Raimund Seidel
This article de nes input perturbations so that an algorithm designed under certain restrictions on the input can execute on arbitrary instances. A syntactic definition of perturbations is proposed...
Efficient perturbations for handling geometric degeneracies (1997)
Ioannis Z. Emiris, John F. Canny, Raimund Seidel
Abstract. This article defines input perturbations so that an algorithm designed under certain restrictions on the input can execute on arbitrary instances. A syntactic definition of perturbations is...
Certified approximate univariate GCDs (1997)
Ioannis Z. Emiris, Henri Lombardi
We study the approximate GCD of two univariate polynomials given with limited accuracy or, equivalently, the exact GCD of the perturbed polynomials within some prescribed tolerance. A perturbed...
A General Solver Based on Sparse Resultants: Numerical Issues and Kinematic Applications (1997)
Ioannis Z. Emiris, Ioannis Z. Emiris
Sparse elimination and the sparse resultant exploit the structure of polynomials by measuring their complexity in terms of Newton polytopes instead of total degree. We sketch the sparse resultant...
How to Count Efficiently All Affine Roots of a Polynomial System (1997)
Jan Verschelde, Ioannis Z. Emiris, Ioannis Z. Emiris, Projet Safir
Polynomials are ubiquitous in a variety of applications. A relatively recent theory exploits their sparse structure by associating a point configuration to each polynomial system; however, it has so...
Exact Modular Arithmetic With Single Precision (1997)
Hervé Brönnimann, Herv Br#nnimann, Ioannis Z. Emiris, Sylvain Pion, Victor Y. Pan
Sign determination is a fundamental problem in algebraic as well as geometric computing. It is the critical operation when using real algebraic numbers and exact geometric predicates. We propose an...
Computer Algebra Methods for Studying and Computing Molecular Conformations (1997)
Ioannis Emiris And, Ioannis Z. Emiris, Bernard Mourrain
A relatively new branch of computational biology has been emerging as an eoeort to supplement traditional techniques of large scale search in drug design by structure-based methods, in order to...
A Complete Implementation for Computing General Dimensional Convex Hulls (1997)
We present a robust implementation of the Beneath-Beyond algorithm for computing convex hulls in arbitrary dimension. Certain techniques used are of independent interest in the implementation of...
Symbolic and Numeric Methods for Exploiting Structure in Constructing Resultant Matrices (1997)
Ioannis Z. Emiris, Victor Y. Pan
This paper identifies and exploits the structure of Newton matrices by designing an efficient numerical rank test and exact polynomial arithmetic in the context of sparse elimination. This yields...
Computing Exact Geometric Predicates Using Modular Arithmetic with Single Precision (1997)
Hervé Brönnimann, Herv Br#nnimann, Ioannis Z. Emiris, Sylvain Pion, Ioannis Z. Emiris, Victor Y. Pan, ...
We propose an efficient method that determines the sign of a multivariate polynomial expression with integer coefficients. This is a central operation on which the robustness of many geometric...
Computer Algebra Methods for Studying and Computing Molecular Conformations (1997)
Ioannis Z. Emiris, Bernard Mourrain
A relatively new branch of computational biology has been emerging as an effort to supplement traditional techniques of large scale search in drug design by structure-based methods, in order to...
The Structure of Sparse Resultant Matrices (1997)
Ioannis Z. Emiris, Victor Y. Pan
Resultants characterize the existence of roots of systems of multivariate nonlinear polynomial equations, while their matrices reduce the computation of all common zeros to a problem in linear...
Efficient Perturbations for Handling Geometric Degeneracies (1997)
Ioannis Z. Emiris, John F. Canny, Raimund Seidel
. This article defines input perturbations so that an algorithm designed under certain restrictions on the input can execute on arbitrary instances. A syntactic definition of perturbations is...
Symbolic-Numeric Algebra for Polynomials (1997)
this article, the coeOEcients are most often rational, but could also be complex. The fundamental computational problem of algebra is to compute all values of x for which the polynomial evaluates to...
Efficient Perturbations for Handling Geometric Degeneracies (1997)
Ioannis Z. Emiris, John F. Canny, Raimund Seidel
. This article defines input perturbations so that an algorithm designed under certain restrictions on the input can execute on arbitrary instances. A syntactic definition of perturbations is...
Distributed Computation of Mixed Volume (1997)
Ioannis Z. Emiris, Thierry Giordano
We propose a parallel algorithm for computing the mixed volume of n convex polytopes in n-dimensional space. Mixed volume generalizes standard Euclidean volume and is the cornerstone of a, relatively...
Polynomial System Solving: the Case of a Six-Atom Molecule (1996)
Emiris, Ioannis Z., Mourrain, Bernard
A relatively new branch of computational biology and chemistry has been emerging as an effort to apply successful paradigms and algorithms from geometry and robot kinematics to predicting the...
Polynomial System Solving: the Case of a Six-Atom Molecule (1996)
Emiris, Ioannis Z., Mourrain, Bernard
A relatively new branch of computational biology and chemistry has been emerging as an effort to apply successful paradigms and algorithms from geometry and robot kinematics to predicting the...
> ; dim oe = dimF 1 + \Delta \Delta \Delta + dimFn : On utilise une d#nition pour le volume mixte qui dioe#re de la d#nition classique par un facteur n!, o# n est la dimension de l'espace...
Le Résultant: Théorie Et Applications (1996)
Ioannis Z. Emiris, Le Bessat, Ff L
Deux r#sultants principaux ffl Le r#sultant classique pour de polyn#mes denses homogeneis#s : L n = P n [vdW50]. Syst#mes lin#aires : f i = c i1 x 1 + \Delta \Delta \Delta + c in x n + c i(n+1) . R =...
On the Complexity of Sparse Elimination (1996)
Sparse elimination exploits the structure of a multivariate polynomial by considering its Newton polytope instead of its total degree. We concentrate on polynomial systems that generate...
Notes Creuses Sur Le Resultant Creux (1996)
Introduction La th#orie d'#limination creuse utilise plusieurs notions g#om#triques dans l'#tude de polyn#mes et de syst#mes alg#briques. Avant d'examiner le passage de l'alg#bre...
Polynomial System Solving: The Case of a Six-Atom Molecule (1996)
Ioannis Z. Emiris, Ioannis Z. Emiris, Bernard Mourrain, Bernard Mourrain
: A relatively new branch of computational biology and chemistry has been emerging as an eoeort to apply successful paradigms and algorithms from geometry and robot kinematics to predicting the...
Numerical Univariate Polynomial GCD (1996)
Ioannis Z. Emiris, Andre Galligo, Henri Lombardi
We formalize the notion of approximate GCD for univariate polynomials given with limited accuracy and then address the problem of its computation. Algebraic concepts are applied in order to provide a...
On the Complexity of Sparse Elimination (1996)
Sparse elimination exploits the structure of a set of multivariate polynomials by measuring complexity in terms of Newton polytopes. We examine polynomial systems that generate 0-dimensional ideals:...
Workshop on Symbolic-Numeric Algebra for Polynomials (1996)
B. Mourrain, S. Watt, Ioannis Z. Emiris, Bernard Mourrain
This meeting is intended as a timely workshop to discuss the emerging understanding of problems involving polynomials with inexactly-known coe cients. Such polynomial problems arise, for example,...
A Complete Implementation for Computing General Dimensional Convex Hulls (1995)
We study two important, and often complementary, issues in the implementation of geometric algorithms, namely exact arithmetic and degeneracy. We focus on integer arithmetic and propose a general and...
A Complete Implementation for Computing General Dimensional Convex Hulls (1995)
We study two important, and often complementary, issues in the implementation of geometric algorithms, namely exact arithmetic and degeneracy. We focus on integer arithmetic and propose a general and...
A general approach to removing degeneracies (1995)
Abstract. We wish to increase the power of an arbitrary algorithm designed for non-degenerate input, by allowing it to execute on all inputs. We concentrate on in nitesimal symbolic perturbations...
Efficient incremental algorithms for the sparse resultant and the mixed volume (1995)
Ioannis Z. Emiris, John F. Canny
We propose a new and efficient algorithm for computing the sparse resultant of a system of n + 1 polynomial equations in n unknowns. This algorithm produces a matrix whose entries are coefficients of...
A Complete Implementation for Computing General Dimensional Convex Hulls (1995)
Ioannis Z. Emiris, Ioannis Z. Emiris
: We study two important, and often complementary, issues in the implementation of geometric algorithms, namely exact arithmetic and degeneracy. We focus on integer arithmetic and propose a general...
Efficient Incremental Algorithms for the Sparse Resultant and the Mixed Volume (1995)
Ioannis Z. Emiris, John F. Canny
This article continues work by Canny and Emiris (1993) for constructing matrix formulae for the sparse resultant. As in that article, we build resultant matrices whose entries are either zero or...
An Efficient Algorithm for the Sparse Resultant (1993)
John F. Canny, Ioannis Z. Emiris
We propose a compact formula for the sparse resultant of an arbitrary system of n+1 Laurent polynomials in n variables. This resultant generalizes the classical one and has significantly lower degree...
A General Approach To Removing Degeneracies (1991)
Ioannis Z. Emiris, John F. Canny
. We wish to increase the power of an arbitrary algorithm designed for non-degenerate input, by allowing it to execute on all inputs. We concentrate on infinitesimal symbolic perturbations that do...
How to Count Efficiently All Affine Roots of a Polynomial System (1990)
Ioannis Z. Emiris, Jan Verschelde
Polynomials are ubiquitous in a variety of applications. A relatively recent theory exploits their sparse structure by associating a point configuration to each polynomial system; however, it has so...