数学建模及其应用杂志 数值计算与计算机应用.doc

数学建模及其应用杂志 数值计算与计算机应用 导读：就爱阅读网友为您分享以下“数值计算与计算机应用”资讯，希望对您有所帮助，感谢您对92的支持! ２００９年３月 Ｍａｒ．，２００９数值计算与计算机应用ＪｏｕｒｎａｌＯｎＮｕｍｅｒｉｃａｌＭｅｔｈｏｄｓａｎｄＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓ第３０卷第１期Ｖ０１．３０，Ｎｏ．１ 平行六边形区域非均匀节点 快速傅立叶变换术１） 李明亮 （中国科学院软件研究所并行计算实验室 中国科学院研究生院，北京１００１９０） 李会元孙家昶 （中国科学院软件研究所并行计算实验室，北京１００１９０） 摘要 本文研究平行六边形区域上的非均匀节点离散傅立叶变换的快速算法及其实现．首先在晶格（Ｌａｔｔｉｃｅ）的框架下建立了平行六边形区域上的非均匀节点离散傅立叶变换（ＮＤＦＴＨ）．在此基础上设计了平行六边形区域上的非均匀节点快速傅立叶变换（ＮＦＦＴＨ）算法．其核心思想是以局部性态良好的窗口函数为基底，以平行六边形区域上均匀节点快速傅立叶变换（ＦＦＴＨ）为时空域和频域转换工具，通过在时窄域和频域上截取其展开级数的少量几项来快速近似计算，最终降低其计算复杂度．数值计算结果表明，本文算法是合理、稳定，高效的． 关键词：非均匀节点快速傅立叶变换；平行六边形；快速算法及实现；数值实验 ＭＲ（２０００）主题分类：６５Ｔ５０，４２８０５ ＮｏＮＥＱＵＩＳＰＡＣＥＤＦＡＳＴＦｏＵＲＩＥＲＴＲＡＮＳＦｏＲＭｏＮ ＰＡＲＡＬＬＥＬＨＥＸＡＧｏＮ ＬｉＭｉｎｇｌｉａｎｇ ＬＬａｂｏｒａｔｏｒｙｏ｛ＰａｒａｌｌｅｌＣｏｍｐｕｔｉｎｇ，ＩｎｓｔｉｔｕｔｅｏｌＳｏｆｔｗａｒｅ，Ｃｈｉｎｅｓｅ ＧｒａｄｕａｔｅＵｎｉｖｅｒｓｉｔｙＡｃａｄｅｍｙｏｌＳｃｉｅｎｃｅｓ；ｏｆＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，Ｂｅ彬ｎｇ１００１９以Ｃｈｉｎａ） ＬｉＨｕｉｙｕａｎＳｕｎＪｉａｃｈａｎｇ （Ｌａｂｏｒａｔｏｒｙ０，ＰａｒａｌｌｅｌＣｏｍｐｕｔｉｎｇ，ＩｎｓｔｉｔｕｔｅｏｆＳｏｌｔｗａｒｅ，ＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ １００１９０，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ Ｉｎｔｈｉｓｐａｐｅｒ，ｔｈｅｎｏｎｅｑｕｉｓｐａｃｅｄｄｉｓｃｒｅｔｅＦｏｕｒｉｅｒｔｒａｎｓｆｏｒｍｏｎ ｉｓｅｓｔａｂｌｉｓｈｅｄｉｎｔｈｅｆｒａｍｅｏｆＬａｔｔｉｃｅ．ｔｈｅｎａａｐａｒａｌｌｅｌｈｅｘａｇｏｎ（ＮＤＦＴＨ） ｔｏｌｌｓｅｆａｓｔａｌｇｏｒｉｔｈｍｎａｍｅｄＮＦＦＴＨｉｓｄｅｖｉｓｅｄａｎｄｉｔｓｓｔａｎｄａｒｄｉｍｐｌｅｍｅｎｔａｔｉｏｎｉｓｓｔｕｄｉｅｄｉｎｄｅｔａｉｌｆｏｒｅｖａｌｕａｔｉｎｇＮＤＦＴＨ．Ｔｈｅｍａｉｎｉｄｅａｉｓ ＦＦＴＨｓａｎｄ ｑｕｅｎｃｙａｗｉｎｄｏｗｆｕｎｃｔｉｏｎｗｈｉｃｈｉｓｗｅｌｌｌｏｃａｌｉｚｅｄｉｎｔｈｅｓｐａｔｉａｌｄｏｍａｉｎａｎｄｉｎｔｈｅｆｒｅ－ｄｏｍａｉｎ．ＮｕｍｅｒｉｃａｌｒｅｓｕｌｔｓｄｅｍｏｎｓｔｒａｔｅｔｈｅＮＦＦＴＨｉｓａｃｃｕｒａｔｅ，ｓｔａｂｌｅ，ａｎｄｈｉｇｈｌｙｅ儡ｃｉｅｎｔ． ＋２００７年１２月１０日收到．１）本研究课题受国家自然科学基金（ＮｏＮｏＮｏ资助万方数据 ｋＵｋ １期李明亮等：平行六边形区域非均匀节点５９ Ｋｅｙｗｏｒｄｓ：ｆａｓｔａｌｇｏｒｉｔｈｍ；ｎｏｎｅｑｕｉｓｐａｃｅｄｄｉｓｃｒｅｔｅＦｏｕｒｉｅｒｔｒａｎｓｆｏｒｍ；ｐａｒａｌｌｅｌｈｅｘａｇｏｎ； ｉｍｐｌｅｍｅｎｔａｔｉｏｎ；ｎｕｍｅｒｉｃａｌｒｅｓｕｌｔｓ ２０００ＭａｔｈｅｍａｔｉｃｓＳｕｂｊｅｃｔＣｌａｓｓｉｆｉｃａｔｉｏｎ：６５Ｔ５０，４２８０５ １．引言 快速傅立叶变换（ＦＦＴ）是公认的二十世纪最重要的十个算法之一【１１．它在信号处理，多媒体压缩，模式识别，计算化学等众多领域有着广泛的应用．众所周知，傅立叶变换的研究是从一维开始，并通过张量积的方法推广到二维及更高维．其适用区域为规则方形区域，计算节点为均匀分布，因而其适用范围也受到诸多限制．为拓宽傅立叶变换及其离散变换的应用范围，我们需要在非规则区域及非均匀节点上建立非张量积形式的傅立叶变换理论和快速算法． 借助齐次坐标，孙家昶研究员首先构造了二维三向周期的复指数函数系， ｅ孕ｊ一， 它构成平行六边形区域ｊ：＝｛（后１，ｋ２，ｋ３）ｚ３：ｋｌ＋ｋ２＋ｋ３＝ｏ）．（１．１） Ｑ：＝｛（ｔｌ，ｔ２，ｔ３）Ｒ５：－１≤ｔ１，ｔ２，一ｔ３＜１；ｔｌ＋ｔ２＋ｔ３＝０｝（１－２） 上的一组标准正交基．籍此，孙家昶等人建立了平行六边形上的傅立叶变换和级数理论【２】．其后，孙家昶等人【３，４】提出了平行六边形区域Ｑ上均匀节点离散傅立叶变换 ：ｉ≥