Computing Reeb Graphs as a Union of Contour Trees

The Reeb graph of a scalar function tracks the evolution of the topology of its level sets. This paper describes a fast algorithm to compute the Reeb graph of a piecewise-linear (PL) function defined over manifolds and non-manifolds. The key idea in the proposed approach is to maximally leverage the efficient contour tree algorithm to compute the Reeb graph. The algorithm proceeds by dividing the input into a set of subvolumes that have loop-free Reeb graphs using the join tree of the scalar function and computes the Reeb graph by combining the contour trees of all the subvolumes. Since the key ingredient of this method is a series of union-find operations, the algorithm is fast in practice. Experimental results demonstrate that it outperforms current generic algorithms by a factor of up to two orders of magnitude, and has a performance on par with algorithms that are catered to restricted classes of input. The algorithm also extends to handle large data that do not fit in memory.

A study of vertical cloud structure of the Indian summer monsoon using CloudSat data

Precise specification of the vertical distribution of cloud optical properties is important to reduce the uncertainty in quantifying the radiative impacts of clouds. The new global observations of vertical profiles of clouds from the CloudSat mission provide opportunities to describe cloud structures and to improve parameterization of clouds in the weather and climate prediction models. In this study, four years (2007-2010) of observations of vertical structure of clouds from the CloudSat cloud profiling radar have been used to document the mean vertical structure of clouds associated with the Indian summer monsoon (ISM) and its intra-seasonal variability. Active and break monsoon spells associated with the intra-seasonal variability of ISM have been identified by an objective criterion. For the present analysis, we considered CloudSat derived column integrated cloud liquid and ice water, and vertically profiles of cloud liquid and ice water content. Over the South Asian monsoon region, deep convective clouds with large vertical extent (up to 14 km) and large values of cloud water and ice content are observed over the north Bay of Bengal. Deep clouds with large ice water content are also observed over north Arabian Sea and adjoining northwest India, along the west coast of India and the south equatorial Indian Ocean. The active monsoon spells are characterized by enhanced deep convection over the Bay of Bengal, west coast of India and northeast Arabian Sea and suppressed convection over the equatorial Indian Ocean. Over the Bay of Bengal, cloud liquid water content and ice water content is enhanced by similar to 90 and similar to 200 % respectively during the active spells. An interesting feature associated with the active spell is the vertical tilting structure of positive CLWC and CIWC anomalies over the Arabian Sea and the Bay of Bengal, which suggests a pre-conditioning process for the northward propagation of the boreal summer intra-seasonal variability. It is also observed that during the break spells, clouds are not completely suppressed over central India. Instead, clouds with smaller vertical extent (3-5 km) are observed due to the presence of a heat low type of circulation. The present results will be useful for validating the vertical structure of clouds in weather and climate prediction models.

A Hybrid Parallel Algorithm for Computing and Tracking Level Set Topology

The contour tree is a topological abstraction of a scalar field that captures evolution in level set connectivity. It is an effective representation for visual exploration and analysis of scientific data. We describe a work-efficient, output sensitive, and scalable parallel algorithm for computing the contour tree of a scalar field defined on a domain that is represented using either an unstructured mesh or a structured grid. A hybrid implementation of the algorithm using the GPU and multi-core CPU can compute the contour tree of an input containing 16 million vertices in less than ten seconds with a speedup factor of upto 13. Experiments based on an implementation in a multi-core CPU environment show near-linear speedup for large data sets.

Least squares QR-based decomposition provides an efficient way of computing optimal regularization parameter in photoacoustic tomography

A computationally efficient approach that computes the optimal regularization parameter for the Tikhonov-minimization scheme is developed for photoacoustic imaging. This approach is based on the least squares-QR decomposition which is a well-known dimensionality reduction technique for a large system of equations. It is shown that the proposed framework is effective in terms of quantitative and qualitative reconstructions of initial pressure distribution enabled via finding an optimal regularization parameter. The computational efficiency and performance of the proposed method are shown using a test case of numerical blood vessel phantom, where the initial pressure is exactly known for quantitative comparison. (C) 2013 Society of Photo-Optical Instrumentation Engineers (SPIE)

Hardness results for computing optimal locally Gabriel graphs

Delaunay and Gabriel graphs are widely studied geo-metric proximity structures. Motivated by applications in wireless routing, relaxed versions of these graphs known as Locally Delaunay Graphs (LDGs) and Lo-cally Gabriel Graphs (LGGs) have been proposed. We propose another generalization of LGGs called Gener-alized Locally Gabriel Graphs (GLGGs) in the context when certain edges are forbidden in the graph. Unlike a Gabriel Graph, there is no unique LGG or GLGG for a given point set because no edge is necessarily in-cluded or excluded. This property allows us to choose an LGG/GLGG that optimizes a parameter of interest in the graph. We show that computing an edge max-imum GLGG for a given problem instance is NP-hard and also APX-hard. We also show that computing an LGG on a given point set with dilation ≤k is NP-hard. Finally, we give an algorithm to verify whether a given geometric graph G= (V, E) is a valid LGG.

On Computing Amplitude, Phase, and Frequency Modulations Using a Vector Interpretation of the Analytic Signal

The amplitude-modulation (AM) and phase-modulation (PM) of an amplitude-modulated frequency-modulated (AM-FM) signal are defined as the modulus and phase angle, respectively, of the analytic signal (AS). The FM is defined as the derivative of the PM. However, this standard definition results in a PM with jump discontinuities in cases when the AM index exceeds unity, resulting in an FM that contains impulses. We propose a new approach to define smooth AM, PM, and FM for the AS, where the PM is computed as the solution to an optimization problem based on a vector interpretation of the AS. Our approach is directly linked to the fractional Hilbert transform (FrHT) and leads to an eigenvalue problem. The resulting PM and AM are shown to be smooth, and in particular, the AM turns out to be bipolar. We show an equivalence of the eigenvalue formulation to the square of the AS, and arrive at a simple method to compute the smooth PM. Some examples on synthesized and real signals are provided to validate the theoretical calculations.

Role of the cloud adjustment time scale in simulation of the interannual variability of Indian summer monsoon

The simulation of precipitation in a general circulation model relying on relaxed mass flux cumulus parameterization scheme is sensitive to cloud adjustment time scale (CATS). In this study, the frequency of the dominant intra-seasonal mode and interannual variability of Indian summer monsoon rainfall (ISMR) simulated by an atmospheric general circulation model is shown to be sensitive to the CATS. It has been shown that a longer CATS of about 5 h simulates the spatial distribution of the ISMR better. El Nio Southern Oscillation-ISMR relationship is also sensitive to CATS. The equatorial Indian Ocean rainfall and ISMR coupling is sensitive to CATS. Our study suggests that a careful choice of CATS is necessary for adequate simulation of spatial pattern as well as interannual variation of Indian summer monsoon precipitation.

An exploration framework to identify and track movement of cloud systems

We describe a framework to explore and visualize the movement of cloud systems. Using techniques from computational topology and computer vision, our framework allows the user to study this movement at various scales in space and time. Such movements could have large temporal and spatial scales such as the Madden Julian Oscillation (MJO), which has a spatial scale ranging from 1000 km to 10000 km and time of oscillation of around 40 days. Embedded within these larger scale oscillations are a hierarchy of cloud clusters which could have smaller spatial and temporal scales such as the Nakazawa cloud clusters. These smaller cloud clusters, while being part of the equatorial MJO, sometimes move at speeds different from the larger scale and in a direction opposite to that of the MJO envelope. Hitherto, one could only speculate about such movements by selectively analysing data and a priori knowledge of such systems. Our framework automatically delineates such cloud clusters and does not depend on the prior experience of the user to define cloud clusters. Analysis using our framework also shows that most tropical systems such as cyclones also contain multi-scale interactions between clouds and cloud systems. We show the effectiveness of our framework to track organized cloud system during one such rainfall event which happened at Mumbai, India in July 2005 and for cyclone Aila which occurred in Bay of Bengal during May 2009.

Variability of cloud liquid water and ice over South Asia from TMI estimates

In this study, the Tropical Rainfall Measurement Mission based Microwave Imager estimates (2A12) have been used to compare and contrast the characteristics of cloud liquid water and ice over the Indian land region and the ocean surrounding it, during the premonsoon (May) and monsoon (June-September) seasons. Based on the spatial homogeneity of rainfall, we have selected five regions for our study (three over ocean, two over land). Comparison across three ocean regions suggests that the cloud liquid water (CLW) over the orographically influenced Arabian Sea (close to the Indian west coast) behaves differently from the CLW over a trapped ocean (Bay of Bengal) or an open ocean (equatorial Indian Ocean). Specifically, the Arabian Sea region shows higher liquid water for a lower range of rainfall, whereas the Bay of Bengal and the equatorial Indian Ocean show higher liquid water for a higher range of rainfall. Apart from geographic differences, we also documented seasonal differences by comparing CLW profiles between monsoon and premonsoon periods, as well as between early and peak phases of the monsoon. We find that the CLW during the lean periods of rainfall (May or June) is higher than during the peak and late monsoon season (July-September) for raining clouds. As active and break phases are important signatures of the monsoon progression, we also analysed the differences in CLW during various phases of the monsoon, namely, active, break, active-to-break and break-to-active transition phases. We find that the cloud liquid water content during the break-to-active transition phase is significantly higher than during the active-to-break transition phase over central India. We speculate that this could be attributed to higher amount of aerosol loading over this region during the break phase. We lend credence to this aerosol-CLW/rain association by comparing the central Indian CLW with that over southeast Asia (where the aerosol loading is significantly smaller) and find that in the latter region, there are no significant differences in CLW during the different phases of the monsoon. While our hypothesis needs to be further investigated with numerical models, the results presented in this study can potentially serve as a good benchmark in evaluating the performance of cloud resolving models over the Indian region.

Energy Efficient GPS Acquisition with Sparse-GPS

Following rising demands in positioning with GPS, low-cost receivers are becoming widely available; but their energy demands are still too high. For energy efficient GPS sensing in delay-tolerant applications, the possibility of offloading a few milliseconds of raw signal samples and leveraging the greater processing power of the cloud for obtaining a position fix is being actively investigated. In an attempt to reduce the energy cost of this data offloading operation, we propose Sparse-GPS(1): a new computing framework for GPS acquisition via sparse approximation. Within the framework, GPS signals can be efficiently compressed by random ensembles. The sparse acquisition information, pertaining to the visible satellites that are embedded within these limited measurements, can subsequently be recovered by our proposed representation dictionary. By extensive empirical evaluations, we demonstrate the acquisition quality and energy gains of Sparse-GPS. We show that it is twice as energy efficient than offloading uncompressed data, and has 5-10 times lower energy costs than standalone GPS; with a median positioning accuracy of 40 m.

DEEP WASHINGTON PHOTOMETRY OF INCONSPICUOUS STAR CLUSTER CANDIDATES IN THE LARGE MAGELLANIC CLOUD

We present deep Washington photometry of 45 poorly populated star cluster candidates in the Large Magellanic Cloud (LMC). We have performed a systematic study to estimate the parameters of the cluster candidates by matching theoretical isochrones to the cleaned and dereddened cluster color-magnitude diagrams. We were able to estimate the basic parameters for 33 clusters, out of which 23 are identified as single clusters and 10 are found to be members of double clusters. The other 12 cluster candidates have been classified as possible clusters/asterisms. About 50% of the true clusters are in the 100-300 Myr age range, whereas some are older or younger. We have discussed the distribution of age, location, and reddening with respect to field, as well as the size of true clusters. The sizes and masses of the studied sample are found to be similar to that of open clusters in the Milky Way. Our study adds to the lower end of cluster mass distribution in the LMC, suggesting that the LMC, apart from hosting rich clusters, also has formed small, less massive open clusters in the 100-300 Myr age range.

History of Computing in India: 1955-2010

The history of computing in India is inextricably intertwined with two interacting forces: the political climate determined by the political party in power) and the government policies mainly driven by the technocrats and bureaucrats who acted within the boundaries drawn by the political party in power. There were four break points (which occurred in 1970, 1978, 1991 and 1998) that changed the direction of the development of computers and their applications. This article explains why these breaks occurred and how they affected the history of computing in India.