1,721,076 research outputs found
Combinatorics of 4-dimensional resultant polytopes
No full textThe Newton polytope of the resultant, or resultant polytope, characterizes the resultant polynomial more precisely than total degree. The combinatorics of resultant polytopes are known in the Sylvester case [4] and up to dimension 3 [9]. We extend this work by studying the combinatorial characterization of 4-dimensional resultant polytopes, which show a greater diversity and involve computational and combinatorial challenges. In particular, our experiments, based on software respol for computing resultant polytopes, establish lower bounds on the maximal number of faces. By studying mixed subdivisions, we obtain tight upper bounds on the maximal number of facets and ridges, thus arriving at the following maximal f-vector: (22, 66, 66, 22), i.e. vector of face cardinalities. Certain general features emerge, such as the symmetry of the maximal f-vector, which are intriguing but still under investigation. We establish a result of independent interest, namely that the f-vector is maximized when the input supports are sufficiently generic, namely full dimensional and without parallel edges. Lastly, we offer a classification result of all possible 4-dimensional resultant polytopes.Fil: Dickenstein, Alicia Marcela. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigaciones Matemáticas "Luis A. Santaló". Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigaciones Matemáticas "Luis A. Santaló"; ArgentinaFil: Emiris, Ioannis Z.. University of Athens; GreciaFil: Fisikopoulos, Fisikopoulos. University of Athens; GreciaISSAC'13 : International Symposium on Symbolic and Algebraic ComputationBostonEstados UnidosAssociation for Computing Machiner
Compact Formulae in Sparse Elimination
Get PDFInternational audienceIt has by now become a standard approach to use the theory of sparse (or toric) elimination, based on the Newton polytope of a polynomial, in order to reveal and exploit the structure of algebraic systems. This talk surveys compact formulae, including older and recent results, in sparse elimination. We start with root bounds and juxtapose two recent formulae: a generating function of the m-Bézout bound and a closed-form expression for the mixed volume by means of a matrix permanent. For the sparse resultant, a bevy of results have established determinantal or rational formulae for a large class of systems, starting with Macaulay. The discriminant is closely related to the resultant but admits no compact formula except for very simple cases. We offer a new determinantal formula for the discriminant of a sparse multilinear system arising in computing Nash equilibria. We introduce an alternative notion of compact formula, namely the Newton polytope of the unknown polynomial. It is possible to compute it efficiently for sparse resultants, discriminants, as well as the implicit equation of a parameterized variety. This leads us to consider implicit matrix representations of geometric objects
Mixed Subdivisions Suitable for the Greedy Canny–Emiris Formula
No full textThe Canny–Emiris formula (Canny and Emiris in International symposium on applied algebra, algebraic algorithms, and error-correcting codes, 1993) gives the sparse resultant as the ratio of the determinant of a Sylvester-type matrix over a minor of it, both obtained via a mixed subdivision algorithm. In Checa and Emiris (Proceedings of the 2022 international symposium on symbolic and algebraic computation, 2022), the same authors gave an explicit class of mixed subdivisions for the greedy approach so that the formula holds, and the dimension of the constructed matrices is smaller than that of the subdivision algorithm, following the approach of Canny and Pedersen (An algorithm for the Newton resultant, 1993). Our method improves upon the dimensions of the matrices when the Newton polytopes are zonotopes and the systems are multihomogeneous. In this text, we provide more such cases, and we conjecture which might be the liftings providing minimal size of the resultant matrices. We also describe two applications of this formula, namely in computer vision and in the implicitization of surfaces, while offering the corresponding JULIA code. We finally introduce a novel tropical approach that leads to an alternative proof of a result in Checa and Emiris (Proceedings of the 2022 international symposium on symbolic and algebraic computation, 2022). © The Author(s) 2024
Products of Euclidean Metrics and Applications to Proximity Questions among Curves
Get PDFThe problem of Approximate Nearest Neighbor (ANN) search is fundamental in computer science and has benefited from significant progress in the past couple of decades. However, most work has been devoted to pointsets whereas complex shapes have not been sufficiently treated. Here, we focus on distance functions between discretized curves in Euclidean space: they appear in a wide range of applications, from road segments and molecular backbones to time-series in general dimension. For l_p-products of Euclidean metrics, for any p >= 1, we design simple and efficient data structures for ANN, based on randomized projections, which are of independent interest. They serve to solve proximity problems under a notion of distance between discretized curves, which generalizes both discrete Fréchet and Dynamic Time Warping distances. These are the most popular and practical approaches to comparing such curves. We offer the first data structures and query algorithms for ANN with arbitrarily good approximation factor, at the expense of increasing space usage and preprocessing time over existing methods. Query time complexity is comparable or significantly improved by our algorithms; our approach is especially efficient when the length of the curves is bounded
A General Solver Based on Sparse Resultants: Numerical Issues and Kinematic Applications
No full textSparse 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 generalizes % the classical homogeneous resultant and its degree is a function % of the mixed volumes of the Newton polytopes. We sketch the sparse resultant constructions of Canny and Emiris and show how they reduce the problem of root-finding to an eigenproblem. A little known method for achieving this reduction is presented which does not increase the dimension of the problem. Together with an implementation of the sparse resultant construction, this provides a general solver for polynomial systems. We discuss the overall implementation and emphasize the numerical issues encountered in the matrix computations, based on the condition number of a matrix. We illustrate the program's capabilities by applying it to concrete problems from vision, robotics and computational biology. The high efficiency and accuracy of the solutions suggest that sparse elimination may be the method of choice for systems of moderate size
A General Solver Based on Sparse Resultants: Numerical Issues and Kinematic Applications
Get PDFSparse 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 generalizes % the classical homogeneous resultant and its degree is a function % of the mixed volumes of the Newton polytopes. We sketch the sparse resultant constructions of Canny and Emiris and show how they reduce the problem of root-finding to an eigenproblem. A little known method for achieving this reduction is presented which does not increase the dimension of the problem. Together with an implementation of the sparse resultant construction, this provides a general solver for polynomial systems. We discuss the overall implementation and emphasize the numerical issues encountered in the matrix computations, based on the condition number of a matrix. We illustrate the program's capabilities by applying it to concrete problems from vision, robotics and computational biology. The high efficiency and accuracy of the solutions suggest that sparse elimination may be the method of choice for systems of moderate size
A Complete Implementation for Computing General Dimensional Convex Hulls
Get PDFWe 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 efficient method for its implementation based on modular arithmetic. We suggest that {\em probabilistic modular arithmetic} may be of wide interest, as it combines the advantages of modular arithmetic with randomization in order to speed up the lifting of residues to an integer. We derive general error bounds and discuss the implementation of this approach in our general-dimension convex hull program. The use of perturbations as a method to cope with input degeneracy is also illustrated. We present the implementation of a computationally efficient scheme that, moreover, greatly simplifies the task of programming. We concentrate on {\em postprocessing}, often perceived as the Achilles' heel of perturbations. Starting in the context of a specific application in robotics, we examine the complexity of postprocessing and attempt to delimit the cases where perturbations become a hindrance rather than an enhancement. Lastly, we discuss the visualization capabilities of our software and illustrate them for problems in computational algebraic geometry
A Complete Implementation for Computing General Dimensional Convex Hulls
No full textWe 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 efficient method for its implementation based on modular arithmetic. We suggest that {\em probabilistic modular arithmetic} may be of wide interest, as it combines the advantages of modular arithmetic with randomization in order to speed up the lifting of residues to an integer. We derive general error bounds and discuss the implementation of this approach in our general-dimension convex hull program. The use of perturbations as a method to cope with input degeneracy is also illustrated. We present the implementation of a computationally efficient scheme that, moreover, greatly simplifies the task of programming. We concentrate on {\em postprocessing}, often perceived as the Achilles' heel of perturbations. Starting in the context of a specific application in robotics, we examine the complexity of postprocessing and attempt to delimit the cases where perturbations become a hindrance rather than an enhancement. Lastly, we discuss the visualization capabilities of our software and illustrate them for problems in computational algebraic geometry
Enumerating a subset of the integer points inside a Minkowski sum
No full textAbstractSparse elimination exploits the structure of algebraic equations in order to obtain tighter bounds on the number of roots and better complexity in numerically approximating them. The model of sparsity is of combinatorial nature, thus leading to certain problems in general-dimensional convex geometry. This work addresses one such problem, namely the computation of a certain subset of integer points in the interior of integer convex polytopes. These polytopes are Minkowski sums, but avoiding their explicit construction is precisely one of the main features of the algorithm. Complexity bounds for our algorithm are derived under certain hypotheses, in terms of output-size and the sparsity parameters. A public domain implementation is described and its performance studied. Linear optimization lies at the inner loop of the algorithm, hence we analyze the structure of the linear programs and compare different implementations
Multihomogeneous resultant formulae by means of complexes
No full textAbstractThe first step in the generalization of the classical theory of homogeneous equations to the case of arbitrary support is to consider algebraic systems with multihomogeneous structure. We propose constructive methods for resultant matrices in the entire spectrum of resultant formulae, ranging from pure Sylvester to pure Bézout types, and including matrices of hybrid type of these two. Our approach makes heavy use of the combinatorics of multihomogeneous systems, inspired by and generalizing certain joint results by Zelevinsky, and Sturmfels or Weyman (J. Algebra, 163 (1994) 115; J. Algebraic Geom., 3 (1994) 569). One contribution is to provide conditions and algorithmic tools so as to classify and construct the smallest possible determinantal formulae for multihomogeneous resultants. Whenever such formulae exist, we specify the underlying complexes so as to make the resultant matrix explicit. We also examine the smallest Sylvester-type matrices, generically of full rank, which yield a multiple of the resultant. The last contribution is to characterize the systems that admit a purely Bézout-type matrix and show a bijection of such matrices with the permutations of the variable groups. Interestingly, it is the same class of systems admitting an optimal Sylvester-type formula. We conclude with examples showing the kinds of matrices that may be encountered, and illustrations of our Maple implementation
- …
