notes_decimated_GDTFD_algorithms.org

Computational load and memory for algorithms

#

critically-sampled TFDs

kernel-type	no. of FFTs	load	memory (real-valued points)
non-separable	3N/2 × FFT-N	3N²/2 log₂ N	N²
LI	N/2 × FFT-Ntime	NNtime/2 log₂ Ntime	Ntime × N
DI	N/2 × FFT-Nfreq	NNfreq/2 log₂ Nfreq	N × Nfreq
separable	Pₕ ×(FFT-N + FFT-Ntime)	Pₕ(N log₂N +Ntime log₂Ntime)	Ntime × Nfreq
	+ Ntime/2 × FFT-Nfreq	+ NtimeNfreq/2 log₂ Nfreq

decimated TFDs

kernel-type	no. of FFTs	load	memory (real-valued points)	grid
non-separable	N/2×FFT-N + L/2×FFT-J	N²/2 log₂ N + LJ/2 log₂ J	L × J	ρ[an,bn]
LI	V/2 × FFT-Ltime	VLtime/2 log₂ Ltime	Ltime × V	ρ[an,kᵢ]
LI	(V/2 + 1) × FFT-Ltime
DI	U/2 × FFT-Jfreq	UJfreq/2 log₂ Jfreq	U × Jfreq	ρ[nᵢ,bk]
DI (when U is odd)	(U/2 +1) × FFT-Jfreq
separable	Jfreq/2 × (FFT-N + FFT-Ltime)	JfreqN/2 log₂N	Ltime × Jfreq	ρ[an,bn]
	+ Ltime/2 × FFT-Jfreq	+ LtimeJfreq log₂ LtimeJfreq
separable (when L is odd)	Jfreq/2 × (FFT-N + FFT-Ltime)		Ltime × Jfreq	ρ[an,bn]
	+ (Ltime/2 +1) × FFT-Jfreq

notation

symbol	explanation
N	length of signal
U	length of sequence nᵢ {nᵢ for 1<=i<=U}, U<=N and 0<=nᵢ<=N-1
V	length of sequence kᵢ {kᵢ for 1<=i<=V}, V<=N and 0<=kᵢ<=N-1
J	N/b, b is decimation integer in frequency direction
L	N/a, a is decimation integer in time direction
Jfreq	Nfreq/b, b is decimation integer in frequency direction
Ltime	Ntime/a, a is decimation integer in time direction

kernel-type	load	memory (real-valued points)
non-separable	3N²/2 log₂ N	N²
LI	NNtime/2 log₂ Ntime	Ntime × N
DI	NNfreq/2 log₂ Nfreq	N × Nfreq
separable	Pₕ(N log₂N +Ntime log₂Ntime)	Ntime × Nfreq
	+ NtimeNfreq/2 log₂ Nfreq

kernel-type	load	memory (real-valued points)	grid
non-separable	N²/2 log₂ N + LJ/2 log₂ J	L × J	ρ[an,bn]
LI	VLtime/2 log₂ Ltime	Ltime × V	ρ[an,kᵢ]
DI	UJfreq/2 log₂ Jfreq	U × Jfreq	ρ[nᵢ,bk]
separable	JfreqN/2 log₂N	Ltime × Jfreq	ρ[an,bn]
	+ LtimeJfreq log₂ LtimeJfreq