A constant factor approximation algorithm for boxicity of circular arc graphs

Boxicity of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of k-dimensional axis parallel boxes in Rk. Equivalently, it is the minimum number of interval graphs on the vertex set V such that the intersection of their edge sets is E. It is known that boxicity cannot be approximated even for graph classes like bipartite, co-bipartite and split graphs below O(n0.5-ε)-factor, for any ε > 0 in polynomial time unless NP = ZPP. Till date, there is no well known graph class of unbounded boxicity for which even an nε-factor approximation algorithm for computing boxicity is known, for any ε < 1. In this paper, we study the boxicity problem on Circular Arc graphs - intersection graphs of arcs of a circle. We give a (2+ 1/k)-factor polynomial time approximation algorithm for computing the boxicity of any circular arc graph along with a corresponding box representation, where k ≥ 1 is its boxicity. For Normal Circular Arc(NCA) graphs, with an NCA model given, this can be improved to an additive 2-factor approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity is O(mn+n2) in both these cases and in O(mn+kn2) which is at most O(n3) time we also get their corresponding box representations, where n is the number of vertices of the graph and m is its number of edges. The additive 2-factor algorithm directly works for any Proper Circular Arc graph, since computing an NCA model for it can be done in polynomial time.

A Savitzky-Golay Filtering Perspective of Dynamic Feature Computation

We address the classical problem of delta feature computation, and interpret the operation involved in terms of Savitzky- Golay (SG) filtering. Features such as themel-frequency cepstral coefficients (MFCCs), obtained based on short-time spectra of the speech signal, are commonly used in speech recognition tasks. In order to incorporate the dynamics of speech, auxiliary delta and delta-delta features, which are computed as temporal derivatives of the original features, are used. Typically, the delta features are computed in a smooth fashion using local least-squares (LS) polynomial fitting on each feature vector component trajectory. In the light of the original work of Savitzky and Golay, and a recent article by Schafer in IEEE Signal Processing Magazine, we interpret the dynamic feature vector computation for arbitrary derivative orders as SG filtering with a fixed impulse response. This filtering equivalence brings in significantly lower latency with no loss in accuracy, as validated by results on a TIMIT phoneme recognition task. The SG filters involved in dynamic parameter computation can be viewed as modulation filters, proposed by Hermansky.

Network-error correcting codes using small fields

Recently, Ebrahimi and Fragouli proposed an algorithm to construct scalar network codes using small fields (and vector network codes of small lengths) satisfying multicast constraints in a given single-source, acyclic network. The contribution of this paper is two fold. Primarily, we extend the scalar network coding algorithm of Ebrahimi and Fragouli (henceforth referred to as the EF algorithm) to block network-error correction. Existing construction algorithms of block network-error correcting codes require a rather large field size, which grows with the size of the network and the number of sinks, and thereby can be prohibitive in large networks. We give an algorithm which, starting from a given network-error correcting code, can obtain another network code using a small field, with the same error correcting capability as the original code. Our secondary contribution is to improve the EF Algorithm itself. The major step in the EF algorithm is to find a least degree irreducible polynomial which is coprime to another large degree polynomial. We suggest an alternate method to compute this coprime polynomial, which is faster than the brute force method in the work of Ebrahimi and Fragouli.

Renormalization of noncommutative quantum field theories

We report on a comprehensive analysis of the renormalization of noncommutative phi(4) scalar field theories on the Groenewold-Moyal plane. These scalar field theories are twisted Poincare invariant. Our main results are that these scalar field theories are renormalizable, free of UV/IR mixing, possess the same fixed points and beta-functions for the couplings as their commutative counterparts. We also argue that similar results hold true for any generic noncommutative field theory with polynomial interactions and involving only pure matter fields. A secondary aim of this work is to provide a comprehensive review of different approaches for the computation of the noncommutative S-matrix: noncommutative interaction picture and noncommutative Lehmann-Symanzik-Zimmermann formalism. DOI: 10.1103/PhysRevD.87.064014

Accelerating Reduction for Enabling Fast Multiplication over Large Binary Fields

In this paper we present a hardware-software hybrid technique for modular multiplication over large binary fields. The technique involves application of Karatsuba-Ofman algorithm for polynomial multiplication and a novel technique for reduction. The proposed reduction technique is based on the popular repeated multiplication technique and Barrett reduction. We propose a new design of a parallel polynomial multiplier that serves as a hardware accelerator for large field multiplications. We show that the proposed reduction technique, accelerated using the modified polynomial multiplier, achieves significantly higher performance compared to a purely software technique and other hybrid techniques. We also show that the hybrid accelerated approach to modular field multiplication is significantly faster than the Montgomery algorithm based integrated multiplication approach.

Motion segmentation using curve fitting on Lagrangian particle trajectories

In this paper we present a segmentation algorithm to extract foreground object motion in a moving camera scenario without any preprocessing step such as tracking selected features, video alignment, or foreground segmentation. By viewing it as a curve fitting problem on advected particle trajectories, we use RANSAC to find the polynomial that best fits the camera motion and identify all trajectories that correspond to the camera motion. The remaining trajectories are those due to the foreground motion. By using the superposition principle, we subtract the motion due to camera from foreground trajectories and obtain the true object-induced trajectories. We show that our method performs on par with state-of-the-art technique, with an execution time speed-up of 10x-40x. We compare the results on real-world datasets such as UCF-ARG, UCF Sports and Liris-HARL. We further show that it can be used toper-form video alignment.

Stiff string approximations in Rayleigh-Ritz method for rotating beams

The governing differential equation of the rotating beam reduces to that of a stiff string when the centrifugal force is assumed as constant. The solution of the static homogeneous part of this equation is enhanced with a polynomial term and used in the Rayleighs method. Numerical experiments show better agreement with converged finite element solutions compared to polynomials. Using this as an estimate for the first mode shape, higher mode shape approximations are obtained using Gram-Schmidt orthogonalization. Estimates for the first five natural frequencies of uniform and tapered beams are obtained accurately using a very low order Rayleigh-Ritz approximation.

Spectral-envelope-group-delay models for transients

Transient signals such as plosives in speech or Castanets in audio do not have a specific modulation or periodic structure in time domain. However, in the spectral domain they exhibit a prominent modulation structure, which is a direct consequence of their narrow time localization. Based on this observation, a spectral-domain AM-FM model for transients is proposed. The spectral AM-FM model is built starting from real spectral zero-crossings. The AM and FM correspond to the spectral envelope (SE) and group delay (GD), respectively. Taking into account the modulation structure and spectral continuity, a local polynomial regression technique is proposed to estimate the GD function from the real spectral zeros. The SE is estimated based on the phase function computed from the estimated GD. Since the GD estimation is parametric, the degree of smoothness can be controlled directly. Simulation results based on synthetic transient signals generated using a beta density function are presented to analyze the noise-robustness of the SEGD model. Three specific applications are considered: (1) SEGD based modeling of Castanet sounds; (2) appropriateness of the model for transient compression; and (3) determining glottal closure instants in speech using a short-time SEGD model of the linear prediction residue.

On the Chern number of I-admissible filtrations of ideals

Let I be an m-primary ideal of a Noetherian local ring (R, m) of positive dimension. The coefficient e(1)(I) of the Hilbert polynomial of an I-admissible filtration I is called the Chern number of I. A formula for the Chern number has been derived involving the Euler characteristic of subcomplexes of a Koszul complex. Specific formulas for the Chern number have been given in local rings of dimension at most two. These have been used to provide new and unified proofs of several results about e(1)(I).

Resolution of Singularities for a Class of Hilbert Modules

Let M be the completion of the polynomial ring C(z) under bar] with respect to some inner product, and for any ideal I subset of C (z) under bar], let I] be the closure of I in M. For a homogeneous ideal I, the joint kernel of the submodule I] subset of M is shown, after imposing some mild conditions on M, to be the linear span of the set of vectors {p(i)(partial derivative/partial derivative(w) over bar (1),...,partial derivative/partial derivative(w) over bar (m)) K-I] (., w)vertical bar(w=0), 1 <= i <= t}, where K-I] is the reproducing kernel for the submodule 2] and p(1),..., p(t) is some minimal ``canonical set of generators'' for the ideal I. The proof includes an algorithm for constructing this canonical set of generators, which is determined uniquely modulo linear relations, for homogeneous ideals. A short proof of the ``Rigidity Theorem'' using the sheaf model for Hilbert modules over polynomial rings is given. We describe, via the monoidal transformation, the construction of a Hermitian holomorphic line bundle for a large class of Hilbert modules of the form I]. We show that the curvature, or even its restriction to the exceptional set, of this line bundle is an invariant for the unitary equivalence class of I]. Several examples are given to illustrate the explicit computation of these invariants.

Effect of electro-mechanical coupling on actuation behavior of a carbon nanotube cellular structure

We demonstrate the effect of mechanical strain on the electrostrictive behavior of catalytically grown cellular structure of carbon nanotube (CNT). In the small strain regime, where the stress-strain behavior of the material is linear, application of an electric-field along the mechanical loading direction induces an instantaneous increase in the stress and causes an increase in the apparent Young's modulus. The instantaneous increase in the stress shows a cubic-polynomial dependence on the electric-field, which is attributed to the non-linear coupling of the mechanical strain and the electric-field induced polarization of the CNT. The electrostriction induced actuation becomes >100 times larger if the CNT sample is pre-deformed to a small strain. However, in the non-linear stress-strain regime, although a sharp increase in the apparent Young's modulus is observed upon application of an electric-field, no instantaneous increase in the stress occurs. This characteristic suggests that the softening due to the buckling of individual CNT compensates for any instantaneous rise in the electrostriction induced stress at the higher strains. We also present an analytical model to elucidate the experimental observations. (C) 2013 Elsevier Ltd. All rights reserved.

An approximately H-1-optimal Petrov-Galerkin meshfree method: application to computation of scattered light for optical tomography

Nearly pollution-free solutions of the Helmholtz equation for k-values corresponding to visible light are demonstrated and verified through experimentally measured forward scattered intensity from an optical fiber. Numerically accurate solutions are, in particular, obtained through a novel reformulation of the H-1 optimal Petrov-Galerkin weak form of the Helmholtz equation. Specifically, within a globally smooth polynomial reproducing framework, the compact and smooth test functions are so designed that their normal derivatives are zero everywhere on the local boundaries of their compact supports. This circumvents the need for a priori knowledge of the true solution on the support boundary and relieves the weak form of any jump boundary terms. For numerical demonstration of the above formulation, we used a multimode optical fiber in an index matching liquid as the object. The scattered intensity and its normal derivative are computed from the scattered field obtained by solving the Helmholtz equation, using the new formulation and the conventional finite element method. By comparing the results with the experimentally measured scattered intensity, the stability of the solution through the new formulation is demonstrated and its closeness to the experimental measurements verified.

On the sphere decoding complexity of high-rate multigroup decodable STBCs in asymmetric MIMO systems

A space-time block code (STBC) is said to be multigroup decodable if the information symbols encoded by it can be partitioned into two or more groups such that each group of symbols can be maximum-likelihood (ML) decoded independently of the other symbol groups. In this paper, we show that the upper triangular matrix encountered during the sphere decoding of a linear dispersion STBC can be rank-deficient even when the rate of the code is less than the minimum of the number of transmit and receive antennas. We then show that all known families of high-rate (rate greater than 1) multigroup decodable codes have rank-deficient matrix even when the rate is less than the number of transmit and receive antennas, and this rank-deficiency problem arises only in asymmetric MIMO systems when the number of receive antennas is strictly less than the number of transmit antennas. Unlike the codes with full-rank matrix, the complexity of the sphere decoding-based ML decoder for STBCs with rank-deficient matrix is polynomial in the constellation size, and hence is high. We derive the ML sphere decoding complexity of most of the known high-rate multigroup decodable codes, and show that for each code, the complexity is a decreasing function of the number of receive antennas.

Application of the random eigenvalue problem in forced response analysis of a linear stochastic structure

The random eigenvalue problem arises in frequency and mode shape determination for a linear system with uncertainties in structural properties. Among several methods of characterizing this random eigenvalue problem, one computationally fast method that gives good accuracy is a weak formulation using polynomial chaos expansion (PCE). In this method, the eigenvalues and eigenvectors are expanded in PCE, and the residual is minimized by a Galerkin projection. The goals of the current work are (i) to implement this PCE-characterized random eigenvalue problem in the dynamic response calculation under random loading and (ii) to explore the computational advantages and challenges. In the proposed method, the response quantities are also expressed in PCE followed by a Galerkin projection. A numerical comparison with a perturbation method and the Monte Carlo simulation shows that when the loading has a random amplitude but deterministic frequency content, the proposed method gives more accurate results than a first-order perturbation method and a comparable accuracy as the Monte Carlo simulation in a lower computational time. However, as the frequency content of the loading becomes random, or for general random process loadings, the method loses its accuracy and computational efficiency. Issues in implementation, limitations, and further challenges are also addressed.

Closed-form solutions for non-uniform Euler-Bernoulli free-free beams

In this paper, the free vibration of a non-uniform free-free Euler-Bernoulli beam is studied using an inverse problem approach. It is found that the fourth-order governing differential equation for such beams possess a fundamental closed-form solution for certain polynomial variations of the mass and stiffness. An infinite number of non-uniform free-free beams exist, with different mass and stiffness variations, but sharing the same fundamental frequency. A detailed study is conducted for linear, quadratic and cubic variations of mass, and on how to pre-select the internal nodes such that the closed-form solutions exist for the three cases. A special case is also considered where, at the internal nodes, external elastic constraints are present. The derived results are provided as benchmark solutions for the validation of non-uniform free-free beam numerical codes. (C) 2013 Elsevier Ltd. All rights reserved.