Cylindrical decomposition for systems transcendental in the first variable

We present a generalization of the Cylindrical Algebraic Decomposition (CAD) algorithm to systems of equations and inequalities in functions of the form p(x,f₁(x),…,f_m(x),y₁,…,y_n), where p∈Q[x,t₁,…,t_m,y₁,…,y_n] and f₁(x),…,f_m(x) are real univariate functions such that there exists a real root isolation algorithm for functions from the algebra Q[x,f₁(x),…,f_m(x)]. In particular, the algorithm applies when f₁(x),…,f_m(x) are real exp-log functions or tame elementary functions.     

Substitutions into propositional tautologies

We prove that there is a polynomial time substitution (y₁,…,yn):=g(x₁,…,xk) with k?n such that whenever the substitution instance A(g(x₁,…,xk)) of a 3DNF formula A(y₁,…,yn) has a short resolution proof it follows that A(y₁,…,yn) is a tautology. The qualification “short” depends on the parameters k and n.     

Fixed point theorem of generalized quasi-contractive mapping in cone metric space

In this paper, we introduce the generalized quasi-contractive mapping f in a cone metric space (X,d). f is called a generalized quasi-contractive if there is a real λ∈[0,1) such that for all x,y∈X,

d(fx,fy)≤λs     

Variance based sensitivity analysis of model output. Design and estimator for the total sensitivity index

Variance based methods have assessed themselves as versatile and effective among the various available techniques for sensitivity analysis of model output. Practitioners can in principle describe the sensitivity pattern of a model Y=f(X₁,X₂,…,Xk) with k uncertain input factors via a full decomposition of the variance V of Y into terms depending on the factors and their interactions. More often practitioners are satisfied with computing just k first order effects and k total effects, the latter describing synthetically interactions among input factors. In sensitivity analysis a key concern is the computational cost of the analysis, defined in terms of number of evaluations of f(X₁,X₂,…,Xk) needed to complete the analysis, as f(X₁,X₂,…,Xk) is often in the form of a numerical model which may take long processing time. While the computational cost is relatively cheap and weakly dependent on k for estimating first order effects, it remains expensive and strictly k-dependent for total effect indices. In the present note we compare existing and new practices for this index and offer recommendations on which to use.     

Efficient evaluation of specific queries in constraint databases

Let F₁,…,Fs∈R[X₁,…,Xn] be polynomials of degree at most d, and suppose that F₁,…,Fs are represented by a division free arithmetic circuit of non-scalar complexity size L. Let A be the arrangement of Rn defined by F₁,…,Fs.For any point x∈Rn, we consider the task of determining the signs of the values F₁(x),…,Fs(x) (sign condition query) and the task of determining the connected component of A to which x belongs (point location query). By an extremely simple reduction to the well-known case where the polynomials F₁,…,Fs are affine linear (i.e., polynomials of degree one), we show first that there exists a database of (possibly enormous) size sO(L+n) which allows the evaluation of the sign condition query using only (Ln)^O(1)log(s) arithmetic operations. The key point of this paper is the proof that this upper bound is almost optimal.By the way, we show that the point location query can be evaluated using dO(n)log(s) arithmetic operations. Based on a different argument, analogous complexity upper-bounds are exhibited with respect to the bit-model in case that F₁,…,Fs belong to Z[X₁,…,Xn] and satisfy a certain natural genericity condition. Mutatis mutandis our upper-bound results may be applied to the sparse and dense representations of F₁,…,Fs.     

Strong orientations of complete k-partite graphs achieving the strong diameter

In this paper, we consider each integer d between the lower and upper orientable strong diameter of the complete k-partite graph K(m₁,m₂,…,mk), and show that there does exist a strong orientation of K(m₁,m₂,…,mk) such that sdiam(K)=d.     

Acyclic and k-distance coloring of the grid

In this paper, we give a relatively simple though very efficient way to color the d-dimensional grid G(n₁,n₂,…,n_d) (with n_i vertices in each dimension 1?i?d), for two different types of vertex colorings: (1) acyclic coloring of graphs, in which we color the vertices such that (i) no two neighbors are assigned the same color and (ii) for any two colors i and j, the subgraph induced by the vertices colored i or j is acyclic; and (2) k-distance coloring of graphs, in which every vertex must be colored in such a way that two vertices lying at distance less than or equal to k must be assigned different colors. The minimum number of colors needed to acyclically color (respectively k-distance color) a graph G is called acyclic chromatic number of G (respectively k-distance chromatic number), and denoted a(G) (respectively χ_k(G)).The method we propose for coloring the d-dimensional grid in those two variants relies on the representation of the vertices of G_d(n₁,…,n_d) thanks to its coordinates in each dimension; this gives us upper bounds on a(G_d(n₁,…,n_d)) and χ_k(G_d(n₁,…,n_d)).We also give lower bounds on a(G_d(n₁,…,n_d)) and χ_k(G_d(n₁,…,n_d)). In particular, we give a lower bound on a(G) for any graph G; surprisingly, as far as we know this result was never mentioned before. Applied to the d-dimensional grid G_d(n₁,…,n_d), the lower and upper bounds for a(G_d(n₁,…,n_d)) match (and thus give an optimal result) when the lengths in each dimension are “sufficiently large” (more precisely, if ). If this is not the case, then these bounds differ by an additive constant at most equal to . Concerning χ_k(G_d(n₁,…,n_d)), we give exact results on its value for (1) k=2 and any d?1, and (2) d=2 and any k?1.In the case of acyclic coloring, we also apply our results to hypercubes of dimension d, H_d, which are a particular case of G_d(n₁,…,n_d) in which there are only 2 vertices in each dimension. In that case, the bounds we obtain differ by a multiplicative constant equal to 2.     

Geodesic methods in quantitative image analysis

Let X be a part of an image to be analysed. Given two arbitrary points x and y of X, let us define the number d_x(x, y) as follows: d_x(x, y) is the lower bound of the lengths of the arcs in X ending at points x and y, if such arcs exist, and + α if not. The function d_x is an X-intrinsic distance function, called ‘geodesic distance’. Note that if x and y belong to two disjoint connected components of X, d_x(x, y) = + α. In other words, d_x seems to be an appropriate distance function to deal with connectivity problems.In the metric space (X, d_x), all the classical morphological transformations (dilation, erosion, skeletonization, etc.) can be defined. The geodesic distance d_x also provides rigorous definitions of topological transformations, which can be performed by automatic image analysers with the help of parallel iterative algorithms.All these notions are illustrated by several examples (definition of the length of a fibre and of an effective length factor; automatic detection of cells having at least one nucleus or having one single nucleus; definitions of the geodesic center and of the ends of an object without a hole; etc.). The corresponding algorithms are described.     

Online Metric Tracking and Smoothing

We consider the online smoothing problem, in which a tracker is required to maintain distance no more than Δ≥0 from a time-varying signal f while minimizing its own movement. The problem is determined by a metric space (X,d) with an associated cost function c:?→?. Given a signal f ₁,f ₂,…∈X the tracker is responsible for producing a sequence a ₁,a ₂,… of elements of X that meet the proximity constraint: d(f _i ,a _i )≤Δ. To complicate matters, the tracker is on-line—the value a _i may only depend on f ₁,…,f _i —and wishes to minimize the cost of his travels, ∑c(d(a _i ,a _i+1)). We evaluate such tracking algorithms competitively, comparing this with the cost achieved by an optimal adversary apprised of the entire signal in advance. The problem was originally proposed by Yi and Zhang (In: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms (SODA), pp. 1098–1107. ACM Press, New York, 2009), who considered the natural circumstance where the metric spaces are taken to be ? ^k with the ? ₂ metric and the cost function is equal to 1 unless the distance is zero (thus the tracker pays a fixed cost for any nonzero motion).

We begin by studying arbitrary metric spaces with the “pay if you move” metric of Yi and Zhang (In: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms (SODA), pp. 1098–1107. ACM Press, New York, [2009]) described above and describe a natural randomized algorithm that achieves a O(logb _Δ)-competitive ratio, where b _Δ=max _x∈X |B _Δ(x)| is the maximum number of points appearing in any ball of radius Δ. We show that this bound is tight.

We then focus on the metric space ? with natural families of monotone cost functions c(x)=x ^p for some p≥0. We consider both the expansive case (p≥1) and the contractive case (p<1), and show that the natural lazy algorithm performs well in the expansive case. In the contractive case, we introduce and analyze a novel deterministic algorithm that achieves a constant competitive ratio depending only on p. Finally, we observe that by slightly relaxing the guarantee provided by the tracker, one can obtain natural analogues of these algorithms that work in continuous metric spaces.

     

Two methods for the calculation of the degree of an approximate greatest common divisor of two inexact polynomials

The calculation of the degree d of an approximate greatest common divisor of two inexact polynomials f(y) and g(y) reduces to the determination of the rank loss of a resultant matrix, the entries of which are functions of the coefficients of f(y) and g(y). This paper considers this issue by describing two methods to calculate d, such that knowledge of the noise level imposed on the coefficients of f(y) and g(y) is not assumed. One method uses the residual of a linear algebraic equation whose coefficient matrix and right hand side vector are derived from the Sylvester resultant matrix S(f,g), and the other method uses the first principal angle between a line and a hyperplane, the equations of which are calculated from S(f,g). Computational results on inexact polynomials whose exact forms have multiple roots of high degree are shown and very good results are obtained. These results are compared with the rank loss of S(f,g) for the calculation of d, and it is shown that this method yields incorrect results for these examples.     

On the Practical Solution of Genus Zero Diophantine Equations

Let f(X, Y) be an absolutely irreducible polynomial with integer coefficients such that the curve defined by the equation f(X, Y)  =  0 is of genus 0 having at least three infinite valuations. This paper describes a practical general method for the explicit determination of all integer solutions of the diophantine equation f(X, Y)  =  0. Some elaborated examples are given.     

Optimal evaluation of generalized Euler angles with applications to control

Given two linearly independent matrices in so(3), Z₁ and Z₂, every rotation matrix, X_f∈SO(3), can be written as the product of alternate elements from the one-dimensional subgroups corresponding to Z₁ and Z₂, namely X_f=e^Z₁t₁e^Z₂t₂e^Z₁t₃?e^Z₁t_s. The parameters t_i, i=1,…,s are called Generalized Euler Angles. In this paper, the minimum number of factors required for the factorization of X_f∈SO(3), as a function of X_f, is evaluated. An algorithm is given to determine the generalized Euler angles, in the optimal factorization. The results can be applied to the bang-bang control, with minimum number of switches, of some classical and quantum systems.     

The interval-merging problem

A closed interval is an ordered pair of real numbers [x, y], with x ? y. The interval [x, y] represents the set {i ∈ R∣x ? i ? y}. Given a set of closed intervals I={[a₁,b₁],[a₂,b₂],…,[a_k,b_k]}, the Interval-Merging Problem is to find a minimum-cardinality set of intervals M(I)={[x₁,y₁],[x₂,y₂],…,[x_j,y_j]}, j ? k, such that the real numbers represented by equal those represented by . In this paper, we show the problem can be solved in O(d log d) sequential time, and in O(log d) parallel time using O(d) processors on an EREW PRAM, where d is the number of the endpoints of I. Moreover, if the input is given as a set of sorted endpoints, then the problem can be solved in O(d) sequential time, and in O(log d) parallel time using O(d/log d) processors on an EREW PRAM.     

Set-contractive mappings and difference equations in Banach spaces

In this paper, we consider the difference equation on an arbitrary Banach space (X, ∥·∥_x), Δ(q_nΔx_n + f_n(x_n) = 0, where {q_n} is a positive sequence and f_n is X-valued. We shall give conditions so that for a given x ϵ X, there exists a solution of this equation asymptotically equal to x.     

Asymptotic equivalence between two difference systems

In this paper, we study the asymptotic equivalence between the linear system Δx(n) = A(n)x(n) and its perturbation Δy(n) = A(n)y(n)+g(n, y(n)) by using the comparison principle and supplementary projections. Furthermore, we establish some asymptotic properties for the nonlinear system Δx(n) = f(n, x(n)).     

Solving Genus Zero Diophantine Equations with at Most Two Infinite Valuations

Let f(X, Y) be an absolutely irreducible polynomial with integer coefficients such that the curve defined by the equation f(X, Y)  =  0 is of genus 0 having at most two infinite valuations. This paper describes a practical general method for the explicit determination of all integer solutions of the diophantine equation f(X, Y)  =  0. Several elaborated examples are given. Furthermore, a necessary and sufficient condition for a curve of genus 0 to have infinitely many integer points is obtained.     

The F5 criterion revised

The purpose of this work is to generalize part of the theory behind Faugère’s “F5” algorithm. This is one of the fastest known algorithms to compute a Gröbner basis of a polynomial ideal I generated by polynomials f₁,…,f_m. A major reason for this is what Faugère called the algorithm’s “new” criterion, and we call “the F5 criterion”; it provides a sufficient condition for a set of polynomials G to be a Gröbner basis. However, the F5 algorithm is difficult to grasp, and there are unresolved questions regarding its termination.This paper introduces some new concepts that place the criterion in a more general setting: S-Gröbner bases and primitive S-irreducible polynomials. We use these to propose a new, simple algorithm based on a revised F5 criterion. The new concepts also enable us to remove various restrictions, such as proving termination without the requirement that f₁,…,f_m be a regular sequence.     

A Linear Time Algorithm for L(2,1)-Labeling of Trees

An L(2,1)-labeling of a graph G is an assignment f from the vertex set V(G) to the set of nonnegative integers such that |f(x)?f(y)|≥2 if x and y are adjacent and |f(x)?f(y)|≥1 if x and y are at distance 2, for all x and y in V(G). A k-L(2,1)-labeling is an L(2,1)-labeling f:V(G)→{0,…,k}, and the L(2,1)-labeling problem asks the minimum k, which we denote by λ(G), among all possible assignments. It is known that this problem is NP-hard even for graphs of treewidth 2, and tree is one of very few classes for which the problem is polynomially solvable. The running time of the best known algorithm for trees had been O(Δ ^4.5 n) for more than a decade, and an O(min{n ^1.75,Δ ^1.5 n})-time algorithm has appeared recently, where Δ and n are the maximum degree and the number of vertices of an input tree, however, it has been open if it is solvable in linear time. In this paper, we finally settle this problem by establishing a linear time algorithm for L(2,1)-labeling of trees. Furthermore, we show that it can be extended to a linear time algorithm for L(p,1)-labeling with a constant p.     

Applications of complete discrimination system for polynomial for classifications of traveling wave solutions to nonlinear differential equations

If a partial differential equation is reduced to an ordinary differential equation in the form u^′(ξ)=G(u,θ₁,…,θm) under the traveling wave transformation, where θ₁,…,θm are parameters, its solutions can be written as an integral form . Therefore, the key steps are to determine the parameters' scopes and to solve the corresponding integral. When G is related to a polynomial, a mathematical tool named complete discrimination system for polynomial is applied to this problem so that the parameter's scopes can be determined easily. The complete discrimination system for polynomial is a natural generalization of the discrimination △=b²−4ac of the second degree polynomial ax²+bx+c. For example, the complete discrimination system for the third degree polynomial F(w)=w³+d₂w²+d₁w+d₀ is given by and . In the paper, we give some new applications of the complete discrimination system for polynomial, that is, we give the classifications of traveling wave solutions to some nonlinear differential equations through solving the corresponding integrals. In finally, as a result, we give a partial answer to a problem on Fan's expansion method.