锐客网

  1. 首页 > 睿知 > >

fft算法c语言实现详解 fft程序

生活知识睿知

Fft程序(fft算法C语言实现细节)09 16:27未来愿景
从Fortran到arXiv.org ， 计算机程序和平台的进步使得生物学、气候科学和物理学飞速发展 。
2019年 ， 视界望远镜首次向世界揭开了黑洞的神秘面纱 。然而 ， 我们看到的发光环形黑洞的图像并不是直接拍摄的 ， 而是利用美国、墨西哥、智利、西班牙和南极洲的射电望远镜捕捉到的数据 ， 通过复杂的数学变换和计算获得的[1] 。在公布成果的同时 ， 团队还公开了实现这一突破性成果的代码 ， 使科学界能够详细了解其实现过程 ， 并在此基础上进一步研究 。
从天文学到动物学 ， 这种研究模式在所有学科中越来越普遍:近代每一个重大科学发现的背后 ， 总有一台计算机 。加州史丹福大学的计算生物学家迈克尔·莱维特 ， 因其在化学结构建模的计算策略方面的杰出贡献 ， 分享了2013年诺贝尔化学奖 。他提到 ， 当他在1967年刚开始这项工作时 ， 实验室计算机的内存和计算性能还不到今天笔记本电脑的十分之一 。他说:“尽管我们现在拥有强大的计算资源 ， 但思维的重要性丝毫没有减弱 。」
这需要科学家和程序员 。如果没有能够处理研究问题的软件 ， 没有懂得编写和使用程序的研究人员 ， 计算机再强大也是没有用的 。Neil Chue Hong是总部位于英国爱丁堡的软件可持续发展研究所的负责人 ， 该研究所主要致力于不断改进科学软件的研发和使用 。尼尔说 ， “现在大多数科学研究都是利用软件进行的 ， 软件已经渗透到研究的方方面面 。」
插图:Pawe Jo ê ca
科学发现应该是媒体的头版 。但在这一期的《自然》杂志中 ， 我们想和读者一起聊聊这些发现背后的故事 ， 回顾一下过去几十年中极大改变研究进程的关键代码 。
虽然这个榜单不是绝对的 ， 但在过去的一年里 ， 我们调查了大量的研究人员 ， 总结出了不同领域中对科研有重大影响的十大软件工具 。
编程先锋:Fortran编译器(1957)第一台现代电子计算机对用户不友好 。编程需要一个一个手动链接电路来完成 。虽然随后的机器语言和汇编语言的快速发展使得用户可以通过代码进行编程 ， 但仍然需要对计算机体系结构有深刻的理解 ， 这阻碍了许多科学家使用计算机的效率 。
随着50年代符号语言的发展 ， 效率逐渐提高 ， 特别是公式翻译语言Fortran的出现 ， 改变了这种情况 。Fortran语言是由约翰·巴科斯和他在加州圣何塞的IBM团队开发的 。用户可以在Fortran中使用人类可读的指令进行编程 ， 比如写出x=3+5的计算公式 ， 然后编译器就可以将其转换成快速高效的机器码 。
CDC 3600计算机于1963年交付给科罗拉多州博尔德的国家大气研究中心 ， 它可以借助Fortran编译器进行编程 。
但是编程仍然不是一件容易的事情:早期的程序员使用穿孔卡来输入代码 ， 稍微复杂一点的模拟需要数万张穿孔卡来编写程序 。但是新泽西州普林斯顿大学的气候学家Syukuro Manabe说 ， Fortran为非计算机科学家的研究人员提供了一个有效的编程工具 。“第一次 ， 我们可以自己给计算机编程 ， ”Manabe说 。他和他的同事用Fortran语言开发了第一个成功的气候模型 。
如今 ， Fortran已经进入第八个十年 ， 在气象建模、流体力学、计算化学等需要复杂线性代数和强大计算能力的学科中 ， 它仍然被广泛应用 。生成的代码计算效率高 ， 大部分程序员仍然使用Fortran 。中世纪的Fortran代码库仍然活跃在世界各地的超级计算机和实验室中 。“以前的程序员知道他们在做什么 ， ”加州蒙特雷海军研究生院的应用数学家和气候建模专家弗兰克·吉拉尔多说 。“他们很注重记忆 ， 因为以前的记忆很小 。」
信号处理器:快速傅立叶变换(1965)射电天文学家在扫描天空空时 ， 会捕捉到一系列随时间变化的复杂信号 。为了理解这些电波的本质 ， 他们需要看看这些信号转换成频率方程后是什么样子 。研究人员可以使用一种叫做傅立叶变换的数学过程来完成这个过程 。问题是它的效率非常低 ， 一个N大小的数据集需要N2计算 。
但在1965年 ， 美国数学家JamesCooley和John Tukey发明了一种加速这一过程的方法 。利用递归这种“分而治之”的编程方法(算法可以反复调用自身) ， 快速傅里叶变换(FFT)可以将傅里叶变换的计算减少到Nlog2(N)步 。计算速度随着数据集的增加而增加 ， 在1000个数据点的情况下增加100倍 ， 在100万个数据点的情况下增加50000倍 。
英国牛津大学数学家尼克·特雷费森(Nick Trefethen)表示 ， 这实际上是一个重复的发现——德国数学家卡尔·弗里德里希·高斯(Carl Friedrich Gauss)在1805年提出了这个算法 ， 但他没有发表 。然而 ， Cooley和Tukey为数字信号处理、图像分析、结构生物学等开辟了广泛的应用空 。特雷费森说 ， “这确实是应用数学和工程领域的一件大事 。代码中多次实现了FFT ， 最著名的是FFTW(西方最快的傅立叶变换) 。
西澳大利亚默奇森射电天文望远镜的宽视场阵列的夜景 。望远镜使用快速傅立叶变换来收集数据 。
加州Lawrence Berkeley国家实验室分子生物学和集成生物成像部门负责人保罗·亚当斯回忆说 ， 1995年优化细菌蛋白质GroEL的结构时[2] ， 即使使用了快速傅立叶变换和超级计算机 ， 计算也花费了大量时间 。他说 ， “没有FFT ， 我甚至不知道完成这些计算是否现实 ， 可能永远也完成不了 。」
分子编目:生物学数据库(1965)数据库是当代科学研究不可或缺的一部分 ， 但容易忽略的是 ， 它是由软件驱动的 。在过去的几十年中 ， 这些资源得到了大规模的扩展 ， 许多领域的研究方法也发生了变化 ， 但也许没有一个领域像生物领域一样发生了翻天覆地的变化 。
今天的大规模基因和蛋白质数据库起源于马里兰州国家生物研究基金会的生物信息学先驱MargaretDayhoff的工作 。20世纪60年代初 ， 生物学家致力于揭开蛋白质的氨基酸序列结构 ， 戴霍夫开始整理这些信息 ， 寻找不同物种之间进化关系的线索 。她与三位合作者合著的《蛋白质序列和结构图谱》于1965年首次出版 ， 描述了当时蛋白质的65种已知序列、结构和相似性 。历史学家Bruno Strasser在2010年写道[3] ， 这个数据库是第一个不限于特定研究问题的数据集 。Dayhoff通过打孔纸带对这些数据进行编码 ， 使得这个数据集具有扩展和搜索的潜力 。
在这项研究之后 ， 其他计算生物学数据库开始出现 。诞生于1971年的蛋白质数据库 ， 现在包含了超过17万种大分子结构的详细信息 。加州大学圣地亚哥分校的进化生物学家拉塞尔·杜利特尔(Russell Doolittle)于1981年创建了另一个名为Newat的蛋白质数据库 。然后在1982年 ， 后来的国际核酸序列数据库(GenBank)诞生了 ， GenBank的DNA档案由美国国立卫生研究院(NIH)维护 。
蛋白质数据库包含超过170 ， 000个分子结构 ， 包括这个结合了RNA和蛋白质合成的细菌表达组 。
这些数据库在1983年7月证明了它们的巨大价值 ， 当时由伦敦帝国癌症研究所的蛋白质生物化学家Michael Waterfield和Doolittle领导的两个小组分别报告了一种特定的人类生长因子和一种可导致猴子癌症的病毒的蛋白质序列之间的相似性 。观察结果提示了一种模拟生长因子的病毒致癌机制 ， 它可以诱导细胞快速增殖而不受调控[4] 。国家生物信息学中心(NCBI)前主任詹姆斯·奥斯特尔(James Ostell)说:“这让生物学家意识到 ， 他们可以使用计算机和统计学来进行研究 。通过比较蛋白质序列 ， 我们可以加深对癌症的了解 。」
此外 ， 奥斯特尔表示 ， 这一发现标志着“客观生物学的来临” 。除了设计实验来验证假设 ， 研究人员还可以通过挖掘开放数据库来发现数据收集者可能从未想到的联系 。随着越来越多的数据库被连接在一起 ， 这种研究范式的巨大潜力已经急剧增加 。1991年 ， NCBI的程序员开发了Entrez ， 一个可以在DNA、蛋白质和文献中自由导航的工具 ， 并实现了这个想法 。
StephenSherry是马里兰州贝塞斯达NCBI的负责人 ， 他在研究生阶段就使用了Entrez 。他说:“我还记得当时的感觉很神奇 。」
天气预报领导者:大气环流模型(1969)二战末期 ， 计算机先驱约翰·冯·诺依曼将战时用于弹道计算和武器设计的技术转向了天气预报的研究 。Manabe说:“在此之前 ， 天气预报依靠经验 ， 而冯·诺依曼的团队希望利用物理定律实现数值天气预报 。」
Venkatramani Balaji是普林斯顿国家海洋和大气管理局地球物理流体动力学实验室模拟系统的负责人 。他说 ， 描述这些过程的方程已经存在了几十年 ， 但早期的气象学家不知道如何求解这些方程 。因为这些方程的计算需要给定当前的条件 ， 在短时间内计算它们随时间的变化 ， 然后重复 ， 这个过程非常耗时 ， 计算速度赶不上天气的变化 。1922年 ， 数学家Lewis Fry Richardson花了几个月计算德国慕尼黑的6小时天气预报 。但根据记录 ， 预测结果“极不准确” ， 出现了“在任何已知地表下都不可能发生”的预测结果 。计算机的出现使这个问题变得容易多了 。
20世纪40年代末 ， 冯·诺依曼在普林斯顿高级研究所建立了他的天气预报团队 。1955年 ， 二队在地球物理流体动力学实验室开始了“无限预报”(气候模式)的研究 。
Manabe于1958年加入气候建模团队 ， 致力于大气模型的研究 。他的同事柯克·布莱恩专注于海洋 。1969年 ， 他们成功地将两者结合起来 ， 2006年 ， 《自然》杂志称之为科学计算的“里程碑” 。
【fft算法c语言实现详解 fft程序】今天的气象模型可以把地表划分成25*25km的区域 ， 大气层可以划分成几十个层次进行研究 。Manabe和Bryan在组合海洋-大气模型[5]时 ， 使用了500平方公里的面积和9个级别 ， 并且只覆盖了地球表面的1/6 。然而 ， 巴拉吉仍然认为“这个模型是一个伟大的作品” ， 这使得该团队首次能够在计算机中模拟二氧化碳水平上升对气候的影响 。
数字加速器:BLAS(1979)科学计算通常使用向量和矩阵进行相对简单的数学运算 ， 但计算量仍然很大 。在20世纪70年代 ， 科学界缺乏一套通用的计算工具来执行这些操作 。所以科学界的程序员不得不花时间写代码来完成基本的数学运算 ， 而不是专注于科学问题 。
但是编程世界需要一个标准 。于是 ， 在1979年 ， 基本线性代数子程序(BLAS)出现了[6] 。这个标准一直发展到1990年 ， 为向量和后来的矩阵数学定义了一系列基本程序 。
田纳西大学计算机科学家杰克·唐加拉(Jack Dongarra)认为 ， BLAS实际上是将复杂的矩阵和向量运算简化为简单的计算单元 ， 其基础与加减法相同 。他是BLAS开发团队的成员 。
在加州劳伦斯利弗莫尔国家实验室的Cray-1超级计算机等机器上工作的研究人员没有线性代数标准 。
德克萨斯大学奥斯汀分校的计算机科学家罗伯特·范德盖因(Robert van de Geijn)表示 ， BLAS“可能是科学计算领域定义的最重要的接口” 。除了为常用函数提供标准命名 ， 研究人员还可以确保基于BLAS的代码可以在任何计算机上以相同的方式运行 。这一标准也使计算机制造商能够不断优化BLAS ， 使其硬件能够快速运行 。
40多年来 ， BLAS已经成为科学计算技术栈的核心 ， 使得科学计算软件不断发展 。乔治·华盛顿大学的机械和航空工程师Lorena Barba[/k0/]称之为“代码五层结构的内部机制” 。
东加拉说 ， “它是计算的基础设施 。」
基本显微镜:NIH图像(1987)20世纪80年代初 ， 程序员WayneRasband在马里兰州贝塞斯达的美国国立卫生研究院(NIH)脑成像实验室工作 。该团队有一个可以数字化x光片 ， 但不能在计算机上分析和显示 。拉斯班德写了一个程序来实现这个功能 。
这个程序是专门为价值15万美元的PDP-11微型计算机(安装在机架上的那种计算机 ， 绝不是个人用的)设计的 。然后在1987年 ， 苹果发布了Macintosh II ， 更友好 ， 更实惠 。拉斯班说:“我认为这显然是一个更好的实验室图像分析系统 。于是他把软件搬到了一个新的平台(Macintosh II)上 ， 并重新命名 ， 从而引领了图像分析生态系统的发展 。
NIH Image及其后继产品可以让研究人员在任何计算机上查看和量化任何图像 。该软件家族包括Java版本软件ImageJ由Rasband为Windows和Linux用户编写；还有斐济 ， 德国马普学会分子细胞生物学与遗传学研究所Pavel Tomancak开发的ImageJ ， 里面有关键插件 。在马萨诸塞州布罗德研究所成像平台工作的计算生物学家贝丝·西米尼(Beth Cimini)表示 ， “ImageJ无疑是我们拥有的最基本的软件工具 。我从没见过哪个生物学家想不用ImageJ或者斐济的显微镜 。」
借助插件ImageJ工具 ， 可以自动识别显微图像中的细胞核 。资料来源:Ignacio Arganda-Carreras/ImageJ
拉斯班德认为 ， 部分原因是这些工具是免费的 ， 但威斯康星大学生物医学工程师凯文·埃利塞利(Kevin Eliceiri)认为 ， 更重要的是它们使用户能够根据自己的需求简单地定制工具 。他的团队在拉斯班德退休后领导了ImageJ的研发工作 。ImageJ有一个极简的用户界面 ， 从90年代开始就没怎么变过 。但这个工具由于内置了宏记录器(允许用户保存鼠标点击和菜单选择的操作顺序来记录工作流)、强大的文件格式兼容性和灵活的插件架构 ， 几乎可以无限扩展 。Eliceiri团队的编程负责人柯蒂斯·鲁登(Curtis Rueden)表示 ， 数百人正在上传插件 。这些不断增加的插件极大地扩展了研究人员可用的工具集 ， 包括从跟踪视频中的对象到自动识别细胞的丰富功能 。
“这个软件的目的不是成为一切或者终结一切 ， 而是为用户服务 。”Eliceiri说 ， “与其他程序不同 ， ImageJ可以是用户想要的任何东西 。」
序列检索器:爆炸(1990)一个软件的名字从名词变成了动词 ， 这确实恰当地说明了它的文化重要性 。在搜索界 ， 有谷歌 ， 而在基因领域 ， 人们会想到BLAST 。
进化以取代、敲除、空缺失和重排的形式刻在分子序列上 。通过寻找序列(尤其是蛋白质)之间的相似结构 ， 研究人员可以发现它们之间的进化关系 ， 并对基因功能有更深入的了解 。实现这一想法的关键在于在迅速膨胀的分子信息数据库中进行快速全面的分析 。
1978年 ， 戴霍夫为这个难题增加了一个关键部分 。她提出了一种称为“可接受的点突变”矩阵(PAM matrix)的描述方法 ， 使研究人员能够通过序列之间的相似性和进化距离来对两种蛋白质之间的相关性进行评分 。
1985年 ， 弗吉尼亚大学的WilliamPearson和NCBI的大卫·李普曼基于Dayhoff矩阵的思想提出了一种更快的算法FASTP 。
几年后 ， Lipman与NCBI的Warren Gish和Stephen Altschul、宾夕法尼亚州立大学的Webb Miller和亚利桑那大学的Gene Myers合作开发了一个更强大的版本:Blast(基本局部比对搜索工具) 。
当BLAST在1990年发布时 ， 它结合了处理快速增长的数据库的快速搜索的能力和识别具有长进化距离的匹配的能力 。同时 ， 它还可以计算出这些匹配偶然发生的可能性有多大 。
Altschul说结果出奇的快:“只需要喝一口咖啡就可以完成一个复杂的搜索！但更重要的是 ， 这个工具很好用 。在通过电子邮件更新数据库的时代 ， Gish建立了电子邮件更新系统 ， 后来又建立了基于网络的架构 ， 使用户能够远程访问NCBI计算机进行搜索 ， 从而保证了数据的实时性 。
可以在github:https://github.com/jperkel/nature_code_survey.上获得上面的数据列表和可视化代码
哈佛大学计算生物学家肖恩·艾迪(Sean Eddy)认为 ， 这个系统为当时的胚胎基因组生物学提供了一个革命性的工具 ， 通过相关基因的特征来研究未知基因的特征 。对于世界各地的基因测序实验室来说 ， 它提供了一个新词:“这是一种会流入动词的名词 ， ”埃迪说 。“你会说你在爆自己的序列 。」
预印本发电厂:arXiv.org(1991)在20世纪80年代末 ， 高能物理学家通常会向同行发送论文副本以征求意见 ， 这也是一种礼貌——但仅限于少数人 。“处于学术圈较低层次的人会依赖科学名人的青睐 ， 而不在精英机构的有才华和抱负的研究人员往往会被排除在外” ， 物理学家保罗·金斯伯格(Paul Ginsparg)在2011年写道[7] 。
1991年 ， 在新墨西哥州洛斯阿莫斯的实验室工作的金斯伯格编写了一个自动邮件回复系统 ， 以促进该领域的公平发展 。订户将收到每日预印的论文 ， 每篇文章将被分配一个固定的文章标识号 。只需一封电子邮件 ， 世界各地的用户就可以从实验室计算机系统提交或接收论文 ， 获得最新论文的列表 ， 或按标题和作者进行搜索 。
Ginsparg希望最快能把文章保留3个月 ， 而且仅限于高能物理领域 。不过在同事的劝说下 ， 我开始无限期保存文章 。他说:“那是从电子公告板到数据库存档的关键时刻 。随后 ， 这个系统的发展远远超出了金斯帕格自己的学科 。1993年 ， 他把这个系统移植到广域网上 ， 1998年 ， 他把域名改成了现在的arXiv.org 。
如今 ， 三十年过去了 ， arXiv已经积累了180多万篇预印论文 ， 全部免费开放给公众 。同时 ， 它每月吸引15 ， 000次提交和超过3 ， 000万次下载 。《自然光子学》的编辑十年前[8]在网站20周年之际写道:“不难看出arXiv为什么如此受欢迎 。该系统为研究人员提供了一种方便的方法来标记他们的工作和发现时间 ， 避免了传统同行评审过程所需的交易和持续时间 。」
资料来源:arXiv.org
该网站的成功推动了包括生物学、医学、社会科学等姊妹领域的预印本网站的蓬勃发展 。如今 ， 已有数万篇关于新型冠状病毒病毒研究的预印本论文发表 ， 可见其影响力 。
金斯伯格说 ， “三十年前 ， 这种方法被认为是粒子物理世界之外的一种奇怪方式 。很高兴看到人们现在把它视为普遍现象 。从这个角度来说 ， 它就像一个成功的科研项目 。」
数据探索工具:IPython笔记本(2011)2001年 ， 当FernandoPé rez还是“寻找拖延症”项目的研究生时 ， 他决定开始开发Python的一个核心组件 。
Python是一种解释性语言 ， 这意味着它需要逐行执行 。程序员通常使用名为REPL(Read-Evaluate-Print Loop ， 一种交互式编程环境)的计算机呼叫响应工具来编程 ， 并使用解释器来执行代码 。l可以用于快速探索和迭代开发 ， 但佩REPL认为Python不是为科学而构建的语言 ， 比如它不能轻松加载代码块或保持数据可视化开发 。所以他写了自己的版本 。
这创造了IPython ， 一个“交互式”Python解释器 。佩雷斯在2001年12月发布了这个259行的版本 。十年后 ， 佩雷斯与物理学家布莱恩·格兰杰和数学家埃文·帕特森合作 ， 将这一工具移植到浏览器中 ， 开发出IPython Notebook ， 掀起了数据科学的革命浪潮 。
与其他计算笔记本一样 ， IPython Notebook将代码、结果、图形界面和文本内容组合在一个文件中 。但与其他项目不同 ， IPython Notebook是开源的 ， 开发者社区可以为其做出贡献 。它还支持科学家常用的语言Python 。2014年 ， 这个项目发展成为Jupyter ， 它支持一百多种语言 ， 允许用户在远程超级计算机上探索数据进行分析 ， 就像使用自己的计算机一样容易 。
"对于数据科学家来说 ， Jupyter已经成为实际的标准. "《自然》2018年写道[9] 。当时 ， 代码共享平台GitHub上有超过250万台Jupyter笔记本 。今天有近1000万份 ， 包括2016年发现的引力波和2019年对黑洞成像的代码 。"我们为这个项目做的小小工作已经带来了巨大的回报. "佩雷斯说 。
高速学习机:AlexNet(2012)人工智能(AI)有两种不同的实现形式 。一种使用编码规则 ， 另一种使用计算机通过模拟大脑的神经结构来“学习” 。加拿大多伦多大学计算机科学家杰弗里·辛顿(Geoffrey Hinton)表示 ， 几十年来 ， AI研究人员认为后一种方法是“无稽之谈” 。直到2012年 ， Hinton的研究生AlexKrizhevsky和Ilya Sutskever证明并非如此 。
ImageNet是一年一度的竞赛 。研究人员需要在一百万个日常物体的数据集上训练AI ， 并在另一个独立的图像数据集上进行测试 。辛顿说 ， 那时 ， 最好的算法将识别大约1/4的错误图像 。Krizhevsky和Sutskever提出的AlexNet是一种基于神经网络的“深度学习”算法 ， 将误差降低到16%[10] 。“我们基本上把错误率减少了一半 ， 差不多一半 。辛顿补充道 。
Hinton认为 ， 他的团队在2012年的成功反映了generate的巨大潜力 ， 这是一个足够大的训练数据集、优秀的编程和新的强大GPU(第一个旨在加速计算机视频性能的处理器)的结合 。“突然间 ， 我们可以以30倍的速度运行算法 ， ”他说 ， “或者在30倍的数据上学习 。」
辛顿说 ， 算法上真正的突破其实是在三年前实现的 。当时 ， 他的实验室创建的神经网络能够实现比传统的优化了几十年的AI更准确的语音识别 。“虽然它(比传统人工智能)只好一点点 ， ”辛顿说 ， “但它已经预示了未来 。」
这些成就表明了深度学习在实验室和行业的兴起 。这就是为什么手机可以理解语音查询 ， 图像分析工具可以从光学显微镜图像中快速选择细胞 。同时 ， 这也是为什么AlexNet可以用很多重要的计算机工具从根本上改变科学 ， 改变世界 。
参考资料:
1.事件视界望远镜合作 。L1 j . lett . 875(2019) 。
2.Braig ， k . ， Adams ， P. D. & Brünger ， A. T.《自然结构》 。生物2 ， 1083–1094(1995年) 。
3.史特拉瑟 。生物学43 ， 623–660(2010年) 。
4.纽马克 ， 自然杂志304 ， 108 (1983) 。
5.Manabe ， s .和Bryan ， K.J. AtmosSci.26 ， 786–789(1969年) 。
6.罗森 ， C. L . ， 汉森 ， R. J . ， 金凯德 ， D. R. & Krogh ， F. T.ACM Trans .数学 。软件5 ， 308–323(1979年) 。
7.http://arxiv.org/abs/1108.2700大学的预印本(2011年) 。
8.《自然光子》6 ， 1 (2012) 。
9.自然563 ， 145–146(2018) 。
10.Krizhevsky ， a . ， Sutskever ， I. & Hinton ， G. E. inProc .第25国际 。糖膏剂神经信息处理系统1097–1105(柯伦协会 ， 2012年) 。
作者:杰弗里·m·佩克尔
-自然科学

    推荐阅读


    上一篇：巴伦支海海战 威海卫之战

    下一篇：海洋中最大的鱼多大？ 最大的鱼是什么鱼呢