中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 并行计算实验室  > 学位论文
题名:
平行六边形及三角形区域非均匀节点快速法傅立叶变换
作者: 李明亮
答辩日期: 2008-06-02
导师: 孙家昶 ; 李会元
专业: 计算机软件与理论
授予单位: 中国科学院软件研究所
授予地点: 软件研究所
学位: 硕士
关键词: 快速傅立叶变换 ; 广义三角变换 ; 非均匀节点 ; 非规则区域 ; 平行六边形区域 ; 三角形区域
其他题名: Non-equispaced Fast Fourier Transform on Hexagon and Triangle domains
部门归属: 并行计算实验室
摘要: 快速傅立叶变换(FFT)是公认的二十世纪最重要的十个算法之一。它在信号处理,多媒体压缩,模式识别,计算化学等众多领域有着广泛的应用。众所周知,傅立叶变换的研究是从一维开始,并通过张量积的方法推广到二维及更高维。其适用区域为规则方形区域,计算节点为均匀分布,因而其适用范围受到诸多限制。为拓宽傅立叶变换及其离散变换的应用范围,需要在非规则区域及非均匀节点上建立非张量积形式的傅立叶变换理论和快速算法。 孙家昶等人建立了平行六边形上的傅立叶变换和级数理论,提出了平行六边形区域上均匀节点离散傅立叶变换,紧接着又设计了相应的快速傅立叶变换的串、并行算法(FFTH)。目前,这种非张量积的傅立叶变换理论和算法已经完全推广到三维的平行十二面体,四面体以及任意的d维d+1向的超单纯形、单纯形区域。杨志杰等在三角形区域建立了广义三角变换,并应用于可伸缩视频压缩中。 Stefan Kunis 和Daniel Potts等人研究了规则张量积区域上的非均匀节点的快速傅立叶变换。通过窗口函数近似计算的方法实现了非均匀节点快速傅立叶变换算法,开发出了相应的数学软件包NFFT。以此为基础,他们又进一步研究了几类特殊的快速算法,他们这些算法在核磁共振成像(MRI)等领域得到了应用。 本文立足于建立非规则区域上的非均匀节点快速傅立叶变换算法,主要研究一类二维非规则区域上的非均匀节点快速傅立叶变换算法。本文首先介绍了三向齐次坐标系,然后引入晶格概念,设计了平行六边形区域上的非均匀节点快速傅立叶变换。以此为基础,进一步考虑三角形区域上的非均匀节点快速傅立叶变换,从三向齐次坐标出发,以平行六边形快速傅立叶变换为基础,重新阐释了三角形上的广义正余弦变换算法。进一步,本文设计了非均匀节点广义快速正余弦变换算法,算法复杂度由$\mathbf{O}(N^4)$ 降为$\mathbf{O}(N^2log N)$。 数值实验证明本文算法是稳定、高效的。
英文摘要: Fast Fourier Transform (FFT) is one of the top ten algorithms in 20th century, and plays a key role in computing and information sciences. It is well known that FFT was originally studied in one dimension and then extended into two and even higher dimensions by the method of tensor product. Rigorously, the tensor product approach is still staying in the one dimensional level. and its result can only be applicable for regular domains and equispaced nodes. This fact hinders the classical FFT from further applying to irregular domains in high dimensions. To match the increasing needs of non-classic FFTs, we establish the non-equispaced fast Fourier transforms(NFFT) on a class of irregular domains in 2-dimensions. Originally, Sun studied the Fourier series on parallel hexagon, and then proposed the discrete Fourier transform on parallel hexagon. Later on, Sun designed the hexagonal fast Fourier transform and developed the corresponding library(FFTH). Since the triangle is the fundamental domain inside the parallel hexagon, under certain reflection symmetry group, the generalized sine and cosine are actually invariant(symmetric) and anti-invariant(asymmetric) projections of the Fourier basis on the parallel hexagon. In such a way, Yang and Sun further designed the gereralized sine and cosine transform on the triangle, and applied it in scalable video coding. More recently, the 2-dimensional results have been extended to 3-dimension for parallel dodecahedrons and tetrahedrons. On the other hand, Stefan Kunis and Daniel Potts proposed the non-equispaced Fourier transform on box domains, such as rectangles and cubes. They designed the fast alogrithm for an efficient and approximate evaluation of the NDFTs, which shares the same order of computational complexity as the classic FFT. They also developed an open source library which are now been widely used in (magnetic resonance imaging)MRI and so on. This paper concentrates on the study of non-equispaced fast Fourier transforms on 2-dimensional irregular domains such as parallel hexagon and triangle in an attempt to enhance the adaptivity of our hexagonal FFTs. The main idea is to combine our FFTH with non-quispaced FFT. For this purpose, We first introduce the three directional homogeneous coordinates and the concept of lattice. Then we establish the non-equispaced FFT on the parallel hexagon. Further, We study the non-equispaced fast cosine and sine transforms, via reflection(symmetry). Our fast algorithms reduce the computational complexity from $\mathbf{O}(N^4)$ to $\mathbf{O}(N^2log N)$. Numerical results demonstrate that these algorithms are accurate efficient and stable.
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/6410
Appears in Collections:并行计算实验室 _学位论文

Files in This Item:
File Name/ File Size Content Type Version Access License
10001_200528015029008李明亮_paper.pdf(979KB)----限制开放-- 联系获取全文

Recommended Citation:
李明亮. 平行六边形及三角形区域非均匀节点快速法傅立叶变换[D]. 软件研究所. 中国科学院软件研究所. 2008-06-02.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[李明亮]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[李明亮]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace