Model conversions of uncertain linear systems via the interval Pade approximation method

This paper presents a new interval Pade approximation method to convert a continuous-time (discrete-time) uncertain linear system to an equivalent discrete-time (continuous-time) uncertain model via interval arithmetic operations. Based on the inclusion theorem related to the interval arithmetic, the interval Pade's approximants and their associated interval error matrices with interval arguments are obtained via the Pade's approximants and their associated error matrices with degenerate (real) arguments, respectively. Tighter error bounds of various approximate uncertain models with respect to their exact uncertain models are determined and used to modify the obtained Pade's approximants, so that the resulting approximate uncertain models are able to tightly enclose the original uncertain systems. Thus, the analysis and design of the original uncertain systems can be indirectly carried out using the converted uncertain models in either the continuous-time or the discrete-time domain.This work was supported in part by the U.S. Army Research Office under contract DAAH-04-94-G-0227 and the NASA-Johnson Space Center under Grant NAG-9-746.     

Covariance decompositions via elementary transformations. Applications to filtering

This paper depicts the connection between algorithms for the factorization of covariance matrices, a basic operation in linear estimation, and whitening or modeling filters. General algorithms for arbitrary covariances are presented and related to the four fundamental types of cascade filters: feed-forward and feed-back tapped delay line or ladder filter. Systolic implementations of the algorithms and realizations of the associated filters illustrate the correspondence between algorithms and filters. Finally, fast algorithms for special covariances are introduced through two important examples: constant-parameter tapped delay line and ladder filter.This work was supported by the Defense Advanced Research Projects Agency under Contract MDA903-80-C-0331 and in part by the Army Research Office under contract DAAG29-79-C-0215, the National Science Foundation under Grant ENG-78-1003, and the Joint Services Electronics Programs under Contract DAAG29-79-C-0047, while the authors were at Stanford University.     

Resource-constrained loop list scheduler for DSP algorithms

We present a new algorithm for resource-constrained scheduling for digital signal processing (DSP) applications when the number of processors is fixed and the objective is to obtain a schedule with the minimum iteration period. This type of scheduling is best suited for moderate speed applications where conservation of area and power is more important than speed. We define and make use of newgraph dependent constraints to obtain a lower bound estimate on the iteration period for any data-flow graph. By satisfying these constraints before performing the scheduling task, we can restrict the design space and can generate valid schedules in less time than previously reported. The graph dependent constraints provide a more accurate lower bound estimate on the iteration period than previously published results. This new scheduling algorithm exploits the iterative nature of DSP algorithms and uses aniterative-loop based scheduling approach. This resource scheduling algorithm has been incorporated in the Minnesota ARchitecture Synthesis (MARS) system. Our approach exploits inter-iteration and intra-iteration precedence constraints and incorporates implicit retiming and pipelining to generate optimal and near optimal schedules.This research was supported by the Advanced Research Projects Agency under grant number F33615-93-C-1309 and the office of Naval Research under contract number N00014-91-J-1008.     

Determining the minimum iteration period of an algorithm

Digital signal processing algorithms are repetitive in nature. These algorithms are described by iterative data-flow graphs where nodes represent computations and edges represent communications. For all data-flow graphs, there exists a fundamental lower bound on the iteration period referred to as theiteration bound. Determining the iteration bound for signal processing algorithms described by iterative data-flow graphs is an important problem. In this paper we review two existing algorithms for determination of the iteration bound. Then we propose another novel method based on theminimum cycle mean algorithm to determine the iteration bound with a lower polynomial time complexity than the two existing techniques. It is convenient to represent many multi-rate signal processing algorithms by multi-rate data-flow graphs. The iteration bound of a multi-rate data-flow graph (MRDFG) can be determined by considering the single-rate data-flow graph (SRDFG) equivalent of the MRDFG. However, the equivalent single-rate data-flow graph contains many redundant nodes and edges. The iteration bound of the MRDFG can be determined faster if these redundancies in the equivalent SRDFG are first removed. A previous approach has considered elimination of edge redundancy. In this paper we present an approach to eliminatenode redundancy in the MRDFG. We combine elimination of node and edge redundancies to propose a novel algorithm for faster determination of the iteration bound of the MRDFG.This research was supported by the Advanced Research Projects Agency and monitored by Wright—Patterson AFB under contract number F33615-93-C-1309.     

2D grid architectures for the DFT and the 2D DFT

New algorithms for the DFT and the 2-dimensional DFT are presented. The DFT and the 2-dimensional DFT matrices can be expressed as the Kronecker product of DFT matrices of smaller dimension. These algorithms are synthesized by combining the efficient factorization of the Kronecker product of matrices with the highly hardware efficient recursive implementation of the smaller DFT matrices, to yield these algorithms. The architectures of the processors implementing these algorithms consist of 2-dimensional grid of processing elements, have temporal and spatial locality of connections. For computing the DFT of sizeN or for the 2D DFT of sizeN=N ₁ byN ₁, these algorithms require 2N multipliers and adders, take approximately computational steps for computing a transform vector, and take approximately computation steps between the computation of two successive transform vectors.     

Stability analysis of complex dynamical systems

We present two new algorithms to estimate the domain of attraction of the equilibriumx=0 of a nonlinear systemx=f(x). One of these algorithms utilizes quadratic Lyapunov functions while the second algorithm makes use of norm Lyapunov functions. Both of these procedures yield estimates for the domain of attraction which are comparable to those obtained by existing methods; however, the present algorithms appear to be significantly more efficient than existing algorithms.We also show how sometimes the applicability of the above results can be extended to high order systems by invoking the comparison principle. In doing so, we establish some results for the comparison principle which are of interest in their own right. Specifically, we relate the domain of attraction of a low order comparison system to the domain of attraction of a higher order system and we give an interpretation of the comparison principle in terms of stability preserving maps.In order to demonstrate the applicability of the present results, and in order to compare the present results with existing results, several specific examples are presented.Supported in part by the National Science Foundation under grants ENG77-28446 and ECS-81-00690.     

Fault-tolerant VLSI sorters

Parallel sorting algorithms have been proposed for VLSI implementation. Random defects in the silicon wafer and fabrication errors render processors in the wafer faulty, and may cause these algorithms to fail despite a significant number of nonfaulty processors. This paper presents twofault-tolerant pipelined sorting algorithms that would work on a wafer comprised of faulty and nonfaulty processors. Both the algorithms useO(n) processors and requireO(n) time to sortn elements.P. J. Varman's research was supported by an IBM Faculty Development Award, I. V. Ramakrishnan's by the ONR Grant N00014-84-K-0530 and NSF Grant ECS-84-04399, and D. S. Fussell's by NSF Grant MCS-8104017.     

Robust stabilization of singular systems withH ∞-bounded uncertainty

In this paper the problem of robust stabilizing a linear, time-invariant singular system is studied. The characterization is given in terms ofH -bounded perturbations to the numerator and denominator factors of its normalized left coprime factorization. An optimal stability margin is provided in terms of the definition of the Hankel norm of a singular system. The Hankel norm is computed using two generalized Lyapunov equations.This research was supported by the Defense Advanced Research Projects Agency under contract MDA-972-93-1-0032 and MDA-972-95-3-0016.     

Decomposition of Binary Matrices and Fast Hadamard Transforms

Binary matrices or (± 1)-matrices have numerous applications in coding, signal processing, and communications. In this paper, a general and efficient algorithm for decomposition of binary matrices and the corresponding fast transform is developed. As a special case, Hadamard matrices are considered. The difficulties of the construction of 4n-point Hadamard transforms are related to the Hadamard problem: the question of the existence of Hadamard matrices. (It is not known whether for every integer n, there is an orthogonal 4n × 4n matrix with elements ± 1.) In the derived fast algorithms, the number of real operations is reduced from O(N²) to O(N log N) compared to direct computation. The proposed scheme requires no zero padding of the input data. Comparisions revealing the efficiency of the proposed algorithms with respect to the known ones are given. In particular, it is demonstrated that, in typical applications, the proposed algorithm is significantly more efficient than the conventional Walsh-Hadamard transform. Note that for Hadamard matrices of orders ≥ 96 the general algorithm is more efficient than the classical Walsh-Hadamard transform whose order is a power of 2. The algorithm has a simple and symmetric structure. The results of numerical examples are presented.     

Continuation algorithms for the eigenvalue problems

Three algorithms for the solution of the eigenvalue problem for a continuously parameterized family of sparse matrices are presented; a continuousLU (orLR) algorithm, a continuousQR algorithm, and a continuous Hessenberg algorithm. Each of the three algorithms may be implemented recursively and the sparsity of the given matrices is preserved throughout the numerical process.This research was supported by the Joint Services Electronics Program at Texas Tech under ONR Contract 76-C-1176.     

Systolic architectures for adaptive multichannel least squares lattice filters

A family of systolic array architectures for adaptive multichannel least squares lattice (MLSL) filters is presented. These architectures are based on a recently developed algorithm that provides an efficient, numerically sound, and well-structured set of recursions for realizing MLSL filters. The algorithm is based on the recursive QR decomposition of the forward and backward error correlation matrices. Form input channels andp filter taps,O(pm ²) computations are required per time step. Numerous space-time tradeoffs are available in mapping the algorithm's recursions to systolic architectures, leading to the architectural family presented here.Los Alamos National Laboratory is operated by the University of California for the United States Department of Energy under contract W-7405-ENG-36.     

FFT computation with linear processor arrays using a data-driven control scheme

We consider the practical design of linear controllers to meet a given set ofH ₂ specifications. TheQ-parametrization reduces the problem to a quadratic minimization subject to multiple quadratic constraints, which we solve using semi-definite programming (SDP) methods. Each SDP iteration requires calculating a primal and dual search direction and minimizing the cost function along the plane defined by these search directions. The primal direction requires solving a least squares problem whose normal equation matrix is composed of a block-Toeplitz portion plus other structured matrices. We make use of Kronecker products and FFT's to greatly reduce the calculation. The dual search direction and plane search are accelerated by low-rank representations of the SDP structured matrices.As an example, we design controllers which explore the optimal tradeoff between in-band residual and out-of-band enhancement of acoustic radiation from a (mathematically modeled) submerged spherical shell, while simultaneously constraining two sensitivity measures. For this example we show that significant reduction in out-of-band enhancement is possible with only minor in-band penalties.This work was supported by the Office of Naval Research under Contract N00014-94-C-0128     

On reduced polynomial-based split algorithms

In this work we analyze the mathematical structure associated with the split algorithms for computing the reflection coefficients for a given real, symmetric, positive-definite Toeplitz matrix. A new form of three-term recurrence relation is derived and computationally efficient alternatives to the Levinson-Durbin, Schur, lattice, and normalized lattice algorithms are obtained. The computational complexity of the new algorithms is the same as those of the split algorithms described in the recent literature. The relationships between the various algorithms are also established. These algorithms also provide further insight into the mathematical properties of the structurally rich Toeplitz matrices.This research was supported by the SDIO/IST and managed by the Army Research Office under Contract DAAL03-87-K-0027.     

Shorted matrices in star and related orderings

A new class of shorted operators is considered. The shorted operator has an intimate relationship with electrical networks and has been extensively studied. In this work we consider the class of matrices with row and column spans in specified linear subspaces and dominated in a given partial order by a matrixA. If this class of matrices has an unique maximal element under the partial order, then this maximal element is called the shorted matrix ofA relative to the given linear subspaces and the relevant partial order. We study the shorted matrix under the star order of Drazin, the minus order, and also under partial orders induced by the minimum norm and least squares g-inverses. The parallel sum of matrices is intimately related to the shorted matrix and results are given for parallel addition.     

Spectral mimicry: A method of synthesizing matching time series with different Fourier spectra

Given a stationary time seriesX and another stationary time seriesY (with a different power spectral density), we describe an algorithm for constructing a stationary time series Z that contains exactly the same values asX permuted in an order such that the power spectral density ofZ closely resembles that ofY. We call this methodspectral mimicry. We prove (under certain restrictions) that, if the univariate cumulative distribution function (CDF) ofX is identical to the CDF ofY, then the power spectral density ofZ equals the power spectral density ofY. We also show, for a class of examples, that when the CDFs ofX andY differ modestly, the power spectral density ofZ closely approximates the power spectral density ofY. The algorithm, developed to design an experiment in microbial population dynamics, has a variety of other applications.The work of J. E. Cohen was supported by U.S. National Science Foundation grant BSR92-07293. The research of C. M. Newman was supported in part by NSA Grant MDA 904-96-I-0033 and by NSF Grants DMS-95-00868 and DMS-98-03267. The work of O. L. Petchey and A. Gonzalez was supported by the U.K. Natural Environment Research Council.     

Higher order cumulants and cumulant spectra

An exposition of joint cumulants and cumulant spectra is presented. A distinction is emphasized in this paper between the cumulant spectrum of a time series and its stationary version, here called apolyspectrum. The variance and covariance of the sample bispectrum is then derived using a relationship between cumulant spectra of the finite Fourier transform for the 2nd and 4th cumulant function, and the bispectrum and trispectrum of the time series.This work was supported by the Office of Naval Research under contract N00014-91-J-1276.     

Steepest Descent Algorithms for Optimization Under Unitary Matrix Constraint

In many engineering applications we deal with constrained optimization problems with respect to complex-valued matrices. This paper proposes a Riemannian geometry approach for optimization of a real-valued cost function T of complex-valued matrix argument W, under the constraint that W is an n times n unitary matrix. We derive steepest descent (SD) algorithms on the Lie group of unitary matrices U(n). The proposed algorithms move towards the optimum along the geodesics, but other alternatives are also considered. We also address the computational complexity and the numerical stability issues considering both the geodesic and the nongeodesic SD algorithms. Armijo step size [1] adaptation rule is used similarly to [2], but with reduced complexity. The theoretical results are validated by computer simulations. The proposed algorithms are applied to blind source separation in MIMO systems by using the joint diagonalization approach [3]. We show that the proposed algorithms outperform other widely used algorithms.     

Wavelet packets for fast solution of electromagnetic integralequations

This paper considers the problem of wavelet sparsification of matrices arising in the numerical solution of electromagnetic integral equations by the method of moments. Scattering of plane waves from two-dimensional (2-D) cylinders is computed numerically using a constant number of test functions per wavelength. Discrete wavelet packet (DWP) similarity transformations and thresholding are applied to system matrices to obtain sparsity. If thresholds are selected to keep the relative residual error constant the matrix sparsity is of order O(N^P) with p<2. This stands in contrast with O(N² ) sparsities obtained with standard wavelet transformations. Numerical tests also show that the DWP method yields faster matrix-vector multiplication than some fast multipole algorithms     

Bidiagonalization and symmetric tridiagonalization by systolic arrays

We give a systolic algorithm and array for bidiagonalization of ann × n matrix inO(n logn) time, usingO(n ²) cells. Bandedness of the input matrix may be effectively exploited. If the matrix is banded, withp nonzero subdiagonals andq nonzero superdiagonals, then 4n ln(p+q)+O(n) clocks and 2n(p+q)+O((p+q) ²+n) cells are needed. This is faster than the best previously reported result by the factor log₂ e=1.44.... Moreover, in contrast to earlier systolic designs, which require the matrix to be preloaded into the array and the result matrix extracted after bidiagonalization, the present arrays are pipelined.This work was performed at Rensselaer Polytechnic Institute, Troy, New York 12180-3590. This research was partially supported by the Office of Naval Research under Contract N00014-86-K-0610.     

An Efficient Parallel Algorithm for Merging in the Postal Model

Given two sorted lists A = (a0, a1 ^…, al-1) and B = (b0, b1, ^…, bm-¹), we are to merge these two lists into a sorted list C = (c0, c1, ^…, cn-1), where n = l + m. Since this is a fundamental problem useful to solve many problems such as sorting and graph problems, there have been many efficient parallel algorithms for this problem. But these algorithms cannot be performed efficiently in the postal model since the communication latency …, which is of prime importance in this model, is not needed to be considered for those algorithms. Hence, in this paper we propose an efficient merge algorithm in this model that runs in time by using a new property of the bitonic sequence which is crucial to our algorithm. We also show that our algorithm is near-optimal by proving that the lower bound of this problem in the postal model is , where