Opportunistic splitting for scheduling via stochastic approximation

We consider the problem of scheduling a wireless channel among multiple users. A slot is given to a user with a highest metric (e.g., channel gain) in that slot. The scheduler may not know the channel states of all the users at the beginning of each slot. In this scenario opportunistic splitting is an attractive solution. However this algorithm requires that the metrics of different users form independent, identically distributed (iid) sequences with same distribution and that their distribution and number be known to the scheduler. This limits the usefulness of opportunistic splitting. In this paper we develop a parametric version of this algorithm. The optimal parameters of the algorithm are learnt online through a stochastic approximation scheme. Our algorithm does not require the metrics of different users to have the same distribution. The statistics of these metrics and the number of users can be unknown and also vary with time. We prove the convergence of the algorithm and show its utility by scheduling the channel to maximize its throughput while satisfying some fairness and/or quality of service constraints.

Modified kinetic flux vector splitting (m-KFVS) method for compressible flows

To resolve many flow features accurately, like accurate capture of suction peak in subsonic flows and crisp shocks in flows with discontinuities, to minimise the loss in stagnation pressure in isentropic flows or even flow separation in viscous flows require an accurate and low dissipative numerical scheme. The first order kinetic flux vector splitting (KFVS) method has been found to be very robust but suffers from the problem of having much more numerical diffusion than required, resulting in inaccurate computation of the above flow features. However, numerical dissipation can be reduced by refining the grid or by using higher order kinetic schemes. In flows with strong shock waves, the higher order schemes require limiters, which reduce the local order of accuracy to first order, resulting in degradation of flow features in many cases. Further, these schemes require more points in the stencil and hence consume more computational time and memory. In this paper, we present a low dissipative modified KFVS (m-KFVS) method which leads to improved splitting of inviscid fluxes. The m-KFVS method captures the above flow features more accurately compared to first order KFVS and the results are comparable to second order accurate KFVS method, by still using the first order stencil. (C) 2011 Elsevier Ltd. All rights reserved.

Fast edge splitting and Edmonds' arborescence construction for unweighted graphs

Given an unweighted undirected or directed graph with n vertices, m edges and edge connectivity c, we present a new deterministic algorithm for edge splitting. Our algorithm splits-off any specified subset S of vertices satisfying standard conditions (even degree for the undirected case and in-degree ≥ out-degree for the directed case) while maintaining connectivity c for vertices outside S in Õ(m+nc2) time for an undirected graph and Õ(mc) time for a directed graph. This improves the current best deterministic time bounds due to Gabow [8], who splits-off a single vertex in Õ(nc2+m) time for an undirected graph and Õ(mc) time for a directed graph. Further, for appropriate ranges of n, c, |S| it improves the current best randomized bounds due to Benczúr and Karger [2], who split-off a single vertex in an undirected graph in Õ(n2) Monte Carlo time. We give two applications of our edge splitting algorithms. Our first application is a sub-quadratic (in n) algorithm to construct Edmonds' arborescences. A classical result of Edmonds [5] shows that an unweighted directed graph with c edge-disjoint paths from any particular vertex r to every other vertex has exactly c edge-disjoint arborescences rooted at r. For a c edge connected unweighted undirected graph, the same theorem holds on the digraph obtained by replacing each undirected edge by two directed edges, one in each direction. The current fastest construction of these arborescences by Gabow [7] takes Õ(n2c2) time. Our algorithm takes Õ(nc3+m) time for the undirected case and Õ(nc4+mc) time for the directed case. The second application of our splitting algorithm is a new Steiner edge connectivity algorithm for undirected graphs which matches the best known bound of Õ(nc2 + m) time due to Bhalgat et al [3]. Finally, our algorithm can also be viewed as an alternative proof for existential edge splitting theorems due to Lovász [9] and Mader [11].

An operator-splitting finite element method for the efficient parallel solution of multidimensional population balance systems

A finite element method for solving multidimensional population balance systems is proposed where the balance of fluid velocity, temperature and solute partial density is considered as a two-dimensional system and the balance of particle size distribution as a three-dimensional one. The method is based on a dimensional splitting into physical space and internal property variables. In addition, the operator splitting allows to decouple the equations for temperature, solute partial density and particle size distribution. Further, a nodal point based parallel finite element algorithm for multi-dimensional population balance systems is presented. The method is applied to study a crystallization process assuming, for simplicity, a size independent growth rate and neglecting agglomeration and breakage of particles. Simulations for different wall temperatures are performed to show the effect of cooling on the crystal growth. Although the method is described in detail only for the case of d=2 space and s=1 internal property variables it has the potential to be extendable to d+s variables, d=2, 3 and s >= 1. (C) 2011 Elsevier Ltd. All rights reserved.

Phase separation by nanoparticle splitting

The present report illustrates the phenomenon of phase separation leading to the splitting of solid solution structured Ag-Co nanoparticles into pure Ag and pure Co nanoparticles upon isothermal annealing inside a transmission electron microscope. In bulk, Ag-Co system shows negligible mutual solubility into a single phase solid solution structure upto a very high temperature. The Ag-Co nanoparticle splitting revealed that room temperature, solid solution atomic configuration, between bulk immiscible Ag and Co atoms coexisting in a nano-sized particle, is a kinetically frozen atomic arrangement and not a thermodynamically stable structure. The observed phase separation behavior resulting in particle splitting at high temperatures can be used to produce devices for sensor applications. (C) 2011 Elsevier B.V. All rights reserved.

An operator-splitting Galerkin/SUPG finite element method for population balance equations : stability and convergence

We present a heterogeneous finite element method for the solution of a high-dimensional population balance equation, which depends both the physical and the internal property coordinates. The proposed scheme tackles the two main difficulties in the finite element solution of population balance equation: (i) spatial discretization with the standard finite elements, when the dimension of the equation is more than three, (ii) spurious oscillations in the solution induced by standard Galerkin approximation due to pure advection in the internal property coordinates. The key idea is to split the high-dimensional population balance equation into two low-dimensional equations, and discretize the low-dimensional equations separately. In the proposed splitting scheme, the shape of the physical domain can be arbitrary, and different discretizations can be applied to the low-dimensional equations. In particular, we discretize the physical and internal spaces with the standard Galerkin and Streamline Upwind Petrov Galerkin (SUPG) finite elements, respectively. The stability and error estimates of the Galerkin/SUPG finite element discretization of the population balance equation are derived. It is shown that a slightly more regularity, i.e. the mixed partial derivatives of the solution has to be bounded, is necessary for the optimal order of convergence. Numerical results are presented to support the analysis.

Operator-splitting finite element algorithms for computations of high-dimensional parabolic problems

An operator-splitting finite element method for solving high-dimensional parabolic equations is presented. The stability and the error estimates are derived for the proposed numerical scheme. Furthermore, two variants of fully-practical operator-splitting finite element algorithms based on the quadrature points and the nodal points, respectively, are presented. Both the quadrature and the nodal point based operator-splitting algorithms are validated using a three-dimensional (3D) test problem. The numerical results obtained with the full 3D computations and the operator-split 2D + 1D computations are found to be in a good agreement with the analytical solution. Further, the optimal order of convergence is obtained in both variants of the operator-splitting algorithms. (C) 2012 Elsevier Inc. All rights reserved.

Capture-Induced, Fast, Distributed, Splitting Based Selection with Imperfect Power Control

Opportunistic selection selects the node that improves the overall system performance the most. Selecting the best node is challenging as the nodes are geographically distributed and have only local knowledge. Yet, selection must be fast to allow more time to be spent on data transmission, which exploits the selected node's services. We analyze the impact of imperfect power control on a fast, distributed, splitting based selection scheme that exploits the capture effect by allowing the transmitting nodes to have different target receive powers and uses information about the total received power to speed up selection. Imperfect power control makes the received power deviate from the target and, hence, affects performance. Our analysis quantifies how it changes the selection probability, reduces the selection speed, and leads to the selection of no node or a wrong node. We show that the effect of imperfect power control is primarily driven by the ratio of target receive powers. Furthermore, we quantify its effect on the net system throughput.

Artificial photosynthesis and the splitting of water to generate hydrogen

It is no exaggeration to state that the energy crisis is the most serious challenge that we face today. Among the strategies to gain access to reliable, renewable energy, the use of solar energy has clearly emerged as the most viable option. A promising direction in this context is artificial photosynthesis. In this article, we briefly describe the essential features of artificial photosynthesis in comparison with natural photosynthesis and point out the modest success that we have had in splitting water to produce oxygen and hydrogen, specially the latter.

Anisotropic merging and splitting of dipolar Bose-Einstein condensates

We study the merging and splitting of quasi-two-dimensional Bose-Einstein condensates with strong dipolar interactions. We observe that if the dipoles have a non-zero component in the plane of the condensate, the dynamics of merging or splitting along two orthogonal directions, parallel and perpendicular to the projection of dipoles on the plane of the condensate, are different. The anisotropic merging and splitting of the condensate is a manifestation of the anisotropy of the roton-like mode in the dipolar system. The difference in dynamics disappears if the dipoles are oriented at right angles to the plane of the condensate as in this case the Bogoliubov dispersion, despite having roton-like features, is isotropic.