Non-negativity certificates for polynomials

Abstract

This study addresses questions in real algebraic geometry, including its intersection with computational aspects. In particular, the work focuses on characterizing the non-negativity of multivariate polynomials. The content is organized into four sections, followed by some conclusions. The first chapter provides a detailed introduction to the fundamental concepts of the field, including basic definitions and the main theoretical tools necessary for understanding the subject. These concepts are also contextualized within their historical framework, with the aim of offering a comprehensive overview of the topic. The second chapter presents a generalization of the work developed in "Rational certificates of non-negativity on semialgebraic subsets of cylinders" by Gabriela Jeronimo and Daniel Perrucci (see [9]), thereby extending the obtained results. Additionally, an explicit calculation of a question posed in the same article is included, with the objective of offering a more complete and detailed resolution. The third chapter presents the implementation of three algorithms along with a set of examples of their executions. The first algorithm determines whether a multivariate polynomial is a sum of squares and, if so, provides a decomposition. The second algorithm allows us to determine whether a multivariate polynomial belongs to the quadratic module generated by a set of polynomials. Again, if this is the case, such a decomposition in the quadratic module is provided. The third and final algorithm checks whether a quadratic module is archimedean and, if so, provides a decomposition in the quadratic module. For archimedeanity only theoretical characterizations previously existed, and in this work, a computational version has been developed. Additionally, the code for the quadratic module algorithm has been optimized through parallelization to run on the MareNostrum 5 super- computer at the Barcelona Supercomputing Center. Finally, the fourth chapter focuses on the parallelization of the quadratic module algorithm and its performance evaluation. It details the methodology used to enhance efficiency and analyzes the resulting improvements in execution time and scalability. The assessment includes a comparison of sequential and parallel versions, highlighting the effectiveness and potential limitations of the parallelization strategy implemented.

Aquest estudi aborda qüestions de geometria algebraica real, incloent la seva intersecció amb aspectes computacionals. En particular, el treball es centra en la caracterització de la no negativitat de polinomis en diverses variables. El contingut s’organitza en quatre blocs, seguits d’algunes conclusions. El primer capítol proporciona una introducció detallada als conceptes fonamentals de l’àrea, incloent-hi les definicions bàsiques i les principals eines teòriques necessàries per comprendre la matèria. També es contextualitzen aquests conceptes dins el seu marc històric, amb l’objectiu d’oferir una visió global del tema. En el segon capítol, es presenta una generalització del treball desenvolupat a "Rational certificates of non-negativity on semialgebraic subsets of cylinders" per Gabriela Jeronimo i Daniel Perrucci (veure [9]), ampliant així els resultats obtinguts. A més, s’inclou el càlcul explícit d’una qüestió plantejada en el mateix article, amb l’objectiu de proporcionar una resolució més completa i detallada. El tercer capítol presenta la implementació de tres algorismes juntament amb un conjunt d’exemples de les seves execucions. El primer algorisme determina si un polinomi en diverses variables és una suma de quadrats i, en cas afirmatiu, permet obtenir una descomposició. El segon algorisme permet determinar si un polinomi en diverses variables pertany al mòdul quadràtic generat per un conjunt de polinomis. De nou, en cas afirmatiu, es proporciona tal descomposició en el mòdul quadràtic. El tercer i últim algorisme permet comprovar si un mòdul quadràtic és arquimedià i, en cas que ho sigui, proporciona una descomposició en el mòdul quadràtic. Per a l’arquimedianeitat només existien caracteritzacions teòriques, i en aquest treball s’ha desenvolupat una versió computacional. A més, s’ha dut a terme una optimització del codi de l’algorisme del mòdul quadràtic mitjançant paral·lelització, per tal d’executar-lo al superodinador MareNostrum 5 del Barcelona Supercomputing Center. Finalment, el quart capítol es centra en la paral·lelització de l’algorisme del mòdul quadràtic i la seva avaluació de rendiment. Detalla la metodologia utilitzada per millorar l’eficiència i analitza les millores obtingudes en el temps d’execució axí com l’escalabilitat. L’avaluació inclou una comparació entre les versions seqüencial i paral·lela, destacant l’efectivitat i les possibles limitacions de l’estratègia de paral·lelització implementada.