Faster Algorithms for Incremental Topological Ordering.Robert Tarjan

We present two online algorithms for maintaining a topological order of a directed acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm takes O(m 1/2) amortized time per arc and our second algorithm takes O(n 2.5/m) amortized time per arc, where n is the number of vertices and m is the total number of arcs. For sparse graphs, our O(m 1/2) bound improves the best previous bound by a factor of logn and is tight to within a constant factor for a natural class of algorithms that includes all the existing ones. Our main insight is that the two-way search method of previous algorithms does not require an ordered search, but can be more general, allowing us to avoid the use of heaps (priority queues). Instead, the deterministic version of our algorithm uses (approximate) median-finding; the randomized version of our algorithm uses uniform random sampling. For dense graphs, our O(n 2.5/m) bound improves the best previously published bound by a factor of n 1/4 and a recent bound obtained independently of our work by a factor of logn. Our main insight is that graph search is wasteful when the graph is dense and can be avoided by searching the topological order space instead. Our algorithms extend to the maintenance of strong components, in the same asymptotic time bounds.

Incremental natural-gradient actor-critic algorithms

We present four new reinforcement learning algorithms based on actor-critic and natural-gradient ideas, and provide their convergence proofs. Actor-critic rein- forcement learning methods are online approximations to policy iteration in which the value-function parameters are estimated using temporal difference learning and the policy parameters are updated by stochastic gradient descent. Methods based on policy gradients in this way are of special interest because of their com- patibility with function approximation methods, which are needed to handle large or infinite state spaces. The use of temporal difference learning in this way is of interest because in many applications it dramatically reduces the variance of the gradient estimates. The use of the natural gradient is of interest because it can produce better conditioned parameterizations and has been shown to further re- duce variance in some cases. Our results extend prior two-timescale convergence results for actor-critic methods by Konda and Tsitsiklis by using temporal differ- ence learning in the actor and by incorporating natural gradients, and they extend prior empirical studies of natural actor-critic methods by Peters, Vijayakumar and Schaal by providing the first convergence proofs and the first fully incremental algorithms.

Relation between Local Structure and Glass Forming Ability of Liquid Alloys

An attempt has been made to describe the glass forming ability (GFA) of liquid alloys, using the concepts of the short range order (SRO) and middle range order (MRO) characterizing the liquid structure.A new approach to obtain good GFA of liquid alloys is based on the following four main factors: (1) formation of new SRO and competitive correlation with two or more kinds of SROs for crystallization, (2) stabilization of dense random packing by interaction between different types of SRO, (3) formation of stable cluster (SC) or middle range order (MRO) by harmonious coupling of SROs, and (4) difference between SRO characterizing the liquid structure and the near-neighbor environment in the corresponding equilibrium crystalline phases. The atomic volume mismatch estimated from the cube of the atomic radius was found to be a close relation with the minimum solute concentration for glass formation. This empirical guideline enables us to provide the optimum solute concentration for good GFA in some ternary alloys. Model structures, denoted by Bernal type and the Chemical Order type, were again tested in the novel description for the glass structure as a function of solute concentration. We illustrated the related energetics of the completion between crystal embryo and different types of SRO. Recent systematic measurements also provide that thermal diffusivity of alloys in the liquid state may be a good indicator of their GFA.

Modified McMurray Inverter with Pulse Forming Network Commutation Circuits

The modified McMurray Inverter with Pulse Forming Network (PFN) has been explained. The current and voltage waveshapes of the PFN commutation ci rcuit have been compared with conventional L-commutation circuit. The design method of PFN has been explained. Advantages of this type of commutation have been discussed. Experimental results are given.

Efficacies of multivalent vs monovalent poly(ether imine) dendritic catalysts within a generation in multiple C-C bond forming reactions

Dendrimers are ideal platforms to study multivalent effects due to the presence of uniform end groups at their peripheries. This report concerns with a study of multivalent dendritic catalysts, both within and across dendrimer generations, and their effects to mediate C-C bond forming reactions on multivalent substrates that have two and three acrylate reactive sites. As many as fourteen multivalent dendritic catalysts were prepared using 0-3 generations of poly(propyl ether imine) dendrimers, incorporated with Pd(II) catalytic sites, both within and across the dendrimer generations. C-C Bond forming reactions of these substrates with iodobenzene, mediated by uniform concentration of the metal across all catalysts, showed formation of partially and fully functionalized cinnamates in varying ratios, depending on the extent of clustering of catalytic moieties at the peripheries of dendrimers within a dendrimer generation. In a given generation, higher clustering of catalytic moieties greatly assisted multiple C-C bond formations than presenting the same in lesser number. The studies demonstrate true benefits of clustering catalytic moieties within a dendrimer generation and the beneficial effects applicable to catalysis of substrates presenting more than one reactive center. (C) 2011 Elsevier B.V. All rights reserved.

The omega phase formation during laser cladding and remelting of quasicrystal forming AlCuFe on pure aluminum

We report the formation omega phase in the remelted layers during laser cladding and remelting of quasicrystal forming Al65Cu23.3Fe11.7 alloy on pure aluminum. The omega phase is absent in the clad layers. In the remelted layer, the phase nucleates at the periphery of the primary icosahedral phase particles. A large number of omega phase particles forms enveloping the icosahedral phase growing into aluminum rich melt, which solidify as alpha-Al solid solution. On the other side it develops an interface with aluminum. A detailed transmission electron microscopic analysis shows that omega phase exhibits orientation relationship with icosahedral phase. The composition analysis performed using energy dispersive x-ray analyzer suggests that this phase has composition higher aluminum than the icosahedral phase. The analysis of the available phase diagram information indicates that the present results represent large departure from equilibrium conditions. A possible scenario of the evolution of the omega phase has been suggested.

Characterization of the dynamics of glass-forming liquids from the properties of the potential energy landscape

We develop a framework for understanding the difference between strong and fragile behavior in the dynamics of glass-forming liquids from the properties of the potential energy landscape. Our approach is based on a master equation description of the activated jump dynamics among the local minima of the potential energy (the so-called inherent structures) that characterize the potential energy landscape of the system. We study the dynamics of a small atomic cluster using this description as well as molecular dynamics simulations and demonstrate the usefulness of our approach for this system. Many of the remarkable features of the complex dynamics of glassy systems emerge from the activated dynamics in the potential energy landscape of the atomic cluster. The dynamics of the system exhibits typical characteristics of a strong supercooled liquid when the system is allowed to explore the full configuration space. This behavior arises because the dynamics is dominated by a few lowest-lying minima of the potential energy and the potential energy barriers between these minima. When the system is constrained to explore only a limited region of the potential energy landscape that excludes the basins of attraction of a few lowest-lying minima, the dynamics is found to exhibit the characteristics of a fragile liquid.

Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance

We present two online algorithms for maintaining a topological order of a directed n-vertex acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm handles m arc additions in O(m(3/2)) time. For sparse graphs (m/n = O(1)), this bound improves the best previous bound by a logarithmic factor, and is tight to within a constant factor among algorithms satisfying a natural locality property. Our second algorithm handles an arbitrary sequence of arc additions in O(n(5/2)) time. For sufficiently dense graphs, this bound improves the best previous bound by a polynomial factor. Our bound may be far from tight: we show that the algorithm can take Omega(n(2)2 root(2lgn)) time by relating its performance to a generalization of the k-levels problem of combinatorial geometry. A completely different algorithm running in Theta (n(2) log n) time was given recently by Bender, Fineman, and Gilbert. We extend both of our algorithms to the maintenance of strong components, without affecting the asymptotic time bounds.

Adam-Gibbs Relation for Glass-Forming Liquids in Two, Three, and Four Dimensions

The Adam-Gibbs relation between relaxation times and the configurational entropy has been tested extensively for glass formers using experimental data and computer simulation results. Although the form of the relation contains no dependence on the spatial dimensionality in the original formulation, subsequent derivations of the Adam-Gibbs relation allow for such a possibility. We test the Adam-Gibbs relation in two, three, and four spatial dimensions using computer simulations of model glass formers. We find that the relation is valid in three and four dimensions. But in two dimensions, the relation does not hold, and interestingly, no single alternate relation describes the results for the different model systems we study.

Analysis of Strain Rates and Microstructural Evaluation during Metal Forming: Role of Surface Texture and Friction

The surface texture of a die plays an important role in friction during metal forming. In the present study, unidirectional and random surface finishes were produced on hardened steel plate surfaces. To understand the influence of surface texture on friction, experiments were conducted using Al-Mg alloy pins that slid against steel plates of different surface textures. In the sliding experiments, a high coefficient of friction was observed when the pins slid perpendicular to the unidirectional grinding marks and low friction occurred when the pins slid on the random surfaces. Finite element simulations were performed using the measured friction values to understand the stress and strain evolutions in the deforming material using dies with various friction. The numerical results showed that the states of stress and strain rates are strongly influenced by the friction at the interface and hence would influence the final material microstructure. To substantiate the numerical results, laboratory compression tests were conducted. Different surface textures were obtained in order to experience different friction values at different locations. A large variation in the microstructure at these locations was observed during experiments, verifying that surface texture and die friction significantly influence fundamental material formation behavior.

Damage limit states of reinforced concrete beams subjected to incremental cyclic loading using relaxation ratio analysis of AE parameters

This paper presents an experimental study on damage assessment of reinforced concrete (RC) beams subjected to incremental cyclic loading. During testing acoustic emissions (AEs) were recorded. The analysis of the AE released was carried out by using parameters relaxation ratio, load ratio and calm ratio. Digital image correlation (DIC) technique and tracking with available MATLAB program were used to measure the displacement and surface strains in concrete. Earlier researchers classified the damage in RC beams using Kaiser effect, crack mouth opening displacement and proposed a standard. In general (or in practical situations), multiple cracks occur in reinforced concrete beams. In the present study damage assessment in RC beams was studied according to different limit states specified by the code of practice IS-456:2000 and AE technique. Based on the two ratios namely load ratio and calm ratio and when the deflection reached approximately 85% of the maximum allowable deflection it was observed that the RC beams were heavily damaged. The combination of AE and DIC techniques has the potential to provide the state of damage in RC structures.