Dentro del campo de las matemáticas, el problema de hallar las raíces de un polinomio es un problema fundamental. Este trabajo tiene como objetivo aplicar métodos de dinámica compleja e iteración de polinomios para resolver dicho problema. Partimos de ejemplos y buscamos las generalidades de los mismos con el objetivo de desarrollar un algoritmo general, que nos permita factorizar un polinomio arbitrario. Además, consideramos un análisis de los posibles limitaciones que presenta el algoritmo.

The polynomial eigenvalue problem appears in many areas of scientific and technical computing. It can be seen as a generalization of the linear eigenvalue problem in which the equation P(lambda)x = 0, that defines the problem, involves a polynomial P(lambda), of degree d, in the parameter lambda (the eigenvalue), and d+1 matrix coefficients. In its turn, the polynomial eigenvalue problem is a particular case of the nonlinear eigenvalue problem, T(lambda)x = 0, in which T is a nonlinear matrix function. These problems appear in diverse areas of application such as acoustics, fluid mechanics, structure analysis, or photonics. This thesis focuses on the study of methods for the numerical resolution of the polynomial eigenvalue problem, as well as the adaptation of such methods to the most general nonlinear case. Mainly, we consider methods of projection, that are appropriate for the case of sparse matrices of large dimension, where only a small percentage of eigevalues and eigenvectors are required. The algorithms are studied from the point of view of high-performance computing, considering issues like (computational and memory) efficiency and parallel computation. SLEPc, Scalable Library for Eigenvalue Problem Computations, is a software library for the parallel solution of large-scale eigenvalue problems. It is of general purpose and can be used for standard and generalized problems, both symmetric and nonsymmetric, with real or complex arithmetic. As a result of this thesis, we have developed several solvers for polynomial an nonlinear eigenproblems, which have included in the last versions of this software. On one hand, we consider methods based on the linearization of the polynomial problem, that solves an equivalent linear eigenproblem of dimension several times the initial size. Among them, the TOAR method stands out, that repre- sents the search subspace basis in an efficient way in terms of memory, and is appropriate to handle the increase of dimension of the linear problem. The thesis also proposes specific variants for the particular case of symmetric matrices. In all these methods we consider several aspects to provide the implementations with robustness and flexibility, such as spectral transformations, scaling, and techniques of extraction. In addition to the methods of linearization, we propose methods of Newton type, such as the method of Jacobi-Davidson with deflation and the method of Newton for invariant pairs. Due to its characteristics, the latter is not usually employed as a proper method, but as a technique for refinement of the solutions obtained with another method. The previous methods can also be applied to the resolution of the nonlinear problem, using techniques like polynomial or rational interpolation, being necessary in some cases to adapt the algorithms. This thesis covers also these cases. For all the considered algorithms we have made parallel implementations in SLEPc, and have studied its numerical behaviour and its parallel performance in problems coming from real applications. / El problema polinómico de valores propios aparece en muchas áreas de la computación científica y técnica. Puede verse como una generalización del problema lineal de valores propios en el que la ecuación P(lambda)x=0, que define el problema, involucra un polinomio P(lambda), de grado d, en el parámetro lambda del autovalor, y d+1 coeficientes matriciales. A su vez, el problema polinómico de valores propios es un caso particular del problema no lineal de valores propios, T(lambda)x=0, en el que T es una función matricial no lineal. Estos problemas aparecen en diversas áreas de aplicación como acústica, mecánica de fluidos, análisis de estructuras, o fotónica. Esta tesis se centra en el estudio de métodos para la resolución numérica del problema polinómico de valores propios, así como la adaptación de dichos métodos al caso más general no lineal. Principalmente, se consideran métodos de proyección, que son apropiados para el caso de matrices dispersas de gran dimensión cuando se requiere solo un pequeño porcentaje de los valores y vectores propios. Los algoritmos se estudian desde el punto de vista de la computación de altas prestaciones, teniendo en consideración aspectos como la eficiencia (computacional y de memoria) y la computación paralela. SLEPc, Scalable Library for Eigenvalue Problem Computations, es una biblioteca software para la resolución de problemas de valores propios de gran dimensión en paralelo. Es de propósito general y puede usarse para problemas estándares y generalizados, simétricos y no simétricos, con aritmética real o compleja. Como fruto de esta tesis, se han desarrollado diversos solvers para problemas polinómicos y no lineales, los cuales se han incluido en las últimas versiones de este software. Por un lado, se abordan métodos basados en la linealización del problema polinómico, que resuelven un problema lineal equivalente de dimensión varias veces la del inicial. Entre ellos se destaca el método TOAR, que representa la base del subespacio de búsqueda de una forma eficiente en términos de memoria, y es adecuado para manejar el aumento de dimensión del problema lineal. La tesis también propone variantes específicas para el caso particular de matrices simétricas. En todos estos métodos se consideran diversos aspectos para dotar a las implementaciones de robustez y flexibilidad, tales como transformaciones espectrales, escalado, y técnicas de extracción. Además de los métodos de linealización, se proponen métodos de tipo Newton, como el método de Jacobi-Davidson con deflación y el método de Newton para pares invariantes. Por sus características, este último no suele utilizarse como un método en sí mismo sino como técnica de refinamiento de las soluciones obtenidas con otro método. Los métodos anteriores pueden aplicarse a la resolución del problema no lineal, utilizando técnicas como la interpolación polinómica o racional, siendo necesario en algunos casos adaptar los algoritmos. La tesis cubre también estos casos. Para todos los algoritmos considerados se han realizado implementaciones paralelas en SLEPc, y se ha estudiado su comportamiento numérico y sus prestaciones paralelas en problemas procedentes de aplicaciones reales. / El problema polinòmic de valors propis apareix en moltes àrees de la computació científica i tècnica. Pot veure's com una generalització del problema lineal de valors propis en el qual l'equació P(lambda)x=0, que defineix el problema, involucra un polinomi P(lambda), de grau d, en el paràmetre lambda de l'autovalor, i d+1 coeficients matricials. Al seu torn, el problema polinòmic de valors propis és un cas particular del problema no lineal de valors propis, T(lambda)x=0, en el qual T és una funció matricial no lineal. Aquests problemes apareixen en diverses àrees d'aplicació com a acústica, mecànica de fluids, anàlisis d'estructures, o fotònica. Aquesta tesi se centra en l'estudi de mètodes per a la resolució numèrica del problema polinòmic de valors propis, així com l'adaptació d'aquests mètodes al cas més general no lineal. Principalment, es consideren mètodes de projecció, que són apropiats per al cas de matrius disperses de gran dimensió quan es requereix solament un reduït percentatge dels valors i vectors propis. Els algorismes s'estudien des del punt de vista de la computació d'altes prestacions, tenint en consideració aspectes com l'eficiència (computacional i de memòria) i la computació paral·lela. SLEPc, Scalable Library for Eigenvalue Problem Computations, és una biblioteca software per a la resolució de problemes de valors propis de gran dimensió en paral·lel. És de propòsit general i pot usar-se per a problemes estàndards i generalitzats, simètrics i no simètrics, amb aritmètica real o complexa. Com a fruit d'aquesta tesi, s'han desenvolupat diversos solvers per a problemes polinòmics i no lineals, els quals s'han inclòs en les últimes versions d'aquest software. D'una banda, s'aborden mètodes basats en la linealització del problema polinòmic, que resolen un problema lineal equivalent de dimensió diverses vegades la de l'inicial. Entre ells es destaca el mètode TOAR, que representa la base del subespai de cerca d'una forma eficient en termes de memòria, i és adequat per a manejar l'augment de dimensió del problema lineal. La tesi també proposa variants específiques per al cas particular de matrius simètriques. En tots aquests mètodes es consideren diversos aspectes per a dotar a les implementacions de robustesa i flexibilitat, tals com a transformacions espectrals, escalat, i tècniques d'extracció. A més dels mètodes de linealització, es proposen mètodes de tipus Newton, com el mètode de Jacobi-Davidson amb deflació i el mètode de Newton per a parells invariants. Per les seues característiques, aquest últim no sol utilitzar-se com un mètode en si mateix sinó com a tècnica de refinament de les solucions obtingudes amb un altre mètode. Els mètodes anteriors poden aplicar-se a la resolució del problema no lineal, utilitzant tècniques com la interpolació polinòmica o racional, sent necessari en alguns casos adaptar els algorismes. La tesi cobreix també aquests casos. Per a tots els algorismes considerats s'han realitzat implementacions paral·leles en SLEPc, i s'ha estudiat el seu comportament numèric i les seues prestacions paral·leles en problemes procedents d'aplicacions reals. / Campos González, MC. (2017). Implementación paralela de métodos iterativos para la resolución de problemas polinómicos de valores propios [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/86134

The present work focuses on Nodal Discontinuous Galerkin Method applied to the one-dimensional linear advection equation, which approximates the global solution, partitioning its domain into elements. In each element the local solution is approximated by using interpolation in such a way that the total numerical solution is a direct sum of those approximations (polynomials). This method aims at reaching a high order through a simple implementation. This model is studied by Hesthaven and Warburton [16], with the particularity of Joining the best of the Finite Volumes Method and the best of Finit Element Method . First, the main results are revised in detail concerning the Jacobi orthogonal polynomials; more precisely, its generation formula and other results which help implementing the method. Concepts regarding interpolation and best approximation are studied. Furthermore, some notions about Sobolev space interpolation is revised. Secondly, theoretical aspects of the method are explained in detail , as well as its functioning. Thirdly, both the two method consistency theorems (better approximation and interpolation), proposed by Canuto and Quarteroni [4], and error behavior theorem based on Hesthaven and Warburton [16] are explained in detail. Finally, the consistency theorem referred to the interpolation is veri ed numerically through the usage of the Python language as well as the error behavior. It is worth mentioning that, from our numerical results, we propose a new bound for the consistency (relation 4.2 (4.2)), whose demonstration will remain for a future investigation. / El presente trabajo consiste en el estudio del método numérico Galerkin Discontinuo Nodal aplicado a la ecuación de advección lineal unidimensional, el cual aproxima la solución global, particionando su dominio en elementos. En cada elemento se aproxima la solución local usando interpolación; de tal manera que la solución numérica total es una suma directa de dichas aproximaciones (polinomios). El método busca alcanzar un alto orden mediante una implementación sencilla. Este modelo es estudiado por Hesthaven y Warburton[16], con la particularidad de Fusionar lo mejor del método de Volúmenes Finitos con lo mejor del método de Elementos Finitos . Primero se revisan en detalle los principales resultados sobre los polinomios ortogonales de Jacobi; más precisamente, su fórmula de generación y otros resultados que ayudan en la implementación del método. Se estudian los conceptos de interpolación y mejor aproximación. Además, se revisan algunas nociones de interpolación de espacios de Sobolev. Segundo, se detallan aspectos teóricos del método, así como su funcionamiento. Tercero, se brinda en detalle tanto la demostración de los dos teoremas de consistencia del método (mejor aproximación e interpolación) propuestos en Canuto y Quarteroni[4] como el comportamiento del error basado en Hesthaven y Warburton [16] . Finalmente, se veri ca numéricamente, mediante el uso del lenguaje Python, el teorema de consistencia referido a interpolación, así como el comportamiento del error. Se propone una nueva cota para el consistencia (relación (4.2)) basados en los resultados numéricos, cuya demostración quedará para una futura investigación. / Tesis

Let K be an algebraically closed field of characteristic zero. The Jacobian Conjecture (JC) in dimension two stated by Keller in [8] says that any pair of polynomials P;Q ∈ L := K[x; y] with [P;Q] := axPayQ - axQayP ∈ Kx (a Jacobian pair ) defines an automorphism of L via x-> P and y -> Q. It turns out that the Newton polygons of such a pair of polynomials are closely related, and by analyzing them, much information can be obtained on conditions that a Jacobian pair must satisfy. Specifically, if there exists a Jacobian pair that does not define an automorphism (a counterexample) then their Newton polygons have to satisfy very restrictive geometric conditions. Based mostly on the work in [1], we present an algorithm to give precise geometrical descriptions of possible counterexamples. This means that, assuming (P;Q) is a counterexample to the Jacobian Conjecture with gcd(deg(P); deg(Q)) = k, we can generate the possible shapes of the Newton Polygon of P and Q and how it transforms under certain linear automorphisms. By analyzing the minimal possible counterexamples, we sketch a path to increase the lower bound of max(deg(P); deg(Q)) to 125 for a minimal possible counterexample to the Jacobian Conjecture. / Sea K un cuerpo algebraicamente cerrado de característica zero. La Conjetura del Jacobiano en dimensión dos postulada por Keller en [8] dice que cualquier par de polinomios P;Q ∈ L := K[x; y] with [P;Q] := axPayQ - axQayP ∈ Kx (un par Jacobiano) define un automofismo de L via x-> P and y -> Q. Resulta que los polígonos de Newton de tal par de polinomios están relacionados íntimamente, y al analizarlos, mucha información puede ser obtenida sobre condiciones que un par Jacobiano debe satisfacer. Específicamente, si existe un par Jacobiano que no define un automorfismo (un contraejemplo) entonces sus polígonos de Newton deben satisfacer condiciones geométricas bastante restrictivas. Basado en gran parte en el trabajo en [1], presentamos un algoritmo para dar una descripción geométrica precisa de posibles contraejemplos. Esto significa que, asumiendo que (P;Q) es un contraejemplo a la Conjetura del Jacobiano con gcd(deg(P); deg(Q)) = k, podemos generar las posibles formas del Polígono de Newton de P y Q y cómo se transforman bajo ciertos automorfismos lineales. Al analizar los posibles contraejemplos minimales, esbozamos un camino para incrementar la cota inferior de max(deg(P); deg(Q)) a 125 para un posible contraejemplo minimal a la Conjetura del Jacobiano. / Tesis

En teoría de Galois clásica, las raíces de un polinomio f(X) ∈ K [X], sus raíces generan una extensión E del cuerpo K, llamado el cuerpo de descomposición E de f(X). En el presente trabajo estudiaremos su análogo en teoría de Galois diferencial. Si dotamos a un anillo de una operacion llamada derivación (que verifica las propiedades básicas de la derivada usual) llamaremos a este par, anillo diferencial. Veremos que dado un cuerpo diferencial K y un operador diferencial lineal homogéneo L definido sobre el, sus soluciones generan una extension diferencial E del cuerpo diferencial K, dicha extensión es llamada de Picard-Vessiot. Mostraremos con detalle la construcción de una extensión de Picard-Vessiot [1] y veremos que en efecto siempre es posible realizarla. También veremos que es única salvo K−isomorfismo diferencial. / Tesis

Neste trabalho estudamos os homomorfismos entre anéis de polinômios do ponto de vista da teoria de bases de Groebner. Em particular, determinamos o núcleo de um tal homomorfismo e desenvolvemos um método para determinar quando este é sobrejetivo. Estes resultados são então generalizados para anéis quocientes. O estudo de tais homomorfismos nos permite determinar os polinômos minimais de elementos em extensões de corpos, bem como encontrar soluções para um problema de programação inteira. / In this work we study the homomorphisms between polynomial rings as an application of the Groebner basis theory. In particular, we determine generators for the kemel of such a homomorphism and we give a method to determine whether it is onto. We then generalize these results to the case of quocient rings. The study of these homomorphisms allows us to determine mini mal polynomials of elements in field extensions, as well as to find solutions to an integer programming problem.

Neste trabalho estudamos os homomorfismos entre anéis de polinômios do ponto de vista da teoria de bases de Groebner. Em particular, determinamos o núcleo de um tal homomorfismo e desenvolvemos um método para determinar quando este é sobrejetivo. Estes resultados são então generalizados para anéis quocientes. O estudo de tais homomorfismos nos permite determinar os polinômos minimais de elementos em extensões de corpos, bem como encontrar soluções para um problema de programação inteira. / In this work we study the homomorphisms between polynomial rings as an application of the Groebner basis theory. In particular, we determine generators for the kemel of such a homomorphism and we give a method to determine whether it is onto. We then generalize these results to the case of quocient rings. The study of these homomorphisms allows us to determine mini mal polynomials of elements in field extensions, as well as to find solutions to an integer programming problem.

The present paper is a study of modied Hermite polynomials of two variables Hn(x; y; a) which for a = e reduces to Hermite polynomials of two variables Hn(x; y) due to M.A. Khan and G.S. Abukhammash. / El presente artculo se estudian polinomios modicados de Hermite de dos variables Hn(x; y; a) que para a = e se reducen a los polinomios de Hermite de dos variables Hn(x; y) introducidos por M.A. Khan y G.S.Abukhammash.

Neste trabalho estudamos os homomorfismos entre anéis de polinômios do ponto de vista da teoria de bases de Groebner. Em particular, determinamos o núcleo de um tal homomorfismo e desenvolvemos um método para determinar quando este é sobrejetivo. Estes resultados são então generalizados para anéis quocientes. O estudo de tais homomorfismos nos permite determinar os polinômos minimais de elementos em extensões de corpos, bem como encontrar soluções para um problema de programação inteira. / In this work we study the homomorphisms between polynomial rings as an application of the Groebner basis theory. In particular, we determine generators for the kemel of such a homomorphism and we give a method to determine whether it is onto. We then generalize these results to the case of quocient rings. The study of these homomorphisms allows us to determine mini mal polynomials of elements in field extensions, as well as to find solutions to an integer programming problem.

Orientador: Cleonice Fátima Bracciali / Banca: Fernando Rodrigo Rafaeli / Banca: Eliana Xavier Linhares de Andrade / Resumo: O objetivo des trabalho é estudar os polinômios ortogonais em várias variáveis com relação a um funcional linear, L e suas propriedades análogas às dos polinômios ortogonais em uma variável, tais como: a relação de três termos, a relação de recorrência de três termos, o teorema de Favard, os zeros comuns ea cubatura gaussiana. Além disso, apresentamos um método para gerar polinômios ortonormais em duas variáveis e alguns exemplos. / Abstract: The aim here is to study the orthogonal polynomials in several variables with respect to a linear functional, L. also, to study its properties analogous to orthogonal polynomials in one variable, such as the theree term relation, the three term recurrence relation, Favard's theorem, the common zeros and Gaussian cubature. A method to generating orthonormal polynomials in two variables and some examples are presented. / Mestre