Дискретное преобразование Фурье, ускорение расчета - PullRequest
Новая
       77

Дискретное преобразование Фурье, ускорение расчета

0 голосов
/ 25 февраля 2020

Ввод: эрмитова матрица \rho_{i,j} с i,j=0,1,..d-1

Выход: neg=\sum |W(mu,m)|-W(mu,m), сумма по всем mu,m=0,..d-1 и W(mu,m)=\sum exp(-4i\pi mu n /d) \rho_{(m-n)%d,(m+n)%d}, где n=0,..d-1

Проблема: 1) для больших d (d> 5 000) прямой метод (см. фрагмент 1) довольно медленный.

2 ) использование 'np.fft.fft ()' намного быстрее, но в определении используется показатель степени с 2, а не 4 https://docs.scipy.org/doc/numpy/reference/routines.fft.html#module - numpy .fft

Можно ли улучшить фрагмент 1, используя фрагмент 2 для ускорения расчета скорости? Может быть, можно использовать 2D FFT?

Фрагмент 1: 

W=np.zeros([d,d])
neg=0
        for mu in range(d):
            for m in range(d):
                x=0            
                for n in range(d): 
                    x+=np.exp(-4*np.pi*1.0j*mu*n/N)*rho[(m-n)%d,(m+n)%d]
                W[mu,m]=x.real
                neg+=np.abs(W[mu,m])-W[mu,m]

Фрагмент 2: 

# create matrix \rho
psi=np.random.rand(500)
psi=psi/np.linalg.norm(psi) # normalize it
d=len(psi) 
rho=np.outer(psi,np.conj(psi)) 

#
start_time=time.time()
m=1 # for example, use particular m 

a=np.array([rho[(m-nn)%d,(m+nn)%d] for nn in range(d)])
ft=np.fft.fft(a)

end_time=time.time()
print(end_time-start_time)

1 Ответ

1 голос
/ 25 февраля 2020

Удалите вложенные циклы, используя numpy s арифметику массива. 

import numpy as np

def my_sins(x):
    return np.sin(2*x) + np.cos(4*x) + np.sin(3*x)

def dft(x, n=None):
    if n is None:
        n = len(x)   
    k = len(x)    
    cn = np.sum(x*np.exp(-2*np.pi*1j*np.outer(np.arange(k),np.arange(n))/n),1)
    return cn

Для некоторых примеров данных 

x = np.linspace(0,2*np.pi,1000)
y = my_sins(x)

%timeit dft(y)

В моей системе это дает: 

145 ms ± 953 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
...