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.

Efficient Output-Sensitive Construction of Reeb Graphs

The Reeb graph tracks topology changes in level sets of a scalar function and finds applications in scientific visualization and geometric modeling. This paper describes a near-optimal two-step algorithm that constructs the Reeb graph of a Morse function defined over manifolds in any dimension. The algorithm first identifies the critical points of the input manifold, and then connects these critical points in the second step to obtain the Reeb graph. A simplification mechanism based on topological persistence aids in the removal of noise and unimportant features. A radial layout scheme results in a feature-directed drawing of the Reeb graph. Experimental results demonstrate the efficiency of the Reeb graph construction in practice and its applications.

Efficient algorithms for computing Reeb graphs

The Reeb graph tracks topology changes in level sets of a scalar function and finds applications in scientific visualization and geometric modeling. We describe an algorithm that constructs the Reeb graph of a Morse function defined on a 3-manifold. Our algorithm maintains connected components of the two dimensional levels sets as a dynamic graph and constructs the Reeb graph in O(nlogn+nlogg(loglogg)3) time, where n is the number of triangles in the tetrahedral mesh representing the 3-manifold and g is the maximum genus over all level sets of the function. We extend this algorithm to construct Reeb graphs of d-manifolds in O(nlogn(loglogn)3) time, where n is the number of triangles in the simplicial complex that represents the d-manifold. Our result is a significant improvement over the previously known O(n2) algorithm. Finally, we present experimental results of our implementation and demonstrate that our algorithm for 3-manifolds performs efficiently in practice.

Comments on a decentralized control of linear multivariable systems

A strongly connected decentralized control system may be made single channel controllable and observable with respect to any channel by decentralized feedbacks. It is noted here that the system example considered by Corfmat and Morse to illustrate this fact is already single channel controllable and observable, with respect to one of the channels. An alternate example which fits into the situation is presented in this item.

Wave analysis of sound decay in rectangular rooms

The decay of sound in a rectangular room is analyzed for various boundary conditions on one of its walls. It is shown that the decay of the sound-intensity level is in general nonlinear. But for specific areas and impedances of the material it is possible to obtain a linear initial decay. It is also shown that the coefficients derived from the initial decay rates neither correspond to the predictions of Sabine's or Eyring's geometrical theories nor to the normal coefficients of Morse's wave theory. The dependence of the coefficients on the area of the material is discussed. The influence of the real and the imaginary parts of the specific acoustic impedance of the material on the coefficients is also discussed. Finally, the existence of a linear initial decay corresponding to the decay of a diffuse field in the case of a highly absorbing material partially covering a wall is explained on the basis of modal coupling.

Wave analysis of sound decay in rectangular rooms

The decay of sound in a rectangular room is analyzed for various boundary conditions on one of its walls. It is shown that the decay of the sound-intensity level is in general nonlinear. But for specific areas and impedances of the material it is possible to obtain a linear initial decay. It is also shown that the coefficients derived from the initial decay rates neither correspond to the predictions of Sabine's or Eyring's geometrical theories nor to the normal coefficients of Morse's wave theory. The dependence of the coefficients on the area of the material is discussed. The influence of the real and the imaginary parts of the specific acoustic impedance of the material on the coefficients is also discussed. Finally, the existence of a linear initial decay corresponding to the decay of a diffuse field in the case of a highly absorbing material partially covering a wall is explained on the basis of modal coupling.

Study of thermal fluctuations during thermal denaturation of DNA

In this paper we address the fundamental issue of temperature fluctuation during the thermal denaturation (or the unzipping of the two strands on heating) of double stranded (ds) DNA. From our experiments we observe the presence of extremely high thermal fluctuations during DNA denaturation. This thermal fluctuation is several orders higher than the thermal fluctuation at temperatures away from the denaturation temperature range. This fluctuation is absent in single stranded (ss) DNA. The magnitude of fluctuation is much higher in heteropolymeric DNA and is almost absent in short homopolymeric DNA fragments. The temperature range over which the denaturation occurs (i.e., over which the thermal fluctuation is large) depends on the length of the DNA and is largest for the longest DNA.

Theory of polymer breaking under tension

We consider the breaking of a polymer molecule which is fixed at one end and is acted upon by a force at the other. The polymer is assumed to be a linear chain joined together by bonds which satisfy the Morse potential. The applied force is found to modify the Morse potential so that the minimum becomes metastable. Breaking is just the decay of this metastable bond, by causing it to go over the barrier. Increasing the force causes the potential to become more and more distorted and eventually leads to the disappearance of the barrier. The limiting force at which the barrier disappears is D(e)a/2,D-e with a the parameters characterizing the Morse potential. The rate of breaking is first calculated using multidimensional quantum transition state theory. We use the harmonic approximation to account for vibrations of all the units. It includes tunneling contributions to the rate, but is valid only above a certain critical temperature. It is possible to get an analytical expression for the rate of breaking. We have calculated the rate of breaking for a model, which mimics polyethylene. First we calculate the rate of breaking of a single bond, without worrying about the other bonds. Inclusion of other bonds under the harmonic approximation is found to lower this rate by at the most one order of magnitude. Quantum effects are found to increase the rate of breaking and are significant only at temperatures less than 150 K. At 300 K, the calculations predict a bond in polyethylene to have a lifetime of only seconds at a force which is only half the limiting force. Calculations were also done using the Lennard-Jones potential. The results for Lennard-Jones and Morse potentials were rather different, due to the different long-range behaviors of the two potentials. A calculation including friction was carried out, at the classical level, by assuming that each atom of the chain is coupled to its own collection of harmonic oscillators. Comparison of the results with the simulations of Oliveira and Taylor [J. Chem. Phys. 101, 10 118 (1994)] showed the rate to be two to three orders of magnitude higher. As a possible explanation of discrepancy, we consider the translational motion of the ends of the broken chains. Using a continuum approximation for the chain, we find that in the absence of friction, the rate of the process can be limited by the rate at which the two broken ends separate from one another and the lowering of the rate is at the most a factor of 2, for the parameters used in the simulation (for polyethylene). In the presence of friction, we find that the rate can be lowered by one to two orders of magnitude, making our results to be in reasonable agreement with the simulations.

Decentralized control of linear multivariable systems

A strongly connected decentralized control system may be made single channel controllable and observable with respect to any channel by decentralized feedbacks. It is noted here that the system example considered by Corfmat and Morse to illustrate this fact is already single channel controllable and observable, with respect to one of the channels. An alternate example which fits into the situation is presented in this item.

Minimal triangulation, complementarity and projective planes

Brehm and Kuhnel proved that if M-d is a combinatorial d-manifold with 3d/2 + 3 vertices and \ M-d \ is not homeomorphic to Sd then the combinatorial Morse number of M-d is three and hence d is an element of {0, 2, 4, 8, 16} and \ M-d \ is a manifold like a projective plane in the sense of Eells and Kuiper. We discuss the existence and uniqueness of such combinatorial manifolds. We also present the following result: ''Let M-n(d) be a combinatorial d-manifold with n vertices. M-n(d) satisfies complementarity if and only if d is an element of {0, 2, 4, 8, 16} with n = 3d/2 + 3 and \ M-n(d) \ is a manifold like a projective plane''.

Performance metrics in a hybrid MPI-OpenMP based molecular dynamics simulation with short-range interactions

We discuss the computational bottlenecks in molecular dynamics (MD) and describe the challenges in parallelizing the computation-intensive tasks. We present a hybrid algorithm using MPI (Message Passing Interface) with OpenMP threads for parallelizing a generalized MD computation scheme for systems with short range interatomic interactions. The algorithm is discussed in the context of nano-indentation of Chromium films with carbon indenters using the Embedded Atom Method potential for Cr-Cr interaction and the Morse potential for Cr-C interactions. We study the performance of our algorithm for a range of MPI-thread combinations and find the performance to depend strongly on the computational task and load sharing in the multi-core processor. The algorithm scaled poorly with MPI and our hybrid schemes were observed to outperform the pure message passing scheme, despite utilizing the same number of processors or cores in the cluster. Speed-up achieved by our algorithm compared favorably with that achieved by standard MD packages. (C) 2013 Elsevier Inc. All rights reserved.

Estimation of mechanical properties of single wall carbon nanotubes using molecular mechanics approach

Molecular mechanics based finite element analysis is adopted in the current work to evaluate the mechanical properties of Zigzag, Armchair and Chiral Single wall Carbon Nanotubes (SWCNT) of different diameters and chiralities. Three different types of atomic bonds, that is Carbon Carbon covalent bond and two types of Carbon Carbon van der Waals bonds are considered in the carbon nanotube system. The stiffness values of these bonds are calculated using the molecular potentials, namely Morse potential function and Lennard-Jones interaction potential function respectively and these stiffness's are assigned to spring elements in the finite element model of the CNT. The geometry of CNT is built using a macro that is developed for the finite element analysis software. The finite element model of the CNT is constructed, appropriate boundary conditions are applied and the behavior of mechanical properties of CNT is studied.

MS3ALIGN: an efficient molecular surface aligner using the topology of surface curvature

Background: Aligning similar molecular structures is an important step in the process of bio-molecular structure and function analysis. Molecular surfaces are simple representations of molecular structure that are easily constructed from various forms of molecular data such as 3D atomic coordinates (PDB) and Electron Microscopy (EM) data. Methods: We present a Multi-Scale Morse-Smale Molecular-Surface Alignment tool, MS3ALIGN, which aligns molecular surfaces based on significant protrusions on the molecular surface. The input is a pair of molecular surfaces represented as triangle meshes. A key advantage of MS3ALIGN is computational efficiency that is achieved because it processes only a few carefully chosen protrusions on the molecular surface. Furthermore, the alignments are partial in nature and therefore allows for inexact surfaces to be aligned. Results: The method is evaluated in four settings. First, we establish performance using known alignments with varying overlap and noise values. Second, we compare the method with SurfComp, an existing surface alignment method. We show that we are able to determine alignments reported by SurfComp, as well as report relevant alignments not found by SurfComp. Third, we validate the ability of MS3ALIGN to determine alignments in the case of structurally dissimilar binding sites. Fourth, we demonstrate the ability of MS3ALIGN to align iso-surfaces derived from cryo-electron microscopy scans. Conclusions: We have presented an algorithm that aligns Molecular Surfaces based on the topology of surface curvature. Awebserver and standalone software implementation of the algorithm available at http://vgl.serc.iisc.ernet. in/ms3align.