# Software for Polynomials

• Sparse resultants by the Incremental Algorithm. Ansi-C library and stand-alone implementation of the incremental algorithm for building sparse resultant matrices of Sylvester-type and for using them in computing all common roots of a well-constrained 0-dimensional polynomial system. Optimal Sylvester-type matrices are constructed for all systems where this is provably possible. See README file, tech.report on the code, and JSC article (postscript).

Maple functions for connecting Maple to the program, including conversion of Maple input to the appropriate format: file mapl2form and file maplib.
• Sparse Resultants by Mixed Subdivisions
(1) Maple overall implementation (mapleV,2002 and maple9,2004) of the greedy method (a Canny-Pedersen variant of the original algorithm) to construct a sparse resultant matrix, including the computation of supports and Newton polytopes; see J.ACM'00 publication (dvi, postscript). There is the option to apply the d'Andrea-Emiris perturbation for handling degenerate coefficients; see manuscript.ps. These are all stand-alone functions. The matrix construction is included in the general Maple resultant library: multires (an update concerning sparse resultants).

(2) Maple implementation of the original Canny-Emiris algorithm to construct a sparse resultant matrix, as well as the denominator which is conjectured to lead to an exact expression for the resultant; see J.ACM'00 publication (dvi, postscript).

(3) Stand-alone MapleV code for constructing hybrid matrices of almost-Sylvester type (one row expressing the toric Jacobian); uses piecewise-linear liftings. Systems of 3 bivariate polynomials only, with Newton polygons being scaled copies of a single polygon. Need 2 files: bivar.mpl and hybridJac.mpl. Joint algorithm with D'Andrea (ISSAC'01).

Code (2) requires Maple functions for converting to the appropriate format: mapl2form. Format conversion is internal to the greedy code (1) but the user gains full control with the functions in mapl2mapl. Additional Maple routines for polynomials and matrices: maplib.
• Sparse Resultants for Multihomogeneous Systems
mhomo.mpl contains Maple V routines for testing the existence, computing the dimension, and constructing sparse (or toric) resultant matrices of Sylvester, Bézout, or hybrid type, either determinantal or not.
• MARS is a Maple/Matlab/C package for resultant matrices and eigen-solving. Jointly with A. Wallack and D. Manocha.
• Mixed Volume, Mixed Subdivisions, Convex Hulls, and more: see software in Computational Geometry.

Ioannis Z Emiris