大整数乘法Sch?nhage-Strassen算法的多核并行化研究

基于数论转换的Sch?nhage-Strassen算法(简称SSA)是目前实际应用中使用较多、速度较快的大整数乘法算法之一.首先对SSA算法原理进行了详细分析,然后从细粒度的角度对SSA算法在多核平台进行比较细致的并行优化.基于大整数运算开源库GMP实现了SSA算法并行化方案,并在Intel X86平台进行了验证和测试.经测试,8线程时的最大加速比可达到6.59,平均加速比6.41.在浪潮TS850服务器对并行方案的扩展性进行测试,实验结果表明:SSA算法并行方案具有良好的扩展性,最大加速比可达21.42.

几个结构矩阵乘积的Strassen算法

运用广义中心对称矩阵和广义中心Hermitian矩阵的约化性质得到了计算此类矩阵乘积的Strassen算法.此算法和传统算法相比,大约是传统算法计算量的一半.

Winograd矩阵乘法算法用于任意阶矩阵时的一种新处理方法

摘要t矩阵乘法StraSsen算法及其变形winograd算法用分而治之的方法把矩阵乘法时间复杂性由传统的D(n。)改进到0(佗kg。n.但是对于奇数阶矩阵,在划分子矩阵时,要作特殊处理才能继续使用此算法.本文提出了一种非等阶“十”字架划分方法,可以最少化填零,最大化性能,使得奇数阶矩阵乘法的时间复杂性更加接近偶数阶矩阵乘法的效果.计算实例显示该方法是有效的.

关于中心对称矩阵的矩阵与矩阵乘积的计算

给出了计算矩阵与矩阵乘积W=AP的几种算法(其中A或P为中心对称矩阵或中心Hermitian矩阵),与计算矩阵与矩阵乘积的传统算法以及Strassen算法相比较,计算量约节省一半、所需内存可节省一半。另外,当A或P为斜中心对称矩阵时也有相似的结论。

素数测试在RSA公开密钥密码算法中的分析研究

论述了 RSA公开密钥密码技术及 RSA安全性分析 ,介绍了 Solovay-Strassen素数测试算法以及 Miller-Rabin素数测试算法 ,进一步论述了产生充分大的素数是切实可行的 .

快速判别H矩阵的计算复杂性

Ｈ矩阵在工程技术和经济学等研究中具有广泛用途，然而，其判别是困难的，关于Ｈ阵判别的研究，已受到高度重视，通过研究Ｈ阵的特征，利用二分递推技术研究其快速判别，证明了计算复杂性为Ｏ（ｎ￣（ｌｏｇ２７））。

矩阵乘法的两个算法分析

矩阵乘法是一种应用十分广泛的基本的运算之一 ,提高矩阵的运算速度有利于减少许多科学及工程领域计算问题的时间耗费 ,通过对矩阵乘法的Strassen算法及其时间复杂性等问题进行分析及总结 ;以实现动态规划法用于寻找矩阵链乘的最优乘积次序算法 .

关于矩阵乘法问题的人工蜂群优化算法研究

矩阵乘法运算作为计算机科学和数学的一个基本运算,在科学研究和工程计算中有着广泛的应用。确定2个矩阵乘积所需要的最小乘法数是当今计算机代数中一直未能求解的重要问题之一。通过将矩阵乘法问题建模为一个组合优化问题,采用人工蜂群启发式搜索算法进行矩阵乘法问题求解。对人工蜂群算法进行了改进,给出一种绕圈遍历方法,避免了对同一个解的相同邻域的重复搜索。通过在2×2矩阵乘法问题上的数值实验验证了算法的有效性,所提算法能够快速地找到2×2矩阵分解的乘积方法。

矩阵乘并行算法的仿真与性能分析

为了优化矩阵乘法的并行运算效率,提高流水线的性能,采用了基于Strassen算法的矩阵乘运算,并通过编码在DLX模拟的并行流水线环境中仿真运行。实验结果表明,优化后的矩阵乘算法降低了时间复杂度,减少了指令条数和运算周期,显著地提高了流水线上矩阵乘法的并行运算效率。