SqFreeEVAL: An (almost) optimal real-root isolation algorithm

Let f be a univariate polynomial with real coefficients, f∈R[X]. Subdivision algorithms based on algebraic techniques (e.g., Sturm or Descartes methods) are widely used for isolating the real roots of f in a given interval. In this paper, we consider a simple subdivision algorithm whose primitives are purely numerical (e.g., function evaluation). The complexity of this algorithm is adaptive because the algorithm makes decisions based on local data. The complexity analysis of adaptive algorithms (and this algorithm in particular) is a new challenge for computer science. In this paper, we compute the size of the subdivision tree for the SqFreeEVAL algorithm.The SqFreeEVAL algorithm is an evaluation-based numerical algorithm which is well-known in several communities. The algorithm itself is simple, but prior attempts to compute its complexity have proven to be quite technical and have yielded sub-optimal results. Our main result is a simple O(d(L+lnd)) bound on the size of the subdivision tree for the SqFreeEVAL algorithm on the benchmark problem of isolating all real roots of an integer polynomial f of degree d and whose coefficients can be written with at most L bits.Our proof uses two amortization-based techniques: first, we use the algebraic amortization technique of the standard Mahler-Davenport root bounds to interpret the integral in terms of d and L. Second, we use a continuous amortization technique based on an integral to bound the size of the subdivision tree. This paper is the first to use the novel analysis technique of continuous amortization to derive state of the art complexity bounds.     

Convex hulls of objects bounded by algebraic curves

We present an0(n ·d ^o(1)) algorithm to compute the convex hull of a curved object bounded by0(n) algebraic curve segments of maximum degreed.     

ε-Optimality for bicriteria programs and its application to minimum cost flows

A subsetS?X of feasible solutions of a multicriteria optimization problem is called ε-optimal w.r.t. a vector-valued functionf:X→Y \( \subseteq \) ? ^K if for allx∈X there is a solutionz _x∈S so thatf _k(z _x)≤(1+ε)f _k (x) for allk=1,...,K. For a given accuracy ε>0, a pseudopolynomial approximation algorithm for bicriteria linear programming using the lower and upper approximation of the optimal value function is given. Numerical results for the bicriteria minimum cost flow problem on NETGEN-generated examples are presented.     

Realizing Boolean functions on disjoint sets of variables

For switching functions f let C(f) be the combinational complexity of f. We prove that for every ε>0 there are arbitrarily complex functions f:{0,1}ⁿ→{0,1}ⁿ such that C(f×f)? (1+ε)C(f) and arbitrarily complex functions f:{0,1}ⁿ→{0,1} such that C(v°(fxf)? (1+ε)C(f). These results and the techniques developed to obtain them are used to show that Ashenhurst decomposition of switching functions does not always yield optimal circuits, and to prove a new result concerning the gap between circuit size and monotone circuit size.     

Bernstein-type operators which preserve polynomials

In this paper we present the sequence of linear Bernstein-type operators defined for f∈C[0,1] by B_n(f°τ⁻¹)°τ, B_n being the classical Bernstein operators and τ being any function that is continuously differentiable ∞ times on [0,1], such that τ(0)=0, τ(1)=1 and τ^′(x)>0 for x∈[0,1]. We investigate its shape preserving and convergence properties, as well as its asymptotic behavior and saturation. Moreover, these operators and others of King type are compared with each other and with B_n. We present as an interesting byproduct sequences of positive linear operators of polynomial type with nice geometric shape preserving properties, which converge to the identity, which in a certain sense improve B_n in approximating a number of increasing functions, and which, apart from the constant functions, fix suitable polynomials of a prescribed degree. The notion of convexity with respect to τ plays an important role.     

Predicting the future of functions on flows

Let Ω be a topological space,S _t ∈ R (R the reals) a homeomorphism group on Ω andμ a Borel measure invariant with respect toS _t , (μ(Ω)=1); forP ∈Ω putS _t (P)=P _t . Assumef ∈L ₂(Ω,μ); according to E. Hopf there is for almost everyP ∈ Ω a well-determined spectral function σ(P,λ),λ ∈ R with lim \(T^{ - 1} \int_0^T {f(P_{t + s} )\overline {f(P_t )} dt = \int_{ - \infty }^{ + \infty } {e^{i\lambda s} d\sigma (P\lambda )} }\) . The question to be considered is:^*) if for a fixedP ∈ Ω we know the “past”f(P _t ), t ≦ 0, is it then possible to compute (or “predict”) the future valuesf(P _t ), t > 0? By using ideas from linear prediction theory we show that if \(\int_{ - \infty }^{ + \infty } {(1 + \lambda ^2 )\log \frac{d}{{d\lambda }}\sigma (P,\lambda )} d\lambda = - \infty\) then the prediction required by^*) is possible. An algorithm is described which accomplishes the prediction.     

On Clark and Suen bound-type results for k-domination and Roman domination of Cartesian product graphs

A set S of vertices of a graph G is a dominating set for G if every vertex of G is adjacent to at least one vertex of S. The domination number γ(G), of G, is the minimum cardinality of a dominating set in G. Moreover, if the maximum degree of G is Δ, then for every positive integer k≤Δ, the set S is a k-dominating set in G if every vertex outside of S is adjacent to at least k vertices of S. The k-domination number of G, denoted by γ _k (G), is the minimum cardinality of a k-dominating set in G. A map f: V→<texlscub>0, 1, 2</texlscub>is a Roman dominating function for G if for every vertex v with f(v)=0, there exists a vertex u∈N(v) such that f(u)=2. The weight of a Roman dominating function is f(V)=∑ _u∈V f(u). The Roman domination number γ_R(G), of G, is the minimum weight of a Roman dominating function on G. In this paper, we obtain that for any two graphs G and H, the k-domination number of the Cartesian product of G and H is bounded below by γ(G)γ _k (H)/2. Also, we obtain that the domination number of Cartesian product of G and H is bounded below by γ(G)γ_R(H)/3.     

Some new sequence spaces derived by the domain of the triple band matrix

Let λ denote any of the classical spaces ?_∞,c,c₀, and ?_p of bounded, convergent, null, and absolutely p-summable sequences, respectively, and let λ(B) also be the domain of the triple band matrix B(r,s,t) in the sequence space λ, where 1<p<∞. The present paper is devoted to studying the sequence space λ(B). Furthermore, the β- and γ-duals of the space λ(B) are determined, the Schauder bases for the spaces c(B), c₀(B), and ?_p(B) are given, and some topological properties of the spaces c₀(B), ?₁(B), and ?_p(B) are examined. Finally, the classes (λ₁(B):λ₂) and (λ₁(B):λ₂(B)) of infinite matrices are characterized, where λ₁∈{?_∞,c,c₀,?_p,?₁} and λ₂∈{?_∞,c,c₀,?₁}.     

Convex hulls of objects bounded by algebraic curves

We present an0(n ·d ^o(1)) algorithm to compute the convex hull of a curved object bounded by0(n) algebraic curve segments of maximum degreed.Research supported in part by NSF Grant MIP-85 21356, ARO Contract DAA G29-85-C0018 under Cornell MSI, and ONR Contract N00014-88-K-0402. This paper is an updated version of a part of [6].     

Riccati equations and normalized coprime factorizations for strongly stabilizable infinite-dimensional systems

The first part of the paper concerns the existence of strongly stabilizing solutions to the standard algebraic Riccati equation for a class of infinite-dimensional systems of the form Σ(A,B,S^−1/2B^*,D), where A is dissipative and all the other operators are bounded. These systems are not exponentially stabilizable and so the standard theory is not applicable. The second part uses the Riccati equation results to give formulas for normalized coprime factorizations over H_∞ for positive real transfer functions of the form D+S^−1/2B^*(author−A)⁻¹,B.     

Robustness of star graph network under link failure

The star graph is an attractive underlying topology for distributed systems. Robustness of the star graph under link failure model is addressed. Specifically, the minimum number of faulty links, f(n, k), that make every (n − k)-dimensional substar S_n−k faulty in an n-dimensional star network S_n, is studied. It is shown that f(n,1)=n+2. Furthermore, an upper bound is given for f(n, 2) with complexity of O(n³) which is an improvement over the straightforward upper bound of O(n⁴) derived in this paper.     

Cyclic codes over R = Fp + uFp +?+ uFp with length pn

In this paper, all cyclic codes with length p^sn, (n prime to p) over the ring R = F_p + uF_p +?+ u^k−1F_p are classified. It is first proved that Tor_j(C) is an ideal of , so that the structure of ideals over extension ring S_u^k(m,ω)=GR(u^k,m)[ω]/〈ω^ps-1〉 is determined. Then, an isomorphism between R[X]/〈X^N − 1〉 and a direct sum ⊕_h∈IS_u^k(m_h,ω) can be obtained using discrete Fourier transform. The generator polynomial representation of the corresponding ideals over F_p + uF_p +?+ u^k−1F_p is calculated via the inverse isomorphism. Moreover, torsion codes, MS polynomial and inversion formula are described.     

On time-space classes and their relation to the theory of real addition

A new lower bound on the computational complexity of the theory of real addition and several related theories is established: any decision procedure for these theories requires either space 2^εn or nondeterministic time 2^εn2 for some constant ε0 and infinitely many n.The proof is based on the families of languages TISP(T(n), S(n)) which can be recognized simultaneously in time T(n) and S(n) and the conditions under which they form a hierarchy.     

Improving bounds on link failure tolerance of the star graph

Determination of the minimum number of faulty links, f(n,k), that make every n-k-dimensional sub-star graph S_n-k faulty in an n-dimensional star network S_n, has been the subject of several studies. Bounds on f(n,k) have already been derived, and it is known that f(n,1)=n+2. Here, we improve the bounds on f(n,k). Specifically, it is shown that f(n,k)?(k+1)F(n,k), where F(n,k) is the minimum number of faulty nodes that make every S_n-k faulty in S_n. The complexity of f(n,k) is shown to be O(n²k) which is an improvement over the previously known upper bound of O(n³); this result in a special case leads to f(n,2)=O(n^↑2), settling a conjecture introduced in an earlier paper. A systematic method to derive the labels of the faulty links in case of f(n,1) is also introduced.     

An optimal algorithm for constructing the weighted voronoi diagram in the plane

Let S denote a set of n points in the plane such that each point p has assigned a positive weight w(p) which expresses its capability to influence its neighbourhood. In this sense, the weighted distance of an arbitrary point x from p is given by d_e(x,p)/w(p) where d_e denotes the Euclidean distance function. The weighted Voronoi diagram for S is a subdivision of the plane such that each point p in S is associated with a region consisting of all points x in the plane for which p is a weighted nearest point of S.An algorithm which constructs the weighted Voronoi diagram for S in O(n²) time is outlined in this paper. The method is optimal as the diagram can consist of Θ(n²) faces, edges and vertices.     

Geometric pattern matching for point sets in the plane under similarity transformations

We consider the following geometric pattern matching problem: Given two sets of points in the plane, P and Q, and some (arbitrary) δ>0, find a similarity transformation T (translation, rotation and scale) such that h(T(P),Q)<δ, where h(⋅,⋅) is the directional Hausdorff distance with L_∞ as the underlying metric; or report that none exists. We are only interested in the decision problem, not in minimizing the Hausdorff distance, since in the real world, where our applications come from, δ is determined by the practical uncertainty in the position of the points (pixels). Similarity transformations have not been dealt with in the context of the Hausdorff distance and we fill the gap here. We present efficient algorithms for this problem imposing a reasonable separation restriction on the points in the set Q. If the L_∞ distance between every pair of points in Q is at least 8δ, then the problem can be solved in O(mn²logn) time, where m and n are the numbers of points in P and Q respectively. If the L_∞ distance between every pair of points in Q is at least cδ, for some c, 0<c<1, we present a randomized approximate solution with expected runtime O(n²c−4ε−8log⁴mn), where ε>0 controls the approximation. Our approximation is on the size of the subset, B⊆P, such that h(T(B),Q)<δ and |B|>(1−ε)|P| with high probability.     

Spatial coherence between remotely sensed ocean color data and vertical distribution of lidar backscattering in coastal stratified waters

Detection of sub-surface optical layers in marine waters has important applications in fisheries management, climate modeling, and decision-based systems related to military operations. Concurrent changes in the magnitude and spatial variability of remote sensing reflectance (R_rs) ratios and submerged scattering layers were investigated in coastal waters of the northern Gulf of Alaska during summer of 2002 based on high resolution and simultaneous passive (MicroSAS) and active (Fish Lidar Oceanic Experimental, FLOE) optical measurements. Principal Component Analysis revealed that the spatial variability of total lidar backscattering signal (S) between 2.1 and 20 m depth was weakly associated with changes in the inherent optical properties (IOPs) of surface waters. Also based on a 250-m footprint, the vertical attenuation of S was inversely related to the IOPs (Spearman Rank Correlation up to −0.43). Low (arithmetic average and standard deviation) and high (skewness and kurtosis) moments of R_rs(443)/R_rs(490) and R_rs(508)/R_rs(555) ratios were correlated with vertical changes in total lidar backscattering signal (S) at different locations. This suggests the use of sub-pixel ocean color statistics to infer the spatial distribution of sub-surface scattering layers in coastal waters characterized by stratified conditions, well defined S layers (i.e., magnitude of S maximum comparable to near surface values), and relatively high vertically integrated phytoplankton pigments in the euphotic zone (chlorophyll a concentration > 150 mg m^− 2).