A new class of separators and planarity of chordal graphs

We introduce a new class of clique separators, called base sets, for chordal graphs. Base sets of a chordal graph closely reflect its structure. We show that the notion of base sets leads to structural characterizations of planar k-trees and planar chordal graphs. Using these characterizations, we develop linear time algorithms for recognizing planar k-trees and planar chordal graphs. These algorithms are extensions of the Lexicographic_Breadth_First_Search algorithm for recognizing chordal graphs and are much simpler than the general planarity checking algorithm. Further, we use the notion of base sets to prove the equivalence of hamiltonian 2-trees and maximal outerplanar graphs.

Parallel circuit partitioning on a reduced array architecture

The physical design of a VLSI circuit involves circuit partitioning as a subtask. Typically, it is necessary to partition a large electrical circuit into several smaller circuits such that the total cross-wiring is minimized. This problem is a variant of the more general graph partitioning problem, and it is known that there does not exist a polynomial time algorithm to obtain an optimal partition. The heuristic procedure proposed by Kernighan and Lin1,2 requires O(n2 log2n) time to obtain a near-optimal two-way partition of a circuit with n modules. In the VLSI context, due to the large problem size involved, this computational requirement is unacceptably high. This paper is concerned with the hardware acceleration of the Kernighan-Lin procedure on an SIMD architecture. The proposed parallel partitioning algorithm requires O(n) processors, and has a time complexity of O(n log2n). In the proposed scheme, the reduced array architecture is employed with due considerations towards cost effectiveness and VLSI realizability of the architecture.The authors are not aware of any earlier attempts to parallelize a circuit partitioning algorithm in general or the Kernighan-Lin algorithm in particular. The use of the reduced array architecture is novel and opens up the possibilities of using this computing structure for several other applications in electronic design automation.

Freezing of a colloidal liquid subject to shear flow

A nonequilibrium generalization of the density-functional theory of freezing is proposed to investigate the shear-induced first-order phase transition in colloidal suspensions. It is assumed that the main effect of a steady shear is to break the symmetry of the structure factor of the liquid and that for small shear rate, the phenomenon of a shear-induced order-disorder transition may be viewed as an equilibrium phase transition. The theory predicts that the effective density at which freezing takes place increases with shear rate. The solid (which is assumed to be a bcc lattice) formed upon freezing is distorted and specifically there is less order in one plane compared with the order in the other two perpendicular planes. It is shown that there exists a critical shear rate above which the colloidal liquid does not undergo a transition to an ordered (or partially ordered) state no matter how large the density is. Conversely, above the critical shear rate an initially formed bcc solid always melts into an amorphous or liquidlike state. Several of these predictions are in qualitative agreement with the light-scattering experiments of Ackerson and Clark. The limitations as well as possible extensions of the theory are also discussed.

The influence of chemical additives on surface charge and hardness of hematite

The zeta potential of high-purity hematite at pH 6 and in a 10−3N NaCl solution has been determined at different concentrations of acetone using the streaming potential technique and the results correlated with the microhardness of the mineral. The zeta potential has been found to decrease as the hardness increases reaching a minimum at 10 cc per litre concentration of acetone when the hardness reaches a maximum. The results have been explained on the basis of competitive adsorption of chloride ions and acetone molecules at low concentrations of acetone and coadsorption of both species above 10 cc per litre concentration. Acetone in distilled water and 10−3N NaCl in distilled water decrease the microhardness of hematite individually between pH 5 to 7 and in combination increase the microhardness reaching a maximum at pH 6.

Experimental analysis of thermo-physical processes in acoustically levitated heated droplets

An experimental setup using radiative heating has been used to understand the thermo-physical phenomena and chemical transformations inside acoustically levitated cerium nitrate precursor droplets. In this transformation process, through infrared thermography and high speed imaging, events such as vaporization, precipitation and chemical reaction have been recorded at high temporal resolution, leading to nanoceria formation with a porous morphology. The cerium nitrate droplet undergoes phase and shape changes throughout the vaporization process. Four distinct stages were delineated during the entire vaporization process namely pure evaporation, evaporation with precipitate formation, chemical reaction with phase change and formation of final porous precipitate. The composition was examined using scanning and transmission electron microscopy that revealed nanostructures and confirmed highly porous morphology with trapped gas pockets. Transmission electron microscopy (TEM) and high speed imaging of the final precipitate revealed the presence of trapped gases in the form of bubbles. TEM also showed the presence of nanoceria crystalline structures at 70 degrees C. The current study also looked into the effect of different heating powers on the process. At higher power, each phase is sustained for smaller duration and higher maximum temperature. In addition, the porosity of the final precipitate increased with power. A non-dimensional time scale is proposed to correlate the effect of laser intensity and vaporization rate of the solvent (water). The effect of acoustic levitation was also studied. Due to acoustic streaming, the solute selectively gets transported to the bottom portion of the droplet due to strong circulation, providing it rigidity and allows it become bowl shaped. (C) 2010 Elsevier Ltd. All rights reserved.

A Deterministic Optimization Approach to Protein Sequence Design Using Continuous Models

Determining the sequence of amino acid residues in a heteropolymer chain of a protein with a given conformation is a discrete combinatorial problem that is not generally amenable for gradient-based continuous optimization algorithms. In this paper we present a new approach to this problem using continuous models. In this modeling, continuous "state functions" are proposed to designate the type of each residue in the chain. Such a continuous model helps define a continuous sequence space in which a chosen criterion is optimized to find the most appropriate sequence. Searching a continuous sequence space using a deterministic optimization algorithm makes it possible to find the optimal sequences with much less computation than many other approaches. The computational efficiency of this method is further improved by combining it with a graph spectral method, which explicitly takes into account the topology of the desired conformation and also helps make the combined method more robust. The continuous modeling used here appears to have additional advantages in mimicking the folding pathways and in creating the energy landscapes that help find sequences with high stability and kinetic accessibility. To illustrate the new approach, a widely used simplifying assumption is made by considering only two types of residues: hydrophobic (H) and polar (P). Self-avoiding compact lattice models are used to validate the method with known results in the literature and data that can be practically obtained by exhaustive enumeration on a desktop computer. We also present examples of sequence design for the HP models of some real proteins, which are solved in less than five minutes on a single-processor desktop computer Some open issues and future extensions are noted.

A heuristic clustering algorithm using union of overlapping pattern-cells

Relative geometric arrangements of the sample points, with reference to the structure of the imbedding space, produce clusters. Hence, if each sample point is imagined to acquire a volume of a small M-cube (called pattern-cell), depending on the ranges of its (M) features and number (N) of samples; then overlapping pattern-cells would indicate naturally closer sample-points. A chain or blob of such overlapping cells would mean a cluster and separate clusters would not share a common pattern-cell between them. The conditions and an analytic method to find such an overlap are developed. A simple, intuitive, nonparametric clustering procedure, based on such overlapping pattern-cells is presented. It may be classified as an agglomerative, hierarchical, linkage-type clustering procedure. The algorithm is fast, requires low storage and can identify irregular clusters. Two extensions of the algorithm, to separate overlapping clusters and to estimate the nature of pattern distributions in the sample space, are also indicated.

Analytical and numerical solutions of inward spherical solidification of a superheated melt with radiative-convective heat transfer and density jump at freezing front

Analytical and numerical solutions of a general problem related to the radially symmetric inward spherical solidification of a superheated melt have been studied in this paper. In the radiation-convection type boundary conditions, the heat transfer coefficient has been taken as time dependent which could be infinite, at time,t=0. This is necessary, for the initiation of instantaneous solidification of superheated melt, over its surface. The analytical solution consists of employing suitable fictitious initial temperatures and fictitious extensions of the original region occupied by the melt. The numerical solution consists of finite difference scheme in which the grid points move with the freezing front. The numerical scheme can handle with ease the density changes in the solid and liquid states and the shrinkage or expansions of volumes due to density changes. In the numerical results, obtained for the moving boundary and temperatures, the effects of several parameters such as latent heat, Boltzmann constant, density ratios, heat transfer coefficients, etc. have been shown. The correctness of numerical results has also been checked by satisfying the integral heat balance at every timestep.

An optimal parallel algorithm for sparse matrix bandwidth reduction on a linear array

A simple and efficient algorithm for the bandwidth reduction of sparse symmetric matrices is proposed. It involves column-row permutations and is well-suited to map onto the linear array topology of the SIMD architectures. The efficiency of the algorithm is compared with the other existing algorithms. The interconnectivity and the memory requirement of the linear array are discussed and the complexity of its layout area is derived. The parallel version of the algorithm mapped onto the linear array is then introduced and is explained with the help of an example. The optimality of the parallel algorithm is proved by deriving the time complexities of the algorithm on a single processor and the linear array.

Automatic verification of distributed logic specifications

Formal specification is vital to the development of distributed real-time systems as these systems are inherently complex and safety-critical. It is widely acknowledged that formal specification and automatic analysis of specifications can significantly increase system reliability. Although a number of specification techniques for real-time systems have been reported in the literature, most of these formalisms do not adequately address to the constraints that the aspects of 'distribution' and 'real-time' impose on specifications. Further, an automatic verification tool is necessary to reduce human errors in the reasoning process. In this regard, this paper is an attempt towards the development of a novel executable specification language for distributed real-time systems. First, we give a precise characterization of the syntax and semantics of DL. Subsequently, we discuss the problems of model checking, automatic verification of satisfiability of DL specifications, and testing conformance of event traces with DL specifications. Effective solutions to these problems are presented as extensions to the classical first-order tableau algorithm. The use of the proposed framework is illustrated by specifying a sample problem.

Signals of additional Z ` boson in e(+)e(-) -> W+W- at the ILC with polarized beams

We consider the possibility of fingerprinting the presence of heavy additional Z' bosons that arise naturally in extensions of the standard model such as E-6 models and left-right symmetric models, through their mixing with the standard model Z boson. By considering a class of observables including total cross sections, energy distributions and angular distributions of decay leptons we find significant deviation from the standard model predictions for these quantities with right-handed electrons and left-handed positrons at root s= 800GeV. The deviations being less pronounced at smaller centre of mass energies as the models are already tightly constrained. Our work suggests that the ILC should have a strong beam polarization physics program particularly with these configurations. On the other hand, a forward backward asymmetry and lepton fraction in the backward direction are more sensitive to new physics with realistic polarization due to interesting interplay with the neutrino t-channel diagram. This process complements the study of fermion pair production processes that have been considered for discrimination between these models.

Entanglement and nonclassicality for multimode radiation-field states

Nonclassicality in the sense of quantum optics is a prerequisite for entanglement in multimode radiation states. In this work we bring out the possibilities of passing from the former to the latter, via action of classicality preserving systems like beam splitters, in a transparent manner. For single-mode states, a complete description of nonclassicality is available via the classical theory of moments, as a set of necessary and sufficient conditions on the photon number distribution. We show that when the mode is coupled to an ancilla in any coherent state, and the system is then acted upon by a beam splitter, these conditions turn exactly into signatures of negativity under partial transpose (NPT) entanglement of the output state. Since the classical moment problem does not generalize to two or more modes, we turn in these cases to other familiar sufficient but not necessary conditions for nonclassicality, namely the Mandel parameter criterion and its extensions. We generalize the Mandel matrix from one-mode states to the two-mode situation, leading to a natural classification of states with varying levels of nonclassicality. For two-mode states we present a single test that can, if successful, simultaneously show nonclassicality as well as NPT entanglement. We also develop a test for NPT entanglement after beam-splitter action on a nonclassical state, tracing carefully the way in which it goes beyond the Mandel nonclassicality test. The result of three-mode beam-splitter action after coupling to an ancilla in the ground state is treated in the same spirit. The concept of genuine tripartite entanglement, and scalar measures of nonclassicality at the Mandel level for two-mode systems, are discussed. Numerous examples illustrating all these concepts are presented.

Parallel computing concepts and methods for floquet analysis of helicopter trim and stability

Floquet analysis is widely used for small-order systems (say, order M < 100) to find trim results of control inputs and periodic responses, and stability results of damping levels and frequencies, Presently, however, it is practical neither for design applications nor for comprehensive analysis models that lead to large systems (M > 100); the run time on a sequential computer is simply prohibitive, Accordingly, a massively parallel Floquet analysis is developed with emphasis on large systems, and it is implemented on two SIMD or single-instruction, multiple-data computers with 4096 and 8192 processors, The focus of this development is a parallel shooting method with damped Newton iteration to generate trim results; the Floquet transition matrix (FTM) comes out as a byproduct, The eigenvalues and eigenvectors of the FTM are computed by a parallel QR method, and thereby stability results are generated, For illustration, flap and flap-lag stability of isolated rotors are treated by the parallel analysis and by a corresponding sequential analysis with the conventional shooting and QR methods; linear quasisteady airfoil aerodynamics and a finite-state three-dimensional wake model are used, Computational reliability is quantified by the condition numbers of the Jacobian matrices in Newton iteration, the condition numbers of the eigenvalues and the residual errors of the eigenpairs, and reliability figures are comparable in both the parallel and sequential analyses, Compared to the sequential analysis, the parallel analysis reduces the run time of large systems dramatically, and the reduction increases with increasing system order; this finding offers considerable promise for design and comprehensive-analysis applications.

Nonequilibrium phase transitions in a driven sandpile model

We construct a driven sandpile slope model and study it by numerical simulations in one dimension. The model is specified by a threshold slope sigma(c), a parameter alpha, governing the local current-slope relation (beyond threshold), and j(in), the mean input current of sand. A non-equilibrium phase diagram is obtained in the alpha-j(in) plane. We find an infinity of phases, characterized by different mean slopes and separated by continuous or first-order boundaries, some of which we obtain analytically. Extensions to two dimensions are discussed.z

Physics with e(+)e(-) linear colliders

The physics potential of e(+) e(-) linear colliders is summarized in this report. These machines are planned to operate in the first phase at a center-of-mass energy of 500 GeV, before being scaled up to about 1 TeV. In the second phase of the operation, a final energy of about 2 TeV is expected. The machines will allow us to perform precision tests of the heavy particles in the Standard Model, the top quark and the electroweak bosons. They are ideal facilities for exploring the properties of Higgs particles, in particular in the intermediate mass range. New vector bosons and novel matter particles in extended gauge theories can be searched for and studied thoroughly. The machines provide unique opportunities for the discovery of particles in supersymmetric extensions of the Standard Model, the spectrum of Higgs particles, the supersymmetric partners of the electroweak gauge and Higgs bosons, and of the matter particles. High precision analyses of their properties and interactions will allow for extrapolations to energy scales close to the Planck scale where gravity becomes significant. In alternative scenarios, i.e. compositeness models, novel matter particles and interactions can be discovered and investigated in the energy range above the existing colliders lip to the TeV scale. Whatever scenario is realized in Nature, the discovery potential of e(+) e(-) linear colliders and the high precision with which the properties of particles and their interactions can be analyzed, define an exciting physics program complementary to hadron machines. (C) 1998 Elsevier Science B.V. All rights reserved.