Polynomial Decompositions in Polynomial Time

Fix a prime p. Given a positive integer k, a vector of positive integers Delta = (Delta(1), Delta(2), ... , Delta(k)) and a function Gamma : F-p(k) -> F-p, we say that a function P : F-p(n) -> F-p is (k, Delta, Gamma)-structured if there exist polynomials P-1, P-2, ..., P-k : F-p(n) -> F-p with each deg(P-i) <= Delta(i) such that for all x is an element of F-p(n), P(x) = Gamma(P-1(x), P-2(x), ..., P-k(x)). For instance, an n-variate polynomial over the field Fp of total degree d factors nontrivially exactly when it is (2, (d - 1, d - 1), prod)- structured where prod(a, b) = a . b. We show that if p > d, then for any fixed k, Delta, Gamma, we can decide whether a given polynomial P(x(1), x(2), ..., x(n)) of degree d is (k, Delta, Gamma)-structured and if so, find a witnessing decomposition. The algorithm takes poly(n) time. Our approach is based on higher-order Fourier analysis.

An Algorithmic Characterization of Polynomial Functions over Z(pn)

In this paper we consider polynomial representability of functions defined over , where p is a prime and n is a positive integer. Our aim is to provide an algorithmic characterization that (i) answers the decision problem: to determine whether a given function over is polynomially representable or not, and (ii) finds the polynomial if it is polynomially representable. The previous characterizations given by Kempner (Trans. Am. Math. Soc. 22(2):240-266, 1921) and Carlitz (Acta Arith. 9(1), 67-78, 1964) are existential in nature and only lead to an exhaustive search method, i.e. algorithm with complexity exponential in size of the input. Our characterization leads to an algorithm whose running time is linear in size of input. We also extend our result to the multivariate case.

A Smooth Discretization Bridging Finite Element and Mesh-free Methods Using Polynomial Reproducing Simplex Splines

This work sets forth a `hybrid' discretization scheme utilizing bivariate simplex splines as kernels in a polynomial reproducing scheme constructed over a conventional Finite Element Method (FEM)-like domain discretization based on Delaunay triangulation. Careful construction of the simplex spline knotset ensures the success of the polynomial reproduction procedure at all points in the domain of interest, a significant advancement over its precursor, the DMS-FEM. The shape functions in the proposed method inherit the global continuity (Cp-1) and local supports of the simplex splines of degree p. In the proposed scheme, the triangles comprising the domain discretization also serve as background cells for numerical integration which here are near-aligned to the supports of the shape functions (and their intersections), thus considerably ameliorating an oft-cited source of inaccuracy in the numerical integration of mesh-free (MF) schemes. Numerical experiments show the proposed method requires lower order quadrature rules for accurate evaluation of integrals in the Galerkin weak form. Numerical demonstrations of optimal convergence rates for a few test cases are given and the method is also implemented to compute crack-tip fields in a gradient-enhanced elasticity model.

A faster algorithm for testing polynomial representability of functions over finite integer rings

Given a function from Z(n) to itself one can determine its polynomial representability by using Kempner function. In this paper we present an alternative characterization of polynomial functions over Z(n) by constructing a generating set for the Z(n)-module of polynomial functions. This characterization results in an algorithm that is faster on average in deciding polynomial representability. We also extend the characterization to functions in several variables. (C) 2015 Elsevier B.V. All rights reserved.

Influence of Anisotropy on Pavement Responses Using Adaptive Sparse Polynomial Chaos Expansion

Modeling the spatial variability that exists in pavement systems can be conveniently represented by means of random fields; in this study, a probabilistic analysis that considers the spatial variability, including the anisotropic nature of the pavement layer properties, is presented. The integration of the spatially varying log-normal random fields into a linear-elastic finite difference analysis has been achieved through the expansion optimal linear estimation method. For the estimation of the critical pavement responses, metamodels based on polynomial chaos expansion (PCE) are developed to replace the computationally expensive finite-difference model. The sparse polynomial chaos expansion based on an adaptive regression-based algorithm, and enhanced by the combined use of the global sensitivity analysis (GSA) is used, with significant savings in computational effort. The effect of anisotropy in each layer on the pavement responses was studied separately, and an effort is made to identify the pavement layer wherein the introduction of anisotropic characteristics results in the most significant impact on the critical strains. It is observed that the anisotropy in the base layer has a significant but diverse effect on both critical strains. While the compressive strain tends to be considerably higher than that observed for the isotropic section, the tensile strains show a decrease in the mean value with the introduction of base-layer anisotropy. Furthermore, asphalt-layer anisotropy also tends to decrease the critical tensile strain while having little effect on the critical compressive strain. (C) 2015 American Society of Civil Engineers.

Efficient coupled polynomial interpolation scheme for out-of-plane free vibration analysis of curved beams

The performance of two curved beam finite element models based on coupled polynomial displacement fields is investigated for out-of-plane vibration of arches. These two-noded beam models employ curvilinear strain definitions and have three degrees of freedom per node namely, out-of-plane translation (v), out-of-plane bending rotation (theta(z)) and torsion rotation (theta(s)). The coupled polynomial interpolation fields are derived independently for Timoshenko and Euler-Bernoulli beam elements using the force-moment equilibrium equations. Numerical performance of these elements for constrained and unconstrained arches is compared with the conventional curved beam models which are based on independent polynomial fields. The formulation is shown to be free from any spurious constraints in the limit of `flexureless torsion' and `torsionless flexure' and hence devoid of flexure and torsion locking. The resulting stiffness and consistent mass matrices generated from the coupled displacement models show excellent convergence of natural frequencies in locking regimes. The accuracy of the shear flexibility added to the elements is also demonstrated. The coupled polynomial models are shown to perform consistently over a wide range of flexure-to-shear (EI/GA) and flexure-to-torsion (EI/GJ) stiffness ratios and are inherently devoid of flexure, torsion and shear locking phenomena. (C) 2015 Elsevier B.V. All rights reserved.

A taxonomic mystery for more than 180 years: the identity and systematic position of Brachysaura minor (HARDWICKE & GRAY, 1827)

Brachysaura is a monotypic genus of agamid lizard found in the Indian subcontinent; the identity and systematic position of B. minor has been long debated, and it has at times been subsumed into Agama, Charasia and Laudakia, with some authors suggesting affinities to Calotes. We constructed nuclear and mitochondrial phylogenetic trees including Brachysaura and allied agamid genera to resolve its phylogenetic position. We also compared osteology and external morphology with the genera Agama, Calotes and Laudakia. Hemipenial morphology was compared with Calotes and some other agamids from South Asia. Both nuclear and mitochondrial phylogenies demonstrate that Brachysaura is nested within the widespread South and Southeast Asian genus Calotes, with which it also shares certain external morphological, osteological and hemipenial characters. Adaptations to ground dwelling in Brachysaura minor has resulted in unique modifications to its body plan, which is likely why generic allocation has been long confused. This study also highlights the need for an integrated systematic approach to resolve taxonomic ambiguity in Asian agamids.

Inverse Polynomial Based Explicit Guidance for Lunar Soft Landing During Powered Braking

In this paper an explicit guidance law for the powered descent phase of the soft lunar landing is presented. The descent trajectory, expressed in polynomial form is fixed based on the boundary conditions imposed by the precise soft landing mission. Adapting an inverse model based approach, the guidance command is computed from the known spacecraft trajectory. The guidance formulation ensures the vertical orientation of the spacecraft during touchdown. Also a closed form relation for the final flight time is proposed. The final time is expressed as a function of initial position and velocity of the spacecraft ( at the start of descent) and also depends on the desired landing site. To ensure the fuel minimum descent the proposed explicit method is extended to optimal guidance formulation. The effectiveness of the proposed guidance laws are demonstrated with simulation results.

Generic identity of Camptorrhiza indica (Colchicaceae) based on cytogenetics and molecular phylogenetics

The tribe Iphigenieae (Colchicaceace, Liliales) includes two genera, viz. Camptorrhiza and Iphigenia, which are distributed in Africa, India, and Australasia. Iphigenia is represented by 12 species, of which six occur in India while Camptorrhiza comprises one species each in Africa (C. strumosa) and India (C. indica). The genus Camptorrhiza possesses a knee-shaped tuber attached to the corms, filaments with a thick bulge in the middle and styles with single stigma. Iphigenia on the other hand lacks knee-shaped tuber, bears linear filaments and has styles with three stigmas. Camptorrhiza indica possesses ovoid corms, linear filaments and styles with a single stigma. These characters are intermediate between Iphigenia and Camptorrhiza and hence we studied the cytogenetics and phylogenetic placement of this species to ascertain its generic identity. Somatic chromosome count (2n = 22) and karyotypic features of C. indica are very similar to that of Iphigenia species. Molecular phylogenetic studies based on atpB-rbcL, rps16, trnL, and trnL-F regions showed that C. indica is nested within a lineage of Indian Iphigenia species. Thus, C. indica was reduced to a species of Iphigenia, i.e., I. ratnagirica. Camptorrhiza is now a monotypic genus restricted only to southern Africa. A key to the Indian Iphigenia species is provided. In addition, a new combination Wurmbea novae-zelandiae is proposed for Iphigenia novae-zelandiae.

FAST AND ACCURATE BILATERAL FILTERING USING GAUSS-POLYNOMIAL DECOMPOSITION

The bilateral filter is a versatile non-linear filter that has found diverse applications in image processing, computer vision, computer graphics, and computational photography. A common form of the filter is the Gaussian bilateral filter in which both the spatial and range kernels are Gaussian. A direct implementation of this filter requires O(sigma(2)) operations per pixel, where sigma is the standard deviation of the spatial Gaussian. In this paper, we propose an accurate approximation algorithm that can cut down the computational complexity to O(1) per pixel for any arbitrary sigma (constant-time implementation). This is based on the observation that the range kernel operates via the translations of a fixed Gaussian over the range space, and that these translated Gaussians can be accurately approximated using the so-called Gauss-polynomials. The overall algorithm emerging from this approximation involves a series of spatial Gaussian filtering, which can be efficiently implemented (in parallel) using separability and recursion. We present some preliminary results to demonstrate that the proposed algorithm compares favorably with some of the existing fast algorithms in terms of speed and accuracy.

Some implications of the volcanic theophany of YHWH on his primeval identity

Abstract: YHWH’s theophany and mode of action are frequently evoked in the Bible as a volcanic event. It is shown here that this representation, of central importance in the story of the Sinai Covenant, is probably not anchored in any specific volcanic eruption experienced by the Israelites in the past. In Antiquity, volcanic activity was specifically associated with the gods who patronized metallurgy, given the homology between lava flowing from a volcano and slag released from a furnace at smelting. Evidence towards such a link is also identified in the Bible. Accordingly, rather than being simply a literary artifice imaging the outstanding powers of YHWH, volcanism may reflect the existence of metallurgical roots in Israelite theology. This contention is supported by Biblical evidences associating YHWH with metal production: (i) his primeval dominion in mining areas, (ii) his special worship by metalworkers, (iii) the representation of his celestial universe as a giant furnace. It is concluded that the volcanic representation of YHWH’s theophany and mode of action reveal a surprising level of preservation of the metallurgic religious traditions in the ancient Israelite theology.

Personal identity. A theoretical and experimental analysis

Published as article in: Journal of Economic Methodology, 2010, vol. 17, issue 3, pages 261-275.