|
Fast Fourier Transform at Nonequispaced Nodes and Applications
Fenn, Markus
|
URL:
|
http://ub-madoc.bib.uni-mannheim.de/1157
|
|
URN:
|
urn:nbn:de:bsz:180-madoc-11577
|
|
Dokumenttyp:
|
Dissertation
|
|
Erscheinungsjahr:
|
2005
|
|
Titel einer Zeitschrift oder einer Reihe:
|
None
|
|
Verlag:
|
Universität Mannheim
|
|
Gutachter:
|
Steidl, Gabriele
|
|
Datum der mündl. Prüfung:
|
8 Dezember 2005
|
|
Sprache der Veröffentlichung:
|
Englisch
|
|
Einrichtung:
|
Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Angewandte Mathematik u. Informatik (Steidl 1996-2011)
|
|
Fachgebiet:
|
004 Informatik
|
|
Fachklassifikation:
|
MSC:
65T50 42A10 42B05 65F50 ,
|
|
Normierte Schlagwörter (SWD):
|
Schnelle Fourier-Transformation
|
|
Freie Schlagwörter (Deutsch):
|
unstrukturierte Knotenmengen , schnelle trigonometrische Transformationen , schnelle Matrix-Vektor Multiplikation , Ridgelets
|
|
Freie Schlagwörter (Englisch):
|
nonequispaced nodes , fast trigonometric transforms , fast matrix-vector multiplication , ridgelets
|
|
Abstract:
|
The direct computation of the discrete Fourier transform at arbitrary nodes requires O(NM) arithmetical operations, too much for practical purposes. For equally spaced nodes the computation can be done by the well known fast Fourier transform (FFT) in only O(N log N) arithmetical operations. Recently, the fast Fourier transform for nonequispaced nodes (NFFT) was developed for the fast approximative computation of the above sums in only O(N log N + M log 1/e), where e denotes the required accuracy. The principal topics of this thesis are generalizations and applications of the NFFT. This includes the following subjects: - Algorithms for the fast approximative computation of the discrete cosine and sine transform at nonequispaced nodes are developed by applying fast trigonometric transforms instead of FFTs. - An algorithm for the fast Fourier transform on hyperbolic cross points with nonequispaced spatial nodes in 2 and 3 dimensions based on the NFFT and an appropriate partitioning of the hyperbolic cross is proposed. - A unified linear algebraic approach to recent methods for the fast computation of matrix-vector-products with special dense matrices, namely the fast multipole method, fast mosaic-skeleton approximation and H-matrix arithmetic, is given. Moreover, the NFFT-based summation algorithm by Potts and Steidl is further developed and simplified by using algebraic polynomials instead of trigonometric polynomials and the error estimates are improved. - A new algorithm for the characterization of engineering surface topographies with line singularities is proposed. It is based on hard thresholding complex ridgelet coefficients combined with total variation minimization. The discrete ridgelet transform is designed by first using a discrete Radon transform based on the NFFT and then applying a dual-tree complex wavelet transform. - A new robust local scattered data approximation method is introduced. It is an advancement of the moving least squares approximation (MLS) and generalizes an approach of van den Boomgard and van de Weijer to scattered data. In particular, the new method is space and data adaptive.
|
|
Übersetzter Titel:
|
Schnelle Fouriertransformation auf unstrukturierten Knotenmengen und Anwendungen
(Deutsch)
|
|
Übersetzung des Abstracts:
|
Die direkte Berechnung der diskreten Fourier-Transformation an beliebigen Knoten erfordert O(NM) arithmetische Operationen. Für äquidistante Knoten kann die Berechnung mittels schneller Fouriertransformation (FFT) in nur O(N log N) arithmetischen Operationen durchgeführt werden. Auf unstrukturierten Knotenmengen hat sich inzwischen ein Algorithmus (NFFT) zur effizienten näherungsweisen Berechnung der diskreten Fourier-Transformation in nur O( N log N + M log 1/e ) etabliert, wobei e die gewünschte Genauigkeit bezeichnet. Das Hauptaugenmerk dieser Dissertation liegt auf Verallgemeinerungen und Anwendungen der NFFT. Im Einzelnen beinhaltet dies die folgenden Ergebnisse: - Es werden schnelle Algorithmen für die näherungsweise Berechnung der diskreten Kosinus- und Sinustransformation auf unstrukturierten Knotenmengen entwickelt, die statt der FFT schnelle trigonometrische Transformationen verwenden. - Ein Algorithmus für die schnelle Fouriertransformation auf hyperbolischen Kreuzen in 2 und 3 Dimensionen mit unstrukturierten Knotenmengen im Zeitbereich wird aufbauend auf der NFFT und einer geeigneten Unterteilung der hyperbolischen Kreuze konstruiert. - Ein einheitlicher algebraischer Zugang zu aktuellen Methoden für die schnelle Berechnung von Matrix-Vektor-Produkten mit speziellen vollbesetzten Matrizen, und zwar die "fast multipole method" (FMM), die "fast mosaic-skeleton"-Approximation und die H-Matrix-Arithmetik, wird gegeben. Desweiteren wird der NFFT-basierte Summationsalgorithmus von Potts und Steidl durch die Verwendung algebraischer an Stelle von trigonometrischen Polynomen vereinfacht, und die Fehlerabschätzungen werden verbessert. - Ein neuer Algorithmus zur Beschreibung der Beschaffenheit technischer Oberflächen mit Liniensingularitäten wird vorgestellt. Er basiert auf einer Kopplung von "hard thresholding" von Ridgeletkoeffizienten mit Verfahren zur Minimierung der totalen Variation. Die diskrete Ridgelettransformation erhält man durch Verwendung einer auf der NFFT basierenden diskreten Radontransformation und anschließender Anwendung einer speziellen komplexen Wavelettransformation, der "dual-tree complex wavelet transform". - Eine neue robuste lokale Approximationsmethode für gestreute Daten wird eingeführt. Sie stellt eine Weiterentwicklung der sogenannten "moving least squares" Approximation (MLS) dar und verallgemeinert einen Ansatz von van den Boomgaard und van de Weijer auf nichtäquidistante Knoten. Insbesondere ist der neue Zugang raum- und datenadaptiv.
(Deutsch)
|
|
Zusätzliche Informationen:
|
|
 | Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt. |
 Suche Autoren in
Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail
Actions (login required)
 |
Eintrag anzeigen |
|
|
![[img]](https://madoc.bib.uni-mannheim.de/style/images/fileicons/application_pdf.png)