计算数学 2004, 26(3) 351-366 DOI:     ISSN: 0254-7791 CN: 11-2125/O1

本期目录 | 下期目录 | 过刊浏览 | 高级检索                                                            [打印本页]   [关闭]
论文
扩展功能
本文信息
Supporting info
PDF(543KB)
[HTML全文](0KB)
参考文献[PDF]
参考文献
服务与反馈
把本文推荐给朋友
加入我的书架
加入引用管理器
引用本文
Email Alert
文章反馈
浏览反馈信息
本文关键词相关文章
本文作者相关文章
PubMed

平行六边形区域上的快速离散傅立叶变换

孙家昶,姚继锋

中科院软件所并行计算实验室,中科院软件所并行计算实验室 北京,100080 ,北京,100080

摘要

1.引言 快速傅立叶变换(FFT)是公认的二十世纪最重要的十个算法之一[1],它在信号处理、多媒体压缩、模式识别、计算化学等众多领域有着广泛的应用[2].考虑如下形式的离散傅立叶变换(DFT):这里叫ωN=e2π/Ni,N=2m.1965年提出的Cooley—Tukey算法[3]通过divide—and—conquer的策略将上式分成m步逐次计算,最后总的浮点运算次数由8N2次降为5N log2 N-6N

关键词

A FAST ALGORITHM OF DISCRETE GENERALIZED FOURIER TRANSFORMS ON HEXAGON DOMAINS

Sun Jiachang Yao Jifeng (Parallel Computing Division, Institute of Software, Academica Sinica, Beijing, 100080)

Abstract:

In this paper, we propose a fast algorithm for computing the DGFT (Discrete Generalized Fourier Transforms) on hexagon domains [6], based on the geometric properties of the domain. Our fast algorithm (FDGFT) reduces the computation complexity of DGFT from O(N4) to O(N2logN). In particulary, for N = 2P23P34P45P56P6, the floating point computation working amount equals to (17/2P-2 + 16p3 + 135/8P4 + 2424/25p5 + 201/2p6)3N2. Numerical examples are given to access our analysis.

Keywords:
收稿日期  修回日期  网络版发布日期 2004-03-14 00:00:00.0 
DOI:
基金项目:

通讯作者:
作者简介:

本刊中的类似文章

Copyright 2008 by 计算数学