Some results on simultaneous stabilization with multiple domains of stability

In this paper, the problem of simultaneous stabilization in the case where each plant has a different domain of stability associated with it is studied. Specifically, it is supposed that one is given plants P₀, P₁,…, P_r together with domains of stability D₀,…, D_r, and the objective is to find a common controller C such that the poles of the closed-loop transfer matrix H(P_i, C) are all inside the corresponding domain of stability D_i, for i = 0,…, r. This formulation of the simultaneous stabilization problem generalizes earlier problem formulations wherein it was assumed that all the domains of stability were the same, and is believed to be a more realistic formulation of the problem of preserving system stability in the event of sensor or actuator failure. In the paper, necessary and sufficient conditions for the existence of a common controller are derived, in the case where one of the domains (say D₀) is a subset of the rest. The case of two plants P₀, P₁ with D₀ a subset of D₁ is studied in great detail, and the following result is established: the two plants can be simultaneously stabilized in the above generalized sense if and only if they can be simultaneously stabilized with respect to the larger of the two regions. More precisely there exists a controller C such that the poles of H(P_i, C) lie inside D_i for i = 0, 1 if and only if there exists a controller such that the poles of bothH(P₀, C) and of H(P₁, C) lie inside the larger region D₁.     

Dynamic Matrix Rank with Partial Lookahead

We consider the problem of maintaining information about the rank of a matrix M under changes to its entries. For an n×n matrix M, we show an amortized upper bound of O(n ^ω?1) arithmetic operations per change for this problem, where ω<2.373 is the exponent for matrix multiplication, under the assumption that there is a lookahead of up to Θ(n) locations. That is, we know up to the next Θ(n) locations (i ₁,j ₁),(i ₂,j ₂),…?, whose entries are going to change, in advance; however we do not know the new entries in these locations in advance. We get the new entries in these locations in a dynamic manner. The dynamic matrix rank problem was first studied by Frandsen and Frandsen who showed an upper bound of O(n ^1.575) and a lower bound of Ω(n) for this problem and later Sankowski showed an upper bound of O(n ^1.495) for this problem when allowing randomization and a small probability of error. These algorithms do not assume any lookahead. For the dynamic matrix rank problem with lookahead, Sankowski and Mucha showed a randomized algorithm (with a small probability of error) that is more efficient than these algorithms.     

On Approximating Polygonal Curves in Two and Three Dimensions

Given a polygonal curve P =[p₁, p₂, . . . , p_n], the polygonal approximation problem considered calls for determining a new curve P′ = [p′₁, p′₂, . . . , p′_m] such that (i) m is significantly smaller than n, (ii) the vertices of P′ are an ordered subset of the vertices of P, and (iii) any line segment [p′_A, p′_{A + 1} of P′ that substitutes a chain [p_B, . . . , p_C] in P is such that for all i where B ≤ i ≤ C, the approximation error of p_i with respect to [p′_A, p′_{A + 1}], according to some specified criterion and metric, is less than a predetermined error tolerance. Using the parallel-strip error criterion, we study the following problems for a curve P in R^d, where d = 2, 3: (i) minimize m for a given error tolerance and (ii) given m, find the curve P′ that has the minimum approximation error over all curves that have at most m vertices. These problems are called the min-# and min-ϵ problems, respectively. For R² and with any one of the L₁, L₂, or L_∞ distance metrics, we give algorithms to solve the min-# problem in O(n²) time and the min-ϵ problem in O(n² log n) time, improving the best known algorithms to date by a factor of log n. When P is a polygonal curve in R³ that is strictly monotone with respect to one of the three axes, we show that if the L₁ and L_∞ metrics are used then the min-# problem can be solved in O(n²) time and the min-ϵ problem can be solved in O(n³) time. If distances are computed using the L₂ metric then the min-# and min-ϵ problems can be solved in O(n³) and O(n³ log n) time, respectively. All of our algorithms exhibit O(n²) space complexity. Finally, we show that if it is not essential to minimize m, simple modifications of our algorithms afford a reduction by a factor of n for both time and space.     

Stable polyhedra in parameter space

A typical uncertainty structure of a characteristic polynomial is P(s)=A(s)Q(s)+B(s) with A(s) and B(s) fixed and Q(s) uncertain. In robust controller design Q(s) may be a controller numerator or denominator polynomial; an example is the PID controller with Q(s)=K_I+K_Ps+K_Ds². In robustness analysis Q(s) may describe a plant uncertainty. For fixed imaginary part of Q(jω), it is shown that Hurwitz stability boundaries in the parameter space of the even part of Q(jω) are hyperplanes and the stability regions are convex polyhedra. A dual result holds for fixed real part of Q(jω). Also σ-stability with the real parts of all roots of P(s) smaller than σ is treated.Under the above conditions, the roots of P(s) can cross the imaginary axis only at a finite number of discrete “singular” frequencies. Each singular frequency generates a hyperplane as stability boundary. An application is robust controller design by simultaneous stabilization of several representatives of A(s) and B(s) by a PID controller. Geometrically, the intersection of convex polygons must be calculated and represented tomographically for a grid on K_P.     

Fractal analysis of temporal variation of air pollutant concentration by box counting

The scale-invariant behavior of air pollutant concentration (APC) time structure was investigated by applying the box counting method to APC time series. One-year series of hourly average APC observations, including O₃, CO, SO₂, NO, NO₂, and PM10 which were obtained from urban, traffic, and national park air monitoring station at Taipei (Taiwan), were transferred into a useful compact form through this method, namely, the box-dimension (D_B)-threshold (T_h) and critical scale (C_S)-threshold (T_h) plots. The validity of this approach was supported with the result that the practical implications of D_B-T_h (or C_S-T_h) plots could be interpreted in terms of traditional statistical parameters. Since the dependences of both D_B and C_S on the T_h values were closely related to the variation of APC in time, they were used to characterize the temporal distribution of APC. The analysis confirmed the existence of scale invariance in those investigated APC time series. Moreover, the D_B (C_S) was shown to be a decreasing (increasing) function of the threshold level, implying multifractal characteristics, i.e. the weak and intense regions scale differently. Some practical applications based on the box counting method were also discussed.     

Shorthand Universal Cycles for Permutations

The set of permutations of ??n??={1,??,n} in one-line notation is ??(n). The shorthand encoding of a ₁?a _n ????(n) is a ₁?a _n?1. A shorthand universal cycle for permutations (SP-cycle) is a circular string of length n! whose substrings of length n?1 are the shorthand encodings of ??(n). When an SP-cycle is decoded, the order of ??(n) is a Gray code in which successive permutations differ by the prefix-rotation ?? _i =(1 2 ? i) for i??{n?1,n}. Thus, SP-cycles can be represented by n! bits. We investigate SP-cycles with maximum and minimum ??weight?? (number of ?? _n?1s in the Gray code). An SP-cycle n a n b?n z is ??periodic?? if its ??sub-permutations?? a,b,??,z equal ??(n?1). We prove that periodic min-weight SP-cycles correspond to spanning trees of the (n?1)-permutohedron. We provide two constructions: B(n) and C(n). In B(n) the spanning trees use ??half-hunts?? from bell-ringing, and in C(n) the sub-permutations use cool-lex order by Williams (SODA, 987?C996, 2009). Algorithmic results are: (1)?memoryless decoding of B(n) and C(n), (2)?O((n?1)!)-time generation of B(n) and C(n) using sub-permutations, (3)?loopless generation of B(n)??s binary representation n bits at a time, and (4)?O(n+??(n))-time ranking of B(n)??s permutations where ??(n) is the cost of computing a permutation??s inversion vector. Results (1)?C(4) improve on those for the previous SP-cycle construction D(n) by Ruskey and Williams (ACM Trans. Algorithms 6(3):Art.?45, 2010), which we characterize here using ??recycling??.     

Low-level dichotomy for quantified constraint satisfaction problems

Building on a result of Larose and Tesson for constraint satisfaction problems (CSPs), we uncover a dichotomy for the quantified constraint satisfaction problem QCSP(B), where B is a finite structure that is a core. Specifically, such problems are either in ALogtime or are L-hard. This involves demonstrating that if CSP(B) is first-order expressible, and B is a core, then QCSP(B) is in ALogtime.We show that the class of B such that CSP(B) is first-order expressible (indeed trivial) is a microcosm for all QCSPs. Specifically, for any B there exists a C — generally not a core — such that CSP(C) is trivial, yet QCSP(B) and QCSP(C) are equivalent under logspace reductions.     

Microfluidic architectures for efficient generation of chemistry gradations in droplets

We demonstrate a strategy for construction of high-throughput microfluidic systems generating gradations of chemistry in micro-droplets. The productivity of the systems that we propose is limited only by the maximum rate of the droplet formation, and does not need to be limited by the rate of mixing. Multilayer polycarbonate chips transform two miscible input streams A and B into N streams of droplets, containing mixtures [A] _i , [B] _i . Exemplary devices generate linear ([B] _i  ∝ i) and logarithmic gradations (ln[B] _i  ∝ i). We also analyze the use of the same strategy for the generation of concentration gradation in the streams of droplets comprising mixtures of liquids of different viscosities. The devices preserve the required distribution of compositions, while allowing the volume of the droplets to be tuned over almost two orders of magnitude (i.e. between 3 and 80 nL).     

On the problem of general structural assignments of linear systems through sensor/actuator selection

A systematic method is developed for determining an output matrix C for a given matrix pair (A,B) such that the resulting linear system characterized by the matrix triple (A,B,C) has the pre-specified system structural properties, such as the finite and infinite zero structure and the invertibility structures. Since the matrix C describes the locations of the sensors, the procedure of choosing C is often referred to as sensor selection. The method developed in this paper for sensor selection can be applied to the dual problem of actuator selection, where, for a given matrix pair (A,C), a matrix B is to be determined such that the resulting matrix triple (A,B,C) has the pre-specified structural properties.     

Broadcasting schemes for hypercubes with background traffic

Optimal broadcasting schemes for interconnection networks (INs) are most essential for the efficient interprocess communication amongst parallel computers. In this paper two novel broadcasting schemes are proposed for hypercube computers with bursty background traffic and a single-port mode of message passing communication. The schemes utilize a maximum entropy (ME) based queue-by-queue decomposition algorithm for arbitrary queueing network models (QNMs) [D.D. Kouvatsos, I. Awan, Perform. Eval. 51 (2003) 191] and are based on binomial trees and graph theoretic concepts. It is shown that the overall cost of the one-to-all broadcasting scheme is given by max{ω₁,ω₂,…,ω_2ⁿ/2}, where ω_i, i=1,2,…,2ⁿ/2 is the total weight at each leaf node of the binomial tree and n is the degree of the hypercube. Moreover, the upper bound of the total cost of the neighbourhood broadcasting scheme is determined by ∑_i=1^Fmax{ω_i}, where F is an upper bound of the number of steps and is equal to 1.33⌈log₂(n−1)⌉+1. Evidence based on empirical studies indicates the suitability of the schemes for achieving optimal broadcasting costs.     

Synthesis of cascaded multiple-loop feedback systems with large plant parameter ignorance

In a cascaded plant with n sensing points, n independent feedback loops are available to achieve quantitative sensitivity specifications. The optimum design is defined as that which achieves this with minimum net effect, of the n sensor noise sources, at the plant input. A design procedure is presented wherein one works backwards step by step from the system output, designing each loop function L_i almost as if the remaining loops (L_i+j, j>0) are perfect. Even in large plant ignorance problems, only the outer loop L_i may be large over some frequency range. In general |L_i|_max < 1, i ≠ 1 and |L_i+1|_max < |L_i|_max. Each L_i has only one distinct frequency range say at ω_{c, i} requiring trade-off between L_i and L_i+1. Only in this range is significant design effort required. However, ω_{c, i+1} >ω_{c, i} so the primary price paid is in the steadily increasing “bandwidth” of each loop. The design procedure is highly transparent with strong universalistic features, permitting the use of universal design curves.     

On the RAS-algorithm

Given a nonnegative real (m, n) matrixA and positive vectorsu, v, then the biproportional constrained matrix problem is to find a nonnegative (m, n) matrixB such thatB=diag (x) A diag (y) holds for some vectorsx ∈ ? ^m andy ∈ ? ⁿ and the row (column) sums ofB equalu _i (v _j )i=1,...,m(j=1,..., n). A solution procedure (called the RAS-method) was proposed by Bacharach [1] to solve this problem. The main disadvantage of this algorithm is, that round-off errors slow down the convergence. Here we present a modified RAS-method which together with several other improvements overcomes this disadvantage.     

Revisiting the Ziegler–Nichols process dynamics characterization

The Ziegler–Nichols process dynamics characterization is based on the estimation of the ultimate gain k_u and ultimate frequency ω_u. The angle φ of the tangent to the Nyquist curve at the frequency ω_u is introduced, as an additional parameter in the frequency domain. The essential dynamic characteristics of the process can be captured by using the tangent rule, proposed here as an extension of the Ziegler–Nichols approach. The validity of the tangent rule is confirmed by using the PID controller optimization on a test batch consisting of stable, integrating and unstable processes, including dead-time. Parameters k_u, ω_u and φ can be determined from the sustained oscillations, using the phase-locked loop identifier module.     

Block-graph width

Let G be a class of graphs. A graph G has G-width k if there are k independent sets N₁,…,N_k in G such that G can be embedded into a graph H∈G such that for every edge e in H which is not an edge in G, there exists an i such that both endvertices of e are in N_i. For the class B of block graphs we show that graphs with B-width at most 4 are perfect. We also show that B-width is NP-complete and show that it is fixed-parameter tractable. For the class C of complete graphs, similar results are also obtained.     

Relationship between the eccentric connectivity index and Zagreb indices

For a (molecular) graph, the first Zagreb index M₁ is equal to the sum of the squares of the degrees of the vertices, and the second Zagreb index M₂ is equal to the sum of the products of the degrees of pairs of adjacent vertices. If G is a connected graph with vertex set V(G), then the eccentric connectivity index of G, ξ^C(G), is defined as, ∑_vi∈V(G)d_ie_i, where d_i is the degree of a vertex v_i and e_i is its eccentricity. In this report we compare the eccentric connectivity index (ξ^C) and the Zagreb indices (M₁ and M₂) for chemical trees. Moreover, we compare the eccentric connectivity index (ξ^C) and the first Zagreb index (M₁) for molecular graphs.     

Scheduling Partially Ordered Jobs Faster than 2 n

In a scheduling problem, denoted by 1|prec|∑C _i in the Graham notation, we are given a set of n jobs, together with their processing times and precedence constraints. The task is to order the jobs so that their total completion time is minimized. 1|prec|∑C _i is a special case of the Traveling Repairman Problem with precedences. A natural dynamic programming algorithm solves both these problems in 2 ⁿ n ^O(1) time, and whether there exists an algorithms solving 1|prec|∑C _i in O(c ⁿ ) time for some constant c<2 was an open problem posted in 2004 by Woeginger. In this paper we answer this question positively.     

Approximation algorithms for covering/packing integer programs

Given matrices A and B and vectors a, b, c and d, all with non-negative entries, we consider the problem of computing . We give a bicriteria-approximation algorithm that, given ε∈(0,1], finds a solution of cost O(ln(m)/ε²) times optimal, meeting the covering constraints (Ax?a) and multiplicity constraints (x?d), and satisfying Bx?(1+ε)b+β, where β is the vector of row sums β_i=∑_jB_ij. Here m denotes the number of rows of A.This gives an O(lnm)-approximation algorithm for CIP—minimum-cost covering integer programs with multiplicity constraints, i.e., the special case when there are no packing constraints Bx?b. The previous best approximation ratio has been O(ln(max_j∑_iA_ij)) since 1982. CIP contains the set cover problem as a special case, so O(lnm)-approximation is the best possible unless P=NP.     

A fully parallel method for the singular eigenvalue problem

In this paper, a fully parallel method for finding some or all finite eigenvalues of a real symmetric matrix pencil (A, B) is presented, where A is a symmetric tridiagonal matrix and B is a diagonal matrix with b₁ > 0 and b_i ≥ 0, i = 2,3,…,n. The method is based on the homotopy continuation with rank 2 perturbation. It is shown that there are exactly m disjoint, smooth homotopy paths connecting the trivial eigenvalues to the desired eigenvalues, where m is the number of finite eigenvalues of (A, B). It is also shown that the homotopy curves are monotonic and easy to follow.