Convoluția - bibliotecă de algoritmi

Prin convoluția discretă a funcțiilor f (t) și g (t). definită pe setul de întregi Z. Se numește următoarea operație:

O convoluție discretă circulară a unei funcții neperiodice f cu funcție periodică g este următoarea operație:

Convoluția discretă are multe aplicații diferite - multiplicarea polinomilor, aritmetica acurateței arbitrare, procesarea semnalelor. Convoluția circulară nu este comutativă - una dintre funcții este un semnal periodic, iar celălalt este un răspuns neperiodic la semnal. Operațiile convoluției obișnuite au adesea o semnificație diferită, însă operația însăși este comutativă - rezultatul convoluției nu se schimbă din permutarea funcțiilor f și g.

Prezentarea datelor

Domeniul de definire a funcțiilor f și g este întregul set de numere întregi, dar în practică avem de-a face cu date de lungime limitată. Este mai convenabil atunci când funcțiile f și g sunt diferite de zero numai pentru t negativ. Subrutinele computaționale ale pachetului ALGLIB rezolvă această problemă particulară - convoluția a două funcții care sunt diferite de zero numai pentru valorile non-negative ale argumentului. Acest lucru ne permite să folosim o corespondență simplă între argumentul funcției și indicele matricei în care sunt stocate valorile sale: f (t = i) = f_array [i], 0 ≤ i

Dacă funcțiile f și g sunt diferite de zero și valori pozitive și negative ale argumentului, este posibil să se utilizeze faptul că deplasarea unuia dintre convolutiile argumente rezultat este de asemenea supusă la forfecare în aceeași direcție cu aceeași sumă (o deplasare a două argumente - pentru suma compensărilor individuale). Doar glisați f și g la dreapta până când toate valoarea non-zero nu va apărea pe de o parte de la zero, numesc o subrutină pentru convoluției, și apoi mutați rezultatul înapoi.

Implementarea unei convoluții în ALGLIB

Aici, pentru simplitate, presupunem că N ≥ M. Al doilea operand este mai lung decât primul, deși viteza algoritmului nu depinde de ordinea în care sunt transferați operanzii. Este cunoscut faptul că convoluția poate fi calculată folosind o transformare rapidă Fourier în timp O (N · log (N)). În același timp, utilizarea directă a transformării Fourier nu este întotdeauna soluția optimă - în cazul în care unul dintre operanzi este mai scurt decât celălalt, este posibil să se accelereze calculele considerabil folosind alți algoritmi. În funcție de lungimea operanților, pachetul ALGLIB poate utiliza următorii algoritmi:

• Dacă M este mic - un algoritm cu complexitate O (M · N)
• Dacă M este semnificativ mai mic decât N., dar este prea mare pentru a utiliza primul algoritm, se folosește un algoritm de suprapunere-adăugare cu complexitate O (N · log (M)).
• Dacă două algoritmul anterior nu dă câștig în viteză - este utilizat pe baza algoritmului FFT cu complexitate O (N · log (N)) (FFT efectuat operanzilor componentwise produs inversului frecvență FFT).

Pentru a calcula convoluția, se folosește algoritmul FFT inclus în ALGLIB. Rutina de convoluție selectează automat lungimea operanzilor, opțional adăugându-le la zerouri pentru a obține performanța optimă (viteza FFT depinde puternic de descompunerea lungimii operanților în factorii prime). Astfel, utilizatorii ALGLIB nu trebuie să vă faceți griji cu privire la lungimea optimă a operanzilor.

Intrări manual

Trimiteți-le prietenilor: