Maximum weight independent sets in hole- and dart-free graphs

The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. The complexity of the MWIS problem for hole-free graphs is unknown. In this paper, we first prove that the MWIS problem for (hole, dart, gem)-free graphs can be solved in O(n(3))-time. By using this result, we prove that the MWIS problem for (hole, dart)-free graphs can be solved in O(n(4))-time. Though the MWIS problem for (hole, dart, gem)-free graphs is used as a subroutine, we also give the best known time bound for the solvability of the MWIS problem in (hole, dart, gem)-free graphs. (C) 2012 Elsevier B.V. All rights reserved.

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 practical approach for cross-functional vehicle body weight optimization

The goal of optimization in vehicle design is often blurred by the myriads of requirements belonging to attributes that may not be quite related. If solutions are sought by optimizing attribute performance-related objectives separately starting with a common baseline design configuration as in a traditional design environment, it becomes an arduous task to integrate the potentially conflicting solutions into one satisfactory design. It may be thus more desirable to carry out a combined multi-disciplinary design optimization (MDO) with vehicle weight as an objective function and cross-functional attribute performance targets as constraints. For the particular case of vehicle body structure design, the initial design is likely to be arrived at taking into account styling, packaging and market-driven requirements. The problem with performing a combined cross-functional optimization is the time associated with running such CAE algorithms that can provide a single optimal solution for heterogeneous areas such as NVH and crash safety. In the present paper, a practical MDO methodology is suggested that can be applied to weight optimization of automotive body structures by specifying constraints on frequency and crash performance. Because of the reduced number of cases to be analyzed for crash safety in comparison with other MDO approaches, the present methodology can generate a single size-optimized solution without having to take recourse to empirical techniques such as response surface-based prediction of crash performance and associated successive response surface updating for convergence. An example of weight optimization of spaceframe-based BIW of an aluminum-intensive vehicle is given to illustrate the steps involved in the current optimization process.

Hybrid organogels and aerogels from co-assembly of structurally different low molecular weight gelators

The blending of perfluorinated bile ester derivatives with the gelator 2,3-didecyloxyanthracene (DDOA) yields a new class of hybrid organo- and aerogels displaying a combination of optical and mechanical properties that differ from those of pure gels. Indeed, the nanofibers constituting the hybrid organogels emit polarized blue light and display dichroic near-UV absorption via the achiral DDOA molecules, thanks to their association with a chiral bile ester. Moreover, the thermal stability and the mechanical yield stress of the mixed organogels in DMSO are enhanced for blends of DDOA with the deoxycholic gelator (DC11) having a C-11 chain, as compared to the pure components' gels. When the chain length of the ester is increased to C-13 (DC13) a novel compound for aerogel formation directly in scCO(2) is obtained under the studied conditions. A mixture of this compound with DDOA is also able to gelate scCO(2) leading to novel composite aerogel materials. As revealed by SAXS measurements, the hybrid and the pure DDOA and DC13 aerogels display cell parameters that are very similar. These SAXS experiments suggest that crystallographic conditions are very favorable for the growth of hybrid molecular arrangements in which DDOA and DC13 units could be interchanged. Specific molecular interactions between two components are not always a pre-requisite condition for the formation of a hybrid nanostructured material in which the components mutually induce properties.

Synthesis and application of weight function for edge cracked semicircular disk (ECSD)

We analyze the utility of edge cracked semicircular disk (ECSD) for rapid assessment of fracture toughness using compressive loading. Continuing our earlier work on ECSD, a theoretical examination here leads to a novel way for synthesizing weight functions using two distinct form factors. The efficacy of ECSD mode-I weight function synthesized using displacement and form factor methods is demonstrated by comparing with finite element results. Theory of elasticity in conjunction with finite element method is utilized to analyze crack opening potency of ECSD under eccentric compression to explore newer configurations of ECSD for fracture testing.

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.

CUDA-for-clusters: a system for efficient execution of CUDA kernels on multi-core clusters

Rapid advancements in multi-core processor architectures coupled with low-cost, low-latency, high-bandwidth interconnects have made clusters of multi-core machines a common computing resource. Unfortunately, writing good parallel programs that efficiently utilize all the resources in such a cluster is still a major challenge. Various programming languages have been proposed as a solution to this problem, but are yet to be adopted widely to run performance-critical code mainly due to the relatively immature software framework and the effort involved in re-writing existing code in the new language. In this paper, we motivate and describe our initial study in exploring CUDA as a programming language for a cluster of multi-cores. We develop CUDA-For-Clusters (CFC), a framework that transparently orchestrates execution of CUDA kernels on a cluster of multi-core machines. The well-structured nature of a CUDA kernel, the growing popularity, support and stability of the CUDA software stack collectively make CUDA a good candidate to be considered as a programming language for a cluster. CFC uses a mixture of source-to-source compiler transformations, a work distribution runtime and a light-weight software distributed shared memory to manage parallel executions. Initial results on running several standard CUDA benchmark programs achieve impressive speedups of up to 7.5X on a cluster with 8 nodes, thereby opening up an interesting direction of research for further investigation.

Prediction of the stiffness of nanoclay-polypropylene composites using a monte carlo finite element analysis approach

The present work deals with the prediction of stiffness of an Indian nanoclay-reinforced polypropylene composite (that can be termed as a nanocomposite) using a Monte Carlo finite element analysis (FEA) technique. Nanocomposite samples are at first prepared in the laboratory using a torque rheometer for achieving desirable dispersion of nanoclay during master batch preparation followed up with extrusion for the fabrication of tensile test dog-bone specimens. It has been observed through SEM (scanning electron microscopy) images of the prepared nanocomposite containing a given percentage (3–9% by weight) of the considered nanoclay that nanoclay platelets tend to remain in clusters. By ascertaining the average size of these nanoclay clusters from the images mentioned, a planar finite element model is created in which nanoclay groups and polymer matrix are modeled as separate entities assuming a given homogeneous distribution of the nanoclay clusters. Using a Monte Carlo simulation procedure, the distribution of nanoclay is varied randomly in an automated manner in a commercial FEA code, and virtual tensile tests are performed for computing the linear stiffness for each case. Values of computed stiffness modulus of highest frequency for nanocomposites with different nanoclay contents correspond well with the experimentally obtained measures of stiffness establishing the effectiveness of the present approach for further applications.

Combinatorial effect of rolling and carbonaceous nanoparticles on the evolution of crystallographic texture and structural properties of ultra high molecular weight polyethylene

Ultra high molecular weight polyethylene (PE) is a structural polymer widely used in biomedical implants. The mechanical properties of PE can be improved either by controlled crystalline orientation (texture) or by the addition of reinforcing agents. However, the combinatorial effect has not received much attention. The objective of this study was to characterize the structure and mechanical properties of PE composites incorporating multiwall carbon nanotubes (MWCNT) and reduced graphene oxide (RGO) subjected to hot rolling. The wide angle X-ray diffraction studies revealed that mechanical deformation resulted in a mixture of orthorhombic and monoclinic crystals. Furthermore, the presence of nanoparticles resulted in lower crystallinity in PE with smaller crystallite size, more so in RGO than in MWCNT composites. Rolling strengthened the texture of both orthorhombic and the monoclinic phases in PE. Presence of RGO weakened the texture of both phases of PE after rolling whereas MWCNT only mildly weakened the texture. This resulted in a reduction in the elastic modulus of RGO composites whereas moduli of neat polymer and the MWCNT composite increased after rolling. This study provides new insight into the role of nanoparticles in texture evolution during polymer processing with implications for processing of structural polymer composites.

Belief propagation for minimum weight many-to-one matchings in the random complete graph

In a complete bipartite graph with vertex sets of cardinalities n and n', assign random weights from exponential distribution with mean 1, independently to each edge. We show that, as n -> infinity, with n' = n/alpha] for any fixed alpha > 1, the minimum weight of many-to-one matchings converges to a constant (depending on alpha). Many-to-one matching arises as an optimization step in an algorithm for genome sequencing and as a measure of distance between finite sets. We prove that a belief propagation (BP) algorithm converges asymptotically to the optimal solution. We use the objective method of Aldous to prove our results. We build on previous works on minimum weight matching and minimum weight edge cover problems to extend the objective method and to further the applicability of belief propagation to random combinatorial optimization problems.

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.