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

• Meeting in Raleigh (October, 5-14, 2011) -- Kick-off meeting
• Meeting in Montpellier (April, 18-19, 2012)
• Visit of E. Kaltofen in Lyon and Paris (June and July 2012)
• Visit of PolSys in Raleigh (Oct. 2012)
• Visit of C. Pernet in Raleigh (Nov. 2012)

Scientific production

Joint articles in 2012:

• Sparse Polynomial Interpolation and Berlekamp/Massey Algorithms That Correct Outlier Errors in Input Values, M. Comer, E. Kaltofen and C. Pernet, ISSAC '12: Proceedings of the 2012 international symposium on Symbolic and algebraic computation, ACM.
• Hoon Hong and Mohab Safey El Din. Variant Quantifier Elimination. Journal of Symbolic Computation, 47(7):883-901, 2012.
• T. Zhao, D. Wang, H. Hong, Ph. Aubry : Real Solution Formulas of Cubic and Quartic Equations Applied to Generate Dynamic Diagrams with Inequality Constraints, SAC 2012: Proceedings of the 27th ACM Symposium on Applied Computing, Trento, ItalyNew York, NY, USA, pp. 94-101, (ACM Press)

Related articles in 2012:

• H. D. Nguyen, N. Revol and P. Theveny: Tradeoffs between accuracy and efficiency for optimized and parallel interval matrix multiplication PARA 2012 - Workshop in the State-of-the-Art in Scientific and Parallel Computing, Helsinki, Finland, 10-13 June 2012, to appear in LNCS, 2012
• P. Theveny and N. Revol : Interval Matrix Multiplication Algorithms - Implementation and Accuracy SCAN 2012 - 15th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic and Verified Numerical Computations, Novosibirsk, Russia, 23-29 September 2012.
• Sparse approaches for the exact distribution of patterns in long state sequences generated by a Markov source. Grégory Nuel et Jean-Guillaume Dumas. Theoretical Computer Science special issue on Symbolic Numeric Algorithms, to appear, 2012.