QOLAPS is a joint Associate Team between the Symbolic
Computation Group at North Carolina State University
(USA), the PolSys Team,
members of the ARIC Team at
Rhone-Alpes (N. Revol and G. Villard) and J.-G. Dumas
and C. Pernet (University Joseph Fourier in Grenoble).
QOLAPS is an acronym for Quantfier elimination, Optimization, Linear Algebra and Polynomial Systems. All these research subjects are fundamental, deserve to be investigated on their own and of first importance for many applications in engineering sciences.
In QOLAPS, we focus on the use of hybrid computational methodologies and approximations to tackle them with the goal to provide exact results. This includes two viewpoints: the first one consists in using symbolic computation efficiently to solve problems that are easier once the specifications on the output have been relaxed (approximation) and to analyze the behaviour of numerical routines. The second one consists in using numerical routines to accelerate symbolic computation but still providing exact results, e.g. by computing certificates. Our goal is to bring foundations for these methodologies, by investigating algorithmic problems in the aforementioned topics.
Activities in QOLAPS are highly related to the ANR HPAC project in which French members of QOLAPS are involved and an NSF project led by E. Kaltofen (North Carolina State University).
As announced in our proposal, we have started to investigate
algorithms for computing certificates in various areas, starting with
Linear Algebra. In Linear Algebra, we focus on sparse problems, for
which we aim at bringing certificates (for rank computations, etc.)
that can be computed fast. For the moment complexities are prohibitive
(i.e. O(n^4)); we have scheduled to tackle these problems with
pseudo-randomness next year.
For global optimization of multivariate polynomials, we are working on certificates for the non-existence of global infima to a given multivariate polynomial. We have succeeded to design such certificates, using properties of singular loci of polynomial maps. Such certificates can be obtained in time polynomial in the Bezout bound which seems optimal. The corresponding article is under preparation.
As announced, we have investigated the use of Quantifier Elimination
(QE) for stability analysis of numerical schemes. One issue was that
traditional algorithms for QE are not efficient enough to handle
relevant instances of such stability analysis. We have designed a new
projection operator for QE based on the computation of critical
points. It outperforms the state-of-the-art and allowed us to perform
the stability analysis of several numerical schemes. These results
have been published in Journal of Symbolic Computation. We plan to
pursue investigations on hybrid computing in this area to solve
We also investigated interpolation of sparse polynomials with errors. We have established a lower bound on the number of necessary evaluation points to solve in a caninical way this problem. We also designed an optimal algorithm for this task. These results have been published in the ISSAC proceedings. For the future, we plan to investigate new questions which arise from this work: connection with error-correcting codes, explain the numerical stability of this algorithm and extension of this algorithm to Cauchy interpolation.
With D. Saunders (Univ. Delaware) we have studied the use of interval arithmetics in the numerical part of a hybrid code for solving linear systems. For the moment, interval arithmetic does not compete with the state-of-the-art in terms of practical performance but allows certification. We plan to improve its practical performance.
Joint articles in 2012:
Related articles in 2012: