Mohab Safey El Din

Professor
Mohab.Safey[at]lip6.fr
Sorbonne Université
LIP6, UMR CNRS 7606
PolSys Team
Institut Universitaire de France (IUF) (promotion 2012)

Research: Computer Algebra, Polynomial System Solving, Computational Real Algebraic Geometry

Projects:

ANR/FWF international project ECARP (coordinator)
ANR project De rerum natura (participant)
ANR project SESAME (local coordination)
Innovative Training Network Marie Curie POEMA (local coordination of the Sorbonne Univ. node)
ANR Project GeoLMI (local coordinator, national coordination: D. Henrion)
Associate Team QOLAPS with NCSU and ARIC (coordinator)
ANR Project HPAC (participant, national coordination: J.G. Dumas)
ECCA Project at LIAMA (joint-coordination with L. Zhi)
ANR/NSFC international project EXACTA (Coordinator of the french part)

Software:

msolve Library for solving multivariate polynomial systems, jointly developed with J. Berthomieu and C. Eder (TU Kaiserslautern)
RAGLib Maple package dedicated to real solutions of polynomial systems
SPECTRA Maple package to solve Linear Matrix Inequalities exactly (with D. Henrion and S. Naldi)
RealCertify Maple package to compute exact sums of squares decompositions of non-negative polynomials jointly developed with V. Magron

Publications:

Homotopy techniques for solving sparse column support determinantal polynomial systems, G. Labahn, M. Safey El Din, É. Schost, T.X. Vu
To appear in Journal of Complexity.
Preliminary version [pdf]

Complete Singularity Analysis for the Perspective-Four-Point Problem, B. Pascual-Escudero, A. Nayak, S. Briot, Olivier Kermorgant, P. Martinet, M. Safey El Din, F. Chaumette,
International Journal of Computer Vision, Springer Verlag, pp.1217-1237, 2021.
Preliminary version [pdf]

Solving determinantal systems using homotopy techniques, J. Hauenstein, M. Safey El Din, É. Schost,
Journal of Symbolic Computation, vol. 104, pp. 754-804, 2021.
Preliminary version [pdf]

Exact Algorithms for Semidefinite Programs with Degenerate Feasible Set, D. Henrion, S. Naldi, M. Safey El Din
Journal of Symbolic Computation, vol. 104, pp. 942-959, 2021.
Preliminary version [pdf]

Computing real radicals and S-radicals of polynomial systems M. Safey El Din, Z. Yang, L. Zhi,
Journal of Symbolic Computation, Vol. 102, pp. 259--278, 2021
Preliminary version [pdf]

Polynomial interrupt timed automata: Verification and expressiveness B. Bérard, S. Haddad, C. Picaronny, M. Safey El Din, M. Sassolas
Information and Computation, pp. 128--151, Vol. 101, Elsevier, 2021
Preliminary version [pdf]

Robots, computer algebra and 8 connected components, J. Capco, M. Safey El Din, J. Schicho
Proceedings of ISSAC 2020, Kalamata, Greece, 2020.
Preliminary version [pdf]

Computing the real isolated points of an algebraic hypersurface, H. P. Le, M. Safey El Din, T. de Wolff
Proceedings of ISSAC 2020, Kalamata, Greece, 2020.
Preliminary version [pdf]

Cooperativity, absolute interaction, and algebraic optimization, N. Kaihnsa, Y. Ren, M. Safey El Din, J. Martini,
Journal of Mathematical Biology, vol. 81, 1169--1191, 2020.
Preliminary version [pdf]

Real root finding for low rank linear matrices, D. Henrion, S. Naldi, M. Safey El Din,
Applicable Algebra in Engineering, Communication and Computing, vol. 31, pp. 101-133, 2020.
Preliminary version [pdf]

SPECTRA -a Maple library for solving linear matrix inequalities in exact arithmetic D. Henrion, S. Naldi, M. Safey El Din
Optimization, Methods and Software, 34(1), pp. 62-78, Taylor and Francis, 2019
Preliminary version [pdf]

Algorithms for weighted sums of squares decompositions of non-negative univariate polynomials, V. Magron, M Safey El Din, M. Schweighofer,
Journal of Symbolic Computation, Num. 93, pp. 200-220, 2019
Preliminary version [pdf]

Computing the volume of compact semi-algebraic sets, P. Lairez, M. Mezzarobba, M. Safey El Din,
Proceedings of ISSAC 2019, Beijing China, 2019.
Preliminary version [pdf]

Exact Algorithms for Semidefinite Programs with Degenerate Feasible Set, D. Henrion, S. Naldi, M. Safey El Din
Proceedings of ISSAC 2018, New-York, USA, 2018.
Preliminary version [pdf]

RealCertify: a Maple package for certifying non-negativity, V. Magron, M. Safey El Din,
ACM Communications in Computer Algebra, 52(2), pp. 34-37, 2018.
Preliminary version [pdf]

On Exact Polya and Putinar's Representations, V. Magron, M. Safey El Din
Proceedings of ISSAC 2018, New-York, USA, 2018.
Preliminary version [pdf]

Real Root Finding for Equivariant Semi-algebraic Systems, C. Riener, M. Safey El Din
Proceedings of ISSAC 2018, New-York, USA, 2018.
Preliminary version [pdf]

On the Complexity of Computing Real Radicals of Polynomial Systems, M. Safey El Din, Z.-H. Yang, L. Zhi
Proceedings of ISSAC 2018, New-York, USA, 2018.
Preliminary version [pdf]

A lower bound on the positive semidefinite rank of convex bodies, H. Fawzi, M. Safey El Din
SIAM Journal on Applied Algebra and Geometry, Vol. 2(1), pp. 126-139, 2018.
Preliminary version [pdf]

Bit complexity for multi-homogeneous polynomial system solving - Application to polynomial minimization. M. Safey El Din, É. Schost
Journal of Symbolic Computation, Vol. 87, 176-206, 2018
Preliminary version [pdf]

A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets, M. Safey El Din, E. Schost
Journal of the ACM, Vol. 63(6), 2017.
Preliminary version [pdf]

Exact algorithms for linear matrix inequalities, D. Henrion, S. Naldi, M. Safey El Din
SIAM Journal on Optimization, 26 (4), pp.2512-2539., 2016.
Preliminary version [pdf]

On the complexity of computing Grobner bases for weighted homogeneous systems, J.-C. Faugere, M. Safey El Din, T. Verron
Journal of Symbolic Computation, 76, pp. 107-141, 2016.
Preliminary version [pdf]

Determinantal sets, singularities and application to optimal control in medical imagery, B. Bonnard, J.-C. Faugere, A. Jacquemard, M. Safey El Din, T. Verron
Proceedings of ISSAC 2016, Waterloo, Canada, 2016.
Preliminary version [pdf]

Real root finding for determinants of linear matrices, D. Henrion, S. Naldi, M. Safey El Din
Journal of Symbolic Computation, 74, 205--238, 2016.
Preliminary version [pdf]

Probabilistic Algorithm for Computing the Dimension of Real Algebraic Sets, I. Bannwarth, M. Safey El Din
Proceedings of ISSAC 2015, Bath, UK, 2015.
Preliminary version [pdf]

Optimizing a Parametric Linear Function over a Non-compact Real Algebraic Variety, F. Guo, M. Safey El Din, C. Wang, L. Zhi
Proceedings of ISSAC 2015, Bath, UK, 2015
Preliminary version [pdf]

Real Root Finding for Rank Defects in Linear Hankel Matrices, D. Henrion, S. Naldi, M. Safey El Din
Proceedings of ISSAC 2015, Bath, UK, 2015
Preliminary version [pdf]

Polynomial Interrupt Timed Automata, B. Berard, S. Haddad, C. Piccaronny, M. Safey El Din, M. Sassolas
Proceedings of Reachability Problems, Warsow, Poland, 2015.
Preliminary version [pdf]

A baby step-giant step roadmap algorithm for general algebraic sets, S. Basu, M.-F. Roy, M. Safey El Din, E. Schost
Foundations of Computational Mathematics, 14(6):1117-1172, 2014.
Preliminary version [pdf]

Probabilistic Algorithm for the Global Optimization of a Polynomial over a Real Algebraic Set, A. Greuet, M. Safey El Din,
SIAM Journal on Optimization, 24(3):1313--1343, 2014.
Preliminary version [pdf]

Computing necessary integrability conditions for planar parametrized homogeneous potentials, A. Bostan, T. Combot, M. Safey El Din,
ISSAC 2014 Proceedings, Kobe, 2014.
Preliminary version [pdf]

Intrinsic complexity estimates in polynomial optimization, B. Bank, M. Giusti, J. Heintz, M. Safey El Din
Journal of Complexity, 30(4):430-443, 2014.
Preliminary version [pdf]

Computing rational solutions of linear matrix inequalities, Q. Guo, M. Safey El Din, L. Zhi
ISSAC 2013 Proceedings, Boston, 2013.
Preliminary version [pdf]

On the complexity of computing Grobner bases for quasi-homogeneous systems, J.-C. Faugère, M. Safey El Din, T. Verron
ISSAC 2013 Proceedings, Boston, 2013.
Preliminary version [pdf]

On the complexity of the generalized MinRank problem, J.-C. Faugère, M. Safey El Din, P.-J. Spaenlehauer
Journal of Symbolic Computation, 55:30-58, 2013.
Preliminary version [pdf]

Grobner bases and critical points: the unmixed case, J.-C. Faugère, M. Safey El Din, P.-J. Spaenlehauer
ISSAC 2012 Proceedings, Grenoble, 2012.
Preliminary version [pdf]

Variant Quantifier Elimination, H. Hong, M. Safey El Din
Journal of Symbolic Computation, 47(7):883--901, 2012.
Preliminary version [pdf]

Global optimization of polynomials restricted to a smooth variety using sums of squares, A. Greuet, F. Guo, M. Safey El Din, L. Zhi
Journal of Symbolic Computation, 47(5):503-518, 2012.
Preliminary version [pdf]

Deciding reachability of the infimum of a multivariate polynomial, A. Greuet, M. Safey El Din
ISSAC 2011 Proceedings, San Jose, 2011.
Preliminary version [pdf]

Grobner bases of bihomogeneous ideals generated by polynomials of bidegree (1,1): algorithms and complexity, J.-C. Faugère, M. Safey El Din, P.-J. Spaenlehauer
Journal of Symbolic Computation, 46(4):406--437, 2011.
Preliminary version [pdf]

A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurfaces, M. Safey El Din, E. Schost
Discrete and Computational Geometry, 45(1):181--220, 2011.
Preliminary version [pdf]

Polynomial System Solver over the Reals: Algorithms, Complexity, Implementations and Applications, M. Safey El Din,
Habilitation Thesis, Univ. Pierre and Marie Curie (Paris 06), 2010.

Computing rational points in convex semi-algebraic sets and sums of squares decompositions, M. Safey El Din, L. Zhi
SIAM Journal on Optimization, 20(6):2876-2889, 2010.
Preliminary version [pdf]

Global Optimization of Polynomials Using Generalized Critical Values and Sums of Squares, F. Guo, M. Safey El Din, L. Zhi
ISSAC 2010 Proceedings, Munich, 2010.
Preliminary version [pdf]

Computing Loci of Rank Defects of Linear Matrices using Grobner Bases and Applications to Cryptology, J.C. Faugere, M. Safey El Din, P.J. Spaenlehauer
ISSAC 2010 Proceedings, Munich, 2010.
Preliminary version [pdf]

On the geometry of polar varieties, B. Bank, M. Giusti, J. Heintz, M. Safey El Din, E. Schost
Applicable Algebra in Engineering, Communication and Computing, 21(1): 33-83, 2010.
Preliminary version [pdf].

The Voronoi diagram of three lines H. Everett, D. Lazard, S. Lazard, M. Safey El Din,
Discrete and Computational Geometry, 42(1):94-130, 2009.
Preliminary version [pdf]

Variant real quantifier elimination: algorithm and application, H. Hong, M. Safey El Din,
ISSAC 2009 Proceedings, J. May (eds), South-Korea (Seoul), 2009.
Preliminary version [pdf]

De l'algèbre linéaire à la résolution des systèmes polynomiaux, J.C. Faugère, M. Safey El Din,
Chapitre de livre paru dans un ouvrage collectif sur les mathématiques appliquées, Pearson Editions, 2009

Computing the global optimum of a multivariate polynomial over the reals, M. Safey El Din,
ISSAC 2008 Proceedings, D. Jeffrey (eds), Austria (Hagenberg), 2008.
Preliminary version [pdf]

Classification of the Perspective-Three-Point problem, Discriminant variety and Real solving polynomial systems of inequalities J.-C. Faugere, G. Moroz, F. Rouillier, M. Safey El Din,
ISSAC 2008 Proceedings, D. Jeffrey (eds), Austria (Hagenberg), 2008.
Preliminary version [pdf]

Practical and theoretical issues for the computation of generalized critical values of a polynomial mapping and its applications, M. Safey El Din
LNAI Proceedings of the Asian Symposium on Computer Mathematics (ASCM) 2007, Vol. 5081, Singapoure, 2008.
Preliminary version [pdf]

Testing Sign Conditions on a Multivariate Polynomial and Applications, M. Safey El Din,
Mathematics in Computer Science Journal, Special inaugural issue on algorithms and complexity, H. Hong and C. Yap (Guest editors), Birkhauser, 31 pages, 2007.
Preliminary version [ps], [pdf]

The Voronoi diagram of three lines in $R^3$, H. Everett, D. Lazard, S. Lazard, M. Safey El Din,
Symposium on Computational Geometry, 27 pages, 2007.
Preliminary version [ps][pdf]

Algorithmes efficaces en géométrie algébrique réelle, (Efficient algorithms in real algebraic geometry in french), M. Safey El Din,
Invited course at National Days of Computer Algebra,
notes du cours dispensé aux Journées Nationales du Calcul Formel 2007, 126 pages.
(version de janvier 2007) [pdf]

POSIX Threads Polynomials (PTPol): a scalable implementation of univariate arithmetic operations, M. Safey El Din, P. Trébuchet,
PASCO'2007 (Parrallel Symbolic Computation), 2007, 3 pages.
Preliminary version [pdf]

Generalized critical values and testing sign conditions on a polynomial, M. Safey El Din,
Proceedings of Mathematical Aspects of Computer and Information Science, 24 pages, Beijing, 2006.
Preliminary version [ps], [pdf]

Computing roadmaps in smooth real algebraic sets, M. Mezzarobba, M. Safey El Din,
Proceedings of Transgressive Computing 2006, J.-G. Dumas (Eds), pp.327-338, 2006.
Preliminary version [pdf]

Finding sampling points on real hypersurfaces is easier in singular situations, M. Safey El Din,
MEGA Conference, 6 pages, 2005.
MEGA 2005 [ps], [pdf]

Properness defects of projections and computation of one point in each connected component of a real algebraic set, M. Safey El Din, E. Schost,
Discrete and Computational Geometry, Vol.32 Number 3, pp. 417-430, Sept. 2004.
Preliminary version in gzipped format [ps]

Generalized critical values and solving polynomial inequalities, M. Safey El Din,
Extended abstract, Proc. International Conference on Polynomial System Solving (ICPSS), in honor of D. Lazard, Paris, 2004.
[ps] [pdf]

On the practical computation of one point in each connected component of a semi-algebraic set defined by a polynomial systems of equations and non-strict inequalities, C. Le Guernic, F. Rouillier, M. Safey El Din,
in Proceedings of EACA'04 conference, L.Gonzalez-Vega and T. Recio Eds, 2004.
Preliminary version in format [ps] [pdf]

Polar varieties and computation of one point in each connected component of a smooth real algebraic set, M. Safey El Din, E. Schost,
in Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, Philadelphia PA, 224-231, ACM Press, 2003.
Preliminary version in gzipped format [ps]

Real Solving for positive dimensional systems, P. Aubry, F. Rouillier, M. Safey El Din,
Journal of Symbolic Computation, Vol. 34 (6), 543-560, December 2002.
Preliminary version in gzipped format [ps]

Resolution reelle des systemes polynomiaux en dimension positive, M. Safey El Din,
PhD Thesis of Pierre et Marie Curie University, 2001.
[pdf]

Solving the Birkhoff Interpolation Problem via the Critical Point Method : an Expermiental Study, F. Rouillier, M. Safey El Din, E. Schost,
Lecture Notes in Computer Science, Automated deduction in geometry, ADG'2000, Zurich, Switzerland, September 25-27, revised papers, Editors: J. Richter-Gebert, D. Wang, Springer-Verlag, Heidelberg.
Preliminary version in gzipped format [ps]

Finding at least one point in each connected component of a real algebraic set defined by a single equation, F. Rouillier, M.-F. Roy, M. Safey El Din,
Journal of Complexity, vol. 16, 716-750, 2000.
Preliminary version in format [pdf]

New Structure Theorems for subresultants, H. Lombardi, M.-F. Roy, M. Safey El Din,
Journal of Symbolic Computation, Special Issue on Symbolic Computation in Algebra, Analysis and Geometry, Avril/Mai 2000.
Preliminary version in format [pdf]