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.

Interplay of software bloat, hardware energy proportionality and system bottlenecks

In large flexible software systems, bloat occurs in many forms, causing excess resource utilization and resource bottlenecks. This results in lost throughput and wasted joules. However, mitigating bloat is not easy; efforts are best applied where savings would be substantial. To aid this we develop an analytical model establishing the relation between bottleneck in resources, bloat, performance and power. Analyses with the model places into perspective results from the first experimental study of the power-performance implications of bloat. In the experiments we find that while bloat reduction can provide as much as 40% energy savings, the degree of impact depends on hardware and software characteristics. We confirm predictions from our model with selected results from our experimental study. Our findings show that a software-only view is inadequate when assessing the effects of bloat. The impact of bloat on physical resource usage and power should be understood for a full systems perspective to properly deploy bloat reduction solutions and reap their power-performance benefits.

Context aware M-commerce services: C-IOB model approach

Context-aware computing is useful in providing individualized services focusing mainly on acquiring surrounding context of user. By comparison, only very little research has been completed in integrating context from different environments, despite of its usefulness in diverse applications such as healthcare, M-commerce and tourist guide applications. In particular, one of the most important criteria in providing personalized service in a highly dynamic environment and constantly changing user environment, is to develop a context model which aggregates context from different domains to infer context of an entity at the more abstract level. Hence, the purpose of this paper is to propose a context model based on cognitive aspects to relate contextual information that better captures the observation of certain worlds of interest for a more sophisticated context-aware service. We developed a C-IOB (Context-Information, Observation, Belief) conceptual model to analyze the context data from physical, system, application, and social domains to infer context at the more abstract level. The beliefs developed about an entity (person, place, things) are primitive in most theories of decision making so that applications can use these beliefs in addition to history of transaction for providing intelligent service. We enhance our proposed context model by further classifying context information into three categories: a well-defined, a qualitative and credible context information to make the system more realistic towards real world implementation. The proposed model is deployed to assist a M-commerce application. The simulation results show that the service selection and service delivery of the system are high compared to traditional system.

Physical ageing in Se-Te-Sb glasses

Bulk Se60-xTe40Sbx glasses in the composition range 0 <= x <= 14 were prepared by the melt quenching method. Differential Scanning Calorimetric (DSC) and thermal crystallization studies were performed to understand the thermodynamic property like glass transition and structural transformations. These glasses exhibit sharp endothermic peak at the glass transition (T-g). Disappearance of the endothermic peak at T-g in the rejuvenated samples clearly indicates the ageing effect in these glasses. Addition of Sb to Se-Te increases the connectivity of the structural network which is evidenced from the increase in T-g. A distinct change in the slope of the T-g at x=6, indicates a major change in the way the network is connected. The glass forming ability and the thermal stability also exhibit a maximum at x=6. T-g increases with the ageing time and the corresponding fictive temperature (T-f) calculated from the specific heat curves shows a decreasing trend. The molecular movements along the polymeric Se chains might cause the structural relaxation and the physical ageing. The physical ageing effect has been understood on the basis of the Bond Free Solid Angle (BFSA) model proposed by Kastner. Thermally crystallized samples show the formation of rhombohedral Sb2Te3, rhombohedral Sb2Se3 and hexagonal Te phases.

Coulomb-hole summations and energies for GW calculations with limited number of empty orbitals: a modified static remainder approach

Ab initio GW calculations are a standard method for computing the spectroscopic properties of many materials. The most computationally expensive part in conventional implementations of the method is the generation and summation over the large number of empty orbitals required to converge the electron self-energy. We propose a scheme to reduce the summation over empty states by the use of a modified static remainder approximation, which is simple to implement and yields accurate self-energies for both bulk and molecular systems requiring a small fraction of the typical number of empty orbitals.

Performance analysis of adaptive physical layer network coding for wireless two-way relaying

The performance analysis of adaptive physical layer network-coded two-way relaying scenario is presented which employs two phases: Multiple access (MA) phase and Broadcast (BC) phase. The deep channel fade conditions which occur at the relay referred as the singular fade states fall in the following two classes: (i) removable and (ii) non-removable singular fade states. With every singular fade state, we associate an error probability that the relay transmits a wrong network-coded symbol during the BC phase. It is shown that adaptive network coding provides a coding gain over fixed network coding, by making the error probabilities associated with the removable singular fade states contributing to the average Symbol Error Rate (SER) fall as SNR-2 instead of SNR-1. A high SNR upper-bound on the average end-to-end SER for the adaptive network coding scheme is derived, for a Rician fading scenario, which is found to be tight through simulations. Specifically, it is shown that for the adaptive network coding scheme, the probability that the relay node transmits a wrong network-coded symbol is upper-bounded by twice the average SER of a point-to-point fading channel, at high SNR. Also, it is shown that in a Rician fading scenario, it suffices to remove the effect of only those singular fade states which contribute dominantly to the average SER.

Influence of physical structure and chemistry of diesel soot suspended in hexadecane on lubrication of steel-on-steel contact

Soot generated from the combustion process in diesel engines affect engine tribology. In this paper, two diesel soot samples; from engine exhaust and oil filter are suspended in hexadecane oil and the suspension is used to lubricate a steel ball on steel flat sliding contact at a contact pressure of 1.3 GPa. The friction and wear of the steel flat are recorded. The data are compared with those recorded when the soot is generated by burning ethylene gas. The rationale for the comparatively poor tribology of diesel soot is explored by quantifying the size and shape of primary particles and agglomerates, hardness of single primary soot particles, the crystallinity and surface and near surface chemistry of soot and interparticle adhesion.

Influence of system size on spatiotemporal dynamics of a model for plastic instability: Projecting low-dimensional and extensive chaos

This work is a continuation of our efforts to quantify the irregular scalar stress signals from the Ananthakrishna model for the Portevin-Le Chatelier instability observed under constant strain rate deformation conditions. Stress related to the spatial average of the dislocation activity is a dynamical variable that also determines the time evolution of dislocation densities. We carry out detailed investigations on the nature of spatiotemporal patterns of the model realized in the form of different types of dislocation bands seen in the entire instability domain and establish their connection to the nature of stress serrations. We then characterize the spatiotemporal dynamics of the model equations by computing the Lyapunov dimension as a function of the drive parameter. The latter scales with the system size only for low strain rates, where isolated dislocation bands are seen, and at high strain rates, where fully propagating bands are seen. At intermediate applied strain rates corresponding to the partially propagating bands, the Lyapunov dimension exhibits two distinct slopes, one for small system sizes and another for large. This feature is rationalized by demonstrating that the spatiotemporal patterns for small system sizes are altered from the partially propagating band types to isolated burst type. This in turn allows us to reconfirm that low-dimensional chaos is projected from the stress signals as long as there is a one-to-one correspondence between the bursts of dislocation bands and the stress drops. We then show that the stress signals in the regime of partially to fully propagative bands have features of extensive chaos by calculating the correlation dimension density. We also show that the correlation dimension density also depends on the system size. A number of issues related to the system size dependence of the Lyapunov dimension density and the correlation dimension density are discussed.

Growth-temperature dependent physical properties of SnS nanocrystalline thin films

In this article we have demonstrated the influence of growth-temperature on the morphology and orientation of SnS films deposited by thermal evaporation technique. While increasing the growth-temperature, the morphology of SnS films changed from flakes-like nanocrystals to regular cubes, whereas their orientation shifted from <111> to <040> direction. The chemical composition of SnS films gradually changed from sulfur-rich to tin-rich with the increase of growth-temperature. The structural analyzes reveal that the crystal structure of SnS films probably changes from orthorhombic to tetragonal at the growth-temperature of about 410 degrees C. Raman studies show that SnS films grown at all temperatures consist of purely SnS phase, whereas the optical studies reveal that the direct optical bandgap of SnS films decreased with the increase of growth-temperature. From these results it has been emphasized that the morphology and orientation along with electrical and optical properties of nearly stoichiometric SnS films strongly depend on their growth-temperature.

Stability analysis of aperiodic messages scheduled in the dynamic segment of flex ray protocol

In a cyber physical system like vehicles number of signals to be communicated in a network system has an increasing trend. More and more mechanical and hydraulic parts are replaced by electronic control units and infotainment and multimedia applications has increased in vehicles. Safety critical hard real time messages and aperiodic messages communicated between electronic control units have been increased in recent times. Flexray is a high bandwidth protocol consisting of static segment for supporting hard real time messages and a dynamic segment for transmitting soft and non real time messages. In this paper, a method to obtain the stability region for the random arrival of messages in each electronic control units which is scheduled in the dynamic segment of Flexray protocol is presented. Number of mini slots available in the dynamic segment of Flexray restricts the arrival rate of tasks to the micro controllers or the number of micro controllers connected to the Flexray bus. Stability region of mathematical model of the system is compared with the Flexray protocol simulation results.

Physical Layer Network Coding for the K-User Multiple Access Relay Channel

We propose a Physical layer Network Coding (PNC) scheme for the K-user wireless Multiple Access Relay Channel, in which K source nodes want to transmit messages to a destination node D with the help of a relay node R. The proposed scheme involves (i) Phase 1 during which the source nodes alone transmit and (ii) Phase 2 during which the source nodes and the relay node transmit. At the end of Phase 1, the relay node decodes the messages of the source nodes and during Phase 2 transmits a many-to-one function of the decoded messages. To counter the error propagation from the relay node, we propose a novel decoder which takes into account the possibility of error events at R. It is shown that if certain parameters are chosen properly and if the network coding map used at R forms a Latin Hypercube, the proposed decoder offers the maximum diversity order of two. Also, it is shown that for a proper choice of the parameters, the proposed decoder admits fast decoding, with the same decoding complexity order as that of the reference scheme based on Complex Field Network Coding (CFNC). Simulation results indicate that the proposed PNC scheme offers a large gain over the CFNC scheme.

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)

e-SURAKSHAK: A Cyber-Physical Healthcare System with Service Oriented Architecture

In this paper we present the design of ``e-SURAKSHAK,'' a novel cyber-physical health care management system of Wireless Embedded Internet Devices (WEIDs) that sense vital health parameters. The system is capable of sensing body temperature, heart rate, oxygen saturation level and also allows noninvasive blood pressure (NIBP) measurement. End to end internet connectivity is provided by using 6LoWPAN based wireless network that uses the 802.15.4 radio. A service oriented architecture (SOA) 1] is implemented to extract meaningful information and present it in an easy-to-understand form to the end-user instead of raw data made available by sensors. A central electronic database and health care management software are developed. Vital health parameters are measured and stored periodically in the database. Further, support for real-time measurement of health parameters is provided through a web based GUI. The system has been implemented completely and demonstrated with multiple users and multiple WEIDs.

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.