Bounds on isoperimetric values of trees

Let G = (V, E) be a finite, simple and undirected graph. For S subset of V, let delta(S, G) = {(u, v) is an element of E : u is an element of S and v is an element of V - S} be the edge boundary of S. Given an integer i, 1 <= i <= vertical bar V vertical bar, let the edge isoperimetric value of G at i be defined as b(e)(i, G) = min(S subset of V:vertical bar S vertical bar=i)vertical bar delta(S, G)vertical bar. The edge isoperimetric peak of G is defined as b(e)(G) = max(1 <= j <=vertical bar V vertical bar)b(e)(j, G). Let b(v)(G) denote the vertex isoperimetric peak defined in a corresponding way. The problem of determining a lower bound for the vertex isoperimetric peak in complete t-ary trees was recently considered in [Y. Otachi, K. Yamazaki, A lower bound for the vertex boundary-width of complete k-ary trees, Discrete Mathematics, in press (doi: 10.1016/j.disc.2007.05.014)]. In this paper we provide bounds which improve those in the above cited paper. Our results can be generalized to arbitrary (rooted) trees. The depth d of a tree is the number of nodes on the longest path starting from the root and ending at a leaf. In this paper we show that for a complete binary tree of depth d (denoted as T-d(2)), c(1)d <= b(e) (T-d(2)) <= d and c(2)d <= b(v)(T-d(2)) <= d where c(1), c(2) are constants. For a complete t-ary tree of depth d (denoted as T-d(t)) and d >= c log t where c is a constant, we show that c(1)root td <= b(e)(T-d(t)) <= td and c(2)d/root t <= b(v) (T-d(t)) <= d where c(1), c(2) are constants. At the heart of our proof we have the following theorem which works for an arbitrary rooted tree and not just for a complete t-ary tree. Let T = (V, E, r) be a finite, connected and rooted tree - the root being the vertex r. Define a weight function w : V -> N where the weight w(u) of a vertex u is the number of its successors (including itself) and let the weight index eta(T) be defined as the number of distinct weights in the tree, i.e eta(T) vertical bar{w(u) : u is an element of V}vertical bar. For a positive integer k, let l(k) = vertical bar{i is an element of N : 1 <= i <= vertical bar V vertical bar, b(e)(i, G) <= k}vertical bar. We show that l(k) <= 2(2 eta+k k)

State space formulation of ammonia reactor dynamics

The specific objective of this paper is to develop a state space model of a tubular ammonia reactor which is the heart of an ammonia plant in a fertiliser complex. A ninth order model with three control inputs and two disturbance inputs is generated from the nonlinear distributed model using linearization and lumping approximations. The lumped model is chosen such that the steady state temperature at the exit of the catalyst bed computed from the simplified state space model is close enough to the one computed from the nonlinear steady state model. The model developed in this paper is very useful for the design of continuous/discrete versions of single variable/multivariable control algorithms.

Resolution of conflicting views on thermodynamics of glass transition: A unified model

Classical description of thermodynamic properties during glass transition has been questioned by the entropy-loss model. The uncompensated loss of entropy at the glass transition temperature and zero residual entropy is at the heart of the controversy. Both the models are critically reviewed. A unified model is presented which incorporates features of both entropy loss and residual entropy. It implies two different types of contributions to the entropy of the supercooled liquid, one of which vanishes at the transition and the other which contributes to residual entropy. Entropy gain during spontaneous relaxation of glass, and the nature of heat capacity `hysteresis' during cooling and heating through the glass transition range support the proposed model. Experiments are outlined for differentiating between the models.

Sequential Assembly of an Active RNA Polymerase Molecule at the Air-Water Interface

At the heart of understanding cellular processes lies our ability to explore the specific nature of communication between sequential information carrying biopolymers. However, the data extracted from conventional solution phase studies may not reflect the dynamics of communication between recognized partners as they occur in the crowded cellular milieu. We use the principle of immobilization of histidine-tagged biopolymers at a Ni(II)-encoded Langmuir monolayer to study sequence-specific protein-protein interactions in an artificially crowded environment The advantage of this technique lies in increasing the surface density of one of the interacting partners that allows us to study macromolecular interactions in a controlled crowded environment, but without compromising the speed of the reactions. We have taken advantage of this technique to follow the sequential assembly process of the multiprotein complex Escherichia coil RNA polymerase at the interface and also deciphered the role of one of the proteins, omega (omega), in the assembly pathway. Our reconstitution studies indicate that in the absence of molecular chaperones or other cofactors, omega (omega) plays a decisive role in refolding the largest protein beta prime (beta') and its recruitment into the multimeric assembly to reconstitute an active RNA polymerase. It was also observed that the monolayer had the ability to distinguish between sequence-specific and -nonspecific interactions despite the immobilization of one of the biomacromolecules. The technique provides a universal two-dimensional template for studying protein-ligand interactions while mimicking molecular crowding.

Ecological Assessment of Lentic Water Bodies of Bangalore

The restoration, conservation and management of water resources require a thorough understanding of what constitutes a healthy ecosystem. Monitoring and assessment provides the basic information on the condition of our waterbodies. The present work details the study carried out at two waterbodies, namely, the Chamarajasagar reservoir and the Madiwala Lake. The waterbodies were selected on the basis of their current use and locations. Chamarajasagar reservoir serves the purpose of supplying drinking water to Bangalore city and is located on the outskirts of the city surrounded by agricultural and forest land. On the other hand, Madiwala lake is situated in the heart of Bangalore city receiving an influx of pollutants from domestic and industrial sewage. Comparative assessment of the surface water quality of both were carried out by instituting the various physico–chemical and biological parameters. The physico-chemical analyses included temperature, transparency, pH, electrical conductivity, dissolved oxygen, alkalinity, total hardness, calcium hardness, magnesium hardness, nitrates, phosphates, sodium, potassium and COD measurements of the given waterbody. The analysis was done based on the standard methods prescribed (or recommended) by (APHA) and NEERI. The biological parameter included phytoplankton analysis. The detailed investigations of the parameters, which are well within the tolerance limits in Chamarajasagar reservoir, indicate that it is fairly unpolluted, except for the pH values, which indicate greater alkalinity. This may be attributed to the natural causes and the agricultural runoff from the catchment. On the contrary, the limnology of Madiwala lake is greatly influenced by the inflow of sewage that contributes significantly to the dissolved solids of the lake water, total hardness, alkalinity and a low DO level. Although, the two study areas differ in age, physiography, chemistry and type of inflows, they still maintain a phytoplankton distribution overwhelmingly dominated by Cyanophyceae members,specifically Microcystis aeruginosa. These blue green algae apparently enter the waterbodies from soil, which are known to harbour a rich diversity of blue green flora with several species common to limnoplankton, a feature reported to be unique to the south Indian lakes.Chamarajasagar water samples revealed five classes of phytoplankton, of which Cyanophyceae (92.15 percent) that dominated other algal forms comprised of one single species of Microcystis aeruginosa. The next major class of algae was Chlorophyceae (3.752 percent) followed by Dinophyceae (3.51 percent), Bacillariophyceae (0.47 percent) and a sparsely available and unidentified class (0.12 percent).Madiwala Lake phytoplankton, in addition to Cyanophyceae (26.20 percent), revealed a high density of Chlorophyceae members (73.44 percent) dominated by Scenedesmus sp.,Pediastrum sp., and Euglena sp.,which are considered to be indicators of organic pollution. The domestic and industrial sewage, which finds its way into the lake, is a factor causing organic pollution. As compared to the other classes, Euglenophyceae and Bacillariophyceae members were the lowest in number. Thus, the analysis of various parameters indicates that Chamarajasagar reservoir is relatively unpolluted except for the high percentage of Microcystis aeruginosa, and a slightly alkaline nature of water. Madiwala lake samples revealed eutrophication and high levels of pollution, which is clarified by the physico–chemical analysis, whose values are way above the tolerance limits. Also, the phytoplankton analysis in Madiwala lake reveals the dominance of Chlorophyceae members, which indicate organic pollution (sewage being the causative factor).

Quadrature approximation properties of the spiral-phase quadrature transform

The notion of the 1-D analytic signal is well understood and has found many applications. At the heart of the analytic signal concept is the Hilbert transform. The problem in extending the concept of analytic signal to higher dimensions is that there is no unique multidimensional definition of the Hilbert transform. Also, the notion of analyticity is not so well under stood in higher dimensions. Of the several 2-D extensions of the Hilbert transform, the spiral-phase quadrature transform or the Riesz transform seems to be the natural extension and has attracted a lot of attention mainly due to its isotropic properties. From the Riesz transform, Larkin et al. constructed a vortex operator, which approximates the quadratures based on asymptotic stationary-phase analysis. In this paper, we show an alternative proof for the quadrature approximation property by invoking the quasi-eigenfunction property of linear, shift-invariant systems. We show that the vortex operator comes up as a natural consequence of applying this property. We also characterize the quadrature approximation error in terms of its energy as well as the peak spatial-domain error. Such results are available for 1-D signals, but their counter part for 2-D signals have not been provided. We also provide simulation results to supplement the analytical calculations.

A Nearly Exact Reformulation of the Girsanov Linearization for Stochastically Driven Nonlinear Oscillators

The Girsanov linearization method (GLM), proposed earlier in Saha, N., and Roy, D., 2007, ``The Girsanov Linearisation Method for Stochastically Driven Nonlinear Oscillators,'' J. Appl. Mech., 74, pp. 885-897, is reformulated to arrive at a nearly exact, semianalytical, weak and explicit scheme for nonlinear mechanical oscillators under additive stochastic excitations. At the heart of the reformulated linearization is a temporally localized rejection sampling strategy that, combined with a resampling scheme, enables selecting from and appropriately modifying an ensemble of locally linearized trajectories while weakly applying the Girsanov correction (the Radon-Nikodym derivative) for the linearization errors. The semianalyticity is due to an explicit linearization of the nonlinear drift terms and it plays a crucial role in keeping the Radon-Nikodym derivative ``nearly bounded'' above by the inverse of the linearization time step (which means that only a subset of linearized trajectories with low, yet finite, probability exceeds this bound). Drift linearization is conveniently accomplished via the first few (lower order) terms in the associated stochastic (Ito) Taylor expansion to exclude (multiple) stochastic integrals from the numerical treatment. Similarly, the Radon-Nikodym derivative, which is a strictly positive, exponential (super-) martingale, is converted to a canonical form and evaluated over each time step without directly computing the stochastic integrals appearing in its argument. Through their numeric implementations for a few low-dimensional nonlinear oscillators, the proposed variants of the scheme, presently referred to as the Girsanov corrected linearization method (GCLM), are shown to exhibit remarkably higher numerical accuracy over a much larger range of the time step size than is possible with the local drift-linearization schemes on their own.

Semisolid Processing of A380 Al Alloy Using Cooling Slope

This study is aimed toward obtaining near spherical microstructural features of Rheocast A380 aluminum alloy. Cooling slope (CS) technique has been used to generate semisolid slurry from the superheated alloy melt. Spherodization of primary grains is the heart of semisolid processing which improves mechanical properties significantly in the parts cast from semisolid state compared to the conventional casting processes. Keeping in view of the desired microstructural morphology, i.e., rosette or spherical shape of primary alpha-Al phase, successive slurry samples have been collected during melt flow and oil quenched to investigate the microstructure evolution mechanism. Conventionally cast A380 Al alloy sample shows dendritic grains surrounded by large eutectic phase whereas finer, near spherical grains have been observed within the cooling slope processed slurry and also in the solidified castings which confirms the effectiveness of semisolid processing of the alloy following cooling slope technique. Grain refiner addition into the alloy melt is found to have favorable effect which leads to the generation of finer primary grains within the slurry with higher degree of sphericity.

Mining Unit Tests for Discovery and Migration of Math APIs

Today's programming languages are supported by powerful third-party APIs. For a given application domain, it is common to have many competing APIs that provide similar functionality. Programmer productivity therefore depends heavily on the programmer's ability to discover suitable APIs both during an initial coding phase, as well as during software maintenance. The aim of this work is to support the discovery and migration of math APIs. Math APIs are at the heart of many application domains ranging from machine learning to scientific computations. Our approach, called MATHFINDER, combines executable specifications of mathematical computations with unit tests (operational specifications) of API methods. Given a math expression, MATHFINDER synthesizes pseudo-code comprised of API methods to compute the expression by mining unit tests of the API methods. We present a sequential version of our unit test mining algorithm and also design a more scalable data-parallel version. We perform extensive evaluation of MATHFINDER (1) for API discovery, where math algorithms are to be implemented from scratch and (2) for API migration, where client programs utilizing a math API are to be migrated to another API. We evaluated the precision and recall of MATHFINDER on a diverse collection of math expressions, culled from algorithms used in a wide range of application areas such as control systems and structural dynamics. In a user study to evaluate the productivity gains obtained by using MATHFINDER for API discovery, the programmers who used MATHFINDER finished their programming tasks twice as fast as their counterparts who used the usual techniques like web and code search, IDE code completion, and manual inspection of library documentation. For the problem of API migration, as a case study, we used MATHFINDER to migrate Weka, a popular machine learning library. Overall, our evaluation shows that MATHFINDER is easy to use, provides highly precise results across several math APIs and application domains even with a small number of unit tests per method, and scales to large collections of unit tests.

An elementary introduction to solar dynamo theory

The cyclically varying magnetic field of the Sun is believed to be produced by the hydromagnetic dynamo process. We first summarize the relevant observational data pertaining to sunspots and solar cycle. Then we review the basic principles of MHD needed to develop the dynamo theory. This is followed by a discussion how bipolar sunspots form due to magnetic buoyancy of flux tubes formed at the base of the solar convection zone. Following this, we come to the heart of dynamo theory. After summarizing the basic ideas of a turbulent dynamo and the basic principles of its mean field formulation, we present the famous dynamo wave solution, which was supposed to provide a model for the solar cycle. Finally we point out how a flux transport dynamo can circumvent some of the difficulties associated with the older dynamo models.

Accelerating Numerical Linear Algebra Kernels on a Scalable Run Time Reconfigurable Platform

Numerical Linear Algebra (NLA) kernels are at the heart of all computational problems. These kernels require hardware acceleration for increased throughput. NLA Solvers for dense and sparse matrices differ in the way the matrices are stored and operated upon although they exhibit similar computational properties. While ASIC solutions for NLA Solvers can deliver high performance, they are not scalable, and hence are not commercially viable. In this paper, we show how NLA kernels can be accelerated on REDEFINE, a scalable runtime reconfigurable hardware platform. Compared to a software implementation, Direct Solver (Modified Faddeev's algorithm) on REDEFINE shows a 29X improvement on an average and Iterative Solver (Conjugate Gradient algorithm) shows a 15-20% improvement. We further show that solution on REDEFINE is scalable over larger problem sizes without any notable degradation in performance.

Velocity Fluctuations in Helical Propulsion: How Small Can a Propeller Be

Helical propulsion is at the heart of locomotion strategies utilized by various natural and artificial swimmers. We used experimental observations and a numerical model to study the various fluctuation mechanisms that determine the performance of an externally driven helical propeller as the size of the helix is reduced. From causality analysis, an overwhelming effect of orientational noise at low length scales is observed, which strongly affects the average velocity and direction of motion of a propeller. For length scales smaller than a few micrometers in aqueous media, the operational frequency for the propulsion system would have to increase as the inverse cube of the size, which can be the limiting factor for a helical propeller to achieve locomotion in the desired direction.