Boxicity and Poset Dimension

Let G be a simple, undirected, finite graph with vertex set V (G) and edge set E(G). A k-dimensional box is a Cartesian product of closed intervals [a(1), b(1)] x [a(2), b(2)] x ... x [a(k), b(k)]. The boxicity of G, box(G), is the minimum integer k such that G can be represented as the intersection graph of k-dimensional boxes; i.e., each vertex is mapped to a k-dimensional box and two vertices are adjacent in G if and only if their corresponding boxes intersect. Let P = (S, P) be a poset, where S is the ground set and P is a reflexive, antisymmetric and transitive binary relation on S. The dimension of P, dim(P), is the minimum integer t such that P can be expressed as the intersection of t total orders. Let G(P) be the underlying comparability graph of P; i.e., S is the vertex set and two vertices are adjacent if and only if they are comparable in P. It is a well-known fact that posets with the same underlying comparability graph have the same dimension. The first result of this paper links the dimension of a poset to the boxicity of its underlying comparability graph. In particular, we show that for any poset P, box(G(P))/(chi(G(P)) - 1) <= dim(P) <= 2box(G(P)), where chi(G(P)) is the chromatic number of G(P) and chi(G(P)) not equal 1. It immediately follows that if P is a height-2 poset, then box(G(P)) <= dim(P) <= 2box(G(P)) since the underlying comparability graph of a height-2 poset is a bipartite graph. The second result of the paper relates the boxicity of a graph G with a natural partial order associated with the extended double cover of G, denoted as G(c): Note that G(c) is a bipartite graph with partite sets A and B which are copies of V (G) such that, corresponding to every u is an element of V (G), there are two vertices u(A) is an element of A and u(B) is an element of B and {u(A), v(B)} is an edge in G(c) if and only if either u = v or u is adjacent to v in G. Let P(c) be the natural height-2 poset associated with G(c) by making A the set of minimal elements and B the set of maximal elements. We show that box(G)/2 <= dim(P(c)) <= 2box(G) + 4. These results have some immediate and significant consequences. The upper bound dim(P) <= 2box(G(P)) allows us to derive hitherto unknown upper bounds for poset dimension such as dim(P) = 2 tree width (G(P)) + 4, since boxicity of any graph is known to be at most its tree width + 2. In the other direction, using the already known bounds for partial order dimension we get the following: (1) The boxicity of any graph with maximum degree Delta is O(Delta log(2) Delta), which is an improvement over the best-known upper bound of Delta(2) + 2. (2) There exist graphs with boxicity Omega(Delta log Delta). This disproves a conjecture that the boxicity of a graph is O(Delta). (3) There exists no polynomial-time algorithm to approximate the boxicity of a bipartite graph on n vertices with a factor of O(n(0.5-is an element of)) for any is an element of > 0 unless NP = ZPP.

Algorithmic approach to simulate Hamiltonian dynamics and an NMR simulation of quantum state transfer

We propose an iterative algorithm to simulate the dynamics generated by any n-qubit Hamiltonian. The simulation entails decomposing the unitary time evolution operator U (unitary) into a product of different time-step unitaries. The algorithm product-decomposes U in a chosen operator basis by identifying a certain symmetry of U that is intimately related to the number of gates in the decomposition. We illustrate the algorithm by first obtaining a polynomial decomposition in the Pauli basis of the n-qubit quantum state transfer unitary by Di Franco et al. [Phys. Rev. Lett. 101, 230502 (2008)] that transports quantum information from one end of a spin chain to the other, and then implement it in nuclear magnetic resonance to demonstrate that the decomposition is experimentally viable. We further experimentally test the resilience of the state transfer to static errors in the coupling parameters of the simulated Hamiltonian. This is done by decomposing and simulating the corresponding imperfect unitaries.

The inhomogeneous extended Bose-Hubbard model: A mean-field theory

We develop an inhomogeneous mean-field theory for the extended Bose-Hubbard model with a quadratic, confining potential. In the absence of this potential, our mean-field theory yields the phase diagram of the homogeneous extended Bose-Hubbard model. This phase diagram shows a superfluid (SF) phase and lobes of Mott-insulator (MI), density-wave (DW), and supersolid (SS) phases in the plane of the chemical potential mu and on-site repulsion U; we present phase diagrams for representative values of V, the repulsive energy for bosons on nearest-neighbor sites. We demonstrate that, when the confining potential is present, superfluid and density-wave order parameters are nonuniform; in particular, we obtain, for a few representative values of parameters, spherical shells of SF, MI, DW, and SS phases. We explore the implications of our study for experiments on cold-atom dipolar condensates in optical lattices in a confining potential.

High-Performance Metal-Insulator-Metal Capacitors Using Europium Oxide as Dielectric

We report the first demonstration of metal-insulator-metal (MIM) capacitors with Eu2O3 dielectric for analog and DRAM applications. The influence of different anneal conditions on the electrical characteristics of the fabricated MIM capacitors is studied. FG anneal results in high capacitance density (7 fF/mu m(2)), whereas oxygen anneal results in low quadratic voltage coefficient of capacitance (VCC) (194 ppm/V-2 at 100 kHz), and argon anneal results in low leakage current density (3.2 x 10(-8) A/cm(2) at -1 V). We correlate these electrical results with the surface chemical states of the films through X-ray photoelectron spectroscopy measurements. In particular, FG anneal and argon anneal result in sub-oxides, which modulate the electrical properties.

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.

Pricing Defaultable Bonds in a Markov Modulated Market

We address the problem of pricing defaultable bonds in a Markov modulated market. Using Merton's structural approach we show that various types of defaultable bonds are combination of European type contingent claims. Thus pricing a defaultable bond is tantamount to pricing a contingent claim in a Markov modulated market. Since the market is incomplete, we use the method of quadratic hedging and minimal martingale measure to derive locally risk minimizing derivative prices, hedging strategies and the corresponding residual risks. The price of defaultable bonds are obtained as solutions to a system of PDEs with weak coupling subject to appropriate terminal and boundary conditions. We solve the system of PDEs numerically and carry out a numerical investigation for the defaultable bond prices. We compare their credit spreads with some of the existing models. We observe higher spreads in the Markov modulated market. We show how business cycles can be easily incorporated in the proposed framework. We demonstrate the impact on spreads of the inclusion of rare states that attempt to capture a tight liquidity situation. These states are characterized by low risk-free interest rate, high payout rate and high volatility.

Two-dimensional flow past circular cylinders using finite volume lattice Boltzmann formulation

In this article, an extension to the total variation diminishing finite volume formulation of the lattice Boltzmann equation method on unstructured meshes was presented. The quadratic least squares procedure is used for the estimation of first-order and second-order spatial gradients of the particle distribution functions. The distribution functions were extrapolated quadratically to the virtual upwind node. The time integration was performed using the fourth-order RungeKutta procedure. A grid convergence study was performed in order to demonstrate the order of accuracy of the present scheme. The formulation was validated for the benchmark two-dimensional, laminar, and unsteady flow past a single circular cylinder. These computations were then investigated for the low Mach number simulations. Further validation was performed for flow past two circular cylinders arranged in tandem and side-by-side. Results of these simulations were extensively compared with the previous numerical data. Copyright (C) 2011 John Wiley & Sons, Ltd.

Practical fully three-dimensional reconstruction algorithms for diffuse optical tomography

We have developed an efficient fully three-dimensional (3D) reconstruction algorithm for diffuse optical tomography (DOT). The 3D DOT, a severely ill-posed problem, is tackled through a pseudodynamic (PD) approach wherein an ordinary differential equation representing the evolution of the solution on pseudotime is integrated that bypasses an explicit inversion of the associated, ill-conditioned system matrix. One of the most computationally expensive parts of the iterative DOT algorithm, the reevaluation of the Jacobian in each of the iterations, is avoided by using the adjoint-Broyden update formula to provide low rank updates to the Jacobian. In addition, wherever feasible, we have also made the algorithm efficient by integrating along the quadratic path provided by the perturbation equation containing the Hessian. These algorithms are then proven by reconstruction, using simulated and experimental data and verifying the PD results with those from the popular Gauss-Newton scheme. The major findings of this work are as follows: (i) the PD reconstructions are comparatively artifact free, providing superior absorption coefficient maps in terms of quantitative accuracy and contrast recovery; (ii) the scaling of computation time with the dimension of the measurement set is much less steep with the Jacobian update formula in place than without it; and (iii) an increase in the data dimension, even though it renders the reconstruction problem less ill conditioned and thus provides relatively artifact-free reconstructions, does not necessarily provide better contrast property recovery. For the latter, one should also take care to uniformly distribute the measurement points, avoiding regions close to the source so that the relative strength of the derivatives for measurements away from the source does not become insignificant. (c) 2012 Optical Society of America

Piecewise Linearization Technique for Compact Charge Modeling of Independent DG MOSFET

Charge linearization techniques have been used over the years in advanced compact models for bulk and double-gate MOSFETs in order to approximate the position along the channel as a quadratic function of the surface potential (or inversion charge densities) so that the terminal charges can be expressed as a compact closed-form function of source and drain end surface potentials (or inversion charge densities). In this paper, in case of the independent double-gate MOSFETs, we show that the same technique could be used to model the terminal charges quite accurately only when the 1-D Poisson solution along the channel is fully hyperbolic in nature or the effective gate voltages are same. However, for other bias conditions, it leads to significant error in terminal charge computation. We further demonstrate that the amount of nonlinearity that prevails between the surface potentials along the channel actually dictates if the conventional charge linearization technique could be applied for a particular bias condition or not. Taking into account this nonlinearity, we propose a compact charge model, which is based on a novel piecewise linearization technique and shows excellent agreement with numerical and Technology Computer-Aided Design (TCAD) simulations for all bias conditions and also preserves the source/drain symmetry which is essential for Radio Frequency (RF) circuit design. The model is implemented in a professional circuit simulator through Verilog-A, and simulation examples for different circuits verify good model convergence.

Bose-Hubbard models in confining potentials: Inhomogeneous mean-field theory

We present an extensive study of Mott insulator (MI) and superfluid (SF) shells in Bose-Hubbard (BH) models for bosons in optical lattices with harmonic traps. For this we apply the inhomogeneous mean-field theory developed by Sheshadri et al. Phys. Rev. Lett. 75, 4075 (1995)]. Our results for the BH model with one type of spinless bosons agree quantitatively with quantum Monte Carlo simulations. Our approach is numerically less intensive than such simulations, so we are able to perform calculations on experimentally realistic, large three-dimensional systems, explore a wide range of parameter values, and make direct contact with a variety of experimental measurements. We also extend our inhomogeneous mean-field theory to study BH models with harmonic traps and (a) two species of bosons or (b) spin-1 bosons. With two species of bosons, we obtain rich phase diagrams with a variety of SF and MI phases and associated shells when we include a quadratic confining potential. For the spin-1 BH model, we show, in a representative case, that the system can display alternating shells of polar SF and MI phases, and we make interesting predictions for experiments in such systems.

Conflict-Free Coloring for Rectangle Ranges Using O(n.382) Colors

Given a set of points P ⊆ R2, a conflict-free coloring of P w.r.t. rectangle ranges is an assignment of colors to points of P, such that each nonempty axisparallel rectangle T in the plane contains a point whose color is distinct from all other points in P ∩ T . This notion has been the subject of recent interest and is motivated by frequency assignment in wireless cellular networks: one naturally would like to minimize the number of frequencies (colors) assigned to base stations (points) such that within any range (for instance, rectangle), there is no interference. We show that any set of n points in R2 can be conflict-free colored with O(nβ∗+o(1)) colors in expected polynomial time, where β∗ = 3−√5 2 < 0.382.

An invariant subspace-based approach to the random eigenvalue problem of systems with clustered spectrum

The repeated or closely spaced eigenvalues and corresponding eigenvectors of a matrix are usually very sensitive to a perturbation of the matrix, which makes capturing the behavior of these eigenpairs very difficult. Similar difficulty is encountered in solving the random eigenvalue problem when a matrix with random elements has a set of clustered eigenvalues in its mean. In addition, the methods to solve the random eigenvalue problem often differ in characterizing the problem, which leads to different interpretations of the solution. Thus, the solutions obtained from different methods become mathematically incomparable. These two issues, the difficulty of solving and the non-unique characterization, are addressed here. A different approach is used where instead of tracking a few individual eigenpairs, the corresponding invariant subspace is tracked. The spectral stochastic finite element method is used for analysis, where the polynomial chaos expansion is used to represent the random eigenvalues and eigenvectors. However, the main concept of tracking the invariant subspace remains mostly independent of any such representation. The approach is successfully implemented in response prediction of a system with repeated natural frequencies. It is found that tracking only an invariant subspace could be sufficient to build a modal-based reduced-order model of the system. Copyright (C) 2012 John Wiley & Sons, Ltd.

On maximum entropy and minimum KL-divergence optimization by Grobner basis methods

In this paper we study constrained maximum entropy and minimum divergence optimization problems, in the cases where integer valued sufficient statistics exists, using tools from computational commutative algebra. We show that the estimation of parametric statistical models in this case can be transformed to solving a system of polynomial equations. We give an implicit description of maximum entropy models by embedding them in algebraic varieties for which we give a Grobner basis method to compute it. In the cases of minimum KL-divergence models we show that implicitization preserves specialization of prior distribution. This result leads us to a Grobner basis method to embed minimum KL-divergence models in algebraic varieties. (C) 2012 Elsevier Inc. All rights reserved.

Surrogate based design optimisation of composite aerofoil cross-section for helicopter vibration reduction

Design optimisation of a helicopter rotor blade is performed. The objective is to reduce helicopter vibration and constraints are put on frequencies and aeroelastic stability. The ply angles of the D-spar and skin of the composite rotor blade with NACA 0015 aerofoil section are considered as design variables. Polynomial response surfaces and space filling experimental designs are used to generate surrogate models of the objective function with respect to cross-section properties. The stacking sequence corresponding to the optimal cross-section is found using a real-coded genetic algorithm. Ply angle discretisation of 1 degrees, 15 degrees, 30 degrees and 45 degrees are used. The mean value of the objective function is used to find the optimal blade designs and the resulting designs are tested for variance. The optimal designs show a vibration reduction of 26% to 33% from the baseline design. A substantial reduction in vibration and an aeroelastically stable blade is obtained even after accounting for composite material uncertainty.

Algorithmic aspects of k-tuple total domination in graphs

For a fixed positive integer k, a k-tuple total dominating set of a graph G = (V. E) is a subset T D-k of V such that every vertex in V is adjacent to at least k vertices of T Dk. In minimum k-tuple total dominating set problem (MIN k-TUPLE TOTAL DOM SET), it is required to find a k-tuple total dominating set of minimum cardinality and DECIDE MIN k-TUPLE TOTAL DOM SET is the decision version of MIN k-TUPLE TOTAL DOM SET problem. In this paper, we show that DECIDE MIN k-TUPLE TOTAL DOM SET is NP-complete for split graphs, doubly chordal graphs and bipartite graphs. For chordal bipartite graphs, we show that MIN k-TUPLE TOTAL DOM SET can be solved in polynomial time. We also propose some hardness results and approximation algorithms for MIN k-TUPLE TOTAL DOM SET problem. (c) 2012 Elsevier B.V. All rights reserved.