Theory, Implementation, and Applications of Sublinear-Time Fourier Transform Algorithms

次线性时间傅里叶变换算法的理论、实现和应用

• 批准号: 0510203
• 负责人: Martin Strauss
• 金额: $ 12.5万
• 依托单位: Regents of the University of Michigan - Ann Arbor
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-07-01 至 2009-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0510203&HistoricalAwards=false
• 关键词: Theory; Implementation; Applications; Sublinear; Time

The problem of computing a Fourier representation of data is afundamental one, that arises in many areas of mathematics, science,and technology. Recently, a class of algorithms has been proposed toapproximate the Fourier transform, with provable quality guarantees,in dramatically less time than required by traditional exactalgorithms. The investigator and his colleagues evaluate competingvariations of the algorithm, both proposed and new, and choose thebest from among them for general purpose use as well as for specificapplication to Magnetic Resonence Imaging and solution of partialdifferential equations, including advection-diffusion equations.The Fourier Transform is a fundamental technique with manyapplications. The investigator and his team investigate recentapproximate methods that are dramatically more efficient thantraditional methods. The team directly addresses applications tobiomedical Magnetic Resonance Imaging and the modeling of liquid andgas behavior, which has further applications to studying theatmosphere and bodies of water in the environment, as well asapplications to manufacturing. The investigator and his team alsomake available fundamental tools that will be useful to others in abroad range of scientific, educational, and engineering settingsincluding modeling the interactions of tiny particles, reliabletelecommunications, and imaging generally. The project combinescutting-edge techniques from several disciplines and trains a graduatestudent in these techniques and their integration.

计算数据的傅里叶表示是一个基本问题，它出现在数学、科学和技术的许多领域。最近，已经提出了一类算法来逼近傅里叶变换，并且具有可证明的质量保证，比传统精确算法所需的时间要少得多。这位研究人员和他的同事们评估了该算法的竞争变体，包括建议的和新的，并从它们中选择了最好的，用于一般用途，以及特定应用于磁共振成像和求解偏微分方程组，包括对流-扩散方程。傅立叶变换是一种具有许多应用的基本技术。这位研究人员和他的团队研究了比传统方法效率高得多的最近的近似方法。该团队直接致力于生物医学磁共振成像和液体和气体行为建模的应用，这将进一步应用于研究大气和环境中的水体，以及在制造业中的应用。这位研究人员和他的团队还提供了一些基本工具，这些工具将在广泛的科学、教育和工程环境中对其他人有用，包括对微小粒子的相互作用进行建模、可靠的电子通信和一般的成像。该项目结合了几个学科的尖端技术，并培训了一名研究生这些技术及其集成。