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.

An Online Actor-Critic Algorithm with Function Approximation for Constrained Markov Decision Processes

We develop an online actor-critic reinforcement learning algorithm with function approximation for a problem of control under inequality constraints. We consider the long-run average cost Markov decision process (MDP) framework in which both the objective and the constraint functions are suitable policy-dependent long-run averages of certain sample path functions. The Lagrange multiplier method is used to handle the inequality constraints. We prove the asymptotic almost sure convergence of our algorithm to a locally optimal solution. We also provide the results of numerical experiments on a problem of routing in a multi-stage queueing network with constraints on long-run average queue lengths. We observe that our algorithm exhibits good performance on this setting and converges to a feasible point.

Numerical Investigation of Heat Transfer from a Two-Dimensional Sudden Expansion Flow Using Nanofluids

Laminar forced convection heat transfer from two-dimensional sudden expansion flow of different nanofluids is studied numerically. The governing equations are solved using the unsteady stream function-vorticity method. The effect of volume fraction of the nanoparticles and type of nanoparticles on heat transfer is examined and found to have a significant impact. Local and average Nusselt numbers are reported in connection with various nanoparticle, volume fraction, and Reynolds number for expansion ratio 2. The Nusselt number reaches peak values near the reattachment point and reaches asymptotic value in the downstream. Bottom wall eddy and volume fraction shows a significant impact on the average Nusselt number.

Spacelike pion form factor from analytic continuation and the onset of perturbative QCD

The factorization theorem for exclusive processes in perturbative QCD predicts the behavior of the pion electromagnetic form factor F(t) at asymptotic spacelike momenta t(= -Q(2)) < 0. We address the question of the onset energy using a suitable mathematical framework of analytic continuation, which uses as input the phase of the form factor below the first inelastic threshold, known with great precision through the Fermi-Watson theorem from pi pi elastic scattering, and the modulus measured from threshold up to 3 GeV by the BABAR Collaboration. The method leads to almost model-independent upper and lower bounds on the spacelike form factor. Further inclusion of the value of the charge radius and the experimental value at -2.45 GeV2 measured at JLab considerably increases the strength of the bounds in the region Q(2) less than or similar to 10 GeV2, excluding the onset of the asymptotic perturbative QCD regime for Q(2) < 7 GeV2. We also compare the bounds with available experimental data and with several theoretical models proposed for the low and intermediate spacelike region.

On the structure of analytic vectors for the Schrodinger representation

This article deals with the structure of analytic and entire vectors for the Schrodinger representations of the Heisenberg group. Using refined versions of Hardy's theorem and their connection with Hermite expansions we obtain very precise representation theorems for analytic and entire vectors.

The Dπ form factors from analyticity and unitarity

We study the shape parameters of the Dπ scalar and vector form factors using as input dispersion relations and unitarity for the moments of suitable heavy-light correlators evaluated with Operator Product Expansions, including O(α 2 s) terms in perturbative QCD. For the scalar form factor, a low energy theorem and phase information on the unitarity cut are implemented to further constrain the shape parameters. We finally determine points on the real axis and isolate regions in the complex energy plane where zeros of the form factors are excluded.

Geometrically non-linear dynamics of composite four-bar mechanisms

This work intends to demonstrate the importance of a geometrically nonlinear cross-sectional analysis of certain composite beam-based four-bar mechanisms in predicting system dynamic characteristics. All component bars of the mechanism are made of fiber reinforced laminates and have thin rectangular cross-sections. They could, in general, be pre-twisted and/or possess initial curvature, either by design or by defect. They are linked to each other by means of revolute joints. We restrict ourselves to linear materials with small strains within each elastic body (beam). Each component of the mechanism is modeled as a beam based on geometrically non-linear 3-D elasticity theory. The component problems are thus split into 2-D analyses of reference beam cross-sections and non-linear 1-D analyses along the three beam reference curves. For the thin rectangular cross-sections considered here, the 2-D cross-sectional non-linearity is also overwhelming. This can be perceived from the fact that such sections constitute a limiting case between thin-walled open and closed sections, thus inviting the non-linear phenomena observed in both. The strong elastic couplings of anisotropic composite laminates complicate the model further. However, a powerful mathematical tool called the Variational Asymptotic Method (VAM) not only enables such a dimensional reduction, but also provides asymptotically correct analytical solutions to the non-linear cross-sectional analysis. Such closed-form solutions are used here in conjunction with numerical techniques for the rest of the problem to predict multi-body dynamic responses more quickly and accurately than would otherwise be possible. The analysis methodology can be viewed as a three-step procedure: First, the cross-sectional properties of each bar of the mechanism is determined analytically based on an asymptotic procedure, starting from Classical Laminated Shell Theory (CLST) and taking advantage of its thin strip geometry. Second, the dynamic response of the non-linear, flexible four-bar mechanism is simulated by treating each bar as a 1-D beam, discretized using finite elements, and employing energy-preserving and -decaying time integration schemes for unconditional stability. Finally, local 3-D deformations and stresses in the entire system are recovered, based on the 1-D responses predicted in the previous step. With the model, tools and procedure in place, we identify and investigate a few four-bar mechanism problems where the cross-sectional non-linearities are significant in predicting better and critical system dynamic characteristics. This is carried out by varying stacking sequences (i.e. the arrangement of ply orientations within a laminate) and material properties, and speculating on the dominating diagonal and coupling terms in the closed-form non-linear beam stiffness matrix. A numerical example is presented which illustrates the importance of 2-D cross-sectional non-linearities and the behavior of the system is also observed by using commercial software (I-DEAS + NASTRAN + ADAMS). (C) 2012 Elsevier Ltd. All rights reserved.

VAM applied to dimensional reduction of non-linear hyperelastic plates

This work aims at dimensional reduction of non-linear isotropic hyperelastic plates in an asymptotically accurate manner. The problem is both geometrically and materially non-linear. The geometric non-linearity is handled by allowing for finite deformations and generalized warping while the material non-linearity is incorporated through hyperelastic material model. The development, based on the Variational Asymptotic Method (VAM) with moderate strains and very small thickness to shortest wavelength of the deformation along the plate reference surface as small parameters, begins with three-dimensional (3-D) non-linear elasticity and mathematically splits the analysis into a one-dimensional (1-D) through-the-thickness analysis and a two-dimensional (2-D) plate analysis. Major contributions of this paper are derivation of closed-form analytical expressions for warping functions and stiffness coefficients and a set of recovery relations to express approximately the 3-D displacement, strain and stress fields. Consistent with the 2-D non-linear constitutive laws, 2-D plate theory and corresponding finite element program have been developed. Validation of present theory is carried out with a standard test case and the results match well. Distributions of 3-D results are provided for another test case. (c) 2012 Elsevier Ltd. All rights reserved.

3-MANIFOLD GROUPS, KÄHLER GROUPS AND COMPLEX SURFACES

Let G be a Kahler group admitting a short exact sequence 1 -> N -> G -> Q -> 1 where N is finitely generated. (i) Then Q cannot be non-nilpotent solvable. (ii) Suppose in addition that Q satisfies one of the following: (a) Q admits a discrete faithful non-elementary action on H-n for some n >= 2. (b) Q admits a discrete faithful non-elementary minimal action on a simplicial tree with more than two ends. (c) Q admits a (strong-stable) cut R such that the intersection of all conjugates of R is trivial. Then G is virtually a surface group. It follows that if Q is infinite, not virtually cyclic, and is the fundamental group of some closed 3-manifold, then Q contains as a finite index subgroup either a finite index subgroup of the three-dimensional Heisenberg group or the fundamental group of the Cartesian product of a closed oriented surface of positive genus and the circle. As a corollary, we obtain a new proof of a theorem of Dimca and Suciu in Which 3-manifold groups are Kahler groups? J. Eur. Math. Soc. 11 (2009) 521-528] by taking N to be the trivial group. If instead, G is the fundamental group of a compact complex surface, and N is finitely presented, then we show that Q must contain the fundamental group of a Seifert-fibered 3-manifold as a finite index subgroup, and G contains as a finite index subgroup the fundamental group of an elliptic fibration. We also give an example showing that the relation of quasi-isometry does not preserve Kahler groups. This gives a negative answer to a question of Gromov which asks whether Kahler groups can be characterized by their asymptotic geometry.

Revisiting Riesz transforms on Heisenberg groups

We characterise higher order Riesz transforms on the Heisenberg group and also show that they satisfy dimension-free bounds under some assumptions on the multipliers. Using transference theorems, we deduce boundedness theorems for Riesz transforms on the reduced Heisenberg group and hence also for the Riesz transforms associated to multiple Hermite and Laguerre expansions.

Perturbative expansion of the QCD Adler function improved by renormalization-group summation and analytic continuation in the Borel plane

We examine the large-order behavior of a recently proposed renormalization-group-improved expansion of the Adler function in perturbative QCD, which sums in an analytically closed form the leading logarithms accessible from renormalization-group invariance. The expansion is first written as an effective series in powers of the one-loop coupling, and its leading singularities in the Borel plane are shown to be identical to those of the standard ``contour-improved'' expansion. Applying the technique of conformal mappings for the analytic continuation in the Borel plane, we define a class of improved expansions, which implement both the renormalization-group invariance and the knowledge about the large-order behavior of the series. Detailed numerical studies of specific models for the Adler function indicate that the new expansions have remarkable convergence properties up to high orders. Using these expansions for the determination of the strong coupling from the hadronic width of the tau lepton we obtain, with a conservative estimate of the uncertainty due to the nonperturbative corrections, alpha(s)(M-tau(2)) = 0.3189(-0.0151)(+0.0173), which translates to alpha(s)(M-Z(2)) = 0.1184(-0.0018)(+0.0021). DOI: 10.1103/PhysRevD.87.014008

Radial Deformation of Cylinders Due to Torsion

Classical literature on solid mechanics claims existence of radial deformation due to torsion but there is hardly any literature on analytic solutions capturing this phenomenon. This paper tries to solve this problem in an asymptotic sense using the variational asymptotic method (VAM). The method makes no ad hoc assumptions and hence asymptotic correctness is assured. The VAM splits the 3D elasticity problem into two parts: A 1D problem along the length of the cylinder which gives the twist and a 2D cross-sectional problem which gives the radial deformation. This enables closed form solutions, even for some complex problems. Starting with a hollow cylinder, made up of orthotropic but transversely isotropic material, the 3D problem has been formulated and solved analytically despite the presence of geometric nonlinearity. The general results have been specialized for particularly useful cases, such as solid cylinders and/or cylinders with isotropic material. DOI: 10.1115/1.4006803]

Optimal control problem for the time-dependent Kirchhoff-Love plate in a domain with rough boundary

In this paper, we study the asymptotic behavior of an optimal control problem for the time-dependent Kirchhoff-Love plate whose middle surface has a very rough boundary. We identify the limit problem which is an optimal control problem for the limit equation with a different cost functional.

A channel-aware, fast sub-channel to user assignment algorithm in OFDMA systems

Channel-aware assignment of sub-channels to users in the downlink of an OFDMA system demands extensive feedback of channel state information (CSI) to the base station. Since the feedback bandwidth is often very scarce, schemes that limit feedback are necessary. We develop a novel, low feedback splitting-based algorithm for assigning each sub-channel to its best user, i.e., the user with the highest gain for that sub-channel among all users. The key idea behind the algorithm is that, at any time, each user contends for the sub-channel on which it has the largest channel gain among the unallocated sub-channels. Unlike other existing schemes, the algorithm explicitly handles multiple access control aspects associated with the feedback of CSI. A tractable asymptotic analysis of a system with a large number of users helps design the algorithm. It yields 50% to 65% throughput gains compared to an asymptotically optimal one-bit feedback scheme, when the number of users is as small as 10 or as large as 1000. The algorithm is fast and distributed, and scales with the number of users.

Quadrature approximation properties of the spiral-phase quadrature transform

The notion of the 1-D analytic signal is well understood and has found many applications. At the heart of the analytic signal concept is the Hilbert transform. The problem in extending the concept of analytic signal to higher dimensions is that there is no unique multidimensional definition of the Hilbert transform. Also, the notion of analyticity is not so well under stood in higher dimensions. Of the several 2-D extensions of the Hilbert transform, the spiral-phase quadrature transform or the Riesz transform seems to be the natural extension and has attracted a lot of attention mainly due to its isotropic properties. From the Riesz transform, Larkin et al. constructed a vortex operator, which approximates the quadratures based on asymptotic stationary-phase analysis. In this paper, we show an alternative proof for the quadrature approximation property by invoking the quasi-eigenfunction property of linear, shift-invariant systems. We show that the vortex operator comes up as a natural consequence of applying this property. We also characterize the quadrature approximation error in terms of its energy as well as the peak spatial-domain error. Such results are available for 1-D signals, but their counter part for 2-D signals have not been provided. We also provide simulation results to supplement the analytical calculations.