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     

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     

Computational aspects of the bilinear transformation basedalgorithm for S-plane to Z-plane mapping

The author analyzes the computational complexity of an algorithm by F.D. Groutage et al. (ibid., vol.AC-32, no.7, p.635-7, July 1987) for performing the transformation of a continuous transfer function to a discrete equivalent by a bilinear transformation. Groutage et al. defend their method by noting that their technique is not limited to the bilinear transformation. Rather, it can be extended to any higher-order integration rule (Simpson, Runge-Kutta, etc.), or to any higher-order expansion of the ln function. In general, using the method, s can be any appropriate mapping function s=f (z)     

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     

Indirect adaptive suboptimal control for linear dynamic systemshaving polynomial nonlinearities

An indirect adaptation algorithm to adaptively implement a control weighted one-step-ahead suboptimal control law previously derived for the control of stochastic linear dynamic systems having polynomial nonlinearities is presented. Since identification is separated from the calculation of controller design and a single adaptation algorithm is used, the indirect scheme provides more flexibility and has the advantage that few estimated parameters and less memory space are required in the case when the system time delay d and/or degree p of the polynomial are large. It has been shown that the proposed indirect scheme has the same global convergence property as the direct scheme given by Zhang and Lang (see ibid., vol.AC-32, no.8 (1987))     

Order-determination theorems and system identification

Theorems for order-determination without a priori knowledge of upper bounds on the order in MIMO dynamic systems are developed. Also, deterministic procedures are introduced to determine orders and estimate parameters simultaneously by recursively computing the order-determining quantity S_n(a,b,k), which plays a crucial role in order-determination procedures, and the least-squares estimate &thetas;_n(a,b) of &thetas;(p,q), with p and q denoting the true orders     

Necessary and sufficient conditions for mixedH2 and H∞ optimal control

It is shown that D.S. Bernstein and W.M. Hadad's (ibid., vol.34, no.3, p.293, 1989) necessary condition for full-order mixed H ₂ and H_∞ optimal control is also sufficient, and that J.C. Doyle et al.'s (Proc. Amer. Control Conf., p.2065, 1989) sufficient condition for full-order mixed H₂ and H_∞ optimal control is also necessary. They are duals of one another     

Decomposing the Laplacian

A correction is made and an elementary derivation is given of Clark's (ibid., vol.11, p.43-57, 1989) decomposition of the Laplacian Δ²f(x,y) into a second directional derivative in the gradient direction of f, and a product of gradient magnitude by curvature of the level curve through f(x,y)     

Comments on `S-plane to Z-plane mapping using asimultaneous equation algorithm based on the bilinear transformation' byF.D. Groutage, et al

The commenter directions attention to a conveniently implementable scheme for implementing the bilinear transformation used in the above mentioned paper (ibid., vol.AC-32, no.7, p.635-7, July 1987), which is based on the use of the Q_n matrix. He suggests that the overall advantages in the use of Q_n matrix cannot be matched by the authors' approach     

A comment on `An inequality for the trace of matrix product' byJ.K. Baksalary and S. Puntanen

An example is provided which illustrates that the new bounds for the trace of the product of an arbitrary n×n real matrix A and an n×n nonnegative definite real symmetric matrix B derived in the above-titled paper (ibid., vol.37, no.2, pp.239-240, Feb. 1992) are not valid     

Optimal H∞ norm computation formultivariable systems with multiple zeros

B. C.Chang and J.B. Peason's (see ibid., vol. AC-29, p.880-7, Oct. 1984) computation of the optimal H^∞ norm is generalized to the case with multiple right half-plane zeros. D. Sarason's (1967) interpolation theory is used to reduce the problem to a simple eigenvalue or singular-value computation     

On the parameterization H∞ controllers

The author clarifies some of the results of J.C. Doyle et al. (ibid., vol.34, no.8, p.831-47, Aug. 1989) and gives some new interpretations. In particular, the author parameterizes all suboptimal H_∞ controllers for the full information (FI) and state feedback control problems and indicates when this FI H_∞ control problem can or cannot be given a differential game saddle point interpretation     

Applications of hysteresis switching in parameter adaptive control

The hysteresis switching algorithm of R.H. Middleton et al. (ibid., vol.33, no.1, p.50-8, Jan. 1988) is reexamined in a broader context. To demonstrate its utility, the algorithm is applied to various families of identifier-based parameterized controllers of both the direct and indirect control types. Application to the direct control type results in a model reference adaptive controller capable of stabilizing, without excitation, any SISO process which can be modeled by a minimum phase linear system whose transfer function has relative and McMillan degrees not exceeding prescribing integers m and n, respectively. It is shown that such processes can also be adaptively stabilized with indirect adaptive controllers and hysteresis switching. A simple numerical example involving a non-minimum-phase process model is used to illustrate how hysteresis switching might be applied to implicitly tuned parameterized controllers to realize an adaptive controller with capabilities which might prove very difficult, if not impossible, to achieve without hysteresis switching or some other form of discontinuous control     

Comments on `Parallel algorithms for hierarchical clustering andcluster validity'

In the above-titled paper (ibid., vol.12, no.11, p.1088-92, Nov. 1990), parallel implementations of hierarchical clustering algorithms that achieve O(n²) computational time complexity and thereby improve on the baseline of sequential implementations are described. The latter are stated to be O( n³), with the exception of the single-link method. The commenter points out that state-of-the-art hierarchical clustering algorithms have O(n²) time complexity and should be referred to in preference to the O(n³ ) algorithms, which were described in many texts in the 1970s. Some further references in the parallelizing of hierarchic clustering algorithms are provided     

Comments on `Conditions for stable zeros of sampled systems' by M.Ishitobi

The commenter argues that the result of the above-titled work (see ibid., vol.37, no.10, p.1558-1561, Oct. 1992) is incorrect. It is pointed out that when sampling a continuous-time system G(s ) using zero-order hold, the zeros of the resulting discrete-time system H(z) become complicated functions of the sampling interval T. The system G(s) has unstable continuous-time zeros, s=0.1±i. The zeros of the corresponding sampled system start for small T from a double zero at z=1 as exp(T(0.1±i )), i.e., on the unstable side. For T>1.067 . . . the zeros become stable. The criterion function of the above-titled work, F(T)=G*(jω_s/2)= H(-1)T/2, is, however, positive for all T, indicating only stable zeros. The zero-locus crosses the unit circle at complex values     

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     

Further comments on `A multivariable generalized self-tuningcontroller with decoupling design'

Results for updating the weighting matrices presented in the work by S.-J. Lang et al. (see ibid., vol.AC-31, p.474-7, May 1986) are shown to be problematic and generally difficult to use     

Systolic computation of multivariable frequency response

An algorithm intended for software implementation on a programmable systolic/wavefront computer is presented for the computation of a complex-valued frequency-response matrix G. Typically, real-valued state-space model matrices are given and the calculation of G must be performed for a very large number of values of the scalar frequency parameter. The algorithm is an orthogonal version of an algorithm described previously by A.J. Laub (ibid., vol.26, no.4, p.407-8, 1981). The system matrix A is reduced initially to an upper Hessenberg form which is preserved as the frequency varies subsequently. A systolic QR factorization of a certain complex-valued matrix is then implemented for effecting the necessary linear system solution (inversion). The critical computational component is the back solve. This computational component's process dependency graph is embedded optimally in space and time through the use of a nonlinear spacetime transformation. The computational period of the algorithm is O(n) where n is the order of the matrix A     

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     

Adaptive control based on explicit model of robot manipulator

Adaptive and nonadaptive control algorithms, which make use of a fundamental mathematical property concerning positive definite matrices and Lyapunov stability theory, are proposed for the control of robot manipulators. Using the fact that the matrix dD(q)/dt-2C(q, dq/ dt) is skew symmetric, nonadaptive controllers which have a simplified structure with less computational burden are proposed. Using the dynamic equations for robot manipulators, parameter adaptation rules are developed for updating the controller's partially or totally unknown parameters, generalizing them to model reference adaptive controllers. To further take advantage of the simplified structure of the proposed adaptive controllers, a method for deriving the dynamic model of a robot manipulator which is linear in terms of its parameters is given. This dynamic model is also suitable for the pure identification of the parameters of links and payload of the manipulator