Discrete Convolutie Algoritme Snelheid

[Xilvo]

Meende ik mij ook te herinneren - wat niet zegt dat het intern niet aanvult tot machten van twee en die later weer stript.

[Xilvo]

Wel opvallend dat het antwoord ook uit integers bestaat.
Dat zou ik niet verwachten als FFT wordt gebruikt.

Ik ga nog wel eens in de numpy documentatie kijken. Maar vandaag niet meer

[OOOVincentOOO]

Dankjewel voor de input. Mocht jij een uitleg voor dummies vinden omtrent die FFT methode houdt ik mij aanbevolen.

Ben benieuwd naar de machten van 2. Morgen eens proberen op het werk onder het motto zelfstudie!

[OOOVincentOOO]

Ik weet dat de convolutie samenhangt met Laplace/Fourier transformaties y(t)*x(t)=Y(s).X(s) (convolutie in tijd is product in frequentie domein). Leuke afleidingen hiervan heb ik gevonden op i-net.

De formule klopt niet zou moeten zijn:

L(y(t)*x(t))=Y(s).X(s)

De Laplace van het product van de convolutie van het tijdsignaal.

Maar de context zou dat toch duidelijk maken nietwaar?

Ik hoop dat de Wetenschapsforum politie mij niet achtervolgt!

[OOOVincentOOO]

Ik durf bijna niets te schrijven op WF was wederom te snel:

De Laplace van de convolutie van het tijdsignaal.

Context is duidelijk? Of woordspelletjes?

[Xilvo]

numpy convolve sommeert discreet, fftconvlove gebruikt FFT.

[OOOVincentOOO]

Dankjewel,

Python doet het veel netter om twee functies te definieren.

Het blijft dan nog een beetje contra intuitief: eerst twee arrays omzetten in f-domein, dan vermenigvuldigen en dan output weer omzetten in t-domein. Ik veronderstel dat het voor grotere datasets efficienter is, volgens mij had ik dat ergens in een flits gelezen. Weet alleen niet meer waar. Een van die te ingewikkelde documenten (voor mij) waarover ik het had.

Ik heb net nog even gechecked: de convolutie in Origin. Hij maakt geen extra elementen aan in output (geen machten van 2). Als de input arrays blanco cellen heeft betrekt die dat ook in de convolutie vandaar meer output elementen.

Echter cellen wat bij discreet convolutie (mijn eigen methode) 0 zijn hebben bij ingebouwde convolutie kleine waarden <10^-20. Dus waarschijnlijk convolutie a.d.v. FFT.

[Xilvo]

Als je twee rijen met lengte N wilt convolueren is de efficiëntie O (N²), ieder element van de ene rij moet je vermenigvuldigen met ieder element van de andere (en ook nog sommeren).

FFT gaat met O (N log(N)) en vermenigvuldigen met O (N).

Voor steeds grotere N gaat FFT => vermenigvuldigen => FFT uiteindelijk sneller dan direct convolueren.

[OOOVincentOOO]

Dankjewel, de formules komen bekend voor. Ergens geskimmed (bedoel: snel gelezen en niet ontouden!) en geskipped.

Dat verklaard ook waarom ik met mijn eigen discrete convolutie (reverse array en vermenigvuldigen dan sommeren) geen tijdverschil kan waarnemen met ingebouwde convolutie. De datasets zijn relatief klein in betreffende process model (<5000 elementen in arrays).

Dezelfde formules komen ook hier voor:
DFT (discreet Fourier): O(N²) (net zoals convolutie)
FFT (fast Fourier): O(N log(N))
https://en.wikipedia.org/wiki/Fast_Fourier_transform

[OOOVincentOOO]

Geen "waarneembaar" tijdverschil wil ik eraan toevoegen. Door ik als mens waargenomen NIET gemeten dus!

[OOOVincentOOO]

FFT gaat met O (N log(N)) en vermenigvuldigen met O (N).

Ik vond deze link nog met uitleg FFT. Nog niet bestudeerd maar na vlot doorgelezen te hebben staat het principe ervan beschreven.

https://towardsdatascience.com/fast-fou ... 7926e591cb