Numerically stable fast convolution algorithm? Suppose you have two vectors of real numbers $\langle a_1, \dots, a_n \rangle, \langle b_1, \dots, b_n \rangle$, with $a_i, b_i \geq 0$, and wish to compute the convolution
$$
c_i = \sum_{j \leq i} a_j b_{i-j}
$$

There is an obvious algorithm to compute this in time $O(n^2)$. This obvious algorithm basically involves a sum of many positive summands, so there is no numerical cancellation. Hence the obvious algorithm is numerically stable.

The other obvious algorithm is to use a Fast Fourier transform to compute $\hat a, \hat b$, obtain $\hat c = \hat a \hat b$, and then use an inverse transform to obtain $c$. This algorithm is much faster, like $O(n \log n)$ time. Unfortunately, the Fourier transforms require adding many terms with different complex phases, so there is catastrophic cancellation. So this algorithm is numerically unstable.

Is there any algorithm which is both fast (near-linear time) and numerically stable?
There is the number theoretic transform where all calculations are done using integers which should completely get round any concerns about numerical stability, at the possible expense of some speed (see e.g. https://ccrma.stanford.edu/~jos/st/Number_Theoretic_Transform.html).  However this will only work for you if your numbers are rational and can be converted to integer representation easily.

There is also a whole range of asymptotically slower algorithms known as Toom-Cook multiplication http://en.wikipedia.org/wiki/Toom-Cook_multiplication. However, I am not sure it is true that multiplication via FFT calculations is necessarily numerically unstable. Do you have a reference for this claim?