QOLAPS Associate Team (2012-2014)

Description

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 LIP, ENS Lyon, INRIA 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).

Scientific results (2012)

Computation of certificates.

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.

Hybrid computations

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 connectivity queries.
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.

Activities in 2011-2012

Scientific production

Joint articles in 2012:

Related articles in 2012: