Parallel smoothing algorithms for causal and acausal systems

Parallel processing algorithms for optimal smoothing of discrete-time linear systems described by two-point boundary value difference equations are presented. These algorithms involve the partitioning of the data interval with one processor for each subinterval. The processing structures consist 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 described produce maximum-likelihood (ML) estimates in which dynamics and a priori conditions play the same role as measurements. Consideration of such ML procedures for descriptor systems requires a general procedure for recursive estimation in situations in which neither the error covariance nor its inverse is well defined. This leads to a generalization of a two-filter algorithm in which the two directions of processing are treated symmetrically. For the local processing, it also simplifies the information exchange. A two-filter implementation of this step and a highly parallel implementation exactly matched to the hypercube computer architecture are presented