中文摘要：

高维非均匀快速傅立叶变换是科学技术研究亟需的重要工具，其计算瓶颈如何快速计算高维过采样数据的傅里叶变换。由于传统快速傅里叶变换算法的计算复杂性会随着位数的增加呈现指数增长，因此并不适用于计算高维过采样数据的傅里叶变换。本项目拟通过稀疏网格的稀疏性质，减弱维数对傅里叶变换复杂性的影响，建立基于稀疏网格上的高精度快速傅里叶变换的第一、二型高维非均匀高精度快速傅立叶变换，建立高维流形上的快速傅里叶变换算法；分析以上算法的复杂性与逼近阶。在以上工作的基础上，将高维非均匀快速傅立叶变换应用于机器学习中正则化核矩阵的求逆，发展具有最优逼近阶与最佳复杂性的机器学习算法高。

结论摘要：

高维非均匀快速傅立叶变换是科学技术研究亟需的重要工具。本项目提出了一种高维高精度快速离散傅立叶变换及其逆变换算法；并以此为基础上，对Besov空间的非光滑函数，建立具有最优逼近阶与最佳复杂性的高维非均匀快速离散傅立叶变换及其逆变换算法。同时，借助傅立叶基函数与正交多项式之间的转换关系，建立高维快速正交多项式变换算法，分析该算法的复杂性与逼近阶。在以上工作的基础上，将高维非均匀快速傅立叶变换算法应用于求解双调和方程导出的边界积分方程，发展具有最优逼近阶与最佳复杂性的高维积分方程快速算法。本项目在三年内产生高质量的研究成果，发表及接收发表一流的学术论文4篇。