A fast algorithm for linear least-squares smoothing and boundary value problems using number-theoretic transforms

Abstract

A fast algorithm for linear least-squares smoothing and boundary value problems using number-theoretic transforms (NTT) is presented. The algorithm utilizes the fact that the fixed interval smoother can be imbedded in a boundary value problem, which can be reformulated as a problem of solving a perturbed-circulant system of equations. The new algorithm solves this perturbed-circulant system of equations by decomposing the solution into a circular deconvolution filter, which can be implemented using NTT, and a small-kernel FIR filter, which only involves a small matrix inversion. The major advantages of this algorithm are (1) it avoids roundoff error and attendant conditioning problems, (2) no storage or computation of complex, irrational roots of unity is required, and (3) computations involving large numbers are broken up into computations involving smaller number, which can be performed faster and in parallel.