Discrete Convolutie Algoritme Snelheid

Moderators: dirkwb, Xilvo

Gebruikersavatar
Berichten: 1.605

Discrete Convolutie Algoritme Snelheid

Geregeld maak ik gebruik van convolutie hiermee heb ik geregeld process simulaties gemaakt. Hat mooie is dat een variabele gesampelde input geconvuleerd kan worden met de impulse responce van een process. De verkregen output is dan als functie van de input, men is dan niet gelimiteerd tot alleen stap responces van de input bijvoorbeeld.

\((f * g)(t) \triangleq\ \int_{-\infty}^\infty f(\tau) g(t - \tau) \, d\tau\)

Discreet:

\((f * g)[n] = \sum_{m=-\infty}^\infty f[m] g[n - m]\)

(ik weet niet wat misgaat maar formules worden in voorbeeld goed weergegeven in draadje niet? Het zijn gewoon de bekende convolutie formules)

In verschillende programmeer talen heeft men ingebouwde snelle convolutie algoritmes. Voor een van mijn process simulaties integreerde ik een PID regelaar met varieerende input. Hierdoor kon ik niet de ingebouwde convolutie algoritmes gebruiken en moest het manueel uitrekenen met twee for loops, zoals:

Code: Selecteer alles

//Input range dd and ee and count items in arrays
int dd=count(wcol(2),1);
int ee=count(wcol(3),1);

//Loop all convolutions items
for (int hh = 1 ;hh <= (dd+ee-1); hh++)
{
	       //Set output element to zero
	       YY(hh)=0:
	       
	       for (int ii = 1 ;ii <= dd; ii++)
               {
                              if (hh-ii+1>0)
                              {
                              		     //Convolution element hh
                                             YY[hh]=YY[hh]+dd[hh]*ee[hh-ii+1];
                              }
               }
Deze methode met twee for loops is erg traag. Ik ben nogal een intuitief met wiskunde en programmeren. Ik had een versnelde berekening convolutie gevonden met een for loop en gebruik makende van array berekeningen. Het resultaat naar enig trial en error is de code onderstaand. Ik neem steeds een range van de input arrays en reverse de volgorde van een van de arrays. Hierna vermenigvuldig ik de elementen van de arrays en bepaal de som. Dit is dan de output YY van element n YY(n).

Tot mijn verbazing is deze methode snel en vergelijkbaar als de ingebouwde convolutie algoritmes.
Convolution Picture.jpg

Code: Selecteer alles

//Input range and set to blanco
range YY=Wcol(4);
yy="";

//Input range dd and ee and count items in arrays
int dd=count(wcol(2),1);
int ee=count(wcol(3),1);

//Loop all convolutions items
for (int hh = 1 ;hh <= (dd+ee-1); hh++)
{
               if (dd>=ee)
               {
                              if (hh<=dd)
                              {
                              		     //input range pp and reverse element order
                                             dataset pp=Wcol(2)[1:hh];
                                             pp.reverse();
                                             
                                             //input range uu
                                             dataset uu=Wcol(3)[1:hh];
                                             
                                             //Multiply elements and determine sum.
                                             yy[hh]=total(uu*pp);
                              }
                             else
                              {
                                             dataset pp=WCol(2)[hh-dd+1:dd];
                                             pp.reverse();
                                             dataset uu=WCol(3)[hh-dd+1:dd];
                                             yy[hh]=total(uu*pp);
                              }
               }
		
		if (dd>ee)
		{
				.....
		}

}
Zijn er nog snellere methodes om manueel de convolutie te berekenen? Is dit hoe een convolutie berekening werkt met ingebouwde algoritmes of maken deze gebruik van FFT? Graag een simpel antwoord, ik kan zelf genoeg informatie vinden op internet. Gewoon een vraag gericht aan wiskunde en programmeer ervaren mensen.

Gebruikersavatar
Berichten: 1.605

Re: Discrete Convolutie Algoritme Snelheid

Nu ik hetzelf netjes opschrijf besef ik dat het de gewone definitie is van de convolutie! Werken met arrays in programmeertaal is gewoon efficienter reverse nemen en vermenigvuldigen! Werken met arrays voorkomt twee for loops in elkaar.

Rest nog de vraag of er snellere algoritmes zijn. Kan genoeg vinden op internet (te veel informatie).
Convolution Picture.jpg
Laatst gewijzigd door OOOVincentOOO op zo 21 jun 2020, 20:21, 1 keer totaal gewijzigd.

Gebruikersavatar
Moderator
Berichten: 9.940

Re: Discrete Convolutie Algoritme Snelheid

Welke programmeertaal is dit?

Gebruikersavatar
Berichten: 1.605

Re: Discrete Convolutie Algoritme Snelheid

Ohh, dit voorbeeld is Labtalk van Origin. Ik programmeer een beetje in verschillende talen maar ik noem mijzelf noob/novice.

Het voorbeeld van twee for loops had ik initieel van (matlab):

https://www.mathworks.com/matlabcentral ... onvolution

Maar hier was ik niet tevreden mee. Erg langzaam.
Laatst gewijzigd door OOOVincentOOO op zo 21 jun 2020, 20:28, 1 keer totaal gewijzigd.

Gebruikersavatar
Moderator
Berichten: 9.940

Re: Discrete Convolutie Algoritme Snelheid

Is het een geïnterpreteerde taal?

Gebruikersavatar
Moderator
Berichten: 9.940

Re: Discrete Convolutie Algoritme Snelheid

Even opgezocht, het lijkt me een geïnterpreteerde taal. Die zijn langzamer dan gecompileerde. En dan is gebruik van ingebouwde functies (wel gecompileerd) vele malen sneller.

Gebruikersavatar
Berichten: 1.605

Re: Discrete Convolutie Algoritme Snelheid

Xilvo schreef: zo 21 jun 2020, 20:25 Is het een geïnterpreteerde taal?
Ik moest even opzoeken wat dat geïnterpreteerde taal is. Ik hoef in iedergeval geen compiling te doen het is een beetje vergelijkbaar als programmeren in matlab.

Gebruikersavatar
Berichten: 1.605

Re: Discrete Convolutie Algoritme Snelheid

Xilvo schreef: zo 21 jun 2020, 20:30 Even opgezocht, het lijkt me een geïnterpreteerde taal. Die zijn langzamer dan gecompileerde. En dan is gebruik van ingebouwde functies (wel gecompileerd) vele malen sneller.
Inderdaad ik probeer altijd ingebouwde routines/functies te vinden en deze creatief toe te passen.

Gebruikersavatar
Moderator
Berichten: 9.940

Re: Discrete Convolutie Algoritme Snelheid

OOOVincentOOO schreef: zo 21 jun 2020, 20:32 het is een beetje vergelijkbaar als programmeren in matlab.
Klopt, dat is ook geïnterpreteerd, daarom wordt je er daar ook vaak op gewezen dat het veel effizienter is om ingebouwde functies te gebruiken (waarmee je bijvoorbeeld twee array's in één keer per element kunt optellen of vermenigvuldigen).

Je kunt het zelf ook programmeren, met loops, maar dat is veel trager omdat dat niet gecompileerd wordt, terwijl er feitelijk hetzelfde gebeurt.

In een gecompileerde taal als C zal het weinig schelen in snelheid.

Gebruikersavatar
Berichten: 1.605

Re: Discrete Convolutie Algoritme Snelheid

Ahh, dat wist ik niet.

Is dat omdat C dan "dichter" bij assembly code zit? Lang geleden nog een beetje gespeeld met Z80 assembly. Hier is veel geschuif elementen in geheugen (in mijn eigen taal is eigenlijk ook een array ;) ).

Heb jij enig idee of de ingebouwde convolutie in programmeer talen bepaald word met FFT?

Als ik zoek op internet word ik ondergekt :o st met de meest ingewikkelde documenten waar ik het overzicht verlies.

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.

Eigenlijk probeer een meer intuitief (praktisch) voorbeeld te vinden hoe convolutie alwel dan niet sneller berekend kan worden met mogelijk FFT.

Gebruikersavatar
Moderator
Berichten: 9.940

Re: Discrete Convolutie Algoritme Snelheid

OOOVincentOOO schreef: zo 21 jun 2020, 20:48 Is dat omdat C dan "dichter" bij assembly code zit? Lang geleden nog een beetje gespeeld met Z80 assembly. Hier is veel geschuif element in geheugen.
Niet per se. Maar het wordt vertaald (gecompileerd) naar machinetaal (assembler is machinetaal, maar dan net een beetje beter leesbaar dan enen en nullen) voordat je het draait. Heb ik lang geleden ook gedaan, op de Z80.
Een geïnterpreteerde taal wordt feitelijk vertaald tijdens het draaien, alle code in een lus bijvoorbeeld opnieuw voor elke keer dat die lus wordt uitgevoerd.
OOOVincentOOO schreef: zo 21 jun 2020, 20:48 Heb jij enig idee of de convolutie in programmeer talen bepaald word met FFT?
Weet ik niet zeker maar ik vermoed van wel.
OOOVincentOOO schreef: zo 21 jun 2020, 20:48 Eigenlijk probeer een meer intuitief (praktisch) voorbeeld te vinden hoe convolutie alwel dan niet sneller berekend kan worden met mogelijk FFT.
Convolutie in het ene domein is vermenigvuldigen in het andere.
Dus als je werkt in het tijddomein (waardes als functie van de tijd) en je wilt convolueren, dan moet je die waardes en de convolutie-functie transformeren naar het frequentiedomein, daar vermenigvuldigen (wat makkelijk en efficient is) en dan weer terugtransformeren.

Gebruikersavatar
Berichten: 1.605

Re: Discrete Convolutie Algoritme Snelheid

Dus jij denkt dat de input's in f-domein worden omgezet volgens de meest efficiente methode bijvoorbeeld FFT? En dan standaard vermenigdvuldigd?

Dat zou kunnen, ik merkte wel op dat het handmatig berekenen convolutie (met 2 for loops of array methode) het juiste aantal elementen in array van de output verkregen word. De ingebouwde convolutie tovert extra elementen in output array (met zeer kleine waarden <10^-20 enzo).

Gebruikersavatar
Moderator
Berichten: 9.940

Re: Discrete Convolutie Algoritme Snelheid

OOOVincentOOO schreef: zo 21 jun 2020, 21:07 De ingebouwde convolutie tovert extra elementen in output array (met zeer kleine waarden <10^-20 enzo).
Totdat de lengte een macht van 2 is, 1024, 2048, etc? Dan wordt zeker FFT toegepast.

Gebruikersavatar
Berichten: 1.605

Re: Discrete Convolutie Algoritme Snelheid

Ohh, jja machten van 2, die is goed dat moet ik een keer nagaan. Op het werk dan (geen origin thuis). Of misschien thuis proberen met Python en numpy convolution.

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.

In een van mijn modellen gebruik ik meer dan 100.000 input elementen. Maar hier maak ik gebruik van ingebouwde convolutie algoritme. Werkt prima

Gebruikersavatar
Berichten: 1.605

Re: Discrete Convolutie Algoritme Snelheid

Python schijnt het netjes te doen (juiste aantal elementen in output):
numpy convolution.png

Reageer