The stability of a family of polynomials can be deduced from afinite number 0(k3) of frequency checks

Let φ(s,a)=φ₀(s,a)+ a₁φ₁(s)+a₂ φ₂(s)+ . . .+a_kφ _k(s)=φ₀(s)-q(s, a) be a family of real polynomials in s, with coefficients that depend linearly on parameters a_i which are confined in a k-dimensional hypercube Ω_a . Let φ₀(s) be stable of degree n and the φ_i(s) polynomials (i⩾1) of degree less than n. A Nyquist argument shows that the family φ(s) is stable if and only if the complex number φ₀(jω) lies outside the set of complex points -q(jω,Ω_a) for every real ω. In a previous paper (Automat. Contr. Conf., Atlanta, GA, 1988) the authors have shown that -q(jω,Ω_a ), the so-called `-q locus', is a 2k convex parpolygon. The regularity of this figure simplifies the stability test. In the present paper they again exploit this shape and show that to test for stability only a finite number of frequency checks need to be done; this number is polynomial in k, 0(k³), and these critical frequencies correspond to the real nonnegative roots of some polynomials     

Mapping nested loop algorithms into multidimensional systolicarrays

Consideration is given to transforming depth p-nested for loop algorithms into q-dimensional systolic VLSI arrays where 1⩽q⩽p-1. Previously, there existed complete characterizations of correct transformation only for the cases where q=p-1 or q=1. This gap is filled by giving formal necessary and sufficient conditions for correct transformation of a p-nested loop algorithm into a q-dimensional systolic array for any q, 1⩽q⩽p-1. Practical methods are presented. The techniques developed are applied to the automatic design of special purpose and programmable systolic arrays. The results also contribute toward automatic compilation onto more general purpose programmable arrays. Synthesis of linear and planar systolic array implementations for a three-dimensional cube-graph algorithm and a reindexed Warshall-Floyd path-finding algorithm are used to illustrate the method     

An efficient algorithm for calculating the likelihood andlikelihood gradient of ARMA models

Exact analytical expressions are obtained for the likelihood and likelihood gradient stationary autoregressive moving average (ARMA) models. Denote the sample size by N, the autoregressive order by p, and the moving average order by q. The calculation of the likelihood requires (p+2q+1)N +o(N) multiply-add operations, and the calculation of the likelihood gradient requires (2p+6q+2)N+o(N) multiply-add operations. These expressions may be used to obtain an iterative, Newton-Raphson-type converging algorithm, with superlinear convergence rate, that computes the maximum-likelihood estimator in (2 p+6q+2)N+o(N) multiply-add operations per iteration     

Strict aperiodic property of polynomials with perturbedcoefficients

Let a family of polynomials be P(s)=t ₀sⁿ+t₁s ⁿ±¹ + . . . + t_n where 0<a_j⩽t_j⩽b _j. V.L. Kharitonov (1978) derived a necessary and sufficient condition for the above equation to have only zeros in the open left-half plane. The present authors derive some similar results for the equation to be strictly aperiodic (distinct real roots)     

A study of associative evidential reasoning

Associative evidential reasoning is the mechanism of combining evidence and evaluating hypotheses, which is the core of many computational systems. It is shown that under the generalized symmetry condition, that is, f(a,b)=neg (f(neg(a), neg(b))), where f is the combination operator satisfying common requirements like associativity and monotonicity, and neg maps positive elements to negative ones and vice versa, f is uniquely determined by a one-place mapping from the positive region to the set of positive reals. Furthermore, such combination formulas cannot be made robust, and quantizing the region will cause the loss of associativity or other inconsistencies. The implications on evidential reasoning system are: there exists often only one kind of formula for combining evidence; the quest for robust combination is often infeasible; and the attempt of converting numerical degrees of belief to linguistic quantifiers and vice versa is destined to be fruitless     

A simulation-based estimator for hidden Markov random fields

An estimator for estimating the parameters of a Markov random field X from inaccurate observations is introduced. The author considers first a Markov (Gibbs) random field X={X_i,j} on a lattice L={(i ,j): i=1,2,. . .,n; j=1,2,. . .,m}. The marginal distributions of (X_i,j, X_i+u,j+v) (u,v=-1,0,1) are first estimated from an image. Then, random fields X* are simulated with the probability of X*_i+u,j+v)=b nearly equal to the estimate of P{X_i,j=X _i+u,=b}. A simulation method similar to the Gibbs sampler is used. The parameters of the Markov random field model are estimated from the X*'s with the pseudolikelihood method     

A note on a classical bound for the moduli of all zeros of apolynomial

Considers the monic polynomial f(z):=z ⁿ+a_n-1z^n-1+. . .+a₀ in the complex variable z with complex coefficients. Under the assumption that the nonleading coefficients of f lie in the disk |z|⩽A the authors give an estimate for the smallest disk |z|⩽R containing all zeros of f. The estimate has a guaranteed precision of a few percent. They proceed similarly to obtain a zero-free disk |z |⩽r     

A comparison of two linear methods of estimating the parameters ofARMA models

A finite-order stationary and minimum-phase ARMA (autoregressive moving-average) (p,q) model is equivalent to an infinite-order AR (autoregressive) model. Two methods of estimating the parameters of the ARMA (p,q) model by solving only linear equations are based on or closely related to this equivalence relation. One method was derived directly from the equivalence relation by D. Graupe et al. (ibid., vol.AC-20, p.104-107, Feb. 1975). The other was derived by S. Li and B.W. Dickinson (ibid., vol.AC-31, p.275-278, Mar. 1986 and IEEE Trans. Acoust. Speech Signal Process., vol.ASSP-36, p.502-512, Apr. 1988) based on an iterated least-squares regression approach. The end results bear close resemblance to those of Graupe et al. The two methods are compared, and ways to improve the parameter estimates are suggested     

Identifiability of the AR parameters of an ARMA process usingcumulants

The problem of estimating the autoregressive (AR)-order and the AR parameters of a causal, stable, single input single output (SISO) autoregressive moving average (ARMA) (p,q) model, excited by an unobservable i.i.d. process, is addressed. The observed output is corrupted by additive colored Gaussian noise, whose power spectral density is unknown. The ARMA model may be mixed-phase, and have inherent all-pass factors and repeated poles. It is shown that consistent AR parameter estimates can be obtained via the normal equations based on (p+1) 1-D slices of the mth-order ( m>2) cumulant. It is shown via a counterexample that consistent AR estimates cannot, in general, be obtained from a subset of these p+1 slices. Necessary and sufficient conditions for the existence of a full-rank slice are also derived     

Generalized measures of fault tolerance in n-cube networks

It is shown that for a given p (1<p⩽n ), the n-cube network can tolerate up to p2^(n-p)-1 processor failures and remains connected provided that at most p neighbors of any nonfaulty processor are allowed to fail. This generalizes the result for p=n-1, obtained by A.-M Esfahanian (1989). It is also shown that the n-cube network with n⩾5 remains connected provided that at most two neighbors of any processor are allowed to fail     

Mixed H2/H∞ control:a convex optimization approach

The problem of finding an internally stabilizing controller that minimizes a mixed H₂/H_∞ performance measure subject to an inequality constraint on the H_∞ norm of another closed-loop transfer function is considered. This problem can be interpreted and motivated as a problem of optimal nominal performance subject to a robust stability constraint. Both the state-feedback and output-feedback problems are considered. It is shown that in the state-feedback case one can come arbitrarily close to the optimal (even over full information controllers) mixed H₂/H_∞ performance measure using constant gain state feedback. Moreover, the state-feedback problem can be converted into a convex optimization problem over a bounded subset of (n×n and n ×q, where n and q are, respectively, the state and input dimensions) real matrices. Using the central H_∞ estimator, it is shown that the output feedback problem can be reduced to a state-feedback problem. In this case, the dimension of the resulting controller does not exceed the dimension of the generalized plant     

Efficient algorithms for list ranking and for solving graphproblems on the hypercube

A hypercube algorithm to solve the list ranking problem is presented. Let n be the length of the list, and let p be the number of processors of the hypercube. The algorithm described runs in time O(n/p) when n=Ω(p ^1+ε) for any constant ε>0, and in time O(n log n/p+log³ p) otherwise. This clearly attains a linear speedup when n=Ω(p ^1+ε). Efficient balancing and routing schemes had to be used to achieve the linear speedup. The authors use these techniques to obtain efficient hypercube algorithms for many basic graph problems such as tree expression evaluation, connected and biconnected components, ear decomposition, and st-numbering. These problems are also addressed in the restricted model of one-port communication     

Optimal resilient distributed algorithms for ring election

The problem of electing a leader in a dynamic ring in which processors are permitted to fail and recover during election is discussed. It is shown that &thetas;(n log n+k_r) messages, counting only messages sent by functional processors, are necessary and sufficient for dynamic ring election, where k_r is the number of processor recoveries experienced     

A generalized simultaneous access dictionary machine

A simultaneous access design of a dictionary machine which supports insert, delete, and search operations is presented. The design is able to handle p accesses simultaneously and allows redundant accesses to occur. In the design, processors performing insert or delete operations are free to perform other tasks after submitting their accesses to the design; processors that perform search operations get their response in O(log N) time. Compared to all sequential access designs of a dictionary which require O(p ) time to process p accesses, the presented design provides much higher throughput; specifically, O(p/log p) times better. It also provides a fast mechanism to avoid the sequential access bottleneck in any large multiprocessor system     

Balanced parallel sort on hypercube multiprocessors

A parallel sorting algorithm for sorting n elements evenly distributed over 2^d p nodes of a d-dimensional hypercube is presented. The average running time of the algorithm is O((n log n)/p+p log 2n). The algorithm maintains a perfect load balance in the nodes by determining the (kn/p)th elements (k1,. . ., (p-1)) of the final sorted list in advance. These p-1 keys are used to partition the sorted sublists in each node to redistribute data to the nodes to be merged in parallel. The nodes finish the sort with an equal number of elements (n/ p) regardless of the data distribution. A parallel selection algorithm for determining the balanced partition keys in O(p log2n) time is presented. The speed of the sorting algorithm is further enhanced by the distance-d communication capability of the iPSC/2 hypercube computer and a novel conflict-free routing algorithm. Experimental results on a 16-node hypercube computer show that the sorting algorithm is competitive with the previous algorithms and faster for skewed data distributions     

Compound-Poisson software reliability model

The probability density estimation of the number of software failures in the event of clustering or clumping of the software failures is considered. A discrete compound Poisson (CP) prediction model is proposed for the random variable X_rem, which is the remaining number of software failures. The compounding distributions, which are assumed to govern the failure sizes at Poisson arrivals, are respectively taken to be geometric when failures are forgetful and logarithmic-series when failures are contagious. The expected value (μ) of X_rem is calculated as a function of the time-dependent Poisson and compounding distribution based on the failures experienced. Also, the variance/mean parameter for the remaining number of failures, q_rem, is best estimated by q_past from the failures already experienced. Then, one obtains the PDF of the remaining number of failures estimated by CP(μ,q). CP is found to be superior to Poisson where clumping of failures exists. Its predictive validity is comparable to the Musa-Okumoto log-Poisson model in certain cases     

A smoothly parameterized family of stabilizable, observable linearsystems containing realizations of all transfer functions of McMillandegree not exceeding n

It is shown that there is a continuously parameterized family F of n-dimensional single-input single-output (SISO) stabilizable detectable linear system Σ(p) which contains at least one realization of each reduced, strictly proper transfer function of McMillan degree not exceeding n. The parameterization map p→Σ(p) is a polynomial function in 2n indeterminates from an open convex polyhedron in R²ⁿ to the linear space of all SISO n-dimensional linear systems     

Frequency domain criteria for lp-robuststability of continuous linear systems

Necessary and sufficient criteria in the frequency domain for robust stability are given under the assumption that coefficients of a characteristic polynomial belong to a transformed l^p-ball. Three cases are considered in detail: p =∞ (interval uncertainty), p=2 (ellipsoidal uncertainty), and p=1 (octahedral uncertainty). It is shown that frequency-domain-stability criteria are efficient when one deals with robust stability problems. The frequency-domain approach considered can be extended to various problems of robust stability     

Convolution on mesh connected multicomputers

An efficient parallel algorithm is presented for convolution on a mesh-connected computer with wraparound. The algorithm does not require a broadcast feature for data values, as assumed by previously proposed algorithms. As a result, the algorithm is applicable to both SIMD and MIMD meshes. For an N×N image and a M×M template, the previous algorithms take O (M²q) time on an N×N mesh-connected multicomputer (q is the number of bits in each entry of the convolution matrix). The algorithms have complexity O(M²r), where r=max {number of bits in an image entry, number of bits in a template entry}. In addition to not requiring a broadcast capability, these algorithms are faster for binary images     

Damping margins of polynomials with perturbed coefficients

Considers the polynomial P(s)=t₀ Sⁿ+t₁ S^n-1 +···+t_n where 0<a _j⩽t_j⩽b_j. Recently, V.L. Kharitonov (1978) derived a necessary and sufficient condition for this polynomial to have only zeros in the open left-half plane. Two lemmas are derived to investigate the existence of theorems similar to the theorem of Kharitonov. Using these lemmas, the theorem of Kharitonov is generalized for P(s) to have only zeros within a sector in the complex plane. The aperiodic case is also considered