<p>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. <a href="https://ccrma.stanford.edu/~jos/st/Number_Theoretic_Transform.html" rel="nofollow">https://ccrma.stanford.edu/~jos/st/Number_Theoretic_Transform.html</a>).  However this will only work for you if your numbers are rational and can be converted to integer representation easily.</p>

<p>There is also a whole range of asymptotically slower algorithms known as Toom-Cook multiplication <a href="http://en.wikipedia.org/wiki/Toom-Cook_multiplication" rel="nofollow">http://en.wikipedia.org/wiki/Toom-Cook_multiplication</a>. 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?  </p>

CC BY-SA 3.0
2016-08-25T20:05:00.957Z
One interpretation of a DFT is in evaluating a polynomial at N points (these points being the roots of unity). If you interpret each signal being convolved as the coefficients to two different polynomial, and one of these polynomials has its roots concentrated over a small domain, then evaluating it far outside that domain would result in numbers much larger than when evaluating it near the roots, and thus the difference in magnitude may be impossible to capture with any conventional finite number system (e.g. floating point).
Ponkadoodle
CC BY-SA 3.0
2012-08-09T20:41:23.053Z
2012-08-09T21:05:31.893Z
2012-08-09T21:05:31.893Z
Raphael
<p>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}
$$</p>

<p>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.</p>

<p>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.</p>

<p>Is there any algorithm which is both fast (near-linear time) and numerically stable?</p>

<ds.algorithms><na.numerical-analysis>
Numerically stable fast convolution algorithm?
David Harris
# Numerically stable fast convolution algorithm?

(Asked by: username_0 on 2012-08-08)

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?

**Tags:** ds.algorithms, na.numerical-analysis

---

## 1 answers

### Answer by username_1 on 2012-08-09. Score: 1

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?

> **Comments:**
> **username_2**: One interpretation of a DFT is in evaluating a polynomial at N points (these points being the roots of unity). If you interpret each signal being convolved as the coefficients to two different polynomial, and one of these polynomials has its roots concentrated over a small domain, then evaluating it far outside that domain would result in numbers much larger than when evaluating it near the roots, and thus the difference in magnitude may be impossible to capture with any conventional finite number system (e.g. floating point).  

---

