Parallel Computation of 2D Morse-Smale Complexes

The Morse-Smale complex is a useful topological data structure for the analysis and visualization of scalar data. This paper describes an algorithm that processes all mesh elements of the domain in parallel to compute the Morse-Smale complex of large two-dimensional data sets at interactive speeds. We employ a reformulation of the Morse-Smale complex using Forman's Discrete Morse Theory and achieve scalability by computing the discrete gradient using local accesses only. We also introduce a novel approach to merge gradient paths that ensures accurate geometry of the computed complex. We demonstrate that our algorithm performs well on both multicore environments and on massively parallel architectures such as the GPU.

Parallel Computation of 3D Morse-Smale Complexes

The Morse-Smale complex is a topological structure that captures the behavior of the gradient of a scalar function on a manifold. This paper discusses scalable techniques to compute the Morse-Smale complex of scalar functions defined on large three-dimensional structured grids. Computing the Morse-Smale complex of three-dimensional domains is challenging as compared to two-dimensional domains because of the non-trivial structure introduced by the two types of saddle criticalities. We present a parallel shared-memory algorithm to compute the Morse-Smale complex based on Forman's discrete Morse theory. The algorithm achieves scalability via synergistic use of the CPU and the GPU. We first prove that the discrete gradient on the domain can be computed independently for each cell and hence can be implemented on the GPU. Second, we describe a two-step graph traversal algorithm to compute the 1-saddle-2-saddle connections efficiently and in parallel on the CPU. Simultaneously, the extremasaddle connections are computed using a tree traversal algorithm on the GPU.

A mathematical theory of stochastic microlensing. II. Random images, shear, and the Kac-Rice formula

Continuing our development of a mathematical theory of stochastic microlensing, we study the random shear and expected number of random lensed images of different types. In particular, we characterize the first three leading terms in the asymptotic expression of the joint probability density function (pdf) of the random shear tensor due to point masses in the limit of an infinite number of stars. Up to this order, the pdf depends on the magnitude of the shear tensor, the optical depth, and the mean number of stars through a combination of radial position and the star's mass. As a consequence, the pdf's of the shear components are seen to converge, in the limit of an infinite number of stars, to shifted Cauchy distributions, which shows that the shear components have heavy tails in that limit. The asymptotic pdf of the shear magnitude in the limit of an infinite number of stars is also presented. All the results on the random microlensing shear are given for a general point in the lens plane. Extending to the general random distributions (not necessarily uniform) of the lenses, we employ the Kac-Rice formula and Morse theory to deduce general formulas for the expected total number of images and the expected number of saddle images. We further generalize these results by considering random sources defined on a countable compact covering of the light source plane. This is done to introduce the notion of global expected number of positive parity images due to a general lensing map. Applying the result to microlensing, we calculate the asymptotic global expected number of minimum images in the limit of an infinite number of stars, where the stars are uniformly distributed. This global expectation is bounded, while the global expected number of images and the global expected number of saddle images diverge as the order of the number of stars. © 2009 American Institute of Physics.

Homologie de morse et théorème de la signature

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Complexe de Morse et bifurcations

Soit une famille de couples (ft,Xt)t∈J , où J est un intervalle, ft est une fonction lisse à valeurs réelles définie sur une variété lisse et compacte V , et Xt est un pseudo-gradient associé à la fonction ft. L’objet de ce mémoire est l’étude des bifurcations subies par les complexes de Morse associés à ces couples. Deux approches sont utilisées : l’étude directe des bifurcations et l’approche par homotopie. On montre que finalement ces deux approches permettent d’obtenir les mêmes résultats d’un point de vue fonctoriel.

Exact and numerical solutions for diffusio-reaction equations with convection term

Esta dissertação estuda essencialmente dois problemas: (A) uma classe de equações unidimensionais de reacção-difusão-convecção em meios não uniformes (dependentes do espaço), e (B) um problema elíptico não-linear e paramétrico ligado a fenómenos de capilaridade. A Análise de Perturbação Singular e a dinâmica de Hamilton-Jacobi são utilizadas na obtenção de expressões assimptóticas para a solução (com comportamento de frente) e para a sua velocidade de propagação. Os seguintes três métodos de decomposição, Adomian Decomposition Method (ADM), Decomposition Method based on Infinite Products (DIP), e New Iterative Method (NIM), são apresentados e brevemente comparados. Adicionalmente, condições suficientes para a convergência da solução em série, obtida pelo ADM, e uma aplicação a um problema da Telecomunicações por Fibras Ópticas, envolvendo EDOs não-lineares designadas equações de Raman, são discutidas. Um ponto de vista mais abrangente que unifica os métodos de decomposição referidos é também apresentado. Para subclasses desta EDP são obtidas soluções numa forma explícita, para diferentes tipos de dados e usando uma variante do método de simetrias de Bluman-Cole. Usando Teoria de Pontos Críticos (o teorema usualmente designado mountain pass) e técnicas de truncatura, prova-se a existência de duas soluções não triviais (uma positiva e uma negativa) para o problema elíptico não-linear e paramétrico (B). A existência de uma terceira solução não trivial é demonstrada usando Grupos Críticos e Teoria de Morse.

Topological triangle characterization with application to object detection from images

A novel mathematical framework inspired on Morse Theory for topological triangle characterization in 2D meshes is introduced that is useful for applications involving the creation of mesh models of objects whose geometry is not known a priori. The framework guarantees a precise control of topological changes introduced as a result of triangle insertion/removal operations and enables the definition of intuitive high-level operators for managing the mesh while keeping its topological integrity. An application is described in the implementation of an innovative approach for the detection of 2D objects from images that integrates the topological control enabled by geometric modeling with traditional image processing techniques. (C) 2008 Published by Elsevier B.V.

On a Gromoll-Meyer type theorem in globally hyperbolic stationary spacetimes

Following the lines of the celebrated Riemannian result of Gromoll and Meyer, we use infinite dimensional equivariant Morse theory to establish the existence of infinitely many geometrically distinct closed geodesics in a class of globally hyperbolic stationary Lorentzian manifolds.

Sobre o teorema de fibração de Milnor

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Topology Verification for Isosurface Extraction

The broad goals of verifiable visualization rely on correct algorithmic implementations. We extend a framework for verification of isosurfacing implementations to check topological properties. Specifically, we use stratified Morse theory and digital topology to design algorithms which verify topological invariants. Our extended framework reveals unexpected behavior and coding mistakes in popular publicly available isosurface codes.

Topological analysis of singularity loci for serial and parallel manipulators

Singularities of robot manipulators have been intensely studied in the last decades by researchers of many fields. Serial singularities produce some local loss of dexterity of the manipulator, therefore it might be desirable to search for singularityfree trajectories in the jointspace. On the other hand, parallel singularities are very dangerous for parallel manipulators, for they may provoke the local loss of platform control, and jeopardize the structural integrity of links or actuators. It is therefore utterly important to avoid parallel singularities, while operating a parallel machine. Furthermore, there might be some configurations of a parallel manipulators that are allowed by the constraints, but nevertheless are unreachable by any feasible path. The present work proposes a numerical procedure based upon Morse theory, an important branch of differential topology. Such procedure counts and identify the singularity-free regions that are cut by the singularity locus out of the configuration space, and the disjoint regions composing the configuration space of a parallel manipulator. Moreover, given any two configurations of a manipulator, a feasible or a singularity-free path connecting them can always be found, or it can be proved that none exists. Examples of applications to 3R and 6R serial manipulators, to 3UPS and 3UPU parallel wrists, to 3UPU parallel translational manipulators, and to 3RRR planar manipulators are reported in the work.

Free Resolutions from Involutive Bases

We show that the theory of involutive bases can be combined with discrete algebraic Morse Theory. For a graded k[x0 ...,xn]-module M, this yields a free resolution G, which in general is not minimal. We see that G is isomorphic to the resolution induced by an involutive basis. It is possible to identify involutive bases inside the resolution G. The shape of G is given by a concrete description. Regarding the differential dG, several rules are established for its computation, which are based on the fact that in the computation of dG certain patterns appear at several positions. In particular, it is possible to compute the constants independent of the remainder of the differential. This allows us, starting from G, to determine the Betti numbers of M without computing a minimal free resolution: Thus we obtain a new algorithm to compute Betti numbers. This algorithm has been implemented in CoCoALib by Mario Albert. This way, in comparison to some other computer algebra system, Betti numbers can be computed faster in most of the examples we have considered. For Veronese subrings S(d), we have found a Pommaret basis, which yields new proofs for some known properties of these rings. Via the theoretical statements found for G, we can identify some generators of modules in G where no constants appear. As a direct consequence, some non-vanishing Betti numbers of S(d) can be given. Finally, we give a proof of the Hyperplane Restriction Theorem with the help of Pommaret bases. This part is largely independent of the other parts of this work.

On (p, q) − equations with concave terms

We consider a (p, q)− equation (1 < q < p, p ≥ 2) with a parametric concave term and a (p − 1)− linear perturbation. We show that the problem have five nontrivial smooth solutions: four of constant sign and the fifth nodal. When q = 2 (i.e., (p, 2) equation) we show that the problem has six nontrivial smooth solutions, but we do not specify the sign of the sixth solution. Our approach uses variational methods, together with truncation and comparison techniques and Morse theory.

On the critical point structure of eigenfunctions belonging to the first nonzero eigenvalue of a genus two closed hyperbolic surface

We develop a method based on spectral graph theory to approximate the eigenvalues and eigenfunctions of the Laplace-Beltrami operator of a compact riemannian manifold -- The method is applied to a closed hyperbolic surface of genus two -- The results obtained agree with the ones obtained by other authors by different methods, and they serve as experimental evidence supporting the conjectured fact that the generic eigenfunctions belonging to the first nonzero eigenvalue of a closed hyperbolic surface of arbitrary genus are Morse functions having the least possible total number of critical points among all Morse functions admitted by such manifolds