Дисертації з теми "Exact polynomial"

I describe an exact method for computing roots of a system of multivariate polynomials with rational coefficients, called the rational univariate reduction. This method enables performance of exact algebraic computation of coordinates of the roots of polynomials. In computational geometry, curves, surfaces and points are described as polynomials and their intersections. Thus, exact computation of the roots of polynomials allows the development and implementation of robust geometric algorithms. I describe applications in robust geometric modeling. In particular, I show a new method, called numerical perturbation scheme, that can be used successfully to detect and handle degenerate configurations appearing in boundary evaluation problems. I develop a derandomized version of the algorithm for computing the rational univariate reduction for a square system of multivariate polynomials and a new algorithm for a non-square system. I show how to perform exact computation over algebraic points obtained by the rational univariate reduction. I give a formal description of numerical perturbation scheme and its implementation.

An ideal algorithm for solving a particular problem always finds an optimal solution, finds such a solution for every possible instance, and finds it in polynomial time. When dealing with NP-hard problems, algorithms can only be expected to possess at most two out of these three desirable properties. All algorithms presented in this thesis are exact algorithms, which means that they always find an optimal solution. Demanding the solution to be optimal means that other concessions have to be made when designing an exact algorithm for an NP-hard problem: we either have to impose restrictions on the instances of the problem in order to achieve a polynomial time complexity, or we have to abandon the requirement that the worst-case running time has to be polynomial. In some cases, when the problem under consideration remains NP-hard on restricted input, we are even forced to do both. Most of the problems studied in this thesis deal with partitioning the vertex set of a given graph. In the other problems the task is to find certain types of paths and cycles in graphs. The problems all have in common that they are NP-hard on general graphs. We present several polynomial time algorithms for solving restrictions of these problems to specific graph classes, in particular graphs without long induced paths, chordal graphs and claw-free graphs. For problems that remain NP-hard even on restricted input we present exact exponential time algorithms. In the design of each of our algorithms, structural graph properties have been heavily exploited. Apart from using existing structural results, we prove new structural properties of certain types of graphs in order to obtain our algorithmic results.

Dans cette thèse, nous nous intéressons à l'étude des programmes polynomiaux, c'est à dire les problème d'optimisation dont la fonction objectif et/ou les contraintes font intervenir des polynômes de plusieurs variables. Ces problèmes ont de nombreuses applications pratiques et constituent actuellement un champ de recherche très actif. Différentes méthodes permettent de les résoudre de façon exacte ou approchée, en utilisant par exemple des relaxationssemidéfinies positives du type "moments-somme de carrés". Mais ces problèmes restent très difficiles et on ne sait résoudre en toute généralité que des instances de petite taille.Dans le cas quadratique, une approche de résolution exacte efficace a été initialement proposée à travers la méthode QCR. Elle se base sur une reformulation quadratique convexe "optimale" au sens de la borne par relaxation continue.Une des motivations de cette thèse est de généraliser cette approche pour le cas des problèmes polynomiaux. Dans la majeure partie de ce manuscrit, nous étudions les problèmes d'optimisation en variables binaires. Nous proposons deux familles de reformulations convexes pour ces problèmes: des reformulations "directes" et des reformulations passant par la quadratisation.Pour les reformulations directes, nous nous intéressons tout d'abord aux linéarisations. Nous introduisons le concept de q-linéarisation, une linéarisation utilisant q variables additionnelles, et comparons les bornes obtenues par relaxation continue pour différentes valeurs de q. Ensuite, nous appliquons la reformulation convexe au problème polynomial, en ajoutant des termes supplémentaires à la fonction objectif, mais sans ajouter de variables ou de contraintes additionnelles.La deuxième famille de reformulations convexes vise à étendre la reformulation quadratique convexe au cas polynomial. Nous proposons plusieurs nouvelles reformulations alternatives que nous comparons aux méthodes existantes sur des instances de la littérature. En particulier nous présentons l'algorithme PQCR pour résoudre des problèmes polynomiaux binaires sans contrainte. La méthode PQCR permet de résoudre des instances jusqu'ici non résolues. En plus des expérimentations numériques, nous proposons aussi une étude théorique visant à comparer les différentes reformulations quadratiques de la littérature puis à leur appliquer une reformulation convexe.Enfin nous considérons des cas plus généraux et nous proposons une méthode permettant de calculer des relaxations convexes pour des problèmes continus
In this thesis, we are interested in the study of polynomial programs, that is optimization problems for which the objective function and/or the constraints are expressed by multivariate polynomials. These problems have many practical applications and are currently actively studied. Different methods can be used to find either a global or a heuristic solution, using for instance, positive semi-definite relaxations as in the "Moment/Sum of squares" method. But these problems remain very difficult and only small instances are addressed. In the quadratic case, an effective exact solution approach was initially proposed in the QCR method. It is based on a quadratic convex reformulation, which is optimal in terms of continuous relaxation bound.One of the motivations of this thesis is to generalize this approach to the case of polynomial programs. In most of this manuscript, we study optimization problems with binary variables. We propose two families of convex reformulations for these problems: "direct" reformulations and quadratic ones.For direct reformulations, we first focus on linearizations. We introduce the concept of q-linearization, that is a linearization using q additional variables, and we compare the bounds obtained by continuous relaxation for different values of q. Then, we apply convex reformulation to the polynomial problem, by adding additional terms to the objective function, but without adding additional variables or constraints.The second family of convex reformulations aims at extending quadratic convex reformulation to the polynomial case. We propose several new alternative reformulations that we compare to existing methods on instances of the literature. In particular we present the algorithm PQCR to solve unconstrained binary polynomial problems. The PQCR method is able to solve several unsolved instances. In addition to numerical experiments, we also propose a theoretical study to compare the different quadratic reformulations of the literature and then apply a convex reformulation to them.Finally, we consider more general problems and we propose a method to compute convex relaxations for continuous problems

Dans cette thèse, nous nous intéressons à l'étude des structures déterminantielles apparaissent dans l'optimisation semi-définie (SDP), le prolongement naturel de la programmation linéaire au cône des matrices symétrique semi-définie positives. Si l'approximation d'une solution d'un programme semi-défini peut être calculé efficacement à l'aide des algorithmes de points intérieurs, ni des algorithmes exacts efficaces pour la SDP sont disponibles, ni une compréhension complète de sa complexité théorique a été atteinte. Afin de contribuer à cette question centrale en optimisation convexe, nous concevons un algorithme exact pour décider la faisabilité d'une inégalité matricielle linéaire (LMI) $A(x)\succeq 0$. Quand le spectraèdre associé (le lieu $\spec$ des $x \in \RR^n$ ou $A(x)\succeq 0$) n'est pas vide, la sortie de cet algorithme est une représentation algébrique d'un ensemble fini qui contient au moins un point $x \in \spec$: dans ce cas, le point $x$ minimise le rang de $A(x)$ sur $\spec$. La complexité est essentiellement quadratique en le degré de la représentation en sortie, qui coïncide, expérimentalement, avec le degré algébrique de l'optimisation semi-définie. C'est un garantie d'optimalité de cette approche dans le contexte des algorithmes exacts pour les LMI et la SDP. Remarquablement, l'algorithme ne suppose pas la présence d'un point intérieur dans $\spec$, et il profite de l'existence de solutions de rang faible de l'LMI $A(x)\succeq 0$. Afin d'atteindre cet objectif principal, nous développons une approche systématique pour les variétés déterminantielles associées aux matrices linéaires. Nous prouvons que décider la faisabilité d'une LMI $A(x)\succeq 0$ se réduit à calculer des points témoins dans les variétés déterminantielles définies sur $A(x)$. Nous résolvons ce problème en concevant un algorithme exact pour calculer au moins un point dans chaque composante connexe réelle du lieu des chutes de rang de $A(x)$. Cet algorithme prend aussi avantage des structures supplémentaires, et sa complexité améliore l'état de l'art en géométrie algébrique réelle. Enfin, les algorithmes développés dans cette thèse sont implantés dans une nouvelle bibliothèque Maple appelé Spectra, et les résultats des expériences mettant en évidence la meilleure complexité sont fournis
In this thesis we focus on the study of determinantal structures arising in semidefinite programming (SDP), the natural extension of linear programming to the cone of symetric positive semidefinite matrices. While the approximation of a solution of a semidefinite program can be computed efficiently by interior-point algorithms, neither efficient exact algorithms for SDP are available, nor a complete understanding of its theoretical complexity has been achieved. In order to contribute to this central question in convex optimization, we design an exact algorithm for deciding the feasibility of a linear matrix inequality (LMI) $A(x) \succeq 0$. When the spectrahedron $\spec = \{x \in \RR^n \mymid A(x) \succeq 0\}$ is not empty, the output of this algorithm is an algebraic representation of a finite set meeting $\spec$ in at least one point $x^*$: in this case, the point $x^*$ minimizes the rank of the pencil on the spectrahedron. The complexity is essentially quadratic in the degree of the output representation, which meets, experimentally, the algebraic degree of semidefinite programs associated to $A(x)$. This is a guarantee of optimality of this approach in the context of exact algorithms for LMI and SDP. Remarkably, the algorithm does not assume the presence of an interior point in the spectrahedron, and it takes advantage of the existence of low rank solutions of the LMI. In order to reach this main goal, we develop a systematic approach to determinantal varieties associated to linear matrices. Indeed, we prove that deciding the feasibility of a LMI can be performed by computing a sample set of real solutions of determinantal polynomial systems. We solve this problem by designing an exact algorithm for computing at least one point in each real connected component of the locus of rank defects of a pencil $A(x)$. This algorithm admits as input generic linear matrices but takes also advantage of additional structures, and its complexity improves the state of the art in computational real algebraic geometry. Finally, the algorithms developed in this thesis are implemented in a new Maple library called {Spectra}, and results of experiments highlighting the complexity gain are provided

Dans cette thèse, nous étudions la suite de mesures de Mahler d’une famille de polynômes à deux variables exacts et réguliers, que nous notons Pd := P0≤i+j≤d xiyj . Elle n’est bornée ni en volume, ni en genre de la courbe algébrique sous-jacente. Nous obtenons une expression pour la mesure de Mahler de Pd comme somme finie de valeurs spéciales du dilogarithme de Bloch-Wigner. Nous utilisons SageMath pour approximer m(Pd) pour 1 ≤ d ≤ 1000. En recourant à trois méthodes différentes, nous prouvons que la limite de la suite de mesures de Mahler de cette famille converge vers 92π2 ζ(3). De plus, nous calculons le développement asymptotique de la mesure de Mahler de Pd et prouvons que sa vitesse de convergence est de O(log dd2 ). Nous démontrons également une généralisation du théorème de Boyd-Lawton, affirmant que les mesures de Mahler multivariées peuvent être approximéess en utilisant les mesures de Mahler de dimension inférieure. Enfin, nous prouvons que la mesure de Mahler de Pd pour d arbitraire peut être écrite comme une combinaison linéaire de fonctions L associées à un caractère de Dirichlet primitif impair. Nous calculons finalement explicitement la représentation de la mesure de Mahler de Pd en termes de fonctions L, pour 1 ≤ d ≤ 6
In this thesis we investigate the sequence of Mahler measures of a family of bivariate regular exact polynomials, called Pd := P0≤i+j≤d xiyj , unbounded in both degree and the genus of the algebraic curve. We obtain a closed formula for the Mahler measure of Pd in termsof special values of the Bloch–Wigner dilogarithm. We approximate m(Pd), for 1 ≤ d ≤ 1000,with arbitrary precision using SageMath. Using 3 different methods we prove that the limitof the sequence of the Mahler measure of this family converges to 92π2 ζ(3). Moreover, we compute the asymptotic expansion of the Mahler measure of Pd which implies that the rate of the convergence is O(log dd2 ). We also prove a generalization of the theorem of the Boyd-Lawton which asserts that the multivariate Mahler measures can be approximated using the lower dimensional Mahler measures. Finally, we prove that the Mahler measure of Pd, for arbitrary d can be written as a linear combination of L-functions associated with an odd primitive Dirichlet character. In addition, we compute explicitly the representation of the Mahler measure of Pd in terms of L-functions, for 1 ≤ d ≤ 6

La thèse est portée essentiellement sur la stabilisation et la contrôlabilité de deux équations des ondes moyennant un seul contrôle agissant sur le bord du domaine. Dans le cas du contrôle dynamique, le contrôle est introduit dans le système par une équation différentielle agissant sur le bord. C'est en effet un système hybride. Le contrôle peut être aussi applique directement sur le bord d'une équation, c'est le cas du contrôle indirecte mais non borne. La nature du système ainsi coupledépend du couplage des équations, et ceci donne divers résultats par la stabilisation (exponentielle et polynomiale) et la contrôlabilité exacte (espace contrôlable). Des nouvelles inégalités d'énergie permettent de mettre en oeuvre la Méthode fréquentielle et la Méthode d'Unicité de Hilbert.

We describe a fast method for the evaluation of an arbitrary high-dimensional multivariate algebraic polynomial in Chebyshev form at the nodes of an arbitrary rank-1 Chebyshev lattice. Our main focus is on conditions on rank-1 Chebyshev lattices allowing for the exact reconstruction of such polynomials from samples along such lattices and we present an algorithm for constructing suitable rank-1 Chebyshev lattices based on a component-by-component approach. Moreover, we give a method for the fast, exact and stable reconstruction.

In this paper, we develop a scheme to recover a single erasure when using a Cartesian code,in the context of a distributed storage system. Particularly, we develop a scheme withconsiderations to minimize the associated bandwidth and maximize the associateddimension. The problem of recovering a missing node's data exactly in a distributedstorage system is known as theexact repair problem. Previous research has studied theexact repair problem for Reed-Solomon codes. We focus on Cartesian codes, and show wecan enact the recovery using a linear exact repair scheme framework, similar to the oneoutlined by Guruswami and Wooters in 2017.
Master of Science
Distributed storage systems are systems which store a single data file over multiple storage nodes. Each storage node has a certain storage efficiency, the "space" required to store the information on that node. The value of these systems, is their ability to safely store data for extended periods of time. We want to design distributed storage systems such that if one storage node fails, we can recover it from the data in the remaining nodes. Recovering a node from the data stored in the other nodes requires the nodes to communicate data with each other. Ideally, these systems are designed to minimize the bandwidth, the inter-nodal communication required to recover a lost node, as well as maximize the storage efficiency of each node. A great mathematical framework to build these distributed storage systems on is erasure codes. In this paper, we will specifically develop distributed storage systems that use Cartesian codes. We will show that in the right setting, these systems can have a very similar bandwidth to systems build from Reed-Solomon codes, without much loss in storage efficiency.

Dans cette thèse, nous nous intéressons à deux types de décompositions des graphes introduits par Robertson et Seymour: les décompositions arborescentes et les décompositions en branches. À ces décompositions sont associés deux paramètres des graphes: la largeur arborescente et la largeur de branches. Nous montrons que ces deux décompositions peuvent être vues comme issues d'une même structure combinatoire; les deux paramètres mentionné ci-dessus sont égaux aux valeurs minimales de deux paramètres de cette structure commune. En poussant plus avant cette analogie, nous montrons comment adapter une technique de calcul de la largeur arborescente au calcul de la largeur de branches. Ceci nous permet de calculer la largeur de branches des graphes de nombre astéroïde borné ayant un nombre polynômial de séparateurs minimaux et celle des graphes d-trapézoïdes circulaires. Ce parallèle nous permet aussi d'adapter certains résultats structurels sur les décompositions en branches aux décompositions arborescentes. Dans le cas des graphes planaires, nous interprétons ces propriétés à l'aide d'outils topologiques. De cette façon, nous donnons une démonstration simple d'un théorème de dualité reliant la largeur arborescente d'un graphe planaire et celle de son dual. Ces outils nous permettent aussi d'énumérer de façon efficace les séparateurs minimaux des graphes planaires.

Dans cette thèse, on s'intéresse à des problèmes de multiflot entier et de multicoupe, qui généralisent les problèmes classiques de flot maximum et de coupe minimum. Deux aspects de ces problèmes y sont étudiés en particulier : la résolution exacte en temps polynomial et l'approximation polynomiale. Du point de vue de la résolution exacte, nos principales contributions portent sur les sujets suivants : chemins disjoints dans les graphes de nombre cyclomatique borné ; multicoupes dans les graphes orientés sans circuits, dans les graphes non orientés de largeur d'arbre bornée et dans les graphes planaires ; multiflots entiers dans les anneaux ; multicoupes et multiflots entiers dans certains cas particuliers de grilles. Du point de vue de l'approximation polynomiale, nos principales contributions portent sur les sujets suivants : chemins disjoints dans les graphes planaires à k niveaux d'arêtes ; multiflots entiers dans les graphes de nombre cyclomatique borné ; multicoupes dans les graphes orientés non pondérés de largeur d'arbre et de degré maximum bornés ; flots multiterminaux entiers dans les graphes orientés. Nous décrivons également une nouvelle heuristique pour trouver un multiflot entier maximum dans un graphe non orienté, et la testons sur des instances générées aléatoirement
In this thesis, we consider integral multiflow and multicut problems, which generalize the classical max flow and min cut problems. Two aspects of these problems are studied in particular : polynomial-time resolution and polynomial approximation. Concerning the first aspect, our main contributions focus on the following points : disjoint paths in graphs of bounded cyclomatic number ; multicuts in directed acyclic graphs, in undirected graphs of bounded tree-width and in planar graphs ; integral multiflows in rings ; multicuts and integral multiflows in several special types of grids. Concerning the second aspect, our main contributions focus on the following points : disjoint paths in k-edge-outerplanar graphs ; integral multiflows in graphs of bounded cyclomatic number ; multicuts in unweighted digraphs of bounded maximum degree and bounded tree-width ; integral multiterminal flows in digraphs. We also describe a new heuristic to find a maximum integral multiflow in an undirected graph, and test it on randomly generated graphs

碩士
國立中山大學
應用數學系
87
In this paper, we characterize the conditions of weight function such that the exact $n$-point $D$-optimal design and the approximate $D$-optimal design for the weighted polynomial regression model $f(x)=(1,x,\ldots,x^d)$ on $[a,b]$ share the same support points. For $d=1$ and $n\geq 2$, a design which is supported at two endpoints as equally as possible is exact $n$-point $D$-optimal if and only if $\w(a)=r\w(b)>0$ and $\w(x)/\w(a)\le (b-a)^2/(r(x-a)^2+ (x-b)^2)$ for all $x\in [a,b]$. Moreover, based on Gaffke's condition (1987) we also derive a sufficient condition of weight function such that the designs which are supported at the approximate $D$-optimal support points as equally as possible are exact $D$-optimal designs for $d\ge 2$. The numerical result indicates that Gaffke's condition is very conservative for $d=1$ and is very sharp for $d\ge 2$.

碩士
國立中山大學
應用數學系研究所
88
Consider the multiresponse polynomial regression model with one control variable and arbitrary covariance matrix among responses. The present results complement solutions by Krafft and Schaefer (1992) and Imhof (2000), who obtained the n-point D-optimal designs for the multiresponse regression model with one linear and one quadratic. We will show that the D-optimal design is invariant under linear transformation of the control variable. Moreover, the most cases of the exact D-optimal designs on [-1,1] for responses consisting of linear and quadratic polynomials only are derived. The efficiency of the exact D-optimal designs for the univariate quadratic model to that for the above model are also discussed. Some conjectures based on intensively numerical results are also included.

碩士
國立中山大學
應用數學系研究所
88
The D-optimal design problems in polynomial regression models with a one-dimensional control variable and k-dimensional response variable Y=(Y_1,...,Y_k) where there are some common unknown parameters are discussed. The approximate D-optimal designs are shown to be independent of the covariance structure between the k responses when the degrees of the k responses are of the same order. Then, the exact n-point D-optimal designs are also discussed. Krafft and Schaefer (1992) and Imhof (2000) are useful in obtaining our results. We extend the proof of symmetric cases for k>= 2.

A dissertation submitted in fulfillment of the requirements for the degree of Master of Science. August 2016.
The six scalar fields in N = 4 super Yang-Mills theory enjoy a global SO(6) symmetry, and large N but non-planar limits of this theory are well-described by adopting a group representation approach. Studies have shown that the one-loop dilatation operator is highly determined by the action of the su(2)=su(3) subalgebras on restricted Schur polynomials. These actions involve the traces of products of projection operators. In this dissertation, exact analytical formulae for these traces are found which in turn are used to find the exact action of these algebras on restricted Schur polynomials. The potential of the su(2) algebra to determine the one-loop dilatation operator is also explored. This is done by exploiting necessary symmetry conditions and moving to a continuum limit in order to derive a number of partial differential equations which determine the dilatation operator. The ultimate goal of this work is to provide tools to find the exact one-loop dilatation operator in the non-planar limit.
LG2017

Indiana University-Purdue University Indianapolis (IUPUI)
In this dissertation the partition function, $Z_n$, for the six-vertex model with domain wall boundary conditions is solved in the thermodynamic limit in various regions of the phase diagram. In the ferroelectric phase region, we show that $Z_n=CG^nF^{n^2}(1+O(e^{-n^{1-\ep}}))$ for any $\ep>0$, and we give explicit formulae for the numbers $C, G$, and $F$. On the critical line separating the ferroelectric and disordered phase regions, we show that $Z_n=Cn^{1/4}G^{\sqrt{n}}F^{n^2}(1+O(n^{-1/2}))$, and we give explicit formulae for the numbers $G$ and $F$. In this phase region, the value of the constant $C$ is unknown. In the antiferroelectric phase region, we show that $Z_n=C\th_4(n\om)F^{n^2}(1+O(n^{-1}))$, where $\th_4$ is Jacobi's theta function, and explicit formulae are given for the numbers $\om$ and $F$. The value of the constant $C$ is unknown in this phase region. In each case, the proof is based on reformulating $Z_n$ as the eigenvalue partition function for a random matrix ensemble (as observed by Paul Zinn-Justin), and evaluation of large $n$ asymptotics for a corresponding system of orthogonal polynomials. To deal with this problem in the antiferroelectric phase region, we consequently develop an asymptotic analysis, based on a Riemann-Hilbert approach, for orthogonal polynomials on an infinite regular lattice with respect to varying exponential weights. The general method and results of this analysis are given in Chapter 5 of this dissertation.