Время выполнения свертки с использованием fft в Matlab - PullRequest
Новая
       79

Время выполнения свертки с использованием fft в Matlab

0 голосов
/ 10 октября 2018

У меня есть два сигнала x1 и x2.Я пытаюсь сделать свертку один раз, используя CONV (x1, X2) напрямую и один раз, используя fft и ifft, и сравнить время выполнения обеих операций.

Я не знаю, почему время выполнения fft небыстрее, чем при использовании conv. 

n = 0: 2^15 ;
x1(n+1) = (0.25).^n ;
x2(n+1) = 1;

tic
Time_Convolution = conv(x1,x2);
toc


Padding = (length(x1)+ length(x2) - 1)-length(x1) ;
x1_before_fft = [ x1 zeros(1, Padding) ];
x2_before_fft = [ x2 zeros(1,  Padding)];

tic
Convolution = ifft(fft( x1_before_fft).*fft(x2_before_fft));   
toc

Вот вывод

Истекшее время составляет 0,010414 секунды.Прошедшее время составляет 0,017308 секунд.

1 Ответ

0 голосов
/ 10 октября 2018

Ключевым моментом здесь является то, что один из ваших входных сигналов содержит в основном нули, поскольку вы теряете точность при округлении от повышения 0,25 до больших степеней: 

 >> nnz(x1) / numel(x1)
 ans =
     0.0164

Менее 2% от вашего первого вводаненулевая.Прямая реализация свертки может использовать это, чтобы избавиться от множества операций, которые ничего не дают в результате.Однако свертка на основе БПФ всегда будет выполнять примерно одинаковый объем работы, независимо от величины используемых коэффициентов.

Ситуация совершенно иная, если вы сделаете эти коэффициенты ненулевыми.На моей машине я вижу: 

 >> tic; for k = 1:100, conv(x1,x2); end, toc
 Elapsed time is 0.291373 seconds.
 >> x1 = x1 + eps;
 >> tic; for k = 1:100, conv(x1,x2); end, toc
 Elapsed time is 3.937819 seconds.

Еще одна вещь, которую стоит отметить, это то, что вы используете неудачный выбор размера БПФ для свертки через БПФ.Любое преобразование, которое использует по крайней мере length(x1)+length(x2)-1 точек, сделает свое дело (вам просто нужно обрезать любые дополнительные коэффициенты в конце, если у вас есть большее преобразование), поэтому лучше выбрать тот, который имеет малые простые коэффициенты.В этом случае, однако, length(x1)+length(x2)-1 само по себе простое, поэтому это наихудший вариант.Посмотрите на разницу, которую вы можете увидеть, просто увеличив эту длину на 1: 

 >> N = length(x1)+length(x2)-1;  % Original size.
 >> tic; for k = 1:100, ifft(fft( x1, N).*fft(x2,N)); end, toc
 Elapsed time is 1.036913 seconds.
 >> N = length(x1)+length(x2);  % Better size.
 >> tic; for k = 1:100, ifft(fft( x1, N).*fft(x2,N)); end, toc
 Elapsed time is 0.289473 seconds.

Конечно, вы можете добиться большего, если продолжите уменьшать коэффициенты N: 

 >> N = length(x1)+length(x2)
 N =
        65538
 >> while max(factor(N)) > 7, N = N + 2; end
 >> N
 N =
        65610
 >> tic; for k = 1:100, ifft(fft( x1, N).*fft(x2,N)); end, toc
 Elapsed time is 0.250967 seconds.

Так что, просто выбрав лучший размер преобразования, вы получаете ускорение в 4 раза, и теперь даже с возможностью conv оптимизации для всех этих нулей вы получите лучшую скорость.

...