# Efficient algorithm for computing area under convolution?

Consider $N$ discrete signals $x_1(n), x_2(n), \ldots,x_N(n)$ each a bounded support of size $M$.

To convolve them, we can zero-pad each of them, multiply their FFTs, and take the result's inverse FFT.
I believe this requires taking $N$ FFTs of length $N(M-1)+1$ each, taking $O(MN\,\log(MN))$ time.

However, what I need isn't the full convolution. I only need the area under the convolution above zero: $$\sum_{k=0}^\infty y(n)$$ assuming $y$ is the convolution of our signals: $$y = x_1 * x_2 * \ldots * x_N$$

Is there any algorithm that allows me to compute this value with a better time complexity than that required for computing the full convolution, or are the problems equally difficult?

Note that

$$\sum_ny[n]=Y$$

where $Y[k]$ is the DFT of $y[n]$. Since

$$Y[k]=\prod_iX_i[k]$$

with $X_i[k]$ the DFT of $x_i[n]$ (appropriately zero-padded), you have

$$\sum_ny[n]=Y=\prod_iX_i$$

And since

$$X_i=\sum_nx_i[n]$$ you get the final result

$$\sum_ny[n]=\prod_i\sum_nx_i[n]$$

the computation of which requires $N-1$ multiplications and $N(M-1)$ additions.

This little Matlab script illustrates how it works:

M=100;          % length of each signal
N=10;           % number of different signals
X=randn(M,N);   % each column of X contains a signal
Xs=sum(X);      % sums over each signal
Xsp=prod(Xs);   % product of the sums = desired result

% compute convolution of N signals
y=X(:,1);
for i=2:N, y=conv(y,X(:,i)); end
ys=sum(y);      % this should equal Xsp

[Xsp, ys]       % .. and it does

• What are the bounds on your summation? Nov 5, 2014 at 12:20
• @Mehrdad: Well, the product is over all $N$ signals, and the sums simply go over all elements of the respective signals. Nov 5, 2014 at 12:36
• @Mehrdad: I added a little Matlab/Octave script for clarity. Nov 5, 2014 at 16:40
• Why are you going through all elements, though? The question is about elements at n >= 0, not all n. Nov 5, 2014 at 19:25
• @Mehrdad: Why would there be any elements for $n<0$? Nov 5, 2014 at 21:27