许缪尔·维诺格拉特(Shmuel Winograd) is a computer scientist, noted for his work on fast algorithms for arithmetic, and in particular for the algorithm known as the Coppersmith-Winograd algorithm and for his FFT algorithm. From 1970-1974 and 1980-1994 he was the director of the Mathematical Science Department at IBM. In 1994 he was inducted as a Fellow of the Association for Computing Machinery.
许缪尔·维诺格拉特——算法复杂性研究的先驱编辑本段回目录
在首批32位计算机先驱奖获得者之中,许缪尔·维诺格拉特(Shmuel Winograd)是第三位最年轻的,因为他出生于1936年,只比前面已介绍过的最年轻的克努特(D.E.Knuth)大2岁,比罗伯茨(L.G. Roberts)大1岁。他是因为在算法复杂性方面的先驱性研究工作以及在算法设计尤其是高效率算法设计方面的杰出贡献而获此殊荣的。
维诺格拉特1936年1月4日生于巴勒斯坦地区的特拉维夫(Tel Aviv),1948年以色列宣布建国时成为以色列的领土,维诺格拉特也因此成为以色列公民。中学毕业以后他到美国上大学,1959年取得MIT的电气工程学士学位,接着又取得硕士学位。之后他转至纽约大学,改攻数学,于1968年取得数学博士学位。之后他应聘在IBM公司就职。
我们前面提到,IBM公司的沃森研究中心根据哥尔斯廷的建议建立数学科学部,他出任首任主任。IBM沃森研究中心人才济济,在激烈的竞争中维诺格拉特凭什么能脱颖而出,担任这一显要职务呢?他凭的就是在数学方面的深厚底蕴和出色的研究成果。以矩阵计算为例,对于高阶矩阵的乘法,如何降低运算次数,提高运算效率,一直是数学家追求的目标,但矩阵乘法的各种算法的效率始终不能达到满意的结果。
维诺格拉特经过潜心研究,终于取得突破,他为两个N阶矩阵设计的一种新的算法,将所需的运算次数降低到N2.367。这个结果一直到20世纪90年代初期仍保持着世界记录,无人能够突破。再如快速傅里叶变换FFT(Fast Fourier Transform)是数值代数中最活跃的一个领域。所谓FFT是快速计算离散傅里叶变换DFT(Discrete Fourier Transform)的算法。DFT是把/V点序列x(n)(n:0,1,…,/V—1)按线性关系
直接计算N点DFT和IDFF各需要N2次乘法和ⅣN(N-1)次加法,当N很大时,运算量很大。最早的FVF算法是美国学者考利(J.W.Cooley)和托凯(J.W.Tukey)在1965年提出的,其基本思想是利用基函数Wnk的周期性和对称性,改变计算次序与求和次序,利用递推步骤以减少运算量。
由于F1T可用于计算循环卷积、计算多项式乘积、大整数乘积、矩阵的逆和特征值,在函数逼近论和众多实际技术领域,如光谱、声谱、地震谱分析、晶体结构分析、滤波、数字信号处理、图像信号处理、物探、雷达、卫星摄像分析、全息图以及心电图、脑电图、x光相片强化等方面都有大量应用,因而成为众多学者关注的焦点。自1965年第一个FFF算法问世以来,又提出了许多新的FFT算法,以进一步提高计算效率。其中,1974年,维诺格拉特所提出的一种FFT算法就是其中的佼佼者,从而被学术界称为维诺格拉特算法而独领风骚。
维诺格拉特的主要著作有:
《有噪声情况下的可靠计算》(Reliable Computation in the Presence of Noices,MIT Pr.,1963)
《计算的算术复杂性》(Arithmetic Complexity of computations,SLAM,1980)
除了获得计算机先驱奖外,维诺格拉特也是McDowell奖的获得者。他早已加入美国科籍,并且是美国科学院院士。