Parallel smoothing for time-invariant two-point boundary value systems
A parallel and stable algorithm is presented for solving the smoothing problem for two-point boundary value systems. The algorithm uses the generalized Schur decomposition of matrix pencils to decouple the Hamiltonian system that governs the solution to the two-point boundary value smoothing problem into forward-stable and backward-stable recursions. Associative fan-in algorithms are then used to compute in a parallel stable fashion the various quantities that are needed to evaluate the solution of the forward and backward recursions. Those solutions are finally combined to obtain the desired smoothed estimates. The total running time of this procedure is O(log K) time units for 1-D smoothing problems defined on the interval (0, K). The algorithm is characterized by a high efficiency and low interprocessor communications requirements.<<ETX>>