The work on algorithms has been divided into several tasks: general, arithmetic, algebraic, numerical and real. For each task we explain quickly what were the aims and then we describe the activities.
This task was intended to provide:
The FRISCO test suite is a list of univariate polynomials or multivariate polynomial systems, coming from practical examples. For each system, the LaTeX source and a separate postscript file which describes the system individually are also available. These examples come with references, where the reader can find the origin of the problem. The equations are also accessible in a format (i.e. MAPLE) that can be used directly from the screen, so that no effort of translation should be required.
The aim of this database was to provide a list of examples which could be used to illustrate, compare, evaluate different methods for solving polynomial systems. It was also intended to push the discussions forward inside the project, in order to evaluate the different methods, and to gather expertise on the different kinds of systems that we might encounter. This database has been used not only by people from the project, essentially to get examples. We encouraged people to submit their experimentations to this list. But as it usually requires times and some recording effort, we get few answers of this type. We plan to continue this work, which we believe, is of great importance, when one want to evaluate, correct or optimise tools for solving polynomial equations.
This task aimed at producing the arithmetic tools to be used in the various algorithms. The most basic tools had already been developed (largely in the PoSSo project), and were completed to form a deliverable. The rest of the task consisted of the development of advanced tools and of alternative implementation of the basic tools using faster algorithms.
The two parts of this task were:
The subtasks were:
The main highlights in the task have been:
Coeff class introducing
predicates to allow switches in algorithms implemented with generic
coefficients;
This task aimed at developing algorithms transforming the initial set of equations provided into a new form that can be used to extract information about the polynomial system. For example, once a Gröbner basis is computed, it is possible to know whether there are or not a finite number of solutions and from such a Gröbner basis a rational univariate representation of the solutions can be obtained. When the number of equations is equal to the number of variables there are other techniques based on matrix methods (resultants, bezoutians).
Task 3.3 (algebraic solving) has been organised during the first year, and the task subdivided into four parts, each one subdivided into several subtasks.
Task 3.3.1, Buchberger-like algorithms. The involutive algorithm for computing Gröbner bases has been integrated to the PoSSo library. An implementation and a report on the implementation has been provided for Numerical Gröbner, which consists of computing Gröbner bases using hybrid arithmetic (floats and modulars).
Task 3.3.2, Linear Gröbner algorithms. The new algorithm F4 has been described , and the experimental results confirm that this algorithm is extremely fast. The FGLM algorithm provides the computation of a lexicographical Gröbner basis from an arbitrary pre-computed Gröbner basis and the algorithm RUR a univariate representation of the solutions. They rely on linear algebra techniques. They have been implemented in a multimodular version which makes possible a better control of the size of the coefficients in intermediate computations. Algorithms providing triangular sets were studied and implemented in AXIOM then in ALDOR.
Task 3.3.3, Elimination, residues. Sparse resultant and Bezoutian algorithms provide, directly from the equations, matrices that reduce polynomial system solving to a linear algebra problem. Sparse resultants have been implemented, and integrated into the ALP library. A report has been written on Bezoutians, and they have been implemented.
Task 3.3.4, High-level algorithms. A revised version of a Hilbert function related algorithm has been implemented. Mixed volumes provide a purely combinatorial way of estimating the number of common roots of a system of polynomial equations. Their computation also provides a starting point for computing all of these roots by a homotopy continuation method. The implementation provided is in ANSI C and is currently a stand-alone program. Two reports presenting and comparing the various methods for computing the solution of an algebraic system of equations with parametric coefficients for any values of the parameters have been provided. A report describes and compares the various methods for radical computation in the case of a finite number of solutions. A completely new method for deciding the non-emptiness of an algebraic set has been reported.
The task numerical solving aimed at finding numerical approximations of the solutions of a polynomial system with guaranteed precision. Since one possible output of the algebraic solving part is a rational univariate representation, the univariate numerical solving can be used to solve numerically multivariate polynomial systems as well.
Task 3.4 (numerical solving) has been reorganised during the first year, and the task subdivided into two parts, (univariate and multivariate solving) each subdivided into several subtasks.
One of the main results of FRISCO is the MPSOLVE package. MPSOLVE is a software tool for the numerical computation of the roots of a univariate polynomial. Its input is either a polynomial, or a polynomial black box. The output is an approximation of all the roots for which Newton's method converges quadratically. The program has been prepared in order to deal with different goals. In particular, besides the goal ``Newton isolation'' described above, the program allows the further goals ``approximation'' and ``count roots''. Moreover the user is allowed to restrict the search of the roots to specific subsets of the complex plane (say, unit disk, right half plane, etc), also the automatic detection of multiple roots and/or real and imaginary roots is implemented. The program permits the use of only those digits of the input coefficients which are strictly needed for the requested approximation. This leads to a substantial saving of the time cost in many concrete situations with respect to other algorithms based on explicit factorisation. In order to reach a high speed of computation, almost all the sub-algorithms of the package have been implemented in three slightly different versions: the ``float'' version, the ``dpe'' version and an ``mp'' version. The program tries to perform the majority of the computation in the lowest (cheapest) level. The software is delivered as a stand-alone package, including a full report, with benchmarking and user's guide. The performance of Aberth's algorithms has proved to be much better than the other algorithms analysed, hence the other algorithms after an experimental implementation have been abandoned.
A second important issue has been an implementation of Uspensky's algorithm with a new optimised implementation. In the case of the search for real roots of a polynomials with integer coefficients this new algorithm is for the examples we tested much faster than Aberth's algorithm.
The main issue in multivariate polynomial system solving is the choice between
The main activity in multivariate solving has been to prepare the ground for the comparison between the different approaches through experimental implementations and the preparation of the symbolic and hybrid tools.
The task aimed at providing information about the real solutions of a polynomial system or the geometry of real objects such as algebraic curves. In practice, the user is nearly always interested only in real solutions of the system!
The task 3.5 (real solving) has been reorganised during the first year, and the task subdivided into two parts, each one subdivided into several subtasks.
Task 3.5.1 Basic Real algorithms. The behaviour of Sturm algorithm for counting the number of real roots using hybrid arithmetic was studied. What is essential in the Sturm algorithm is to know the sign of the leading coefficients of the elements in the result. An algorithm that would use only a floating point arithmetic will give bad results since the method is not well conditioned for numerical computations. Two different problems can appear:
A report on Schur-Cohn sub-transforms shows how to deal with the degeneracies and specialisation problems of the Schur-Cohn algorithm to count the complex roots inside the unit circle. New subresultant algorithms, improving the practical efficiency of subresultant computations -- and related real root counting techniques -- for real root counting in the non-defective and defective case have been described.
A further report describes how to use the univariate numerical root solving for real root counting.
As a conclusion, reports compare the efficiency of existing FRISCO tools for real root counting (Aberth's method, Uspensky's method, subresultant method). The result is that the subresultant method cannot be used for the huge univariate polynomials produced by the algebraic solving phase, since the computations do not terminate in reasonable time. On the examples we have tested, Uspensky's method is in general much more efficient than Aberth's method. But, in any case, these two methods mean that the root counting / root isolation is not more the limiting phase. On the other hand subresultants are the only one of these methods that can be used for infinitesimals.
Multivariate symbolic real root counting strategies existing in the FRISCO framework are also described in a report. Further reports describe algorithms for simultaneous inequalities and discuss new strategies for testing emptiness of real hypersurfaces and semi-algebraic sets.
Task 3.5.2 Real geometry. The description and first implementation of a new algorithm TOP for the topology of real place algebraic curves has been performed. The practical results confirm the good complexity analysis. The task entitled ``Computer Aided Design'' is devoted to explore the connections between the industrial users of CAD/CAM software and the FRISCO framework. In this second year the activity was concentrated into the contacts with the Spanish company CANDEMAT S.A. and was directed to try to solve in a more efficient way the mathematical problems arising when manipulating curves and surfaces with the CSIS software. This software is developed and maintained by the company in order to be used for design purposes, production control and quality verification of the final product. It is worth to remark that this company was initially contacted during the ``Needs of Industry FRISCO Workshop'' held in Barcelona in October, 1996. A report on special cases of quantifier elimination describes existing ad-hoc-methods for special cases, since the complexity of the general problem does not allow efficient general algorithms. The computation of the topological degree is presented in two reports, one for the general and the other one for the bivariate case.
According to the recommendations of the evaluation after the second year of the project, the work on algorithms has been oriented towards consolidation and dissemination of the many results obtained during the first two years of the project.
One of the main recommendations of the second year review was to write a book on FRISCO algorithms. This book is a very original project since it is very unusual to have a book where symbolic and numerical methods appear together and are moreover fully integrated. We expect the book to be about 400 to 500 pages, with the numerical part being about 200 pages. The preparation of the book is currently in progress. The editors are D. Bini, L. Gonzalez Vega, M. Niermann, M.-F. Roy, and C. Traverso; the authors are essentially the authors of the FRISCO reports with some extra collaborators, a total of more than twenty people. The table of contents is given in section 6.3.
The editors of the collection Algorithms and Computations in Mathematics published by Springer Verlag are very interested in the project. They have recommended that the book is not a collection of independent contributions but an integrated book with common notation and interrelated chapters. While recognising that this increases the workload on the authors and editors, we have decided to proceed along these lines.
The organisation of the book has been outlined, and it will cover the algebraic, numerical and real parts of the algorithms for solving polynomial systems of equations. Many chapters are already available in preliminary form, and the other chapters are in progress. It is hoped that a preliminary version of the whole book should be available before the summer of 2000.
B. C. Arnold, E. F. Castillo, J. M. Sarabia, L. Gonzalez-Vega Multiple Modes in Densities with Normal Conditionals. To appear in The American Statistician (1999).
P. Aubry and D. Lazard and M. Moreno Maza On the Theories of Triangular Sets, 1999, To appear, J. Symb. Comput.
P. Aubry and M. Moreno Maza, Triangular Sets for Solving Polynomial Systems: A Comparative Implementation of Four Methods, 1999, To appear, Journal of Symb. Comput.
S. Basu R. Pollack M.-F. Roy : Computing connected components of semi-algebraic sets, ISSAC 98
S. Basu R. Pollack M.-F. Roy : Computing roadmaps of semi-algebraic sets on a variety, to appear in Journal of the AMS
D.A. Bini, Using FFT-based techniques in polynomial and matrix computations: recent advances and applications, Numer. Funct. Anal. Optim., 1999 (to appear).
D.A. Bini, Numerical computation of polynomial zeros by means of Aberth's method, Numer. Algoriothms, 13:179-200 (1996).
D.A. Bini, G. Fiorentino, On the parallel evaluation of a sparse polynomial at a point, Numer. Algorithms, 1999 (to appear).
D.A. Bini, G. Fiorentino, Design, analysis and implementation of a polynomial root-finder (in preparation).
D.A. Bini, L. Gemignani, B. Meini, Factorisation of analytic functions by means of Koenig's theorem and Toeplitz computations, T.R., Dipartimento di Informatica Università di Pisa, 1998.
D. Bini, V. Pan, Polynomial and Matrix Computations, vol 2, Selected Topics. Birkhauser, Boston (to appear)
D. Bondyfalat, B. Mourrain, and V.Y. Pan. Controlled iterative methods for solving polynomial systems. In Proc. ISSAC, 252-259. ACM Press., 1998.
D. Bondyfalat, B. Mourrain, and T. Papadopoulo. An application of automatic theorem proving in computer vision. Submitted, 1999.
C. Bonini, K.P. Nischke, C. Traverso, ``Computing Groebner bases numerically, some experiments'', proceedings conference SIMAI 69-74, 1998,
A. Bonnecaze, B. Mourrain, and P. Solé Jacobi polynomials, type II codes, and designs. Designs Codes and Cryptography, 16, 215-234, 1999,
A. Bonnecaze, P. Solé, C. Bachoc, and B. Mourrain. Type II codes over Z4. IEEE Transactions on Information Theory, 43(3):969-976, 1997.
H. Brönnimann, I.Z. Emiris, V. Pan, and S. Pion. Computing exact geometric predicates using modular arithmetic with single precision. Technical Report 3213, INRIA Sophia-Antipolis, France, 1997.
H. Brönnimann, I.Z. Emiris, V. Pan, and S. Pion. Computing exact geometric predicates using modular arithmetic with single precision. In Proc. ACM Symp. on Computational Geometry, pages 174-182, Nice, 1997.
H. Brönnimann, I.Z. Emiris, V. Pan, and S. Pion. Sign determination in Residue Number Systems. Theoretical Computer Science, Special Issue on Real Numbers and Computers, 210, 1, 173-197, 1999.
C. Brunie, Ph. Saux Picart, A fast version of Schur-Cohn algorithm, J. of complexity, to appear.
L. Busé, M. Elkadi, and B. Mourrain. Generalised resultant over an algebraic variety. Submitted, 1999.
M. Caboara: A modified Buchberger Algorithm for resolutions Preprint.
M. Caboara, P. Conti, , C. Traverso: Yet Another Ideal Decomposition Algorithm, Proceedings AAECC-12, Springer LNCS, 1997
M. Caboara, M. Silvestri: A Classification of compatible module ordering. Accepted for publication on the Journal of Pure and Applied Algebra.
M. Caboara, C. Traverso, Efficient algorithms for ideal operations, ISSAC98, ACM press.
P. Comon, O. Grellier, and B. Mourrain. Blind channel identification with MSK inputs. In Asilomar Conference, Pacific Grove, California, November 1-4 1998. Invited session.
P. Comon and B. Mourrain. Decomposition of quantics in sums of power of linear forms. Signal Processing, 53(2):93-107, 1996. Special issue on High-Order Statistics.
P. Conti, C. Traverso, Algorithms for the real radical, preprint.
R.M.Corless, P. Gianni, B.M.Trager, The reordered Shur factorization method for zero-dimensional polynomial systems with multiple roots Proceeding ISSAC '97, ACM.
R. Corless, M. Giesbrecht, D. Jeffrey, and S. Watt. Approximate Polynomial Decomposition. To appear in ISSAC 99.
A. Daíaz and I.Z. Emiris and E. Kaltofen and V.Y. Pan, Algebraic algorithms.. Handbook of Algorithms and Theory of Computation, Algebraic Algorithms, ed. M. Atallah, Ch. 16, CRC Press, 1998.
D. Daney. Mobility constraints on the legs of a parallel robot to improve the kinematic calibration. In New machine concepts for handling and manufacturing devices on the basis of parallel structures, Braunschweig, November 10-11 1998
D. Daney. Self calibration of Gough Platform using leg mobility constraints In IFToMM World Congress Oulu, June 20-23, 1999 To appear.
M. Elkadi and B. Mourrain. Some applications of bezoutians in effective algebraic geometry. Rapport de Recherche 3572, INRIA, 1998.
M. Elkadi and B. Mourrain. Algorithms for residues and lojasiewicz exponents. J. of Pure and Applied Algebra, 1999. To appear.
M. Elkadi and B. Mourrain. A new algorithm for the geometric decomposition of a variety. In Proc. ISSAC, 1999. To appear.
I.Z. Emiris. Symbolic-numeric algebra for polynomials. In Encyclopedia of Computer Science and Technology, Ed. A. Kent and J.G. Williams. Marcel Dekker, New York, 39, 261-281, 1999.
I.Z. Emiris, A. Galligo, and H. Lombardi. Certified approximate univariate GCDs. J. Pure Applied Algebra, Special Issue on Algorithms for Algebra, 117 & 118:229-251, May 1997.
I. Z. Emiris and B. Mourrain. Polynomial system solving; the case of a 6-atom molecule. Rapport de Recherche 3075, INRIA, Dec. 1996.
I.Z. Emiris and B. Mourrain. Computer algebra methods for studying and computing molecular conformations. Algorithmica, Special Issue on Algorithms for Computational Biology, 1999. To appear.
I.Z. Emiris and B. Mourrain. Matrices in elimination theory. J. of Symbolic Computation, 1999. To appear.
I.Z. Emiris and V.Y. Pan. Techniques for exploiting structure in matrix formulae of the sparse resultant. Calcolo, Spec. Issue on Toeplitz Matrices: Structure, Algorithms and Applications, 33:353-369, 1996.
I.Z. Emiris and V.Y. Pan, Handbook of Algorithms and Theory of Computation, Applications of FFT, ed. M. Atallah, Ch. 17, CRC Press, 1998.
I.Z. Emiris and V.Y. Pan. The structure of sparse resultant matrices. In Proc. ACM Intern. Symp. Symbolic Algebraic Comput. (ISSAC), pages 189-196, Maui, Hawaii, July 1997.
I.Z. Emiris and V.Y. Pan, Symbolic and numeric methods for exploiting structure in constructing resultant matrices, J. Symbolic Computation, to appear.
I.Z. Emiris and V.Y. Pan and Y. Yu, Modular Arithmetic for Linear Algebra Computations in the Real Field, JSC, 26 (1): 71-87, 7/1998.
I.Z. Emiris and J. Verschelde, How to Count Efficiently all Affine Roots of a Polynomial System, Discrete Math. and Applications, Special Issue on Computational Geometry, 1999, To appear
J.C. Faugère and F. Moreau de Saint Martin and F .Rouillier, Design of regular nonseparable bidimensional wavelets using Groebner basis techniques, IEEE SP Transactions Special Issue on Theory and Applications of Filter Banks and Wavelets, 1997,30, to Appear in April 1998.
P. Gianni, R.Silhol, M.Seppala, B.M.Trager, Riemann Surfaces, Plane Algebraic Curves and Their Period Matrices. JSC, vol 26, No. 6, December 1998, pp 789-803
P. Gianni, B.M.Trager, Integral Closure of Noetherian Rings in Proceeding ISSAC '97, ACM.
Maria Jose Gonzalez-Lopez and Laureano Gonzalez-Vega: Newton Identities in the multivariate case: Pham Systems. Grobner Bases and Applications. London Mathematical Society Lecture Notes Series 251, 351-366, Cambridge University Press, 1998.
Maria Jose Gonzalez-Lopez and Laureano Gonzalez-Vega: The Birkhoff Interpolation Problem. Some Tapas of Computer Algebra (Editores A.M. Cohen, H. Cuypers and H. Sterk), Algorithms and Computation in Mathematics Series 4, 216-222, Springer-Verlag, 1999.
Maria Jose Gonzalez-Lopez and Laureano Gonzalez-Vega: The Inverse Kinematics Problem in Robotics. Some Tapas of Computer Algebra (Editores A.M. Cohen, H. Cuypers and H. Sterk), Algorithms and Computation in Mathematics Series 4, 210-215, Springer-Verlag, 1999.
Maria Jose Gonzalez-Lopez, Laureano Gonzalez-Vega, Carlo Traverso and Alberto Zanoni: Gröbner Bases Specialisation through Hilbert Functions: The Homogeneous Case. To appear in the ACM SIGSAM Bulletin, 1999.
Laureano Gonzalez-Vega and Neila Gonzalez-Campos: Simultaneous Elimination by using several tools from Real Algebraic Geometry. Journal of Symbolic Computation 27, 325-340, 1999.
Laureano Gonzalez-Vega: Polynomial System Solving for Industrial Problems. Proceedings of the Workshop on European Scientific and Industrial Collaboration on promoting Advanced Technologies in Manufacturing (WESIC-98), 91-96, 1998.
Laureano Gonzalez-Vega: The Needs of Industry for Polynomial System Solving.The SAC Newsletter 3, 21-46, 1998.
Laureano Gonzalez-Vega: A special Quantifier Elimination algorithm for Pham Systems. To appear in the book entitled ``Real Algebraic Geometry and Ordered Structures'' to be published in the Contemporary Mathematics Series of the American Mathematical Society, 1999.
L. Gonzalez-Vega: Implicitization of parametric curves and surfaces by using multidimensional Newton formulae. Journal of Symbolic Computation, 23, 137-151, 1997.
L. Gonzalez-Vega and M. El Kahoui: An improved upper complexity bound for the topology computation of a real algebraic plane curve. Journal of Complexity 12, 527-544, 1996.
Laureano Gonzalez-Vega and Ioana Necula: Quantifier Elimination and Multivariate Birkhoff Interpolation. Proceedings of the 15-th IMACS World Congress on Scientific Computation, Modelling and Applied Mathematics (ed. A. Sydow), Volume 2, 739- 744, Wissenschaft and Technik Verlag, 1997.
Laureano Gonzalez-Vega, Fabrice Rouillier and Marie-Francoise Roy: Symbolic Recipes for Polynomial System Solving. Some Tapas of Computer Algebra (Editors A.M. Cohen, H. Cuypers and H. Sterk, Algorithms and Computation in Mathematics Series 4, 34-65, Springer-Verlag, 1999.
Laureano Gonzalez-Vega, Fabrice Rouillier, Marie-Francoise Roy and Guadalupe Trujillo: Symbolic Recipes for Real Solutions. Some Tapas of Computer Algebra (Editors A.M. Cohen, H. Cuypers and H. Sterk), Algorithms and Computation in Mathematics Series 4, 121-167, Springer-Verlag, 1999.
L. Gonzalez-Vega and G. Trujillo: Multivariate Sturm-Habicht Sequences: real root counting on n-rectangles and triangles. Revista Matematica de la Universidad Complutense de Madrid 10, 119-130, 1997.
I. Itenberg, M.-F. Roy, Interactions between real algebraic geometry and discrete and computational geometry, a paraitre dans le volume AMS SRC in Discrete and Computational Geometry.
Ilias Kotsireas, Algorithmes de resolution des systèmes polynomiaux: application aux configurations centrales du problème des N corps en mécanique céleste. These de Doctorat de l'Universite Pierre et Marie Curie, Paris 6 Specialite : Informatique (Algorithmique), 16 decembre 1998
T. Lickteig M.-F. Roy Semi-algebraic complexity of quotients and sign determinations of remainders, Journal of Complexity 12 (4) 545-571 (1996)
T. Lickteig, M.-F. Roy Cauchy index computation, Calcolo 33 (1996) 337-371
T. Lickteig, M.-F. Roy Sylvester-Habicht sequences and fast Cauchy index computations, to appear in Journal of Symbolic Computation.
H. Lombardi, M.-F. Roy, M. Safey New structure theorems for subresultants, submitted to Journal of Symbolic Computation
J-P. Merlet. Determination of 6D workspaces of a Gough-type 6 d.o.f. parallel manipulator. In RoManSy, pages 261-268, Paris, July 6-9 1998
J-P. Merlet. Determination of the presence of singularities in 6D workspace of a Gough parallel manipulator. In ARK, pages 39-48, Strobl, June 29 - July 4 , 1998
J-P. Merlet. The importance of optimal design for parallel structures. In First European-American Forum on Parallel Kinematic Machines, Milan, August 31- September 1, 1998.
J-P. Merlet. Finding the extremal values of the particular coordinates of a parallel robot In IFToMM World Congress Oulu, June 20-23, 1999 To appear.
J-P. Merlet. Workspaces determination of 6 dof parallel robots In Int. J. of Robotics Research Submitted.
M. Moreno Maza. Calculs de Pgcd au-dessus des Tours d'Extensions Simples et Résolution des Systèmes d'Équations Algébriques. PhD thesis, Université Paris 6, 1997.
B. Mourrain. Isolated points, duality and residues. J. of Pure and Applied Algebra, 117 & 118:469-493, 1996. Special issue for the proc. of the 4th Int. Symp. on Effective Methods in Algebraic Geometry (MEGA).
B. Mourrain. Algorithmes et applications en géométrie algébrique, Habilitation à direiger les recherches, September 1997.
B. Mourrain. Solving polynomial systems by matrix computations. 1997.
B. Mourrain. Computing isolated polynomial roots by matrix methods. J. of Symbolic Computation, Special Issue on Symbolic-Numeric Algebra for Polynomials, 26(6):715-738, Dec. 1998.
B. Mourrain. An introduction to linear algebra methods for solving polynomial equations. In HERCMA'98, 1998.
B. Mourrain. A new criterion for normal form algorithms. Submitted, 1999.
B. Mourrain and V. Y. Pan. Multidimensional structured matrices and polynomial systems. Calcolo, Special Issue, workshop on Toeplitz matrices: Structure, Algorithms and Applications, 33:389-401, 1997.
B. Mourrain and V. Y. Pan. Solving special polynomial systems by using structured matrices and algebraic residues. In F. Cucker and M. Shub, editors, Proc. of the workshop on Foundations of Computational Mathematics (Rio de Janeiro, 1997), pages 287-304. Springer, 1997.
B. Mourrain and V.Y. Pan. Asymptotic acceleration of solving multivariate polynomial systems of equations. In Proc. STOC, pages 488-496. ACM Press., 1998.
B. Mourrain and V.Y. Pan. Multivariate polynomials, duality and structured matrices. Rapport de Recherche 3513, INRIA, 1998.
B. Mourrain and V.Y. Pan. Lifting/descending processes for polynomial zeros. J. of Complexity, 1999. To appear.
B. Mourrain and V.Y. Pan. Multivariate polynomials, duality and structured matrices. J. of Complexity, 1999. To appear.
F. Rouillier, Solving zero-dimensional systems through the Rational Univariate Representation, Technical Report, Loria, (to appear in Journal of AAECC).
F. Rouillier, M.-F. Roy, M. Safey, Finding at least one point in each connected component of a real algebraic set defined by a single equation, to appear in Journal of Complexity
M.-F. Roy , N. Vorobjov Computing the complexification of a semi- algebraic set, to appear in Math. Zeitschrift
Ph. Saux Picart, The Schur-Cohn algorithm revisited, J. Symbolic Computation, vol. 26, 1998.
A. Wallack and I.Z. Emiris and D. Manocha, MARS: A Maple/Matlab/C Resultant-Based Solver, ISSAC 1998, 244-251.