Bo Tian和Qing Huo Liu（新墨西哥州立大学Klipsch电气与计算机工程学院）在1999年IEEE国际会议上发表了一项关于非均匀快速余弦变换（Nonuniform Fast Cosine Transform, NUFCT）及其在切比雪夫伪谱时域（Chebyshev PSTD）算法中应用的原创研究。该研究通过设计高效的非均匀离散余弦变换（NUFCT）及其逆变换（NU-IFCT）算法，解决了传统快速余弦变换（FCT）要求输入数据均匀分布的限制，为计算电磁学和信号处理领域提供了新的工具。

学术背景

快速余弦变换（FCT）在信号处理和计算电磁学中具有广泛应用，例如在频谱分析、图像压缩和偏微分方程求解中。然而，传统FCT要求输入数据必须均匀分布，这一限制影响了其在非均匀采样场景（如自适应网格计算或实验数据拟合）中的适用性。特别是在Chebyshev PSTD方法中，传统FCT要求数据严格位于切比雪夫多项式的极值点，而实际工程问题中的数据分布往往是随机的。因此，开发适用于非均匀数据的FCT算法具有重要科学意义。

针对这一问题，作者提出两种新型高效算法：
1. 前向非均匀FCT（NUFCT-1和NUFCT-2）：通过引入插值系数和快速傅里叶变换（FFT）框架，将非均匀分布的输入数据映射到均匀网格上计算，算法复杂度为O(Nlog₂N)。
2. 逆向非均匀FCT（NU-IFCT）：利用共轭梯度快速傅里叶变换（CG-FFT）方法迭代求解逆问题。

研究流程

1. 前向NUFCT算法设计

   • 问题建模：针对非均匀点集ck∈[0,π]，将离散余弦变换（DCT）重写为指数函数的加权求和（式1-2）。
     
   • 插值策略：通过引入精度因子sk和插值系数ze，将非均匀点映射到均匀网格（式3-5），并构建傅里叶矩阵F（式7-8）以优化计算效率。
     
   • 统一计算框架：利用均匀FCT和FST（快速正弦变换）加速运算（式8），最终通过实部提取得到变换结果。
     

2. 逆向NU-IFCT算法设计

   • 矩阵分解：将逆问题转化为BTB矩阵求解（式9），通过NUFCT-2计算相关系数aj和bj。
     
   • 迭代求解：采用CG-FFT方法进行离散卷积和相关性运算，逐次逼近解。
     

3. 数值验证

   • 实验设置：选取N=64、m=2（过采样率）、q=4（插值阶数），输入数据ak和采样点位置均为[0,1]和[0,2]内的随机数。
     
   • 结果分析：对比NUFCT输出与直接计算结果的误差（图1d），L₂误差为9.41×10⁻⁴，L∞误差为2.50×10⁻⁴，验证了算法的高精度。
     

主要结论

1. 算法普适性：NUFCT和NU-IFCT突破了传统FCT对数据均匀性的依赖，可直接处理随机分布数据，扩展了Chebyshev PSTD方法的适用场景。
   
2. 计算效率：算法复杂度为O(Nlog₂N)，过采样率m=2时，算术运算量级为0(2mnlog₂n)，显著优于直接计算法。
   

研究亮点

1. 方法创新：首次将非均匀插值与傅里叶矩阵结合，实现了非均匀数据的快速余弦变换。
   
2. 工程价值：为电磁场仿真（如散射问题）和信号处理中的非均匀采样提供了高效工具。
   
3. 开源潜力：算法框架可扩展至其他正交变换（如非均匀小波变换）。
   

其他价值

本研究受美国国家科学基金会（NSF）和美国环境保护署（EPA）资助，相关成果为后续研究（如非均匀快速傅里叶变换/NUFFT）提供了理论基础。参考文献中提到的CG-FFT方法（[3]）进一步优化了逆问题的求解效率，体现了跨领域方法的融合。