Similarity of Matrices Over Local Rings of Length Two

Let R be a (commutative) local principal ideal ring of length two, for example, the ring R = Z/p(2)Z with p prime. In this paper, we develop a theory of normal forms for similarity classes in the matrix rings M-n (R) by interpreting them in terms of extensions of R t]-modules. Using this theory, we describe the similarity classes in M-n (R) for n <= 4, along with their centralizers. Among these, we characterize those classes which are similar to their transposes. Non-self-transpose classes are shown to exist for all n > 3. When R has finite residue field of order q, we enumerate the similarity classes and the cardinalities of their centralizers as polynomials in q. Surprisingly, the polynomials representing the number of similarity classes in M-n (R) turn out to have non-negative integer coefficients.

Lower Bounds for Sums of Powers of Low Degree Univariates

We consider the problem of representing a univariate polynomial f(x) as a sum of powers of low degree polynomials. We prove a lower bound of Omega(root d/t) for writing an explicit univariate degree-d polynomial f(x) as a sum of powers of degree-t polynomials.

Spectral solutions to the Korteweg-de-Vries and nonlinear Schrodinger equations

In this paper, we present the solutions of 1-D and 2-D non-linear partial differential equations with initial conditions. We approach the solutions in time domain using two methods. We first solve the equations using Fourier spectral approximation in the spatial domain and secondly we compare the results with the approximation in the spatial domain using orthogonal functions such as Legendre or Chebyshev polynomials as their basis functions. The advantages and the applicability of the two different methods for different types of problems are brought out by considering 1-D and 2-D nonlinear partial differential equations namely the Korteweg-de-Vries and nonlinear Schrodinger equation with different potential function. (C) 2015 Elsevier Ltd. All rights reserved.

An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas

We show here a 2(Omega(root d.log N)) size lower bound for homogeneous depth four arithmetic formulas. That is, we give an explicit family of polynomials of degree d on N variables (with N = d(3) in our case) with 0, 1-coefficients such that for any representation of a polynomial f in this family of the form f = Sigma(i) Pi(j) Q(ij), where the Q(ij)'s are homogeneous polynomials (recall that a polynomial is said to be homogeneous if all its monomials have the same degree), it must hold that Sigma(i,j) (Number of monomials of Q(ij)) >= 2(Omega(root d.log N)). The above mentioned family, which we refer to as the Nisan-Wigderson design-based family of polynomials, is in the complexity class VNP. Our work builds on the recent lower bound results 1], 2], 3], 4], 5] and yields an improved quantitative bound as compared to the quasi-polynomial lower bound of 6] and the N-Omega(log log (N)) lower bound in the independent work of 7].

Counting zero kernel pairs over a finite field

Helmke et al. have recently given a formula for the number of reachable pairs of matrices over a finite field. We give a new and elementary proof of the same formula by solving the equivalent problem of determining the number of so called zero kernel pairs over a finite field. We show that the problem is, equivalent to certain other enumeration problems and outline a connection with some recent results of Guo and Yang on the natural density of rectangular unimodular matrices over F-qx]. We also propose a new conjecture on the density of unimodular matrix polynomials. (C) 2016 Elsevier Inc. All rights reserved.

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.