An Efficient Algorithm for the Classical Least Squares Approximation
Dimitar K. Dimitrov, Lourenço de Lima Peixoto · SIAM Journal on Scientific Computing · 2020
We explore the computational issues concerning a new algorithm for the classical least-squares approximation of $N$ samples by an algebraic polynomial of degree at most $n$ when the number $N$ of the samples is very large. The algorithm is based on a recent idea about accurate numerical approximations of sums with large numbers of terms. For a fixed $n$, the complexity of our algorithm in double precision accuracy is $\mathcal{O}(1)$. It is faster and more precise than the standard algorithm in MATLAB.