An algorithm is presented for computing the triangular factors of the covariance matrix of a random vector whose elements are the successive differences of a stationary time series. This algorithm has applications in ...
详细信息
An algorithm is presented for computing the triangular factors of the covariance matrix of a random vector whose elements are the successive differences of a stationary time series. This algorithm has applications in the modeling of time series using a difference operator rather than using a shift operator, as is done in the conventional autoregressive model. The difference-operator based models offer the benefit of better numerical conditioning when applied to series that are obtained by sampling continuous-time processes at rapid rates. The covariance matrix of differenced data is not Toeplitz;however, it has a Toeplitz-like structure that is exploited in this paper to obtain an O(n2) algorithm. This algorithm is amenable to parallelization;i.e., it requires only O(n) time when using n processors in parallel.
A fast procedure for computing a ''modified'' triangular factorization and inverse of Hermitian Toeplitz and quasi-Toeplitz (matrices congruent in a certain sense to Toeplitz matrices) matrices is pres...
详细信息
A fast procedure for computing a ''modified'' triangular factorization and inverse of Hermitian Toeplitz and quasi-Toeplitz (matrices congruent in a certain sense to Toeplitz matrices) matrices is presented. A modified triangular factorization is an LDL* factorization where L is lower triangular with unit diagonal entries and D is a block diagonal matrix with possibly varying block sizes;only matrices with all leading minors nonzero, often called strongly regular, will always have a purely diagonal and nonsingular D matrix. For the matrices studied herein, the diagonal blocks also have a particular quasi-Toeplitz structure. The algorithms are obtained by extending a generating function approach of Lev-Ari and Kailath [Operator Theory: Adv. Appl., 18 (1986), pp. 301-324.] for matrices with a generalized displacement structure. A particular application of the result is a fast method of computing the rank profile and inertia of the matrices involved.
We derive an efficient recursive procedure for the triangular factorization of strongly regular matrices with generalized displacement structure that includes, as special cases, a variety of previously studied classes...
详细信息
We derive an efficient recursive procedure for the triangular factorization of strongly regular matrices with generalized displacement structure that includes, as special cases, a variety of previously studied classes such as Toeplitz-like and Hankel-like matrices, The derivation is based on combining a simple Gaussian elimination procedure with displacement structure, and leads to a transmission-like interpretation in terms of two cascades of first-order sections. We further derive state-space realizations for each section and for the entire cascades, and show that these realizations satisfy a generalized embedding result and a generalized notion of J-losslessness. The cascades turn out to have intrinsic blocking properties, which can be shown to be equivalent to interpolation constrains.
It is shown that when parallel prefix is used to compute the leading principal miners of a tridiagonal matrix T within a bisection algorithm to compute the eigenvalues of T the relative error in the computed ei,aenval...
详细信息
It is shown that when parallel prefix is used to compute the leading principal miners of a tridiagonal matrix T within a bisection algorithm to compute the eigenvalues of T the relative error in the computed ei,aenvalues can be as great as epsilon kappa(3), where epsilon is machine precision and kappa is the condition number for the problem of computing the eigenvalues of T. An ideal algorithm, like serial bisection, would have forward error epsilon kappa. Forward and backward error bounds for the computed leading principal miners are given. Also, error bounds for the parallel prefix computation of the partial products of a sequence of matrices are given and some applications to other related problems in numerical Linear algebra, including the parallel implementation of the differential qd algorithm, are presented.
We present a family of new fast algorithms for QR factorization of certain structured matrices, including rectangular Toeplitz matrices and a variety of other Toeplitz-like matrices. It possesses a very regular struct...
详细信息
We present a family of new fast algorithms for QR factorization of certain structured matrices, including rectangular Toeplitz matrices and a variety of other Toeplitz-like matrices. It possesses a very regular structure, and appears to be very convenient for parallel implementation. Moreover it is shown that the same architecture can be used for either triangular factorization or QR factorization. Our approach separates the conceptual and implementational aspects of the problem. Our analysis reveals a variety of algorithmic implementations of the basic procedure, all with potentially different numerical properties that need further examination.
This paper considers the problem of finding one compensator which simultaneously stabilizes a family of MIMO plants. The family of plants { P ˆ s,q : q ∊ Q } , represented by their transfer function matrices, may be u...
详细信息
This paper considers the problem of finding one compensator which simultaneously stabilizes a family of MIMO plants. The family of plants { P ˆ s,q : q ∊ Q } , represented by their transfer function matrices, may be uncountable thus allowing for the possibility of a continuum of variations in plant parameters. A “normalized triangular factorization” of the plant is introduced and shown to be quite useful as far as stabilization is concerned. To obtain the desired results, number of assumptions describing the set of allowable plants are imposed. These assumptions include some regularity conditions on the plant and MIMO versions of minimum phase and one sign high frequency gain requirements. The satisfaction of these assumptions guarantees the existence of a strictly proper stable compensator C(s) guaranteeing simultaneous stabilization. The algorithm used for controller design has one most attractive feature: Namely, it is recursive in nature and allows the designer to select one compensator coefficient at a time.
A hybrid granularity model is proposed for general concurrent solution. It is applied to the triangular factorization of a dense matrix ranging in size from 4 to 1024. Concurrency is achieved at two levels: (1) with s...
详细信息
A hybrid granularity model is proposed for general concurrent solution. It is applied to the triangular factorization of a dense matrix ranging in size from 4 to 1024. Concurrency is achieved at two levels: (1) with small (micro) task granularity and (2) with large (blocked) task granularity. Relevance to a many-processor CRAY X-MP is demonstrated by simulation.
Special methods for dealing with constraints of the formx j ≤ x k , called variable upper bounds, were introduced by Schrage. Here we describe a method that circumvents the massive degeneracy inherent in these constr...
详细信息
Special methods for dealing with constraints of the formx j ≤ x k , called variable upper bounds, were introduced by Schrage. Here we describe a method that circumvents the massive degeneracy inherent in these constraints and show how it can be implemented using triangular basis factorizations.
This paper describes a method for computing all the eigenvalues in a user supplied interval [a,b], and their associated eigenvectors, of the symmetric definite quadraticλ-matrix problem (Mλ2+Cλ+K)x=0, where the mat...
详细信息
This paper describes a method for computing all the eigenvalues in a user supplied interval [a,b], and their associated eigenvectors, of the symmetric definite quadraticλ-matrix problem (Mλ2+Cλ+K)x=0, where the matrices ar sufficiently sparse that methods based on similarity transformations are inappropriate. Only the triangular factorization of onen ×n matrix need be computed.
A triangular (LU) factorization of generalized inverse methods is used to derive explicitly solutions to the problem of computing the number of elements in any collection of intersecting sets. This approach reconciles...
详细信息
A triangular (LU) factorization of generalized inverse methods is used to derive explicitly solutions to the problem of computing the number of elements in any collection of intersecting sets. This approach reconciles recently proposed methods by Hellerman and Cavallo2and Schinnar,(6)with applications to a wide range of problems in social accounting and information systems theory.
暂无评论