矩阵乘法的一个最优并行算法

本文给出了向是一机上计算两个n阶矩阵乘法的并行算法。处理机台数P=n;并行步数T＝(n);效率＝0（1）。此算法从阶上已达到并行矩阵乘法的复杂性下界，同时在保证效率为0（1）的前提下，使处理机台数的上界达到最优。     

三角形Toeplitz系统的并行求逆算法

<正> 本文给出了规模为n的三角形Toepfitz 系统的一种并行求逆算法。该算法所需处理机的台数p=n,并行时间步数T_p=O(log_2~2n),从而速度倍数s_p=O(n/log_2n)。另外,我们对多项式快速除法也作了相应的并行处理,并给出了三角形T 矩阵逆的一个显示表达式。     

一类新的分块并行迭代方法

对于求解线性代数方程A(?)。本文在矩阵、向量分块的基础上,进一步分解子矩阵,从而得到一类新的迭代算法。这类新迭代方法包括以前的所有迭代方法,例如:Jacobi迭代,Gauss—Seidel迭代等。建立在这类新方法的基础上,文章给出了二种新的并行迭代方法:分块对角线选代方法和分块双对角线迭代方法。这二个方法适合于在SIMD(除纵向流水线机)和MIMD型并行机上计算。文章假设处理机台数(或等效并行台数)为P。     

并行找近似最大值的位对分技术

<正> 设K是一个数据集,其中每个元素a∈K的键是整数,都可用P位二进制a_1a_2…a_p表示。K 上的全序关系R 定义为:若a_i=b_i(1≤i≤l),a_(l+1)>b_(l+1),o≤lb。显然B=(K,R)是一个数据结构。我们考察在B 上解最大元问题。对并行找最大元,[1]已有相当好的结果。Valiant 利用图论结果得出:若处理机台数为n,每台处理机都以二元比较作为基本运算,则对n 元找最大元的并行比较次数为t_(max)(n)≥log_2log_2n-const事实上若考虑计算机的系统开销,则不论有多少台处理机可用,因问题有n 个输入,分析树高至少为log_2n。     

解K阶线性递归N方程组的一种实用并行算法

本文提出了解K阶线性递归N方程组的一种实用并行算法.当K相似文献   

并行计算稀疏矩阵乘以向量的负载平衡算法

稀疏矩阵乘以一个向量（SpM×V）的问题是许多大型应用问题的核心计算问题，文中提出了一种在并行计算机上并行计算SpMXV的负载平衡算法，计算复杂性为O（N）（N为稀疏矩阵的阶），而目前计算此类问题的最优负载平衡算法的计算复杂性为O（N·P）（P为处理机台数）。文章最后给出了并行数值实验。     

基于GPU的并行Cholesky分解及其应用

在OpenCL并行计算框架的clMAGMA库中,Cholesky分解算法采用大尺寸分块并行方法,不能充分利用GPU的高速局部存储器,且在计算过程中存在多次GPU-CPU间的数据传递。为此,提出采用小尺寸分块并行方法,充分利用GPU中的高速局部存储器,使矩阵子块的逆矩阵得到复用,完成对称正定矩阵的高效Cholesky分解,并且其能够应用于三维视觉光束平差问题中的大型正定矩阵的分解。实验结果表明,该方法的Cholesky分解速度比clMAGMA提升50%以上,针对光束平差问题,比Ceres Solver中使用的Eigen库速度提升约38倍。     

多处理机多前端代码的向量化

本文介绍为直接求解大型稀疏线性方程组而促进多处理机上多前端(multifrontal)代码的向量化在方法设计上应作的变化。这些变化使用了完全高斯消元法中已成功运用过的技术,并象现Level 2和Level 3 BLAS中实现的那样,以使用“矩阵—向量”和“矩阵—矩阵”核心为基础。通过在IBM3090/VF,ETA-10P及Cray-2上运行,我们说明了改进后代码的性能。虽然我们的实验主要是在这些机器的单处理机上进行,我们却主要考虑多重处理的影响。得到的加速比因数大于11,修改后的代码对标准结构问题在Cray-2的单处理机上执行速度大于200MFLOPS。     

背包类问题的并行O(25n/6)时间-空间-处理机折衷

将串行动态二表算法应用于并行三表算法的设计中,提出一种求解背包、精确的可满足性和集覆盖等背包类NP完全问题的并行三表六子表算法.基于EREW-PRAM模型,该算法可使用O(2n/8)的处理机在O(27n/16)的时间和O(213n/48)的空间求解n维背包类问题,其时间-空间-处理机折衷为O(25n/6).与现有文献的性能对比分析表明,该算法极大地提高了并行求解背包类问题的时间-空间-处理机折衷性能.由于该算法能够破解更高维数的背包类公钥和数字水印系统,其结论在密钥分析领域具有一定的理论和实际意义.     

用部分选主元的高斯消去法并行求解线性方程组

高斯消去法,又称高斯消元法,实际上就是我们俗称的加减消元法。数学上,高斯消去法或称高斯-约当消去法,由高斯和约当得名(很多人将高斯消去作为完整的高斯-约当消去的前半部分),它是线性代数中的一个算法,用于决定线性方程组的解,决定矩阵的秩,以及决定可逆方矩阵的逆。当用于一个矩阵时,高斯消去产生行消去梯形形式。用高斯消去法求解线性方程组的解是一种比较常见的解线性方程组的方法,这种方法尤其在利用计算机求解线性方程组时是更是常用。但大多数情况下都是用串行的算法来解方程组,该文介绍了利用高斯消去法并行求解线性方程组的方法。     

一种快速求解二值线性方程组的并行结构

针对求解GF(2)域的线性方程组问题,改进现有的高斯消元算法,提出一种快速求解未知向量的硬件并行结构,通过增加消元与行循环位移的并行操作以降低时间复杂度,采用一类仿“smart memory”基本单元的互联完成整个算法在硬件上的映射。对结构的性能分析表明,对于密度远大于或小于0.5的n阶二值增广矩阵,并行结构平均计算时间约为2n个时钟周期,远小于软件算法时间(1/4n3)。在 3阶~50阶的二值非稀疏增广矩阵上的实现结果表明,与软件实现相比,该结构的性能可提高约2个数量级。     

用GPU加速求解线性方程组的高斯消元法

提出了应用图形处理器(GPU)加速求解线性方程组的高斯消元法,用二维四通道纹理表示系数矩阵与常数向量构成的矩阵,在该矩阵内完成归一化、消元等操作.提出了新的纹理缩减算法,该算法不要求纹理的边长是2的幂,把该纹理算法应用于高斯消元法的列主元搜索和确定主元行号.根据这些算法,使用OpenGL着色语言编程,用图形处理器实现加速求解线性方程组的高斯消元法,运算时间与基于CPU的算法比较,随着方程组未知量数量增多,基于GPU的算法具有较快的运算速度,证实图形处理器能加速线性方程组的求解.     

分段对称反向高斯-约当消元法及其应用

求解变系数方程的高斯消元法与高斯-约当消元法计算原理类似、问题相近,但前者计算速度高于后者.提出分段对称反向高斯-约当消元法,其中包括根据系数矩阵结构特点构成特殊增广阵,以展示和应用元素的变化规律,并分段对上下三角元素消元以大大提高计算效率.对矩阵下三角元素正向消元及对称计算可简化所有下三角元素计算,而对上三角元素反向消元可再省略所有上三角元素计算,而取倒后的对角元素作为规格化因子可大大减少除法计算.根据单位矩阵结构特点,对其规格化或对系数矩阵上下三角元素消元时均仅计算部分对角元素和下三角元素可进一步提高计算效率.所有元素均用四角规则计算而无需计算公式以简化计算和编程.新方法大大减少了高斯-约当消元法中元素的计算,且原理简单、易于编程,可快速求解各种变系数方程,还可利用元素对称性求解常系数的节点阻抗矩阵.与高斯消元法和高斯-约当消元法相比,新方法计算速度大大提高.     

解线性代数方程组的一个高效并行算法

在阵列机或细胞结构向量机上用高斯消去法求解线性代数方程组的基本操作是进行大量的行向量变换。若并行处理机台数S远超过方程组的阶数N,则因在行变换时至少有S-N台处理机不工作而造成系统效率极低。本文提出一种可以在“虚共存细胞结构纵横加工向量机”(以下简称“虚共存机系统”)上实现的高效并行算法,使系统效率大大提高。     

高速并行系统的性能度量

本文介绍了由4096个单元构成的ICL分布式高度并行阵列处理机系统的性能度量方法,并讨论了这种方法和在串行处理机中使用的传统方法的关系。为使讨论有一个基础,文章先简要地对分布式阵列处理机(DAP)硬件和一些算法设计的含义作了描述。接着讨论了并行计算中选择算法的重要性,以使要解问题所用的硬件的并行性能得到最充分的利用,还给出了并行算法和混合使用串行和并行技术的混合算法的例子。最后介绍了以解题为标准的性能比较法,并以DAP用户对应用领域中广泛出现的问题所做的研究结果来阐明这种方法。     

基于高斯消元法下的最佳平方逼近算法效率分析——以一道ACM试题为例

针对ACM数值计算分析类的防AK试题,一般可以利用克拉默法则最佳平方逼近、高斯消元最佳平方逼近、Hilbert矩阵Cholesky分解平方逼近和切比雪夫多项式正交等方法求解。以第39届ACM-ICPC西安邀请赛的一道防AK题为例,对这几种典型算法进行实验分析,并在反复实验中对算法参数进行修正,然后进行质量与效率的分析。测试结果表明,高精度高斯消元最佳平方逼近解法求解ACM数值计算分析类的防AK试题,优于克拉默法则最佳平方逼近、普通高斯消元最佳平方逼近和Hilbert矩阵Cholesky分解平方逼近,是解决数值计算分析类问题的一种有效方法。     

一种改进的适合并行计算的TFQMR算法

TFQMR算法是一种Krylov子空间算法,常用来求解大型稀疏线性方程组．通过改变TFQMR算法的计算次序,提出了一种改进的TFQMR(ITFQMR)算法．对比TFQMR算法,ITFQMR算法的数值稳定性和TFQMR算法相同,几乎没有增加计算量,但考虑了在MIMD并行机上实现时并行算法的性能,其同步开销减少为TFQMR算法的一半,并且所有内积计算以及矩阵向量乘是独立的,没有数据相关性,可以进行计算与通信的重叠．从理论和实验两个角度来讨论ITFQMR算法的性能,当处理机台数较多时,ITFQMR算法的计算速度快于TFQMR算法．实验说明了在有64台处理机机群上进行,最快的并行ITFQMR算法的计算速度大约比TFQMR算法快20％．     

基于多层半可分结构矩阵的快速算法与并行实现

基于多层半可分(HSS)结构矩阵的快速算法可有效降低具有数值低秩属性的稠密线性方程组求解的复杂度.采用随机取样和保结构秩显(SPRR)分解相结合的方法替代秩显QR(RRQR)分解可以快速构造HSS结构矩阵.该方法将压缩构造HSS结构矩阵转换成小矩阵计算,减少存储和通信开销,使构造HSS结构矩阵的时间复杂度进一步降低.在分布式机群上采用ScaLapack的二维循环块分布方式存储各矩阵块,将HSS树和处理机网格进行映射.构造HSS结构矩阵的并行算法包括对矩阵的多层块压缩,数据交换和重分布,然后结合并行ULV分解和并行三角求解实现快速并行求解,分析了该并行算法的复杂度.最后以二维电磁散射问题为例,数值结果表明该算法不仅比直接LU分解快一个数量级,而且具有良好的并行可扩展性.     

图形处理器中平面裁剪算法并行化的设计与验证

为了提高图形处理器中裁剪运算速率,我们提出一种并行化的思想,在得到正确结果的基础上,通过对单个处理机和多个处理机处理裁剪所用的时间进行比较,多个处理机同时工作可以在一定程度上减少运算时间。     

基于消息传递接口的线性方程组并行计算研究——以改进的高斯消元法为例

在传统的线性方程组高斯消元法中需要的时间复杂度,因此在实际工程中,一个高阶的线性方程组的求解可能需要数天甚至数月的时间来求解。为了进一步提高高阶线性方程组的求解效率,本文在基于消息传递接口的并行环境下,对线性方程组的连续高斯消元算法的设计与实现进行了研究,研究的结果表明相较于传统高斯消元法,并行环境下的高斯消元解法具有更好的性能。