Since their conception by Collins in 1975, Cylindrical Algebraic Decompositions (CADs) have been used to analyse the real algebraic geometry of systems of polynomials. Applications for CAD technology range from quantifier elimination to robot motion planning. Although of great use in practice, the CAD algorithm was shown to have doubly exponential complexity with respect to the number of variables for the problem, which limits its use for large examples. Due to the high complexity of CAD, much work has been done to improve its performance. In this thesis new advances will be discussed that improve the practical efficiency of CAD for a variety of problems, with a new complexity result for one set of algorithms. A new invariance condition, truth table invariance (TTICAD), and two algorithms to construct TTICADs are given and shown to be highly efficient. The idea of restricting the output of CADs, allowing for greater efficiency, is formalised as sub-decompositions and two particular ideas are investigated in depth. Efficient selection of various formulation choices for a CAD problem are discussed, with a collection of heuristics investigated and machine learning applied to assist in choosing an optimal heuristic. The mathematical expression of a problem is shown to be of great importance, with preconditioning and reformulation investigated. Finally, these advances are collected together in a general framework for applying CAD in an efficient manner to a given problem. It is shown that their combination is not cumulative and care must be taken. To this end, a prototype software CADassistant is described to help users take advantage of the advances without knowledge of the underlying theory. The effects of the various advances are demonstrated through a guiding example originally considered by Solotareff, which describes the approximation of a cubic polynomial by a linear function. Naïvely applying CAD to the problem takes 916.1 seconds of construction (from which a solution can easily be derived), which is reduced to 20.1 seconds by combining various advances from this thesis.

We prove a strict positivstellensatz for Weyl algebra elements fulfilling an additional, asymptotic strict positivity condition. As a tool we develop a non-commutative analogue to the Newton polytope.

The Mukhin-Tarasov-Varchenko Theorem (previously the Shapiro Conjecture) asserts that a Schubert problem has all solutions distinct and real if the Schubert varieties involved osculate a rational normal curve at real points. When conjectured, it sparked interest in real osculating Schubert calculus, and computations played a large role in developing the surrounding theory. Our purpose is to uncover generalizations of the Mukhin-Tarasov-Varchenko Theorem, proving them when possible. We also improve the state of the art of computationally solving Schubert problems, allowing us to more effectively study ill-understood phenomena in Schubert calculus. We use supercomputers to methodically solve real osculating instances of Schubert problems. By studying over 300 million instances of over 700 Schubert problems, we amass data significant enough to reveal generalizations of the Mukhin-Tarasov- Varchenko Theorem and compelling enough to support our conjectures. Combining algebraic geometry and combinatorics, we prove some of these conjectures. To improve the efficiency of solving Schubert problems, we reformulate an instance of a Schubert problem as the solution set to a square system of equations in a higher- dimensional space. During our investigation, we found the number of real solutions to an instance of a symmetrically defined Schubert problem is congruent modulo four to the number of complex solutions. We proved this congruence, giving a generalization of the Mukhin-Tarasov-Varchenko Theorem and a new invariant in enumerative real algebraic geometry. We also discovered a family of Schubert problems whose number of real solutions to a real osculating instance has a lower bound depending only on the number of defining flags with real osculation points. We conclude that our method of computational investigation is effective for uncovering phenomena in enumerative real algebraic geometry. Furthermore, we point out that our square formulation for instances of Schubert problems may facilitate future experimentation by allowing one to solve instances using certifiable numerical methods in lieu of more computationally complex symbolic methods. Additionally, the methods we use for proving the congruence modulo four and for producing an

<p>This work strengthens and extends an algorithm for computing Betti numbers of symmetric semialgebraic sets developed by Basu and Riener in, <em>Vandermonde Varieties, Mirrored Spaces, and the Cohomology of Symmetric Semi-Algebraic Sets</em>. We first adapt a construction of Gabrielov and Vorobjov in, <em>Approximation of Definable Sets by Compact Families, and Upper Bounds on Homotopy and Homology,</em> for replacing arbitrary definable sets by compact ones to the symmetric case. The original construction provided maps from the homotopy and homology groups of the replacement set to those of the original; we show that for sets symmetric relative to the action of some finite reflection group <em>G</em>, we may construct these maps to be equivariant. This modification to the construction for compact replacement allows us to extend Basu and Riener's theorem on which submodules appear in the isotypic decomposition of each cohomology space to sets not necessarily closed and bounded. Furthermore, by utilizing this equivariant compact approximation, we may obtain a precise description of the aforementioned decomposition of each cohomology space, and not merely the final dimension of the space, from Basu and Riener's algorithm.</p> <p><br></p> <p>    Though our equivariant compact replacement holds for <em>G</em> any finite reflection group, Basu and Riener's results only consider the case of the action the of symmetric group, sometimes termed type <em>A</em>. As a first step towards generalizing Basu and Riener's work, we examine the next major class of symmetry: the action of the group of signed permutations (known as type <em>B</em>). We focus our attention on Vandermonde varieties, a key object in Basu and Riener's proofs. We show that the intersection of a type <em>B</em> Vandermonde variety with a fundamental region of type <em>B</em> symmetry is topologically regular. We also prove a result about the intersection of a type <em>B</em> Vandermonde variety with the walls of this fundamental region, leading to the elimination of factors in a different decomposition of the homology spaces.</p>

In recent years, algebraic geometry (both complex and real) has proven to be useful in numerous applications in optimization, statistics, quantum information, and physics. In this thesis, we concentrate on studying semi-algebraic sets and varieties defined over the real numbers that arise in these applied contexts. We begin with the study of Gibbs manifolds and Gibbs varieties. Gibbs manifolds are images of affine spaces of symmetric matrices under the matrix exponential map. They appear naturally in the context of entropic regularization for semidefinite programming or entropy maximization in quantum information theory. The Gibbs variety is the zero locus of all polynomials that vanish on the Gibbs manifold. We compute these polynomials and show that the Gibbs variety is low-dimensional. We give an exact formula for this dimension, and an upper bound for the degree of the Gibbs variety. We apply our theory to a range of scenarios: matrix pencils, quantum optimal transport, and sparse matrices. The role of Gibbs manifolds in quantum information theory leads us to consider the notion of quantum conditional independence from an algebraic perspective. We take inspiration from algebraic statistics, where graphical models encoding conditional independence relations can be described as intersections of an algebraic variety with the probability simplex, and study quantum counterparts of such models. We present several ways to associate an algebraic variety to such a model. We study basic properties of these varieties and provide algorithms to compute their defining equations. We also study toric varieties defined by commuting Hamiltonians arising from a graph in the context of stabilizer codes. We give an efficient algorithm to compute the defining equations of such a toric variety. Moreover, we investigate a quantum analog of maximum likelihood estimation for quantum exponential families, the so-called quantum information projection. We continue with studying (semi-)algebraic geometry of minimizing dual volumes of polytopes. Similarly to Gibbs manifolds, this appears in the context of regularization of convex optimization problems. The interior point of a convex polytope that leads to a polar dual of minimal volume is called the Santaló point. When translating the facet hyperplanes, the Santaló point traces out a semi-algebraic set called the Santaló patchwork. We describe and compute this set. We then investigate several naturally defined algebraic varieties containing the Santaló patchwork. We continue by treating the question of computing the Santaló points of polytopes numerically. We also explore connections to physics and algebraic statistics. Finally, we study Grasstopes. This is yet another class of semi-algebraic sets inspired by physics. These are linear projections of the positive Grassmannian. When the linear projection is given by a totally positive matrix, we recover the definition of the amplituhedron, a semi-algebraic set that computes scattering amplitudes in a certain quantum field theory. We concentrate on the case when the image lives in the projective space, and give a combinatorial characterization of such Grasstopes in terms of sign flips, extending the results of Karp and Williams for the amplituhedron.

Este trabalho é focado num problema clássico das Ciências e Engenharia, que consiste em cobrir um objeto por esferas de mesmo raio, a ser minimizado. A abordagem prática usual conta com sérias desvantagens. Logo, faz-se necessário trabalhar com isto de forma diferenciada. A técnica proposta aqui envolve a utilização de resultados célebres da geometria algébrica real, que tem como peça central o positivstellensatz de Stengle e, fazendo a devida relação entre esses resultados e otimização com restrições envolvendo representações naturais por somas de quadrados, é possível reduzir o problema original a um de programação semidefinida não linear. Mas, por contar com particularidades que favorecem a aplicação do paradigma de restauração inexata, esta foi a técnica utilizada para resolvê-lo. A versatilidade da técnica e a possibilidade de generalização direta dos objetos envolvidos destacam-se como grandes vantagens desta abordagem, além da visão algébrica inovadora do problema. / This work is focused on a classic problem from Engineering. Basically, it consists of finding the optimal positioning and radius of a set of equal spheres in order to cover a given object. The common approach to this carries some substantial disadvantages, what makes it necessary to nd a dierent way. Here, we explore some renowned results from real algebraic geometry, which has Stengle\'s positivstellensatz as one of its central pieces, and SOS optimization. Once the proper link is made, the original problem can be reduced to a nonlinear semidenite programming one, which has peculiarities that favours the application of an inexact restoration paradigm. We point out the algebraic view and the no use of discretizations as great advantages of this approach, besides the notable versatility and easy generalization in terms of dimension and involved objects.

Este trabalho é focado num problema clássico das Ciências e Engenharia, que consiste em cobrir um objeto por esferas de mesmo raio, a ser minimizado. A abordagem prática usual conta com sérias desvantagens. Logo, faz-se necessário trabalhar com isto de forma diferenciada. A técnica proposta aqui envolve a utilização de resultados célebres da geometria algébrica real, que tem como peça central o positivstellensatz de Stengle e, fazendo a devida relação entre esses resultados e otimização com restrições envolvendo representações naturais por somas de quadrados, é possível reduzir o problema original a um de programação semidefinida não linear. Mas, por contar com particularidades que favorecem a aplicação do paradigma de restauração inexata, esta foi a técnica utilizada para resolvê-lo. A versatilidade da técnica e a possibilidade de generalização direta dos objetos envolvidos destacam-se como grandes vantagens desta abordagem, além da visão algébrica inovadora do problema. / This work is focused on a classic problem from Engineering. Basically, it consists of finding the optimal positioning and radius of a set of equal spheres in order to cover a given object. The common approach to this carries some substantial disadvantages, what makes it necessary to nd a dierent way. Here, we explore some renowned results from real algebraic geometry, which has Stengle\'s positivstellensatz as one of its central pieces, and SOS optimization. Once the proper link is made, the original problem can be reduced to a nonlinear semidenite programming one, which has peculiarities that favours the application of an inexact restoration paradigm. We point out the algebraic view and the no use of discretizations as great advantages of this approach, besides the notable versatility and easy generalization in terms of dimension and involved objects.

Les systèmes polynomiaux réels sont omniprésents dans de nombreux domaines des mathématiques pures et appliquées. A. Khovanskii a fourni une borne fewnomiale supérieure sur le nombre de solutions positives non-dégénérées d'un système polynomial réel de n équations à n variables qui ne dépend que du nombre de monômes apparaissant dans les équations. Cette dernière borne a été récemment améliorée par F. Bihan et F. Sottile, mais la borne résultante peut être encore améliorée, même dans certains cas simples.Le but de ce travail est d'aborder trois problèmes importants dans la théorie des Fewnomials. Considérons une famille de systèmes polynomiaux réels avec une structure donnée (par exemple, support ou le nombre de monômes). Un problème est de trouver de bonnes bornes supérieures pour leurs nombres de solutions réelles (ou positives). Un autre problème est de construire des systèmes dont le nombre de solutions réelles (ou positives) sont proches de la meilleure borne supérieure connue. Lorsqu'une borne supérieure optimale est bien connue, qu'est ce qu'on peut dire dans le cas où elle est atteinte?Dans cette thèse, nous affinons un résultat de M. Avendaño en démontrant que le nombre de points d'intersection réels d'une droite réelle avec une courbe réelle plane définie par un polynôme avec au plus t monômes est soit infini ou ne dépasse pas $6t -7$. En outre, on montre que notre borne est optimale pour t=3 en utilisant les dessins d'enfant réels de Grothendieck. Cela montre que le nombre maximal de points d'intersection réels d'une droite réelle avec une courbe trinomiale réelle plane est onze.Nous considérons ensuite le problème de l'estimation du nombre maximal de points d'intersection transverses positifs d'une courbe plane trinomiale et d'une courbe plane t-nomiale. T-Y Li, J.-M. Rojas et X. Wang ont montré que ce nombre est borné par 2^t - 2, et récemment P. Koiran, N. Portier et S. Tavenas ont trouvé la borne supérieure 2t^3/3 +5t. Nous fournissons la borne supérieure $ 3*2^(t-2) - 1 qui est optimale pour t = 3 et est la plus petite pour t=4,...,9. Ceci est réalisé en utilisant la notion de dessins d'enfant réels. De plus, nous étudions en détail le cas t = 3 et nous donnons une restriction sur les supports des systèmes atteignant la borne optimale cinq.Un circuit est un ensemble de n+ 2 points dans $mathbb{R}^n$ qui sont minimalement affinement dépendants. Il est connu qu'un système supporté sur un circuit a au plus n+1 solutions positives non dégénérées, et que cette borne est optimale. Nous utilisons les dessins d'enfant réels et le patchwork combinatoire de Viro pour donner une caractérisation complète des circuits supportant des systèmes polynomiaux avec le nombre maximal de solutions positives non dégénérées.Nous considérons des systèmes polynomiaux de deux équations à deux variables avec cinq monômes distincts au total. Ceci est l'un des cas les plus simples où la borne supérieure optimale sur le nombre de solutions positives non dégénérées n'est pas connue. F. Bihan et F. Sottile ont prouvé que cette borne optimale est majorée par quinze. D'autre part, les meilleurs exemples avaient seulement cinq solutions positives non dégénérées.Nous considérons des systèmes polynomiaux comme avant, mais défini sur le corps des séries de Puiseux réelles généralisées et localement convergentes. Les images par l'application de valuation des solutions d'un tel système sont des points d'intersection de deux courbes tropicales planes. En utilisant des intersections non transverses des courbes tropicales planes, on obtient une construction d'un système polynomial réel comme ci-dessus ayant sept solutions positives non dégénérées. / Real polynomial systems are ubiquitous in many areas of pure and applied mathematics. A. Khovanskii provided a fewnomial upper bound on the number of non-degenerate positive solutions of a real polynomial system of $n$ equations in n variables that depends only on the number of monomials appearing in the equations. The latter bound was recently improved by F. Bihan and F. Sottile, but the resulting bound still has room for improvement, even in some simple cases.The aim of this work is to tackle three main problems in Fewnomial theory. Consider a family of real polynomial systems with a given structure (for instance, supports or number of monomials). One problem is to find good upper bounds for their numbers of real (or positive) solutions. Another problem is to construct systems whose numbers of real (or positive) solutions are close to the best known upper bound. When a sharp upper bound is known, what can be said about reaching it?In this thesis, we refine a result by M. Avendaño by proving that the number of real intersection points of a real line with a real plane curve defined by a polynomial with at most t monomials is either infinite or does not exceed 6t -7. Furthermore, we prove that our bound is sharp for t=3 using Grothendieck's real dessins d'enfant. This shows that the maximal number of real intersection points of a real line with a real plane trinomial curve is eleven.We then consider the problem of estimating the maximal number of transversal positive intersection points of a trinomial plane curve and a t-nomial plane curve. T-Y Li, J.-M. Rojas and X. Wang showed that this number is bounded by 2^t-2, and recently P. Koiran, N. Portier and S. Tavenas proved the upper bound 2t^3/3 +5t. We provide the upper bound 3*2^{t-2} - 1 that is sharp for t=3 and is the tightest for t=4,...,9. This is achieved using the notion of real dessins d'enfant. Moreover, we study closely the case t=3 and give a restriction on the supports of systems reaching the sharp bound five.A circuit is a set of n+2 points in mathbb{R}^n that is minimally affinely dependent. It is known that a system supported on a circuit has at most n+1 non-degenerate positive solutions, and that this bound is sharp. We use real dessins d'enfant and Viro's combinatorial patchworking to give a full characterization of circuits supporting polynomial systems with the maximal number of non-degenerate positive solutions.We consider polynomial systems of two equations in two variables with a total of five distinct monomials. This is one of the simplest cases where the sharp upper bound on the number of non-degenerate positive solutions is not known. F. Bihan and F. Sottile proved that this sharp bound is not greater than fifteen. On the other hand, the best examples had only five non-degenerate positive solutions. We consider polynomial systems as before, but defined over the field of real generalized locally convergent Puiseux series. The images by the valuation map of the solutions of such a system are intersection points of two plane tropical curves. Using non-transversal intersections of plane tropical curves, we obtain a construction of a real polynomial system as above having seven non-degenerate positive solutions.

La complexité arithmétique est l’étude des ressources nécessaires pour calcu- ler des polynômes en n’utilisant que des opérations arithmétiques. À la fin des années 70, Valiant a défini (de manière semblable à la complexité booléenne) des classes de polynômes. Les polynômes, ayant des circuits de taille polyno- miale, considérés faciles forment la classe VP. Les sommes exponentielles de ces derniers correpondent alors à la classe VNP. L’hypothèse de Valiant est la conjecture que VP ̸= VNP.Bien que cette conjecture soit encore grandement ouverture, cette dernière semble toutefois plus accessible que son homologue booléen. La structure algé- brique sous-jacente limite les possibilités de calculs. En particulier, un résultat important du domaine assure que les polynômes faciles peuvent aussi être cal- culés efficacement en paralèlle. De plus, quitte à autoriser une augmentation raisonnable de la taille, il est possible de les calculer avec une profondeur de calcul bornée par une constante. Comme ce dernier modèle est très restreint, de nombreuses bornes inférieures sont connues. Nous nous intéresserons en premier temps à ces résultats sur les circuits de profondeur constante.Bürgisser a montré qu’une conjecture (la τ-conjecture) qui borne supérieu- rement le nombre de racines de certains polynômes univariés, impliquait des bornes inférieures en complexité arithmétique. Mais, que se passe-t-il alors, si on essaye de réduire, comme précédemment, la profondeur du polynôme consi- déré? Borner le nombre de racines réelles de certaines familles de polynômes permetterait de séparer VP et VNP. Nous étudierons finalement ces bornes su- périeures sur le nombre de racines réelles. / Arithmetic complexity is the study of the required ressources for computing poynomials using only arithmetic operations. In the last of the 70s, Valiant defined (similarly to the boolean complexity) some classes of polynomials. The polynomials which have polynomial size circuits form the class VP. Exponential sums of these polynomials correspond to the class VNP. Valiant’s hypothesis is the conjecture that VP is different tVNP.Although this conjecture is still open, it seems more accessible than its boolean counterpart. The induced algebraic structure limits the possibilities of the computation. In particular, an important result states that the low de- gree polynomials can be efficiently computed in parallel. Moreover, if we allow a fair increasement of the size, it is possible to compute them with a constant depth. As this last model is very particular, some lower bounds are known.Bürgisser showed that a conjecture (τ-conjecture) which bounds the number of roots of some univariate polynomials, implies lower bounds in arithmetic complexity. But, what happens if we try to reduce as before the depth of the circuits for the polynomials? Bounding the number of real roots of some families of polynomials would imply a separation between VP and VNP. Finally we willstudy these upper bounds on the number of real roots.

We prove a strict positivstellensatz for Weyl algebra elements fulfilling an additional, asymptotic strict positivity condition. As a tool we develop a non-commutative analogue to the Newton polytope.