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 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.

Exploiting the Structure of the Constraint Graph for Efficient Points-to Analysis

Points-to analysis is a key compiler analysis. Several memory related optimizations use points-to information to improve their effectiveness. Points-to analysis is performed by building a constraint graph of pointer variables and dynamically updating it to propagate more and more points-to information across its subset edges. So far, the structure of the constraint graph has been only trivially exploited for efficient propagation of information, e.g., in identifying cyclic components or to propagate information in topological order. We perform a careful study of its structure and propose a new inclusion-based flow-insensitive context-sensitive points-to analysis algorithm based on the notion of dominant pointers. We also propose a new kind of pointer-equivalence based on dominant pointers which provides significantly more opportunities for reducing the number of pointers tracked during the analysis. Based on this hitherto unexplored form of pointer-equivalence, we develop a new context-sensitive flow-insensitive points-to analysis algorithm which uses incremental dominator update to efficiently compute points-to information. Using a large suite of programs consisting of SPEC 2000 benchmarks and five large open source programs we show that our points-to analysis is 88% faster than BDD-based Lazy Cycle Detection and 2x faster than Deep Propagation. We argue that our approach of detecting dominator-based pointer-equivalence is a key to improve points-to analysis efficiency.

Quench dynamics and parity blocking in Majorana wires

We theoretically explore quench dynamics in a finite-sized topological fermionic p-wave superconducting wire with the goal of demonstrating that topological order can have marked effects on such non-equilibrium dynamics. In the case studied here, topological order is reflected in the presence of two (nearly) isolated Majorana fermionic end bound modes together forming an electronic state that can be occupied or not, leading to two (nearly) degenerate ground states characterized by fermion parity. Our study begins with a characterization of the static properties of the finite-sized wire, including the behavior of the Majorana end modes and the form of the tunnel coupling between them; a transfer matrix approach to analytically determine the locations of the zero energy contours where this coupling vanishes; and a Pfaffian approach to map the ground state parity in the associated phase diagram. We next study the quench dynamics resulting from initializing the system in a topological ground state and then dynamically tuning one of the parameters of the Hamiltonian. For this, we develop a dynamic quantum many-body technique that invokes a Wick's theorem for Majorana fermions, vastly reducing the numerical effort given the exponentially large Hilbert space. We investigate the salient and detailed features of two dynamic quantities-the overlap between the time-evolved state and the instantaneous ground state (adiabatic fidelity) and the residual energy. When the parity of the instantaneous ground state flips successively with time, we find that the time-evolved state can dramatically switch back and forth between this state and an excited state even when the quenching is very slow, a phenomenon that we term `parity blocking'. This parity blocking becomes prominently manifest as non-analytic jumps as a function of time in both dynamic quantities.

Bond-order wave phase, spin solitons, and thermodynamics of a frustrated linear spin-1/2 Heisenberg antiferromagnet

The linear spin-1/2 Heisenberg antiferromagnet with exchanges J(1) and J(2) between first and second neighbors has a bond-order wave (BOW) phase that starts at the fluid-dimer transition at J(2)/J(1)=0.2411 and is particularly simple at J(2)/J(1)=1/2. The BOW phase has a doubly degenerate singlet ground state, broken inversion symmetry, and a finite-energy gap E-m to the lowest-triplet state. The interval 0.4 < J(2)/J(1) < 1.0 has large E-m and small finite-size corrections. Exact solutions are presented up to N = 28 spins with either periodic or open boundary conditions and for thermodynamics up to N = 18. The elementary excitations of the BOW phase with large E-m are topological spin-1/2 solitons that separate BOWs with opposite phase in a regular array of spins. The molar spin susceptibility chi(M)(T) is exponentially small for T << E-m and increases nearly linearly with T to a broad maximum. J(1) and J(2) spin chains approximate the magnetic properties of the BOW phase of Hubbard-type models and provide a starting point for modeling alkali-tetracyanoquinodimethane salts.

Topological defects in crystals: A density-wave theory

A new approach for describing dislocations and other topological defects in crystals, based on the density wave theory of Ramakrishnan and Yussouff is presented. Quantitative calculations are discussed in brief for the order parameter profiles, the atomic configuration and the free energy of a screw dislocation with Burgers vector b = (a/2, a/2,a/2 ) in a bcc solid. Our results for the free energy of the dislocation in a crystal of sizeR, when expressed as (λb 2/4π) ln (αR/|b|) whereλ is the shear elastic constant, yield, for example, the valueα ⋍ 1·85 for sodium at its freezing temperature (371°K). The density distribution in the presence of the dislocation shows that the dislocation core has a columnar character. To our knowledge, this study represents the first calculation of dislocation structure, including the core, within the framework of an order parameter theory incorporating thermal effects.

Euclideanization, topological theories, higher dimensions and all that

It is shown that the euclideanized Yukawa theory, with the Dirac fermion belonging to an irreducible representation of the Lorentz group, is not bounded from below. A one parameter family of supersymmetric actions is presented which continuously interpolates between the N = 2 SSYM and the N = 2 supersymmetric topological theory. In order to obtain a theory which is bounded from below and satisfies Osterwalder-Schrader positivity, the Dirac fermion should belong to a reducible representation of the Lorentz group and the scalar fields have to be reinterpreted as the extra components of a higher dimensional vector field.

Quantum destruction of spiral order in two-dimensional frustrated magnets

We study the fate of spin-1/2 spiral-ordered two-dimensional quantum antiferromagnets that are disordered by quantum fluctuations. A crucial role is played by the topological point defects of the spiral phase, which are known to have a Z(2) character. Previous works established that a nontrivial quantum spin-liquid phase results when the spiral is disordered without proliferating the Z(2) vortices. Here, we show that when the spiral is disordered by proliferating and condensing these vortices, valence-bond solid ordering occurs due to quantum Berry phase effects. We develop a general theory for this latter phase transition and apply it to a lattice model. This transition potentially provides a new example of a Landau-forbidden deconfined quantum critical point.

Topological analysis of general linear networks

A new method of network analysis, a generalization in several different senses of existing methods and applicable to all networks for which a branch-admittance (or impedance) matrix can be formed, is presented. The treatment of network determinants is very general and essentially four terminal rather than three terminal, and leads to simple expressions based on trees of a simple graph associated with the network and matrix, and involving products of low-order, usually(2 times 2)determinants of tree-branch admittances, in addition to tree-branch products as in existing methods. By comparison with existing methods, the total number of trees and of tree pairs is usually considerably reduced, and this fact, together with an easy method of tree-pair sign determination which is also presented, makes the new method simpler in general. The method can be very easily adapted, by the use of infinite parameters, to accommodate ideal transformers, operational amplifiers, and other forms of network constraint; in fact, is thought to be applicable to all linear networks.

Transport across a junction of topological insulators and a superconductor

We study transport across a line junction lying between two orthogonal topological insulator surfaces and a superconductor which can have either s-wave (spin-singlet) or p-wave (spin-triplet) pairing symmetry. The junction can have three time-reversal invariant barriers on three sides. We compute the charge and the spin conductance across such a junction and study their behaviors as a function of the bias voltage applied across the junction and the three parameters used to characterize the barrier. We find that the presence of topological insulators and a superconductor leads to both Dirac- and Schrodinger-like features in charge and spin conductances. We discuss the effect of bound states on the superconducting side of the barrier on the conductance; in particular, we show that for triplet p-wave superconductors, such a junction may be used to determine the spin state of its Cooper pairs. Our study reveals that there is a nonzero spin conductance for some particular spin states of the triplet Cooper pairs; this is an effect of the topological insulators which break the spin rotation symmetry. Finally, we find an unusual satellite peak (in addition to the usual zero bias peak) in the spin conductance for p-wave symmetry of the superconductor order parameter.

Shock propagation in gas dynamics: explicit form of higher order compatibility conditions

With the use of tensor analysis and the method of singular surfaces, an infinite system of equations can be derived to study the propagation of curved shocks of arbitrary strength in gas dynamics. The first three of these have been explicitly given here. This system is further reduced to one involving scalars only. The choice of dependent variables in the infinite system is quite important, it leads to coefficients free from singularities for all values of the shock strength.

Topological mimicry and epitope duplication in the guanylyl cyclase C receptor

Guanylyl cyclase C (GCC) is the receptor for the gastrointestinal hormones, guanylin, and uroguanylin, in addition to the bacterial heat-stable enterotoxins, which are one of the major causes of watery diarrhea the world over. GCC is expressed in intestinal cells, colorectal tumor tissue and tumors originating from metastasis of the colorectal carcinoma. We have earlier generated a monoclonal antibody to human GCC, GCC:B10, which was useful for the immunohistochemical localization of the receptor in the rat intestine (Nandi A et al., 1997, J Cell Biochem 66:500-511), and identified its epitope to a 63-amino acid stretch in the intracellular domain of GCC. In view of the potential that this antibody has for the identification of colorectal tumors, we have characterized the epitope for GCC:B10 in this study. Overlapping peptide synthesis indicated that the epitope was contained in the sequence HIPPENIFPLE. This sequence was unique to GCC, and despite a short stretch of homology with serum amyloid protein and pertussis toxin, no cross reactivity was detected. The core epitope was delineated using a random hexameric phage display library, and two categories of sequences were identified, containing either a single, or two adjacent proline residues. No sequence identified by phage display was identical to the epitope present in GCC, indicating that phage sequences represented mimotopes of the native epitope. Alignment of these sequences with HIPPENIFPLE suggested duplication of the recognition motif, which was confirmed by peptide synthesis. These studies allowed us not only to define the requirements of epitope recognition by GCC:B10 monoclonal antibody, but also to describe a novel means of epitope recognition involving topological mimicry and probable duplication of the cognate epitope in the native guanylyl cyclase C receptor sequence.

Fault-tolerant characteristics and topological properties of a hierarchical network of hypercubes

We analyse the fault-tolerant parameters and topological properties of a hierarchical network of hypercubes. We take a close look at the Extended Hypercube (EH) and the Hyperweave (HW) architectures and also compare them with other popular architectures. These two architectures have low diameter and constant degree of connectivity making it possible to expand these networks without affecting the existing configuration. A scheme for incrementally expanding this network is also presented. We also look at the performance of the ASCEND/DESCEND class of algorithms on these architectures.

Maximal regularity for second order non-autonomous Cauchy problems

We consider some non-autonomous second order Cauchy problems of the form u + B(t)(u) over dot + A(t)u = f (t is an element of [0, T]), u(0) = (u) over dot(0) = 0. We assume that the first order problem (u) over dot + B(t)u = f (t is an element of [0, T]), u(0) = 0, has L-p-maximal regularity. Then we establish L-p-maximal regularity of the second order problem in situations when the domains of B(t(1)) and A(t(2)) always coincide, or when A(t) = kappa B(t).

Higher-Order Nonlinearity In Accretion Disks: Quasi-Periodic Oscillations Of Black Hole And Neutron Star Sources And Their Spin

We propose a unified model to explain Quasi-Periodic Oscillation (QPO), particularly of high frequency, observed from black hole and neutron star systems globally. We consider accreting systems to be damped harmonic oscillators exhibiting epicyclic oscillations with higher-order nonlinear resonance to explain QPO. The resonance is expected to be driven by the disturbance from the compact object at its spin frequency. The model explains various properties parallelly for both types of the compact object. It describes QPOs successfully for ten different compact sources. Based on this, we predict the spin frequency of the neutron star Sco X-1 and specific angular momentum of black holes GRO J1655–40, XTE J1550–564, H1743–322, and GRS 1915+105.