Discrete Convolutie Algoritme Snelheid
- Moderator
- Berichten: 9.974
Re: Discrete Convolutie Algoritme Snelheid
Meende ik mij ook te herinneren - wat niet zegt dat het intern niet aanvult tot machten van twee en die later weer stript.
- Moderator
- Berichten: 9.974
Re: Discrete Convolutie Algoritme Snelheid
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
Dat zou ik niet verwachten als FFT wordt gebruikt.
Ik ga nog wel eens in de numpy documentatie kijken. Maar vandaag niet meer
- Berichten: 1.605
Re: Discrete Convolutie Algoritme Snelheid
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!
Ben benieuwd naar de machten van 2. Morgen eens proberen op het werk onder het motto zelfstudie!
- Berichten: 1.605
Re: Discrete Convolutie Algoritme Snelheid
De formule klopt niet zou moeten zijn:OOOVincentOOO schreef: ↑zo 21 jun 2020, 20:48 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.
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!
- Berichten: 1.605
Re: Discrete Convolutie Algoritme Snelheid
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?
De Laplace van de convolutie van het tijdsignaal.
Context is duidelijk? Of woordspelletjes?
- Moderator
- Berichten: 9.974
Re: Discrete Convolutie Algoritme Snelheid
numpy convolve sommeert discreet, fftconvlove gebruikt FFT.
- Berichten: 1.605
Re: Discrete Convolutie Algoritme Snelheid
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.
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.
- Moderator
- Berichten: 9.974
Re: Discrete Convolutie Algoritme Snelheid
Als je twee rijen met lengte N wilt convolueren is de efficiëntie O (N2), 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.
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.
- Berichten: 1.605
Re: Discrete Convolutie Algoritme Snelheid
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
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
- Berichten: 1.605
Re: Discrete Convolutie Algoritme Snelheid
Geen "waarneembaar" tijdverschil wil ik eraan toevoegen. Door ik als mens waargenomen NIET gemeten dus!
- Berichten: 1.605
Re: Discrete Convolutie Algoritme Snelheid
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