Nopea Fourier-muunnos pallolla
No Thumbnail Available
URL
Journal Title
Journal ISSN
Volume Title
Helsinki University of Technology |
Diplomityö
Checking the digitized thesis and permission for publishing
Instructions for the author
Instructions for the author
Authors
Date
2004
Major/Subject
Matematiikka
Mcode
Mat-1
Degree programme
Language
fi
Pages
89
Series
Abstract
In this thesis we consider the problem of efficient computation of Fourier transform on the sphere S2 C R3 in the light of group theory. We present an algorithm published in [.JRKM03] and later refined in [JKR04]. On the sphere this is the first asymptotically fast algorithm, which is exact in exact arithmetic. Until past two decades there has been very little done about the computation of Fourier transforms associated with no abelian groups. It is highly interesting to compute efficiently the Fourier transforms of certain no abelian groups and their homogenous spaces. The algorithm presented in this thesis seems to be the first of this kind and it concerns the action of the no abelian rotation group SO(3) on its homogenous space S2. In the beginning we deal with the well-known case of the commutative group T = R/Z. In chapters 3 and 4 we introduce the Fourier transform of the group SO(3) using the machinery of representation theory. The set of continuous functions on the sphere can be embedded to the set of continuous functions on SO(3). Exploiting this property, we define the Fourier transform on §2 from the one on SO(3). In the last chapter we present the fast algorithm. We also consider some approximation results from [Vai96] and [Tur03]. The thesis does not contain new results. However, some of the proofs differ from the ones presented in references, e.g. the proofs of Theorems 4.13, 4.39 and 4.41. We have also made some small modifications to the main algorithm. The thesis is mostly self-contained.Tässä työssä tarkastellaan ryhmäteorian kannalta Fourier-muunnoksen tehokasta laskentaa pallolla S2 C R3. Esiteltävä algoritmi on julkaistu vuonna 2003 artikkelissa [JRKM03] ja sitä on paranneltu myöhemmin artikkelissa [JKR04]. Pallolla tämä on tiettävästi ensimmäinen tarkassa aritmetiikassa tarkka asymptoottisesti nopea algoritmi. Fourier-muunnosten laskentaa epäkommutatiivisilla ryhmillä on tutkittu vasta viimeisten parin vuosikymmenen aikana. Joillakin epäkommutatiivisilla ryhmillä ja niiden homogeenisilla avaruuksilla on nopealle Fourier-muunnosalgoritmille suuri kysyntä. Työssä esitettävä menetelmä on tiettävästi ensimmäinen tällainen algoritmi, ja se liittyy epäkommutatiivisen rotaatioryhmän SO(3) toimintaan homogeenisella avaruudella S2. Työn alussa käymme läpi tunnettua tilannetta kommutatiivisella ryhmällä T = R/Z ilman ryhmäteorian koneistoa. Luvuissa 3 ja 4 johdamme ensin esitysteorian avulla Fourier-muunnoksen ryhmälle SO(3). Pallon jatkuvat funktiot voidaan upottaa jatkuviksi funktioiksi ryhmälle SO(3). Tätä hyödyntämällä ryhmän SO(3) Fourier-muunnos määrittelee pallolle luonnollisen muunnoksen. Viimeisessä luvussa esittelemme nopean algoritmin. Käymme läpi myös eräitä approksimaatiotuloksia artikkeleista [Vai96] ja [Tur03]. Työ ei sisällä uusia tuloksia. Jotkin väitteet on todistettu toisin kuin viitteissä. Muun muassa lauseiden 4.13, 4.39 ja 4.41 todistuksia emme ole löytäneet tässä esitetyssä muodossa. Olemme tehneet myös joitain pieniä muutoksia käsiteltävään algoritmiin. Lukijan ei oleteta olevan perehtynyt ryhmäteoriaan.Description
Supervisor
Gripenberg, GustafThesis advisor
Turunen, VilleKeywords
Fourier transform, Fourier-muunnos, fast Fourier transform, nopea Fourier-muunnos, FFT, FFT, compact groups, kompaktit ryhmät, Lie groups, Lie-ryhmät, torus, torus, rotation group, rotaatioryhmä, sphere, pallo, spherical harmonics, palloharmoniset funktiot, sampling, otanta, Sobolev estimates, Sobolev-estimaatit, SU(2), SU(2), SO(3), SO(3)