Reduced Grobner bases and Macaulay-Buchberger Basis Theorem over Noetherian rings

In this paper, we extend the characterization of Zx]/(f), where f is an element of Zx] to be a free Z-module to multivariate polynomial rings over any commutative Noetherian ring, A. The characterization allows us to extend the Grobner basis method of computing a k-vector space basis of residue class polynomial rings over a field k (Macaulay-Buchberger Basis Theorem) to rings, i.e. Ax(1), ... , x(n)]/a, where a subset of Ax(1), ... , x(n)] is an ideal. We give some insights into the characterization for two special cases, when A = Z and A = ktheta(1), ... , theta(m)]. As an application of this characterization, we show that the concept of Border bases can be extended to rings when the corresponding residue class ring is a finitely generated, free A-module. (C) 2014 Elsevier B.V. All rights reserved.

Error analysis of discontinuous Galerkin methods for the Stokes problem under minimal regularity

In this article, we analyse several discontinuous Galerkin (DG) methods for the Stokes problem under minimal regularity on the solution. We assume that the velocity u belongs to H-0(1)(Omega)](d) and the pressure p is an element of L-0(2)(Omega). First, we analyse standard DG methods assuming that the right-hand side f belongs to H-1(Omega) boolean AND L-1(Omega)](d). A DG method that is well defined for f belonging to H-1(Omega)](d) is then investigated. The methods under study include stabilized DG methods using equal-order spaces and inf-sup stable ones where the pressure space is one polynomial degree less than the velocity space.

Analytical test functions for free vibration analysis of rotating non-homogeneous Timoshenko beams

In this paper, the governing equations for free vibration of a non-homogeneous rotating Timoshenko beam, having uniform cross-section, is studied using an inverse problem approach, for both cantilever and pinned-free boundary conditions. The bending displacement and the rotation due to bending are assumed to be simple polynomials which satisfy all four boundary conditions. It is found that for certain polynomial variations of the material mass density, elastic modulus and shear modulus, along the length of the beam, the assumed polynomials serve as simple closed form solutions to the coupled second order governing differential equations with variable coefficients. It is found that there are an infinite number of analytical polynomial functions possible for material mass density, shear modulus and elastic modulus distributions, which share the same frequency and mode shape for a particular mode. The derived results are intended to serve as benchmark solutions for testing approximate or numerical methods used for the vibration analysis of rotating non-homogeneous Timoshenko beams.

Model domains in C-3 with abelian automorphism group

It is shown that every hyperbolic rigid polynomial domain in C-3 of finite-type, with abelian automorphism group is equivalent to a domain that is balanced with respect to some weight.

Signal tracking approach for phase estimation in digital holographic interferometry

In this research work, we introduce a novel approach for phase estimation from noisy reconstructed interference fields in digital holographic interferometry using an unscented Kalman filter. Unlike conventionally used unwrapping algorithms and piecewise polynomial approximation approaches, this paper proposes, for the first time to the best of our knowledge, a signal tracking approach for phase estimation. The state space model derived in this approach is inspired from the Taylor series expansion of the phase function as the process model, and polar to Cartesian conversion as the measurement model. We have characterized our approach by simulations and validated the performance on experimental data (holograms) recorded under various practical conditions. Our study reveals that the proposed approach, when compared with various phase estimation methods available in the literature, outperforms at lower SNR values (i.e., especially in the range 0-20 dB). It is demonstrated with experimental data as well that the proposed approach is a better choice for estimating rapidly varying phase with high dynamic range and noise. (C) 2014 Optical Society of America

Pressure Dependence of Glass Transition in As2Te3 Glass

Amorphous solids prepared from their melt state exhibit glass transition phenomenon upon heating. Viscosity, specific heat, and thermal expansion coefficient of the amorphous solids show rapid changes at the glass transition temperature (T-g). Generally, application of high pressure increases the T-g and this increase (a positive dT(g)/dP) has been understood adequately with free volume and entropy models which are purely thermodynamic in origin. In this study, the electrical resistivity of semiconducting As2Te3 glass at high pressures as a function of temperature has been measured in a Bridgman anvil apparatus. Electrical resistivity showed a pronounced change at T-g. The T-g estimated from the slope change in the resistivity-temperature plot shows a decreasing trend (negative dT(g)/dP). The dT(g)/dP was found to be -2.36 degrees C/kbar for a linear fit and -2.99 degrees C/kbar for a polynomial fit in the pressure range 1 bar to 9 kbar. Chalcogenide glasses like Se, As2Se3, and As30Se30Te40 show a positive dT(g)/dP which is very well understood in terms of the thermodynamic models. The negative dT(g)/dP (which is generally uncommon in liquids) observed for As2Te3 glass is against the predictions of the thermodynamic models. The Adam-Gibbs model of viscosity suggests a direct relationship between the isothermal pressure derivative of viscosity and the relaxational expansion coefficient. When the sign of the thermal expansion coefficient is negative, dT(g)/dP = Delta k/Delta alpha will be less than zero, which can result in a negative dT(g)/dP. In general, chalcogenides rich in tellurium show a negative thermal expansion coefficient (NTE) in the supercooled and stable liquid states. Hence, the negative dT(g)/dP observed in this study can be understood on the basis of the Adams-Gibbs model. An electronic model proposed by deNeufville and Rockstad finds a linear relation between T-g and the optical band gap (E-g for covalent semiconducting glasses when they are grouped according to their average coordination number. The electrical band gap (Delta E) of As2Te3 glass decreases with pressure. The optical and electrical band gaps are related as Delta E-g = 2 Delta E; thus, a negative dT(g)/dP is expected when As2Te3 glass is subjected to high pressures. In this sense, As2Te3 is a unique glass where its variation of T-g with pressure can be understood by both electronic and thermodynamic models.

A shortest path tree based algorithm for relay placement in a wireless sensor network and its performance analysis

In this paper, we study a problem of designing a multi-hop wireless network for interconnecting sensors (hereafter called source nodes) to a Base Station (BS), by deploying a minimum number of relay nodes at a subset of given potential locations, while meeting a quality of service (QoS) objective specified as a hop count bound for paths from the sources to the BS. The hop count bound suffices to ensure a certain probability of the data being delivered to the BS within a given maximum delay under a light traffic model. We observe that the problem is NP-Hard. For this problem, we propose a polynomial time approximation algorithm based on iteratively constructing shortest path trees and heuristically pruning away the relay nodes used until the hop count bound is violated. Results show that the algorithm performs efficiently in various randomly generated network scenarios; in over 90% of the tested scenarios, it gave solutions that were either optimal or were worse than optimal by just one relay. We then use random graph techniques to obtain, under a certain stochastic setting, an upper bound on the average case approximation ratio of a class of algorithms (including the proposed algorithm) for this problem as a function of the number of source nodes, and the hop count bound. To the best of our knowledge, the average case analysis is the first of its kind in the relay placement literature. Since the design is based on a light traffic model, we also provide simulation results (using models for the IEEE 802.15.4 physical layer and medium access control) to assess the traffic levels up to which the QoS objectives continue to be met. (C) 2014 Elsevier B.V. All rights reserved.

UNO Gets Easier for a Single Player

This work is a follow up to 2, FUN 2010], which initiated a detailed analysis of the popular game of UNO (R). We consider the solitaire version of the game, which was shown to be NP-complete. In 2], the authors also demonstrate a (O)(n)(c(2)) algorithm, where c is the number of colors across all the cards, which implies, in particular that the problem is polynomial time when the number of colors is a constant. In this work, we propose a kernelization algorithm, a consequence of which is that the problem is fixed-parameter tractable when the number of colors is treated as a parameter. This removes the exponential dependence on c and answers the question stated in 2] in the affirmative. We also introduce a natural and possibly more challenging version of UNO that we call ``All Or None UNO''. For this variant, we prove that even the single-player version is NP-complete, and we show a single-exponential FPT algorithm, along with a cubic kernel.

A constant factor approximation algorithm for boxicity of circular arc graphs

The boxicity (resp. cubicity) of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes (resp. cubes) in R-k. Equivalently, it is the minimum number of interval graphs (resp. unit interval graphs) on the vertex set V, such that the intersection of their edge sets is E. The problem of computing boxicity (resp. cubicity) is known to be inapproximable, even for restricted graph classes like bipartite, co-bipartite and split graphs, within an O(n(1-epsilon))-factor for any epsilon > 0 in polynomial time, unless NP = ZPP. For any well known graph class of unbounded boxicity, there is no known approximation algorithm that gives n(1-epsilon)-factor approximation algorithm for computing boxicity in polynomial time, for any epsilon > 0. In this paper, we consider the problem of approximating the boxicity (cubicity) of circular arc graphs intersection graphs of arcs of a circle. Circular arc graphs are known to have unbounded boxicity, which could be as large as Omega(n). We give a (2 + 1/k) -factor (resp. (2 + log n]/k)-factor) polynomial time approximation algorithm for computing the boxicity (resp. cubicity) of any circular arc graph, where k >= 1 is the value of the optimum solution. For normal circular arc (NCA) graphs, with an NCA model given, this can be improved to an additive two approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity (resp. cubicity) is O(mn + n(2)) in both these cases, and in O(mn + kn(2)) = O(n(3)) time we also get their corresponding box (resp. cube) representations, where n is the number of vertices of the graph and m is its number of edges. Our additive two approximation algorithm directly works for any proper circular arc graph, since their NCA models can be computed in polynomial time. (C) 2014 Elsevier B.V. All rights reserved.

Parameterized Algorithms for MAX COLORABLE INDUCED SUBGRAPH Problem on Perfect Graphs

We address the parameterized complexity ofMaxColorable Induced Subgraph on perfect graphs. The problem asks for a maximum sized q-colorable induced subgraph of an input graph G. Yannakakis and Gavril IPL 1987] showed that this problem is NP-complete even on split graphs if q is part of input, but gave a n(O(q)) algorithm on chordal graphs. We first observe that the problem is W2]-hard parameterized by q, even on split graphs. However, when parameterized by l, the number of vertices in the solution, we give two fixed-parameter tractable algorithms. The first algorithm runs in time 5.44(l) (n+#alpha(G))(O(1)) where #alpha(G) is the number of maximal independent sets of the input graph. The second algorithm runs in time q(l+o()l())n(O(1))T(alpha) where T-alpha is the time required to find a maximum independent set in any induced subgraph of G. The first algorithm is efficient when the input graph contains only polynomially many maximal independent sets; for example split graphs and co-chordal graphs. The running time of the second algorithm is FPT in l alone (whenever T-alpha is a polynomial in n), since q <= l for all non-trivial situations. Finally, we show that (under standard complexitytheoretic assumptions) the problem does not admit a polynomial kernel on split and perfect graphs in the following sense: (a) On split graphs, we do not expect a polynomial kernel if q is a part of the input. (b) On perfect graphs, we do not expect a polynomial kernel even for fixed values of q >= 2.

Rainbow Connection Number of Graph Power and Graph Products

Rainbow connection number, rc(G), of a connected graph G is the minimum number of colors needed to color its edges so that every pair of vertices is connected by at least one path in which no two edges are colored the same (note that the coloring need not be proper). In this paper we study the rainbow connection number with respect to three important graph product operations (namely the Cartesian product, the lexicographic product and the strong product) and the operation of taking the power of a graph. In this direction, we show that if G is a graph obtained by applying any of the operations mentioned above on non-trivial graphs, then rc(G) a parts per thousand currency sign 2r(G) + c, where r(G) denotes the radius of G and . In general the rainbow connection number of a bridgeless graph can be as high as the square of its radius 1]. This is an attempt to identify some graph classes which have rainbow connection number very close to the obvious lower bound of diameter (and thus the radius). The bounds reported are tight up to additive constants. The proofs are constructive and hence yield polynomial time -factor approximation algorithms.

Modal tailoring and closed-form solutions for rotating non-uniform Euler-Bernoulli beams

In this paper, the free vibration of a rotating Euler-Bernoulli beam is studied using an inverse problem approach. We assume a polynomial mode shape function for a particular mode, which satisfies all the four boundary conditions of a rotating beam, along with the internal nodes. Using this assumed mode shape function, we determine the linear mass and fifth order stiffness variations of the beam which are typical of helicopter blades. Thus, it is found that an infinite number of such beams exist whose fourth order governing differential equation possess a closed form solution for certain polynomial variations of the mass and stiffness, for both cantilever and pinned-free boundary conditions corresponding to hingeless and articulated rotors, respectively. A detailed study is conducted for the first, second and third modes of a rotating cantilever beam and the first and second elastic modes of a rotating pinned-free beam, and on how to pre-select the internal nodes such that the closed-form solutions exist for these cases. The derived results can be used as benchmark solutions for the validation of rotating beam numerical methods and may also guide nodal tailoring. (C) 2014 Elsevier Ltd. All rights reserved.

Tailoring the second mode of Euler-Bernoulli beams: an analytical approach

In this paper, we study the inverse mode shape problem for an Euler-Bernoulli beam, using an analytical approach. The mass and stiffness variations are determined for a beam, having various boundary conditions, which has a prescribed polynomial second mode shape with an internal node. It is found that physically feasible rectangular cross-section beams which satisfy the inverse problem exist for a variety of boundary conditions. The effect of the location of the internal node on the mass and stiffness variations and on the deflection of the beam is studied. The derived functions are used to verify the p-version finite element code, for the cantilever boundary condition. The paper also presents the bounds on the location of the internal node, for a valid mass and stiffness variation, for any given boundary condition. The derived property variations, corresponding to a given mode shape and boundary condition, also provides a simple closed-form solution for a class of non-uniform Euler-Bernoulli beams. These closed-form solutions can also be used to check optimization algorithms proposed for modal tailoring.

Wave propagation of phonon and phason displacement modes in quasicrystals: Determination of wave parameters

The paper presents the study of wave propagation in quasicrystals. Our interest is in the computation of the wavenumber (k(n)) and group speed (c(g)) of the phonon and phason displacement modes of one, two, and three dimensional quasicrystals. These wave parameter expressions are derived and computed using the elasto-hydrodynamic equations for quasicrystals. For the computation of the wavenumber and group speeds, we use Fourier transform approximation of the phonon and the phason displacement modes. The characteristic equations obtained are a polynomial equation of the wavenumber (k(n)), with frequency as a parameter. The corresponding group speeds (c(g)) for different frequencies are then computed from the wavenumber k(n). The variation of wavenumber and group speeds with frequency is plotted for the 1-D quasicrystal, 2-D decagonal Al-Ni-Co quasicrystals, and 3-D icosahedral Al-Pd-Mn and Zn-Mg-Sc quasicrystals. From the wavenumber and group speeds plots, we obtain the cut-off frequencies for different spatial wavenumber eta(m). The results show that for 1-D, 2-D, and 3-D quasicrystals, the phonon displacement modes are non-dispersive for low values of eta(m) and becomes dispersive for increasing values of eta(m). The cut-off frequencies are not observed for very low values of eta(m), whereas the cut-off frequency starts to appear with increasing eta(m). The group speeds of the phason displacement modes are orders of magnitude lower than that of the phonon displacement modes, showing that the phason modes do not propagate, and they are essentially the diffusive modes. The group speeds of the phason modes are also not influenced by eta(m). The group speeds for the 2-D quasicrystal at 35 kHz is also simulated numerically using Galerkin spectral finite element methods in frequency domain and is compared with the results obtained using wave propagation analysis. The effect of the phonon and phason elastic constants on the group speeds is studied using 3-D icosahedral Al-Pd-Mn and Zn-Mg-Sc quasicrystals. It is also shown that the phason elastic constants and the coupling coefficient do not affect the group speeds of the phonon displacement modes. (C) 2015 AIP Publishing LLC.

Multivariate juggling probabilities

We consider refined versions of Markov chains related to juggling introduced by Warrington. We further generalize the construction to juggling with arbitrary heights as well as infinitely many balls, which are expressed more succinctly in terms of Markov chains on integer partitions. In all cases, we give explicit product formulas for the stationary probabilities. The normalization factor in one case can be explicitly written as a homogeneous symmetric polynomial. We also refine and generalize enriched Markov chains on set partitions. Lastly, we prove that in one case, the stationary distribution is attained in bounded time.