Proposition de thèse : Hyperbolic polynomials : algorithms and implementations


L’ED SISMI propose le sujet de thèse suivant :

Intitulé du sujet : Hyperbolic polynomials : algorithms and implementations

Ce projet serait sous la direction de Moulay Barkatou du laboratoire XLIM à l’Université de Limoges

Co-directeurs renseignés : Simone Naldi /

Les financement sont : bourse, non acquis

Le début de la thèse est prévu pour : Octobre 2020

Mots clés du sujet : hyperbolic polynomials, determinantal representations, convex optimization

Présentation du sujet : The thesis will focus on algorithmic aspects of hyperbolic polynomials, their determinantal representations and applications to partial differential equations and optimization. Hyperbolic polynomials is a class of real polynomials arising in different domains of applied mathematics such as hyperbolic PDEs (since the work of Lax) and convex optimization (Guler, Renegar). The student will develop algorithms for different problems concerning hyperbolic polynomials such as testing hyperbolicity, computing determinantal representations, solving hyperbolic programming problems.

Objectifs : Preliminary work will consist in getting familiarity with the theory of hyperbolic polynomials, determinantal representations and other types of “certificates of hyperbolicity”. Then the priority will be given to algorithmic and complexity aspects concerning the Dixon method and its variants. Depending on the expertise of the student, a part of the thesis might be dedicated to the implementation of a library dedicated to computation with hyperbolic polynomials.

Description du sujet : A univariate polynomial with real coefficients is real-rooted whenever all its roots are real. Testing whether a univariate polynomial is hyperbolic is related to the problem of univariate factorization and to other classical questions in computer algebra, for which efficient algorithms are known [1, 2].

The thesis will focus on algorithmic aspects concerning hyperbolic polynomials, a class of multivariate polynomials that generalize the above univariate setting. In contrast to the univariate case, the problem of testing whether a given multivariate polynomial is hyperbolic is quite open in its whole generality from the viewpoint of computer algebra and effective algebraic geometry. At the same time hyperbolic polynomials appear in different domains of applied mathematics, such as partial differential equations [5, 6], convex optimization [11] and currently represent a central topic in nonlinear algebra [8, 9, 10].

Since a real-rooted univariate polynomial is the characteristic polynomial of some real symmetric matrix, a natural generalization is represented by polynomials of type f = det(x0*Id+x1*A1+…+xn*An) for given real symmetric matrices A1,…,An. “Determinantal polynomials” are hyperbolic, but unfortunately not every hyperbolic polynomial admits such symmetric determinantal representation [3] : this fact constitutes an obstruction to the problem of testing hyperbolicity. For the case of curves, determinantal representations exist [7] and can be computed via the so-called Dixon’s method [4] or its new variants [8, 10].

Contributions in terms of efficient algorithms and software implementations dedicated to hyperbolic polynomials will help in finding new sources of insights into this theory.

[1] S. Basu, R. Pollack, and M-F. Roy. Algorithms in real algebraic geometry, volume 10 of Algorithms and Computation in Mathematics. Springer-Verlag, second edition, 2006.

[2] A. Bostan, F. Chyzak, M. Giusti, R. Lebreton, G. Lecerf, B. Salvy, and É. Schost. Algorithmes efficaces en calcul formel. Lecture notes of MPRI, 2014.

[3] P. Brändén. Obstructions to determinantal representability. Adv. Math., 226(2):1202–1212, 2011.

[4] A. C. Dixon. Note on the reduction of a ternary quantic to a symmetrical determinant. In Proc. Cambridge Philos. Soc, volume 5, pages 350–351, 1902.

[5] L. Gårding. An inequality for hyperbolic polynomials. J. Math. Mech., 8(6):957–965, 1959.

[6] O.Güler .Hyperbolic polynomials and interior point methods for convex programming. Math.Oper.Res.,22(2):350–377,1997.

[7] J.W. Helton and V.Vinnikov. Linear matrix inequality representation of sets. Communications on Pure and Applied Mathematics,60(5):654– 674, 2007.

[8] M.Kummer, S.Naldi, and D.Plaumann. Spectrahedral representations of plane hyperbolic curves. Pac.J.Math., to appear,2019.

[9] M. Kummer, D. Plaumann, and C. Vinzant. Hyperbolic polynomials, interlacers, and sums of squares. Math. Prog., 153(1):223–245,2015.

[10] D. Plaumann, R. Sinn, D. Speyer, and C. Vinzant. Computing Hermitian determinantal representations of hyperbolic curves. Int. Journal of Algebra and Computation, 25(8):1327–1336, 2015.

[11] J. Renegar. Hyperbolic programs, and their derivative relaxations. Found. Comput. Math., 6(1):59–79,2006.

Compétences acquises à l’issue de la thèse : Knowledge of (basic) algebraic geometry of curves and surfaces, especially in the context of hyperbolic polynomials. Use of software for symbolic/numeric computation, such as Maple, Sage and Matlab, for scientific research.

Présentation de l’équipe d’accueil : The thesis will be advised by Moulay Barkatou (Full Professor) and Simone Naldi (Maître de conférences) of Université de Limoges. It will be accomplished at the Laboratoire XLIM, of the Faculté de Sciences et Techniques, Université de Limoges, France. The student will join the team Calcul Formel. The team develops new computational methods with the goal of obtaining exact symbolic representations, as well as certified qualitative and quantitative information on solutions of differential, polynomial and functional equations. Such theoretical and algorithmic results are implemented in software packages that extend the scope of pre-existing solvers for the modelisation and solution of scientific problems.

Compétences souhaitées pour les candidats : Good background in mathematics and computer science (especially linear algebra, convex geometry, algebraic geometry, computer algebra).

Pour plus d’informations et pour candidater, merci de contacter :

Date de dépôt : 04/14/2020 à  14 h 19 min




ED SISMI