Factorization of m-D polynomials in linear m-D factors

This paper presents a solution to the factorization problem of high-order m-D polynomials into special m-D factors that are linear in all variables. By special it is meant that the factors have the form of a sum of one independent variable, say z ₁, and a general first-order polynomial not involving z ₁, i.e. z ₁ + a _j2 z ₂ + [tdot] + a _jm z _m (j = 1, 2,[tdot],N ₁). Two theorems providing the necessary and sufficient conditions for this factorization are given, which have an algorithmic form and are thus appropriate for direct computer use. The results are illustrated by means of three examples.     

On the general problem of pole assignment

Given a linear, time-invariant, minimal and strictly proper system  set of monic polynomials φ _i (s), i = l, 2, [tdot],q, such that φ _i (s) divides φ _i?1 (s), i = 2, 3, [tdot],q a method for finding a proper feedback system  which makes the invariant polynomials of the closed-loop system equal to the φ _i (s) is established and a sufficient condition which ensures the existence of  is determined. This method can also be used to assign the poles of the compensated system provided that certain poles are multiple. The order of the required compensator is generally loss than that of the Luenberger or the Wolovich compensation schemes.     

Lumped model of a non-linear distributed system by finite element method

The finite element method has been used to find an approximate lumped parameter model of a non-linear distributed parameter system. A one dimensional non-linear dispersion system is considered. The space domain is divided into a finite set of k elements. Each element, has n nodes. Within each element the concentration is represented by C(x,t)^(e) = [N][C] ^T where [N] = [n₁(x),n₂(x), [tdot] n_n(x)] and [C] = [C₁(t),C₂(t), [tdot] C_n(t)]. By using Galerkin's criterion a set of (k × n ? n+ 1) first order differential equations are obtained for C_i(t). These equations are solved by an iterative method. The concepts are illustrated by an example taking five three-node elements in the space domain. The results are compared with those obtained by a finite difference method. It is shown that the finite element method can be used effectively in modelling of a distributed system by a lumped system.     

STRUCTURE OF POSSIBILISTIC INFORMATION METRICS AND DISTANCES: PROPERTIES

Systematic analysis of identities and inequalities satisfied by possibilistic information distances is conducted. The analysis is based on their representations as discrete sums and on certain inequalities for rearrangements of sequences. These identities and inequalities express several properties that are usually deemed characteristic of information distances and measures. In the companion paper those properties are used to obtain several axiomatic characterizations of possibility distances. The basic distance is g(p,q) defined for the distributions p = (Pi,[tdot],pn) and q = (qi,[tdot],qn) such that Pi≤qi. =i=1,[tdot],n They serve to define a metric G(p,q)=g<p,p ∨ q)+g(q,p [tdot] q) and a distanceH(p,q) = g(p∧q,p)+g(p ∧ q,q). All these distances are, in turn based on the U-uncertainty information function.     

Nonlinear eigenvalue problems for quasilinear systems

The paper deals with the existence of positive solutions for the quasilinear system (Φ(u'))' + λh(t)f(u) = 0,0 < t < 1 with the boundary condition u(0) = u(1) = 0. The vector-valued function Φ is defined by Φ(u) = (q(t)(p(t)u₁), …, q(t)(p(t)u_n)), where u = (u₁, …, u_n), andcovers the two important cases (u) = u and (u) = up > 1, h(t) = diag[h₁(t), …, h_n(t)] and f(u) = (f¹(u), …, fⁿ (u)). Assume that fⁱ and h_i are nonnegative continuous. For u = (u₁, …, u_n), let

, f₀ = maxf¹₀, …, fⁿ₀ and f_∞ = maxf¹_∞, …, fⁿ_∞. We prove that the boundary value problem has a positive solution, for certain finite intervals of λ, if one of f₀ and f_∞ is large enough and the other one is small enough. Our methods employ fixed-point theorem in a cone.     

General eigenvalue placement in linear control systems by output feedback

Consider the time-invariant system E[xdot] = Ax + Bu, y = Cx where E is a square matrix that may be singular. The problem is to find constant matrices K and L, such that the feedback law u = Ky+L[ydot] yields x = exp (λt)v_i (where v_i is some constant vector) for some preassigned λ_i (i=l, 2, [tdot], r). This problem is equivalent to that of finding K and L which makes a preassigned λ _i an eigenvalue corresponding to the general eigenvalue problem {λ(E ? BLC) ? (A + BKC)}v=0. Using matrix generalized inverses, a method is developed for the construction of a linear system of equations from which the elements of K and L may be computed.     

Synthesis of a control system for a single-input multiple-output plant

Given a constrained plant P with input x and outputs y ₁ y ₂,[tdot],y _n , the assigned specifications require that, at each instant, y i follows the corresponding reference value r j for one index i, while for the other indices, j≠i, y j should be smaller or equal to r j. A quantitative synthesis technique is presented to solve this problem, that reduces it, in quite a transparent way, to the solution of several single-input single-output problems.     

Markov games with unknown random state‐actions‐dependent discount factors: Empirical estimation

The work deals with a class of discrete‐time zero‐sum Markov games under a discounted optimality criterion with random state‐action‐dependent discount factors of the form , where x_n,a_n,b_n, and ξ_n+1 are the state, the actions of players, and a random disturbance at time n, respectively, taking values in Borel spaces. The one‐stage payoff is assumed to be possibly unbounded. In addition, the process {ξ_n} is formed by observable, independent, and identically distributed random variables with common distribution θ, which is unknown to players. By using the empirical distribution to estimate θ, we introduce a procedure to approximate the value V^? of the game; such a procedure yields construction schemes of stationary optimal strategies and asymptotically optimal Markov strategies.     

On counting pairs of intersecting segments and off-line triangle range searching

We describe a method for decomposing planar sets of segments and points. Using this method we obtain new efficientdeterministic algorithms for counting pairs of intersecting segments, and for answering off-line triangle range queries. In particular we obtain the following results:

1. Givenn segments in the plane, the number of pairs of intersecting segments is counted in timeO(n ^1+?+K ^1/3 n ^2/3+?), whereK is the number of intersection points among the segments, and ?>0 is an arbitrarily small constant.
2. Givenn segments in the plane which are colored with two colors, the number of pairs ofbichromatic intersecting segments is counted in timeO(n ^1+?+K _m ^1/3 n ^2/3+?), whereK _m is the number ofmonochromatic intersection points, and ?>0 is an arbitrarily small constant.
3. Givenn weighted points andn triangles on a plane, the sum of weights of points in each triangle is computed in timeO(n ^1+ε+?^1/3 n ^2/3+ε), where ? is the number of vertices in the arrangement of the triangles, and ?>0 is an arbitrarily small constant.

The above bounds depend sublinearly on the number of intersections among input segmentsK (resp.K _m , ?), which is desirable sinceK (resp.K _m , ?) can range from zero toO(n ²). All of the above algorithms use optimal Θ(n) storage. The constants of proportionality in the big-Oh notation increase as ? decreases. These results are based on properties of the sparse nets introduced by Chazelle [Cha3].     

An interpolation problem associated with H-optimal design in systems with distributed input lags

A variety of H^∞ optimal design problems reduce to interpolation of compressed multiplication operators, f(s) → π_k(w(s)f(s)), where w(s) is a given rational function and the subspace K is of the form K=H² φ(s)H². Here we consider φ(s) = (1-e^α-5)/(s - α), which stands for a distributed delay in a system's input. The interpolation scheme we develop, adapts to a broader class of distributed lags, namely, those determined by transfer functions of the form B(e^−s)/b(s), where B(z) and b(s) are polynomials and b(s) = 0 implies B(e^−s) = 0.     

An Efficient Parallel Strategy for ComputingK-Terminal Reliability and Finding Most Vital Edges in 2-Trees and Partial 2-Trees

In this paper, we first develop a parallel algorithm for computingK-terminal reliability, denoted byR(G_K), in 2-trees. Based on this result, we can also computeR(G_K) in partial 2-trees using a method that transforms, in parallel, a given partial 2-tree into a 2-tree. Finally, we solve the problem of finding most vital edges with respect toK-terminal reliability in partial 2-trees. Our algorithms takeO(log n) time withC(m, n) processors on a CRCW PRAM, whereC(m, n) is the number of processors required to find the connected components of a graph withmedges andnvertices in logarithmic time.     

Diagonal polynomials for small dimensions

HereR andN denote respectively the real numbers and the nonnegative integers. Also 0 <n εN, ands(x) =x ₁+...+x _n when x = (x ₁,...,x _n) εR ⁿ. Adiagonal function of dimensionn is a mapf onN ⁿ (or any larger set) that takesN ⁿ bijectively ontoN and, for all x, y inN ⁿ, hasf(x) <f(y) whenevers(x) <s(y). We show that diagonalpolynomials f of dimensionn all have total degreen and have the same terms of that degree, so that the lower-degree terms characterize any suchf. We call two polynomialsequivalent if relabeling variables makes them identical. Then, up to equivalence, dimension two admits just one diagonal polynomial, and dimension three admits just two.     

An enlarged family of packing polynomials on multidimensional lattices

HereN = {0, 1, 2, ...}, while a functionf onN ^m or a larger domain is apacking function if its restrictionf|N ^m is a bijection ontoN. (Packing functions generalize Cantor's [1]pairing polynomials, and yield multidimensional-array storage schemes.) We call two functionsequivalent if permuting arguments makes them equal. Alsos(x) =x ₁ + ... +x _m when x = (x ₁,...,x _m); and such anf is adiagonal mapping iff(x) <f(y) whenever x, y εN ^m ands(x) <s(y). Lew [7] composed Skolem's [14], [15] diagonal packing polynomials (essentially one for eachm) to constructc(m) inequivalent nondiagonal packing polynomials on eachN ^m. For eachm > 1 we now construct 2^m−2 inequivalent diagonal packing polynomials. Then, extending the tree arguments of the prior work, we obtaind(m) inequivalent nondiagonal packing polynomials, whered(m)/c(m) → ∞ asm → ∞. Among these we count the polynomials of extremal degree.     

L(2, 1)-labellings for direct products of a triangle and a cycle

An L(2, 1)-labelling of a graph G is a vertex labelling such that the difference of the labels of any two adjacent vertices is at least 2 and that of any two vertices of distance 2 is at least 1. The minimum span of all L(2, 1)-labellings of G is the λ-number of G and denoted by λ(G). Lin and Lam computed λ(G) for a direct product G=K _m ×P _n of a complete graph K _m and a path P _n . This is a natural lower bound of λ(K _m ×C _n ) for a cycle C _n . They also proved that when n≡ 0±od 5m, this bound is the exact value of λ(K _m ×C _n ) and computed the value when n=3, 5, 6. In this article, we compute the λ-number of G, where G is the direct product K ₃×C _n of the triangle and a cycle C _n for all the other n. In fact, we show that among these n, λ(K ₃×C _n )=7 for all n≠7, 11 and λ(K ₃×C _n )=8 when n=7, 11.     

On Parallel Integer Merging

The problem of merging two sorted arrays A = (a₁, a₂, ..., a_n1) and B = (b₁, b₂, ..., b_n2) is considered. For input elements that are drawn from a domain of integers [1...s] we present an algorithm that runs in O(log log log s) time using n/log log log s CREW PRAM processors (optimal speed-up) and O(ns^ε) space, where n = n₁ + n₂. For input elements that are drawn from a domain of integers [1...n] we present a second algorithm that runs in O(α(n)) time (where α(n) is the inverse of Ackermann′s function) using n/α(n) CREW PRAM processors and linear space. This second algorithm is non-uniform; however, it can be made uniform at a price of a certain loss of speed, or by using a CRCW PRAM.     

Teoremi di confronto per gli zeri di polinomis-ortogonali

Sommaire Dans cette note on donne des théorèmes généraux qui permettent la comparaison entre les zéros des polyn?mess-orthogonaux, relatifs à fonctions poidsp _x (x),p ₀ (x), pour les quelles le rapportp ₁ (x)/p _o(x) est une fonction strictement monotone sur un certain intervalle. Ces thèorèmes, utilisés à propos, permettent d'établir des inégalités entre les zéros des polynomess-orthogonaux relatifs aux fonctions poids de type Jacobi,p(x)=(1-x)^α (1+x)^β), α, β>−1,x∈]−1,1[; inégalités qui sont connues seulement pour des valeurs particuliers de α,β,s, et du degrém du polynome.     

Empirical Bayes estimation of the scale parameter in a Pareto distribution

Let f(xθ) = αθ^αx^−(α+1)I(x>θ) be the pdf of a Pareto distribution with known shape parameter α>0, and unknown scale parameter θ. Let {(X_i, θ_i)} be a sequence of independent random pairs, where X_i's are independent with pdf f(xα_i), and θ_i are iid according to an unknown distribution G in a class of distributions whose supports are included in an interval (0, m), where m is a positive finite number. Under some assumption on the class and squared error loss, at (n + 1)th stage we construct a sequence of empirical Bayes estimators of θ_n+1 based on the past n independent observations X₁,…, X_n and the present observation X_n+1. This empirical Bayes estimator is shown to be asymptotically optimal with rate of convergence O(n^−1/2). It is also exhibited that this convergence rate cannot be improved beyond n^−1/2 for the priors in class .     

A General Stochastic Programming Problem

Stochastic programming problems appear when we make decisions in situations with uncertainty and risk, when any action has an ambiguous outcome and to each solution x = (x₁ …, x_n) it is possible to associate certain indicators fⁱ (x, ω), i = 1, …, m, that depend on x and on the state of nature ω, which is an element of the probabilistic space (Ω, A, P).

Since for any x the value of the objective function f ¹ (x, ω) and of the constraints functions f(x, ω), i = 2,… m, will depend on the realization ω, we have great freedom in determining the feasible and the optimal solutions in stochastic programming problems; for example, deciding whether they should be deterministic or have random solutions.     

Bounded control and discrete-time controllability†

The discrete-time linear system x_k+1 = Ax_k + u_k (k = 0, 1,[tdot]), for which the input u_k belongs to an arbitrary bounded and convex set Ω, is considered. The error in the sufficiency proof of the controllability result when 0 ? ri (Ω) owing to Wing and Desoer is avoided by using convexity arguments, and the result is extended to encompass the case 0 ? ri (Ω)     

Asymmetric quantum Reed-Solomon and generalized Reed-Solomon codes

Two new families of asymmetric quantum codes are constructed in this paper. The first one is derived from the Calderbank-Shor-Steane (CSS) construction applied to classical Reed-Solomon (RS) codes, providing quantum codes with parameters [[N = l(q ^l −1), K = l(q ^l −2d + c + 1), d _z ≥ d/d _x ≥ (d−c)]] _q , where q is a prime power and d > c + 1, c ≥ 1, l ≥ 1 are integers. The second family is derived from the CSS construction applied to classical generalized RS codes, generating quantum codes with parameters [[N = mn, K = m(2k−n + c), d _z ≥ d/d _x ≥ (d−c)]] _q , where q is a prime power, 1 < k < n < 2k + c ≤ q ^m , k = n − d + 1, and n, d > c + 1, c ≥ 1, m ≥ 1 are integers. Although the second proposed construction generalizes the first one, the techniques developed in both constructions are slightly different. These new codes have parameters better than or comparable to the ones available in the literature. Additionally, the proposed codes can be utilized in quantum channels having great asymmetry, that is, quantum channels in which the probability of occurrence of phase-shift errors is large when compared to the probability of occurrence of qudit-flip errors.