# Padding length and error analysis of discrete convolution by FFT

The standard algorithm for discrete convolution of two vectors $$x\in \mathbb{R}^{n}$$ and $$y \in \mathbb{R}^{m}$$ is (in essence) a FFT of the two input vectors, multiplication of the two elementwise, and then an inverse FFT of the result. In practice there are complications, for example if $$m \ne n$$ then we need might need some padding of one of the inputs, and padding of the outputs.

From the following graph, you can see that the length of the zero padding affects the results, especially at the boundary. I have searched through the literature, but I could not find anything on the error analysis of the fast convolution algorithm (like Higham's analysis of the FFT in Accuracy and Stability). What error level should I expect for the fast convolution algorithm, and should the padding have this large of an affect? For reference, the code to generate the figure is here:

#!/usr/bin/env python3
import numpy as np
from numpy import fft as np_fft
from matplotlib import pyplot as plt

# scipy.fftconvolve doesn't allow control of the padding length,
# so make this function mimics what is done in scipy.fftconvolve
# i.e., ifft(fft(a) * fft(b))
fft, ifft = np_fft.rfftn, np_fft.irfftn
result_len = a.size + b.size - 1
ret = ifft(sp1 * sp2, (len_after_padding,))
return ret[:result_len]

def next_power_of_2(x):
return 1 << (x - 1).bit_length()

rng = np.random.default_rng(seed=10000)
a, b = rng.random((800,)), rng.random((800,))

result_direct = np.convolve(a, b)  # direct
len1 = next_power_of_2(a.size + b.size - 1)
result_fft_padding_len1 = convolve_by_fft(a, b, len1)  # fft padding to next power of 2
len2 = 2 * len1
a, b, len2
)  # fft padding to next next power of 2

# verify the error of last element
print(f"last element golden: {a[-1] * b[-1]}")
print(
f"last element direct: {result_direct[-1]}, error = {(result_direct[-1] - a[-1] * b[-1]) / (a[-1] * b[-1])}"
)
print(
)
print(
)
print(
)

# plot the error compare to the direct method
plt.plot(
)
plt.plot(
)
plt.plot(
$$$$
`
• I think the error level is expectable, the zero frequency corresponds to the integral of the function, and with 1600 evaluations at machine precision $10^{-16}$ you'll end up in the order $10^{-13}$. Aug 11, 2022 at 20:02