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

Fft程序(fft算法C语言实现细节)09 16:27未来愿景

从Fortran到arXiv.org,计算机程序和平台的进步使得生物学、气候科学和物理学飞速发展。

2019年,视界望远镜首次向世界揭开了黑洞的神秘面纱。然而,我们看到的发光环形黑洞的图像并不是直接拍摄的,而是使用美国、墨西哥、智利、西班牙和南极洲的射电望远镜捕捉到的数据,通过复杂的数学变换和计算获得的插图:pawejoń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年提出了这个算法,但他没有发表。而库利和图基却为数字信号处理、图像分析、结构生物学等开辟了广泛的应用空 room。特雷费森说,“这确实是应用数学和工程领域的一件大事。代码中多次实现了FFT,最著名的是FFTW(西方最快的傅立叶变换)。

改变科学的十大编程软件西澳大利亚射电天文望远镜murchison宽视场阵列的夜景,它使用快速傅立叶变换收集数据。

加州劳伦斯柏克莱国家实验室分子生物学和整合生物成像部门负责人保罗·亚当斯回忆说,1995年细菌蛋白质GroEL结构优化时,蛋白质数据库包含超过17万个分子结构,包括这个结合了RNA和蛋白质合成过程的细菌表达组。

这些数据库在1983年7月证明了它们的巨大价值,当时由伦敦帝国癌症研究所的蛋白质生物化学家Michael Waterfield和Doolittle领导的两个小组分别报告了一种特定的人类生长因子和一种可导致猴子癌症的病毒的蛋白质序列之间的相似性。结果该观察结果提示了一种模拟生长因子的病毒致癌机制,病毒可诱导细胞快速增殖而不受调控。

20世纪40年代末,冯·诺依曼在普林斯顿高级研究所建立了他的天气预报团队。1955年,二队在地球物理流体动力学实验室开始了“无限预报”(气候模式)的研究。

Manabe于1958年加入气候建模团队,致力于大气模型的研究。他的同事柯克·布莱恩专注于海洋。1969年,他们成功地将两者结合起来,2006年,《自然》杂志称之为科学计算的“里程碑”。

今天的气象模型可以把地表划分成25*25km的区域,大气层可以划分成几十个层次进行研究。当Manabe和Bryan结合海洋大气模型在加利福尼亚劳伦斯利弗莫尔国家实验室的Cray-1超级计算机上工作时,还没有线性代数标准。

德克萨斯大学奥斯汀分校的计算机科学家罗伯特·范德盖因(Robert van de Geijn)表示,BLAS“可能是科学计算领域定义的最重要的接口”。除了为常用函数提供标准命名,研究人员还可以确保基于BLAS的代码可以在任何计算机上以相同的方式运行。这一标准也使计算机制造商能够不断优化BLAS,使其硬件能够快速运行。

40多年来,BLAS已经成为科学计算技术栈的核心,使得科学计算软件不断发展。乔治华盛顿大学的机械和航空工程师Lorena Barba空称之为“代码五层结构的内部机制”。

东加拉说,“它是计算的基础设施。」

基本显微镜:NIH Image(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可以是用户想要的任何东西。」

Sequencer: BLAST(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)上世纪80年代末,高能物理学家通常会把论文的复印件发给同行征求意见,这也是一种礼貌——但仅限于少数人。物理学家保罗·金斯伯格(Paul Ginsparg)在2011年写道:“学术圈下层的人将依赖科学名人的青睐,而那些有才华、有抱负但不在精英机构的研究人员往往被排除在外”。资料来源:arXiv.org。

该网站的成功推动了包括生物学、医学、社会科学等姊妹领域的预印本网站的蓬勃发展。如今,已有数万篇关于新型冠状病毒病毒研究的预印本论文发表,可见其影响力。

金斯伯格说,“三十年前,这种方法被认为是粒子物理世界之外的一种奇怪方式。很高兴看到人们现在把它视为普遍现象。从这个角度来说,它就像一个成功的科研项目。」

数据探索工具:Ipython Notebook(2011)2001年,当fernandoperez还是“寻找拖延症”项目的研究生时,他决定开始开发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.事件视界望远镜合作。列特。875,L1 (2019)。

2.布拉格,k,亚当斯,P. D. & amp勃林格,A. T .自然结构。生物2,1083–1094(1995年)。

3.B. J. J .希斯特.斯特拉瑟。生物学43,623–660(2010年)。

4.纽马克,自然304,108页(1983)。

5.马纳贝公司。布莱恩K. J. Atmos。Sci。26, 786–789 (1969).

6.罗森,C. L .,汉森,R. J .,金凯德,D. R. & amp克拉夫,自由贸易区。数学。软件5,308–323(1979年)。

7.http://arxiv.org/abs/1108.2700大学的预印本(2011年)。

8.自然光子。6, 1 (2012).

9.自然563,145–146(2018)。

10.克日涅夫斯基,a,苏茨基弗,I. & amp辛顿,通用电气正在进行。第25国际。糖膏剂神经信息处理系统。Weinberger,k . o .)1097–1105(Curran Associates,2012)。

作者:杰弗里·m·佩克尔

-自然科学

本文来自投稿,仅供学习参考!不代表本站立场,该文观点仅代表原作者本人,本站不拥有所有权,不承担相关法律责任。如发现本站有抄袭侵权/违规的内容,请发送邮件至83771837@qq.com举报,一经查实,本站将立刻删除。