Något som kallas den snabba Fourier -transformen körs på din mobiltelefon just nu. FFT, som det är känt, är en signalbehandlingsalgoritm som du använder mer än du inser. Det är, enligt titeln på en forskningsartikel, "en algoritm som hela familjen kan använda."

Alexander Stoytchev - docent i el- och datateknik vid Iowa State University som också är ansluten till universitetets Virtual Reality Applications Center, dess forskarprogram för Human Computer Interaction och institutionen för datavetenskap - säger att FFT -algoritmen och dess invers (känd som IFFT) är kärnan i signalbehandlingen.

Och, som sådan, "Det här är algoritmer som gjorde den digitala revolutionen möjlig, " han sa.

De är en del av att strömma musik, ringa ett mobiltelefon, surfa på internet eller ta en selfie.

FFT -algoritmen publicerades 1965. Fyra år senare, forskare utvecklade en mer mångsidig, generaliserad version kallad chirp z-transform (CZT). Men en liknande generalisering av den omvända FFT -algoritmen har gått olöst i 50 år.

Fram tills, det är, Stoytchev och Vladimir Sukhoy-en doktorand i Iowa-staten med huvudämne inom el- och datateknik, och mänsklig datorinteraktion-arbetade tillsammans för att hitta den efterlängtade algoritmen, kallad invers chirp z-transform (ICZT).

Liksom alla algoritmer, det är en steg-för-steg-process som löser ett problem. I detta fall, den mappar utmatningen från CZT -algoritmen tillbaka till dess ingång. De två algoritmerna är lite som en serie av två prisma - den första separerar våglängderna för vitt ljus i ett spektrum av färger och den andra vänder processen genom att kombinera spektrumet tillbaka till vitt ljus, Stoytchev förklarade.

Stoytchev och Sukhoy beskriver sin nya algoritm i en tidning som nyligen publicerades online av Vetenskapliga rapporter , en tidskrift för naturforskning. Deras papper visar att algoritmen matchar beräkningskomplexiteten eller hastigheten hos dess motsvarighet, att den kan användas med exponentiellt förfallna eller växande frekvenskomponenter (till skillnad från IFFT) och att den har testats för numerisk noggrannhet.

Stoytchev sa att han snubblat på idén att försöka formulera den saknade algoritmen medan han letade efter analogier för att hjälpa doktoranderna i hans "Computational Perception" -kurs förstå den snabba Fourier -transformen. Han läste mycket av signalbehandlingslitteraturen och kunde inte hitta något om det omvända till den relaterade kvittret z-transform.

"Jag blev nyfiken, "sa han." Är det för att de inte kunde förklara det, eller är det för att det inte finns? Det visade sig att det inte fanns. "

Och så bestämde han sig för att försöka hitta en snabb invers algoritm.

Sukhoy sa att den inversa algoritmen är ett svårare problem än originalet, framåt algoritm och så "vi behövde bättre precision och kraftfullare datorer för att attackera den." Han sa också att en nyckel var att se algoritmen inom den matematiska ramen för strukturerade matriser.

Även då, det fanns massor av datortestkörningar "för att visa att allt fungerade - vi var tvungna att övertyga oss själva om att detta kunde göras."

Det krävdes mod för att fortsätta attackera problemet, sa James Oliver, chef för Iowa State's Student Innovation Center och tidigare chef för universitetets Virtual Reality Applications Center. Stoytchev och Sukhoy erkänner Oliver i sin uppsats "för att ha skapat den forskningsmiljö där vi kunde driva detta arbete under de senaste tre åren."

Oliver sa att Stoytchev fick sitt stöd för en matematisk och beräkningsmässig utmaning som inte hade lösts på 50 år:"Alex har alltid imponerat på mig med sin passion och engagemang för att ta sig an stora forskningsutmaningar. Det finns alltid risker i forskning och det krävs mod att ägna år av hårt arbete åt ett grundläggande problem. Alex är en begåvad och orädd forskare. "