Held at the conference ACA’2009, June 25–28, 2009, in Montreal, Canada.
Parametric polynomial system solving is a challenge coming from many applications, such as biology, control theory, robotics, etc. When a problem can be modelled by a parametric system, the main issue is not only to return its solutions, but also to describe them. The design of algorithms to solve parametric systems has recently become an active and expanding research field. Manipulating parametric systems is at the heart of computer algebra. It calls upon a wide range of methods, such as Triangular sets, Gröbner bases, Cylindrical Algebraic Decomposition, Quantifier Elimination, etc.
This session is focused on the art of parametric system solving, for general class of systems or dedicated to specific application problems.
The different topics will include :
Any applications in science and engineering of above topics are also welcome.
The call for submission is now opened. If you are interested in presenting a talk in this session, please send an email to the organizers with a title and an abstract, by the extended dead-line Monday, June 8.
| . | . |
|---|---|
| Guillaume Moroz, Maplesoft, Canada | |
| Hirokazu Anai, Fujitsu Laboratories Ltd/ Kyushu University, Japan |
Abstract: We introduce an algorithm to compute Groebner bases within linear algebra. For a given finite set of polynomials, it compute both an appropriate term ordering and the corresponding reduced Groenber basis of the ideal generated by the given polynomials.
Though our original algorithm changes term orderings dynamically for computational efficiency, it is also possible to change them suitable for the Suzuki-Sato algorithm, which compute comprehensive Groebner basis. In this talk, we argue on the algorithms and its implementations.
Abstract: Extending previous results by Dahan and Schost, we show that for an algebraic set V of positive dimension, the bit-length of the coefficients of some suitably normalized regular chains representing V is polynomially bounded in terms of the degree and height of V.
Abstract1: A hyperbolic poynomial is defined in the following way: ∑k=0makcosh(k)+∑k=0mbksinh(k), where ak ∈ R and bk ∈ R. A hyperbolic curve is a real plane curve where each coordinate is given parametrically by a hyperbolic poynomial:
x=∑k=0makcosh(k)+∑k=0mbksinh(k)
y=∑k=0mckcosh(k)+∑k=0mdksinh(k)
By adapting to hyperbolic curves the algorithms presented in
[Hong and Schicho 98] for the trigonometric case, we give
algorithms for simplifying a given parametric representation and
for computing an implicit representation from a given parametric
representation.
We show moreover that some of the algebraic curves arising from the implicitization of a hyperbolic curve have a very special structure containing both one hyperbolic part and one trigonometric part. For example:
2752x2-32x2y+2x4+310632-172y-130y2-y3=0
contains two curves, one trigonometric and the other
hyperbolic.
Abstract: Let S be a polynomial system of equations in X1,...,Xn. Furthermore, assume that its coefficients depend on the symbolic parameters T1,...,Ts. A natural problem in some applications is to compute a parametrization of the solutions of S.
Under some assumptions, the solutions of S can be written under the shape:
X1=Q1(T1,...,Ts,Z), ..., Xn=Qn(T1,...,Ts,Z)
and P(T1,...,Ts,Z)=0
where Q1,...,Qn
are rational functions, P is a
polynomial and Z is a new
symbolic variable.
We will give an overview of different methods computing such a parametrization. Then we will present a parametrization based on Groebner basis computation for a specific product order, and show the advantages of this representation on some examples.
Abstract: Solving systems of parametric polynomial equations symbolically is in demand for an increasing number of applications such as program verification, optimization and the study of dynamical systems. Groebner bases and triangular decompositions are classical techniques for processing parametric systems. Recent research has focused on enhancing theories and algorithms to meet the practical requirement of these systems.
The ParametricSystemTools module of the RegularChains library in Maple implements comprehensive triangular decompositions (CTD) and real root classification (RRC) which are tools dedicated to study polynomial systems with parameters. It is supported by the modules ConstructibleSetTools and SemiAlgebraicSetTools. The first one provides useful commands for solving over the complex numbers and the second over the reals.
This talk is an overview of the functionalities of these three modules. We start with a review of the fundamental concepts of CTD, RRC and Border Polynomial together with their relation with other popular notions for parametric polynomial systems. We consider then applications from program verification and biochemistry. In this latter case, we will combine our library with software tools for modeling.
Abstract: As computer algebra develops, it handles more sophisticated objects, many of which have no precise parallel in conventional mathematics, since mathematicians have handled the concepts on an ad hoc basis. Furthermore, by definition, computer algebra must handle these objects algorithmically, and present them to the user. This is particularly a challenge when the user may not be intimately familiar with the object, and all the special cases that may occur.
We present various issues connected with this in the context of equation solving, and show how the ‘piecewise’ construct of Maple can be employed to build representations of solution objects that:
Abstract: Many problems give rise to polynomial systems. These systems often have several parameters and we are interested to study how the solutions vary when we change the values for the parameters. Using predictor-corrector methods we track the solution paths. A point along a solution path is critical when the Jacobian matrix The simplest case of quadratic turning points is well understood, but these methods no longer work for general types of singularities. We have experimented with criteria to monitor the Jacobian in order not to miss any singular solutions along a path. In case of higher order singularities more accurate predictors are needed, otherwise we do not get in the range for which reconditioning methods such as deflation can be applied. Our methods are implemented in the software package PHCpack and applied to a wide range of polynomial systems arising in various fields of science and engineering. This is joint work with Kathy Piret.
This work has been partially supported by the spanish MICINN grant MTM2008–04699-C03–03. ↩