在1990年发表的《Parallel Algorithm for FGFT and Its Application》一文中,作者李雷有和赵永勇讨论了在非交换环上的离散傅里叶变换(DFT)的一般化FGFT(Fourier-Gauss Transform),及其在快速线性计算问题中的应用,并提供了一个高效的并行算法。以下是从标题、描述、标签以及提供的部分内容中整理出的相关知识点。 文章标题《Parallel Algorithm for FGFT and Its Application》暗示了文章的主要内容是关于FGFT的并行算法以及该算法的应用。FGFT是对传统离散傅里叶变换的扩展,传统DFT定义在交换环上,而FGFT则扩展到非交换环。 在描述中提到的"parallel computation efficiencies for fast algorithms",意味着文章强调了算法的并行计算效率,特别是在快速算法中的应用。这一部分可能探讨了如何利用并行处理来提高算法的执行速度,降低计算复杂性,并有可能讨论了在并行处理中所面临的挑战,比如进一步降低复杂度的难度。 在提供的内容部分,文章首先引入了FGFT的定义。通过给出一个k阶矩阵序列,并定义了广义的傅里叶变换,以及其逆变换。其中用到了对角矩阵E,并给出了变换的具体公式。这一点表明了文章详细讨论了FGFT的数学表达和操作步骤,这对于理解并行算法的原理是至关重要的。 文章接着详细介绍了并行算法中的步骤。特别地,对于计算FGFT及其逆变换的并行步骤,作者声称当使用N个处理器时,并行步骤不会超过O(logN)。这表明算法具有良好的并行性质,并且在计算量上能有显著的提升。 此外,文章还讨论了矩阵序列卷积的并行算法。在定义了矩阵序列卷积之后,作者提出了使用FGFT算法来计算该卷积的并行步骤。根据Theorem 2,当使用kN^3个处理器时,计算矩阵序列A(i)和B(i)的卷积所需的并行步骤为O(logkN)。这是一个重要的结果,因为它显示了并行处理在降低特定计算问题的时间复杂度方面的重要性。 文章中还提到了两个推论,推论进一步说明了使用 FGFT 算法的并行计算步骤与处理器数量之间的关系,强调了 FGFT 在提高矩阵序列卷积计算效率方面的应用。 从标签“自然科学 论文”我们可以推断,这篇文章属于科学论文的范畴,是一篇严谨的学术研究成果,其研究成果可能在计算机科学、数学和工程学等相关领域都有所应用。由于其发表时间较早,1990年,这在当时的计算科学领域中是一个较为前瞻性的研究,对并行算法的设计和理论分析具有一定的指导意义。 总结来说,本文的知识点涵盖了以下方面: 1. FGFT的定义及其与传统DFT的关系。 2. 并行算法设计的原则以及在减少计算复杂性上的应用。 3. FGFT并行算法的具体实现方法和步骤。 4. 并行算法在矩阵序列卷积计算中的应用以及效率分析。 5. 并行处理中处理器数量与计算步骤的数学关系。 这篇文章对后续研究并行处理和快速线性计算问题提供了重要的理论基础,并可能对高性能计算技术的发展起到了推动作用。
- 粉丝: 5
- 资源: 938
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 基于S7-200 PLC和组态王组态污水处理控制系统的设计 1.1 研究的目的和意义 3 1.2 国内外发展概况 3 2 系统设
- C#中的枚举类型:定义、使用与最佳实践
- 基于Python实现智能课堂专注度、考试作弊及智慧教室系统(情绪识别、表情识别、姿态识别和人脸识别结合)+源代码+文档说明
- 基于脉振高频电流注入的永磁同步电机无感FOC 1.采用脉振高频电流注入法实现零低速下无感起动运行,相比电压注入法可以省去电流反馈
- oracle好用卸载工具2个.zip
- Java 算法:冒泡,选择,插入排序算法
- C++ 中的编译错误和警告如何处理
- java+mysql图书管理系统
- C#中的异常处理是如何实现的
- 简单的后台管理系统框架