This dissertation was to study computational theory and methods for ?nding multiple saddle critical points in Banach spaces. Two local minimax methods were developed for this purpose. One was for unconstrained cases and the other was for constrained cases. First, two local minmax characterization of saddle critical points in Banach spaces were established. Based on these two local minmax characterizations, two local minimax algorithms were designed. Their ?ow charts were presented. Then convergence analysis of the algorithms were carried out. Under certain assumptions, a subsequence convergence and a point-to-set convergence were obtained. Furthermore, a relation between the convergence rates of the functional value sequence and corresponding gradient sequence was derived. Techniques to implement the algorithms were discussed. In numerical experiments, those techniques have been successfully implemented to solve for multiple solutions of several quasilinear elliptic boundary value problems and multiple eigenpairs of the well known nonlinear p-Laplacian operator. Numerical solutions were presented by their pro?les for visualization. Several interesting phenomena of the solutions of quasilinear elliptic boundary value problems and the eigenpairs of the p-Laplacian operator have been observed and are open for further investigation. As a generalization of the above results, nonsmooth critical points were considered for locally Lipschitz continuous functionals. A local minmax characterization of nonsmooth saddle critical points was also established. To establish its version in Banach spaces, a new notion, pseudo-generalized-gradient has to be introduced. Based on the characterization, a local minimax algorithm for ?nding multiple nonsmooth saddle critical points was proposed for further study.

The presented work deals with two distinct problems in the field of Mathematical Physics. The first part is dedicated to an 'almost' solution of Villani's conjecture, a known conjecture related to a Statistical Mechanics model invented by Kac in 1956, giving a rigorous explanation of some simple cases of the Boltzmann equation. In 2003 Villani conjectured that the time it will take the system of particles in Kac's model to equilibrate is proportional to the number of particles in the system. Our main result in this part is a proof, up to an epsilon, of that conjecture, showing that for all practical purposes we can consider it to be true. The second part of the presentation is based on a joint work with Prof. Michael Loss and is dedicated to a newly developed trace inequality for the fractional Laplacian, connecting between the fractional Laplacian of a function and its restriction to intersection of hyperplanes. The newly found inequality is sharp and the functions that attain equality in it are completely classified.

We give a strongly polynomial time combinatorial algorithm to minimise the largest eigenvalue of the weighted Laplacian of a bipartite graph. This is accomplished by solving the dual graph embedding problem which arises from a semidefinite programming formulation. In particular, the problem for trees can be solved in time cubic in the number of vertices.

Let G be a connected graph with n vertices and let x=(x1, ..., xn) be a real vector. A positive (negative) sign graph of the vector x is a maximal connected subgraph of G on vertices xi>0 (xi<0). For an eigenvalue of a generalized Laplacian of a tree: We characterize the maximal number of sign graphs of an eigenvector. We give an O(n2) time algorithm to find an eigenvector with maximum number of sign graphs and we show that finding an eigenvector with minimum number of sign graphs is an NP-complete problem. (author's abstract) / Series: Preprint Series / Department of Applied Statistics and Data Processing

No description available.

This thesis addresses statistical estimation and testing of signals over a graph when measurements are noisy and high-dimensional. Graph structured patterns appear in applications as diverse as sensor networks, virology in human networks, congestion in internet routers, and advertising in social networks. We will develop asymptotic guarantees of the performance of statistical estimators and tests, by stating conditions for consistency by properties of the graph (e.g. graph spectra). The goal of this thesis is to demonstrate theoretically that by exploiting the graph structure one can achieve statistical consistency in extremely noisy conditions. We begin with the study of a projection estimator called Laplacian eigenmaps, and find that eigenvalue concentration plays a central role in the ability to estimate graph structured patterns. We continue with the study of the edge lasso, a least squares procedure with total variation penalty, and determine combinatorial conditions under which changepoints (edges across which the underlying signal changes) on the graph are recovered. We will shift focus to testing for anomalous activations in the graph, using the scan statistic relaxations, the spectral scan statistic and the graph ellipsoid scan statistic. We will also show how one can form a decomposition of the graph from a spanning tree which will lead to a test for activity in the graph. This will lead to the construction of a spanning tree wavelet basis, which can be used to localize activations on the graph.

Ένα σημαντικό πρόβλημα είναι η αντιστοίχιση εικόνων με σκοπό τη δημιουργία πανοράματος. Στην παρούσα εργασία έχουν χρησιμοποιηθεί αλγόριθμοι που βασίζονται στη χρήση σημείων κλειδιών. Αρχικά στην εργασία βρίσκονται σημεία κλειδιά για κάθε εικόνα που μένουν ανεπηρέαστα από τις αναμενόμενες παραμορφώσεις με την βοήθεια του αλγορίθμου SIFT (Scale Invariant Feature Transform). Έχοντας τελειώσει αυτή τη διαδικασία για όλες τις εικόνες, προσπαθούμε να βρούμε το πρώτο ζευγάρι εικόνων που θα ενωθεί. Για να δούμε αν δύο εικόνες μπορούν να ενωθούν, ακολουθεί ταίριασμα των σημείων κλειδιών τους. Όταν ένα αρχικό σετ αντίστοιχων χαρακτηριστικών έχει υπολογιστεί, πρέπει να βρεθεί ένα σετ που θα παράγει υψηλής ακρίβειας αντιστοίχιση. Αυτό το πετυχαίνουμε με τον αλγόριθμο RANSAC, μέσω του οποίου βρίσκουμε το γεωμετρικό μετασχηματισμό ανάμεσα στις δύο εικόνες, ομογραφία στην περίπτωσή μας. Αν ο αριθμός των κοινών σημείων κλειδιών είναι επαρκής, δηλαδή ταιριάζουν οι εικόνες, ακολουθεί η ένωσή τους. Αν απλώς ενώσουμε τις εικόνες, τότε θα έχουμε σίγουρα κάποια προβλήματα, όπως το ότι οι ενώσεις των δύο εικόνων θα είναι πολύ εμφανείς. Γι’ αυτό, για την εξάλειψη αυτού του προβλήματος, χρησιμοποιούμε τη μέθοδο των Λαπλασιανών πυραμίδων. Επαναλαμβάνεται η παραπάνω διαδικασία μέχρι να δημιουργηθεί το τελικό πανόραμα παίρνοντας κάθε φορά σαν αρχική την τελευταία εικόνα που φτιάξαμε στην προηγούμενη φάση. / Stitching multiple images together to create high resolution panoramas is one of the most popular consumer applications of image registration and blending. At this work, feature-based registration algorithms have been used. The first step is to extract distinctive invariant features from every image which are invariant to image scale and rotation, using SIFT (Scale Invariant Feature Transform) algorithm. After that, we try to find the first pair of images in order to stitch them. To check if two images can be stitched, we match their keypoints (the results from SIFT). Once an initial set of feature correspondences has been computed, we need to find the set that is will produce a high-accuracy alignment. The solution at this problem is RANdom Sample Consensus (RANSAC). Using this algorithm (RANSAC) we find the motion model between the two images (homography). If there is enough number of correspond points, we stitch these images. After that, seams are visible. As solution to this problem is used the method of Laplacian Pyramids. We repeat the above procedure using as initial image the ex panorama which has been created.

Le problème de l'optimisation des valeurs propres du Laplacien est ancien puisqu'à la fin du XIXème siècle Lord Rayleigh conjecturait que la première valeur propre avec condition de Dirichlet était minimisée par le disque. Depuis le problème a été beaucoup étudié. Et les possibilités de recherches sont multiples : diverses conditions, ajout de contraintes, existence, description des optima ... Dans ce document on se limite aux conditions de Dirichlet et de Neumann, dans R^2 et dans R^3. On procède dans un premier temps à un état de l'art. On se focalise ensuite sur les disques et les boules. En effet, ils font partie des rares formes pour lesquelles il est possible de calculer explicitement et relativement facilement les valeurs propres. On verra malheureusement que ces formes ne sont la plupart du temps pas des minimiseurs. Enfin on s'intéresse aux simulations numériques possibles. En effet, puisque peu de calculs théoriques peuvent être faits il est intéressant d'obtenir numériquement des candidats. Cela permet ensuite d'avoir des hypothèses de travail théorique. `{A} cet effet nous donnerons des éléments de compréhension sur une méthode de simulation numérique ainsi que des résultats obtenus. / The optimization of Laplacian eigenvalues is a classical problem. In fact, at the end of the nineteenth century, Lord Rayleigh conjectured that the first eigenvalue with Dirichlet boundary condition is minimized by a disk. This problem received a lot of attention since this first study and research possibilities are numerous: various conditions, geometrical constraints added, existence, description of optimal shapes... In this document we restrict us to Dirichlet and Neumann boundary conditions in R^2 and R^3. We begin with a state of the art. Then we focus our study on disks and balls. Indeed, these are some of the only shapes for which it is possible to explicitly and relatively easily compute the eigenvalues. But we show in one of the main result of this document that they are not minimizers for most eigenvalues. Finally we take an interest in the possible numerical experiments. Since we can do very few theoretical computations, it is interesting to get numerical candidates. Then we can deduce some theoretical working assumptions. With this in mind we give some keys to understand our numerical method and we also give some results obtained.

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-08-08T20:06:07Z No. of bitstreams: 1 JOSÉ DE BRITO SILVA - DISSERTAÇÃO PPGMAT 2013..pdf: 535262 bytes, checksum: eb7f0d4f7e69b8a4b86d3e1dc0f16739 (MD5) / Made available in DSpace on 2018-08-08T20:06:07Z (GMT). No. of bitstreams: 1 JOSÉ DE BRITO SILVA - DISSERTAÇÃO PPGMAT 2013..pdf: 535262 bytes, checksum: eb7f0d4f7e69b8a4b86d3e1dc0f16739 (MD5) Previous issue date: 2013-10 / Capes / Neste trabalho discutiremos a existência de soluções fracas positivas para um sistema do (p, q)-Laplaciano com mudança de sinal nas funções de peso, com domínio limitado e fronteira suave. Para garantir a existência de soluções fracas positivas primeiramente asseguraremos a solução positiva de um problema calásico que é o problema de autovalor do p-laplaciano, e do problema "linear"do p-laplaciano com condição zero de Dirichlet. Feito isto usaremos a existência destas soluções para assegurar que o problema em questão admite solução fraca positiva, via o método das sub-super-soluções / In this work we discuss the existence of weak positive solutions for a system (p, q)- Laplacian with change of sign in the weight functions with bounded domain and smooth boundary. To ensure the existence of weak positive solutions first will ensure a positive solution to a classic problem that is the problem eigenvalue p-Laplacian value, and the "linear"problem with zero condition p-Laplacian Dirichelt. Having done this we use the existence of these solutions to ensure that the problem in question admits a weak positive solution via the method of sub-super-solutions.

We demonstrate the Splitting Theorem due to Cheeger and Gromoll, which ensures that a complete Riemannian n-manifold which has nonnegative Ricci curvature and a line, can be split isometrically into the Riemannian product of real with a (n-1 )- manifold. / Conselho Nacional de Desenvolvimento Científico e Tecnológico / Demonstramos o Teorema de Decomposição de Cheeger-Gromoll, o qual garante que uma variedade Riemanniana completa ndimensional, com curvatura de Ricci não-negativa, que possui uma linha, pode ser decomposta isometricamente num produto Riemanniano de uma variedade (n-1 )-dimensional com o conjunto dos reais.