Fast Fourier transform algorithms for linear estimation, smoothing and Riccati equations

In the past two decades since the advent of Kalman´s recursive filter, numerous algorithms for linear estimation have emerged. Most of these algorithms are recursive and rely on solving a Riccati equation or equivalent recursive equations. It will be shown how some of the classical problems such as linear smoothing, Riccati equations, boundary value problems, and recursive block filtering problems can be solved exactly by some new nonrecursive algorithms which are based on the fast Fourier transform (FFT). In the context of modern digital signal processing these algorithms have a highly parallel structure and are well suited for VLSI implementations.