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     

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     

Output feedback eigenstructure assignment using two Sylvesterequations

The eigenstructure assignment problem with output feedback is studied for systems satisfying the condition p+m> n. The main tool used is the concept of (C, A, B)-invariance and two coupled Sylvester equations, the solution of which leads to the computation of an output stabilizing feedback. A computationally efficient algorithm for the solution of these two coupled equations, which leads to the computation of a desired output feedback, is presented     

Numerical algorithms for eigenvalue assignment by constant anddynamic output feedback

Algorithms are proposed for eigenvalue assignment (EVA) by constant as well as dynamic output feedback. The main algorithm is developed for single-input, multioutput systems and the results are then extended to multiinput, multioutput systems. In computing the feedback, use is made of the fact that the closed-loop eigenvalues can almost always be assigned arbitrarily close to the desired locations in the complex plane, provided the system satisfies the condition m+ p>n, where m, p, and n are , respectively, the number of inputs, outputs and states of the system. The EVA problem has been treated as a converse of the algebraic eigenvalue problem. The proposed algorithms are based on the implicitly shifted QR algorithm for solving the algebraic eigenvalue problem. The performance of the algorithms is illustrated by several numerical examples     

A solution to the diagonalization problem by constantprecompensator and dynamic output feedback

A solution is presented for the problem of diagonalization (row-by-row decoupling). The problem is solved using a constant precompensator and a dynamic output feedback compensator of a p×m linear time-invariant system. The solvability condition is compact and concerns the dimension of a single subspace defined via the concepts of essential rows and static kernels associated with the transfer matrix. A characterization of the set of all solutions to the problem is also given. In solving this dynamic feedback problem, a complete solution to its state-feedback counterpart, namely, the restricted state-feedback problem of diagonalization, is also presented     

Parameter convergence and stability in continuous-time indirectadaptive control

The author considers an indirect adaptive unity feedback controller consisting of an mth-order SISO (single input, single output) compensator controlling an nth-order strictly proper SISO plant. It is shown that exponential convergence of the plant parameter estimation error as well as asymptotic time invariance and global exponential stability of the controlled closed-loop system can be guaranteed by requiring that the reference input has at least 2n+m points of spectral support     

Balanced realization of stable transfer function matrices

Simple formulas are presented to compute the internally balanced minimal realization and the singular decomposition of the Hankel operator of a given continuous-time p×m stable transfer function matrix E(s)/d(s). The proposed formulas involve the Schwarz numbers of d(s) and the singular eigenvalues-eigenmatrices of a suitable finite matrix. Similar results are also obtained for a given discrete-time transfer function matrix     

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     

M-dimensional Cayley-Hamilton theorem

The theorem states that every block square matrix satisfies its own m-D (m-dimensional, m⩾1) matrix characteristic polynomial. The exact statement and a simple proof of this theorem are given. The theorem refers to a matrix A subdivided into m blocks, and hence having dimension at least m. The conclusion is that every square matrix A with dimension M satisfies several m-D characteristic matrix polynomials with degrees N₁ . . ., N _m, such that N₁+ . . . +N_m ⩽M     

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     

An efficient distributed knot detection algorithm

A distributed knot detection algorithm for general graphs is presented. The knot detection algorithm uses at most O(n log n+m) messages and O(m+n log n) bits of memory to detect all knots' nodes in the network (where n is the number of nodes and m is the number of links). This is compared to O(n²) messages needed in the best algorithm previously published. The knot detection algorithm makes use of efficient cycle detection and clustering techniques. Various applications for the knot detection algorithms are presented. In particular, its importance to deadlock detection in store and forward communication networks and in transaction systems is demonstrated     

Parallel binary search

Two arrays of numbers sorted in nondecreasing order are given: an array A of size n and an array B of size m, where n<m. It is required to determine, for every element of A, the smallest element of B (if one exists) that is larger than or equal to it. It is shown how to solve this problem on the EREW PRAM (exclusive-read exclusive-write parallel random-access machine) in O(logm logn/log log m) time using n processors. The solution is then extended to the case in which fewer than n processors are available. This yields an EREW PRAM algorithm for the problem whose cost is O(n log m, which is O(m)) for n⩽m/log m. It is shown how the solution obtained leads to an improved parallel merging algorithm     

Simple algorithms and architectures for B-spline interpolation

It is proved that the Toeplitz binary value matrix inversion associated with mth-order B-spline interpolation can be implemented using only 2(m+1) additions. Pipelined architectures are developed for real-time B-spline interpolation based on simple running average filters. It is shown that an ideal interpolating function, which is approximated by a truncated sinc function with M half cycles, can be implemented using B-splines with M+2 multiplies. With insignificant loss of performance, the coefficients at the knots of the truncated sinc function can be approximated using coefficients which are powers of two. The resulting implementation requires only M+4m+6 additions. It is believed that the truncated sinc function approximated by zero-order B-spline functions actually achieves the best visual performance     

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     

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     

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     

Parallel implementation of the extended square-root covariancefilter for tracking applications

Parallel implementations of the extended square-root covariance filter (ESRCF) for tracking applications are developed. The decoupling technique and special properties used in the tracking Kalman filter (KF) are employed to reduce computational requirements and to increase parallelism. The application of the decoupling technique to the ESRCF results in the time and measurement updates of m decoupled (n/m)-dimensional matrices instead of one coupled n-dimensional matrix, where m denotes the tracking dimension and n denotes the number of state elements. The updates of m decoupled matrices are found to require approximately m fewer processing elements and clock cycles than the updates of one coupled matrix. The transformation of the Kalman gain which accounts for the decoupling is found to be straightforward to implement. The sparse nature of the measurement matrix and the sparse, band nature of the transition matrix are explored to simplify matrix multiplications     

Job scheduling in a partitionable mesh using a two-dimensionalbuddy system partitioning scheme

The job scheduling problem in a partitionable mesh-connected system in which jobs require square meshes and the system is a square mesh whose size is a power of two is discussed. A heuristic algorithm of time complexity O(n(log n+log p)), in which n is the number of jobs to be scheduled and p is the size of the system is presented. The algorithm adopts the largest-job-first scheduling policy and uses a two-dimensional buddy system as the system partitioning scheme. It is shown that, in the worst case, the algorithm produces a schedule four times longer than an optimal schedule, and, on the average, schedules generated by the algorithm are twice as long as optimal schedules     

A sufficient condition for simultaneous stabilization

The condition under which it is possible to find a single controller that stabilizes k single-input single-output linear time-invariant systems p_i(s) (i=1,. . .,k) is investigated. The concept of avoidance in the complex plane is introduced and used to derive a sufficient condition for k systems to be simultaneously stabilizable. A method for constructing a simultaneous stabilizing controller is also provided and is illustrated by an example     

Built-in self-test of a CMOS ALU

A technique is proposed for implementing BIST (built-in self-test) in a CMOS arithmetic and logic unit (ALU). The approach covers single stuck-open faults and all functional faults that do not induce memory effects. The specific fault set covered by the test includes: (1) all single stuck-open faults on n and p transistors anywhere in the ALU (F1 faults); and (2) all functional faults that affect any single-bit slice of the (F2 faults), a functional fault being any fault that changes one combinational function into another. Functional faults in multiple slices are also detectable, as long as they do not generate identical responses in all even-numbered or odd-numbered ALU slices. With common techniques for test vector generation and response-verification, this BIST implementation provides higher fault coverage with only a small increase in surface area