Parallel Smoothing Algorithms for Casual and Acausal Systems
Abstract
In this paper we describe parallel processing algorithms for optimal smoothing for discrete time linear systems described by two point boundary value difference equations. These algorithms involve the partitioning of the data interval with one processor for each subinterval. The processing structures considered consists of independent parallel processing on each subinterval, followed by an information exchange between processors and then a final sweep of independent subinterval processing. The local processing procedures that we describe produce maximum likelihood (ML) estimates in which dynamics and a priori conditions play the same role as measurements, i.e. they are all noisy constraints. Consideration of such ML procedures for descriptor systems requires that we develop a general procedure for recursive estimation in situations in which neither the error covariance nor its inverse is well defined. This leads among other things to a generalization of the well known Mayne-Fraser two filter algorithm in which the two directions of processing are treated symmetrically,. Furthermore using an ML procedure for the local processing step leads to considerable simplification of the subsequent interprocessor information exchange step. We present both a two filter implementation of this step as well as a highly parallel implementation exactly matched to the hypercube computer architecture. This algorithm by itself yields a new parallel smoothing algorithm and also, significantly, is extendible to higher dimension offering the promise of even more significant computational savings for applications involving the estimation of random fields.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1991
- Accession Number
- ADA459350
Entities
People
- A. S. Willsky
- Dean C. Taylor
Organizations
- Massachusetts Institute of Technology