Complexity of the satisfiability problem for multilinear forms over a finite field

Multilinear forms over finite fields are considered. Multilinear forms over a field are products in which each factor is the sum of variables or elements of this field. Each multilinear form defines a function over this field. A multilinear form is called satisfiable if it represents a nonzero function. We show the N P-completeness of the satisfiability recognition problem for multilinear forms over each finite field of q elements for q ≥ 3. A theorem is proved that distinguishes cases of polynomiality and NP-completeness of the satisfiability recognition problem for multilinear fields for each possible q ≥ 3.     

Time-stepping discontinuous Galerkin approximation of optimal control problem governed by time fractional diffusion equation

In this paper, a piecewise constant time-stepping discontinuous Galerkin method combined with a piecewise linear finite element method is applied to solve control constrained optimal control problem governed by time fractional diffusion equation. The control variable is approximated by variational discretization approach. The discrete first-order optimality condition is derived based on the first discretize then optimize approach. We demonstrate the commutativity of discretization and optimization for the time-stepping discontinuous Galerkin discretization. Since the state variable and the adjoint state variable in general have weak singularity near t =?0and t = T, a time adaptive algorithm is developed based on step doubling technique, which can be used to guide the time mesh refinement. Numerical examples are given to illustrate the theoretical findings.     

Numerical optimization method for packing regular convex polygons

An algorithm is presented for the approximate solution of the problem of packing regular convex polygons in a given closed bounded domain G so as to maximize the total area of the packed figures. On G a grid is constructed whose nodes generate a finite set W on G, and the centers of the figures to be packed can be placed only at some points of W. The problem of packing these figures with centers in W is reduced to a 0-1 linear programming problem. A two-stage algorithm for solving the resulting problems is proposed. The algorithm finds packings of the indicated figures in an arbitrary closed bounded domain on the plane. Numerical results are presented that demonstrate the effectiveness of the method.     

Stabilization of a Class of Uncertain Systems

We consider the problem to synthesize a stabilizing control u synthesis for systems \(\frac{{dx}}{{dt}} = Ax + Bu\) where A ∈ ?^n×n and B ∈ ?^n×m, while the elements α_i,j(·) of the matrix A are uniformly bounded nonanticipatory functionals of arbitrary nature. If the system is continuous, then the elements of the matrix B are continuous and uniformly bounded functionals as well. If the system is pulse-modulated, then the elements of the matrix B are differentiable uniformly bounded functions of time. It is assumed that k isolated uniformly bounded elements \({\alpha _{{i_l},{j_l}}}\left( \cdot \right)\) satisfying the condition \(\mathop {\inf }\limits_{\left( \cdot \right)} \left| {{\alpha _{{i_l},{j_l}}}\left( \cdot \right)} \right|{\alpha _ - } > 0,\quad l \in \overline {1,k}\) are located above the main diagonal of the matrix A(·), where G _k is the set of all isolated elements of the system, J₁ is the set of indices of rows of matrix A(·) containing isolated elements, and J₂ is the set of indices of its rows free of isolated elements. It is assumed that other elements located above the main diagonal are sufficiently small provided that their row indices belong to J₁, i.e., \(\mathop {\sup }\limits_{\left( \cdot \right)} \left| {{\alpha _{i,j}}\left( \cdot \right)} \right| < \delta ,\quad {\alpha _{i,j}} \notin {G_k},\quad i \in {J_1},\quad j > i\). All other elements located above the main diagonal are uniformly bounded. The relation u = S(·)x is satisfied in the continuous case, while the relation u = ξ(t) is satisfied in the pulse-modulated case; here the components of the vector ξ are outputs of synchronous pulse elements. Constructing a special quadratic Lyapunov function, one can determine a matrix S(·) such that the closed system becomes globally exponentially stable in the continuous case. In the pulse-modulated case, input pulses are synthesized such that the system becomes globally asymptotically stable.     

Decay estimates of discretized Green's functions for Schrdinger type operators

For a sparse non-singular matrix A, generally A~(-1)is a dense matrix. However, for a class of matrices,A~(-1)can be a matrix with off-diagonal decay properties, i.e., |A_(ij)~(-1)| decays fast to 0 with respect to the increase of a properly defined distance between i and j. Here we consider the off-diagonal decay properties of discretized Green's functions for Schr¨odinger type operators. We provide decay estimates for discretized Green's functions obtained from the finite difference discretization, and from a variant of the pseudo-spectral discretization. The asymptotic decay rate in our estimate is independent of the domain size and of the discretization parameter.We verify the decay estimate with numerical results for one-dimensional Schr¨odinger type operators.     

Calculation of Bezout’s coefficients for the <Emphasis Type="Italic">k</Emphasis>-ary algorithm of finding GCD

Bezout’s equation is a representation of the greatest common divisor d of integers A and B as a linear combination Ax + By = d, where x and y are integers called Bezout’s coefficients. The task of finding Bezout’s coefficients has numerous applications in the number theory and cryptography, for example, for calculation of multiplicative inverse elements in modular arithmetic. Usually Bezout’s coefficients are caclulated using the extended version of the classical Euclidian algorithm.We elaborate a new algorithm for calculating Bezout’s coefficients based on the k-ary GCD algorithm.     

A modified greedy analysis pursuit algorithm for the cosparse analysis model

In the past decade, the sparse representation synthesis model has been deeply researched and widely applied in signal processing. Recently, a cosparse analysis model has been introduced as an interesting alternative to the sparse representation synthesis model. The sparse synthesis model pay attention to non-zero elements in a representation vector x, while the cosparse analysis model focuses on zero elements in the analysis representation vector Ωx. This paper mainly considers the problem of the cosparse analysis model. Based on the greedy analysis pursuit algorithm, by constructing an adaptive weighted matrix W _k?1, we propose a modified greedy analysis pursuit algorithm for the sparse recovery problem when the signal obeys the cosparse model. Using a weighted matrix, we fill the gap between greedy algorithm and relaxation techniques. The standard analysis shows that our algorithm is convergent. We estimate the error bound for solving the cosparse analysis model, and then the presented simulations demonstrate the advantage of the proposed method for the cosparse inverse problem.     

Parametric Integer Programming Analysis: A Contraction Approach

An algorithm is presented for solving families of integer linear programming problems in which the problems are "related" by having identical objective coefficients and constraint matrix coefficients. The righthand-side constants have the form b + θd where b and d are conformable vectors and θ varies from zero to one.The approach consists primarily of solving the most relaxed problem (θ = 1) using cutting planes and then contracting the region of feasible integer solutions in such a manner that the current optimal integer solution is eliminated.The algorithm was applied to 1800 integer linear programming problems with reasonable success. Integer programming problems which have proved to be unsolvable using cutting planes have been solved by expanding the region of feasible integer solutions (θ = 1) and then contracting to the original region.     

Improved Approximation for Guarding Simple Galleries from the Perimeter

We provide an O(log?log?opt)-approximation algorithm for the problem of guarding a simple polygon with guards on the perimeter. We first design a polynomial-time algorithm for building ε-nets of size \(O(\frac{1}{\varepsilon}\log\log\frac{1}{\varepsilon})\) for the instances of Hitting Set associated with our guarding problem. We then apply the technique of Brönnimann and Goodrich to build an approximation algorithm from this ε-net finder. Along with a simple polygon P, our algorithm takes as input a finite set of potential guard locations that must include the polygon’s vertices. If a finite set of potential guard locations is not specified, e.g., when guards may be placed anywhere on the perimeter, we use a known discretization technique at the cost of making the algorithm’s running time potentially linear in the ratio between the longest and shortest distances between vertices. Our algorithm is the first to improve upon O(log?opt)-approximation algorithms that use generic net finders for set systems of finite VC-dimension.     

On the Generalized Stochastic Dirichlet Problem—Part II: Solvability,Stability and the Colombeau Case

In this paper we consider the stochastic Dirichlet problem \(L\lozenge u=h+\nabla f\) in the framework of white noise analysis combined with Sobolev space and Colombeau algebra methods. The operator L is assumed to be strictly elliptic in divergence form \(L\lozenge u=\nabla(A\lozenge\nabla u+b\lozenge u)+c\lozenge\nabla u+d\lozenge u\). Its coefficients: the elements of the matrix A and of the vectors b, c and d are assumed to be generalized random processes, and the product of two generalized processes is interpreted as the Wick product. Generalized random processes are considered as linear bounded mappings from the Sobolev space \(W_0^{1,2}\) into the Kondratiev space (S)_???1. In this paper we prove existence and uniqueness of the problem of this form in the case when the operator L generates a coercive bilinear form, and then extend this result to the general case. We also consider the case when the coefficients of L, the input data and the boundary condition are Colombeau-type generalized stochastic processes.     

Bounded Engel elements in groups satisfying an identity

We prove that a residually finite group G satisfying an identity \(w\equiv 1\) and generated by a commutator closed set X of bounded left Engel elements is locally nilpotent. We also extend such a result to locally graded groups, provided that X is a normal set. As an immediate consequence, we obtain that a locally graded group satisfying an identity, all of whose elements are bounded left Engel, is locally nilpotent.     

On the lower order of mappings with finite length distortion

We study the problem of the so-called lower order for one kind of mappings with finite distortion, actively investigated in the recent 15–20 years.We prove that mappings with finite length distortion f: D → ? ⁿ , n ≥ 2, whose outer dilatation is integrable to the power α > n ? 1 with finite asymptotic limit have lower order bounded from below.     

On the genericity of loxodromic actions

Suppose that a finitely generated group G acts by isometries on a δ-hyperbolic space, with at least one element acting loxodromically. Suppose that the elements of G have a normal form such that the language of normal forms can be recognized by a finite state automaton. Suppose also that a certain compatibility condition linking the automatic and the δ-hyperbolic structures is satisfied. Then we prove that in the “ball” consisting of elements of G whose normal form is of length at most l, the proportion of elements which act loxodromically is bounded away from zero, as l tends to infinity. We present several applications of this result, including the genericity of pseudo-Anosov braids.     

On homogenization for non-self-adjoint locally periodic elliptic operators

In this note we consider the homogenization problem for a matrix locally periodic elliptic operator on R ^d of the form A ^ε = ?divA(x, x/ε)?. The function A is assumed to be Hölder continuous with exponent s ∈ [0, 1] in the “slow” variable and bounded in the “fast” variable. We construct approximations for (A ^ε ? μ)^?1, including one with a corrector, and for (?Δ) ^s/2(A ^ε ? μ)^?1 in the operator norm on L ₂(R ^d ) ⁿ . For s ≠ 0, we also give estimates of the rates of approximation.     

Conjugate Cauchy Problem for Parabolic Shilov Type Systems with Nonnegative Genus

The problem of solvability of the Gelfand–Shilov conjugate Cauchy problem for parabolic Shilov type systems with variable coefficients of bounded smoothness and nonnegative genus in the spaces S _β is studied by constructing the fundamental solution of this problem and analyzing its basic properties.     

Orthogonal series and limit theorems for canonical <Emphasis Type="Italic">U</Emphasis>-and <Emphasis Type="Italic">V</Emphasis>-statistics of stationary connected observations

The limit behavior is studied for the distributions of normalized U-and V-statistics of an arbitrary order with canonical (degenerate) kernels, based on samples of increasing sizes from a stationary sequence of observations satisfying φ-or α-mixing. The corresponding limit distributions are represented as infinite multilinear forms of a centered Gaussian sequence with a known covariance matrix.     

Robust kernel-based regression with bounded influence for outliers

The kernel-based regression (KBR) method, such as support vector machine for regression (SVR) is a well-established methodology for estimating the nonlinear functional relationship between the response variable and predictor variables. KBR methods can be very sensitive to influential observations that in turn have a noticeable impact on the model coefficients. The robustness of KBR methods has recently been the subject of wide-scale investigations with the aim of obtaining a regression estimator insensitive to outlying observations. However, existing robust KBR (RKBR) methods only consider Y-space outliers and, consequently, are sensitive to X-space outliers. As a result, even a single anomalous outlying observation in X-space may greatly affect the estimator. In order to resolve this issue, we propose a new RKBR method that gives reliable result even if a training data set is contaminated with both Y-space and X-space outliers. The proposed method utilizes a weighting scheme based on the hat matrix that resembles the generalized M-estimator (GM-estimator) of conventional robust linear analysis. The diagonal elements of hat matrix in kernel-induced feature space are used as leverage measures to downweight the effects of potential X-space outliers. We show that the kernelized hat diagonal elements can be obtained via eigen decomposition of the kernel matrix. The regularized version of kernelized hat diagonal elements is also proposed to deal with the case of the kernel matrix having full rank where the kernelized hat diagonal elements are not suitable for leverage. We have shown that two kernelized leverage measures, namely, the kernel hat diagonal element and the regularized one, are related to statistical distance measures in the feature space. We also develop an efficiently kernelized training algorithm for the parameter estimation based on iteratively reweighted least squares (IRLS) method. The experimental results from simulated examples and real data sets demonstrate the robustness of our proposed method compared with conventional approaches.     

A discontinuous Galerkin method for time fractional diffusion equations with variable coefficients

We propose a piecewise-linear, time-stepping discontinuous Galerkin method to solve numerically a time fractional diffusion equation involving Caputo derivative of order μ ∈ (0, 1) with variable coefficients. For the spatial discretization, we apply the standard continuous Galerkin method of total degree ≤ 1 on each spatial mesh elements. Well-posedness of the fully discrete scheme and error analysis will be shown. For a time interval (0, T) and a spatial domain Ω, our analysis suggest that the error in \(L^{2}\left ((0,T),L^{2}({\Omega })\right )\)-norm is \(O(k^{2-\frac {\mu }{2}}+h^{2})\) (that is, short by order \(\frac {\mu }{2}\) from being optimal in time) where k denotes the maximum time step, and h is the maximum diameter of the elements of the (quasi-uniform) spatial mesh. However, our numerical experiments indicate optimal O(k² + h²) error bound in the stronger \(L^{\infty }\left ((0,T),L^{2}({\Omega })\right )\)-norm. Variable time steps are used to compensate the singularity of the continuous solution near t = 0.     

Factorization of cp-rank-3 completely positive matrices

A symmetric positive semi-definite matrix A is called completely positive if there exists a matrix B with nonnegative entries such that A = BB^?. If B is such a matrix with a minimal number p of columns, then p is called the cp-rank of A. In this paper we develop a finite and exact algorithm to factorize any matrix A of cp-rank 3. Failure of this algorithm implies that A does not have cp-rank 3. Our motivation stems from the question if there exist three nonnegative polynomials of degree at most four that vanish at the boundary of an interval and are orthonormal with respect to a certain inner product.     

On the numerical solution of a minimax control problem with a positional functional

The probabilistic analysis of an approximation algorithm for the minimum-weight m-peripatetic salesman problem with different weight functions of their routes (Hamiltonian cycles) is presented. The time complexity of the algorithm is O(mn ²). It is assumed that the elements of the distance matrix are independent equally distributed random variables with values in an upper unbounded domain [a _n , ∞), where a _n > 0. The analysis is carried out for the example of truncated normal and exponential distributions. Estimates for the relative error and failure probability, as well as conditions for the asymptotic exactness of the algorithm, are found.