求解对称带状广义特征值问题的扩展分治算法

提出了分布式环境下计算对称带状广义特征值问题的一种扩展分治算法，给出了特征值分割定理及其证明．算法在扩展分治的基础上，利用二分压缩结合广义Rayleigh商迭代计算广义特征对．理论分析和数值实验表明，对于窄带宽大规模的广义特征值问题，该分治算法明显优于LAPACK软件包．结合并行性好的多分法，在分布式环境下获得了很好的并行效果．     

求解带状线性方程组的一种并行算法

提出了一种在MIMD分布式存储环境下求解带状线性方程组的交替方向迭代并行算法。利用系数矩阵的结构特点分裂矩阵,使整个计算过程只在相邻处理机间通信两次。给出了系数矩阵分别为Hermite正定矩阵和M-矩阵时算法收敛的充分条件。最后,在HP rx2600集群系统上进行的数值计算表明,该算法与多分裂方法相比具有较高的加速比和并行效率。     

带状线性方程组的并行交替方向算法

提出了分布式存储环境下求解带状线性方程组的并行交替方向迭代算法。充分利用系数矩阵的结构特点,给出了在系数矩阵分别为Hermite正定矩阵和M-矩阵时算法的充分条件,并针对采用的分裂方式,讨论了参数的收敛范围,最后在HPrx2600集群系统上进行了数值计算,结果表明实算与理论相一致,算法简便可行且具有良好的并行性。     

求解实对称带状矩阵特征值问题的一种分治算法

gi．引言考虑矩阵特征值问题AX二AX，其中A是半带宽为则1＜，＜＜。）的。Xu实对称带状矩阵，表示如下：即a；j二民当k－j＞，求解上述问题的经典算法是：先用稳定的正交变换（Householder变换或Gi、us变换）将带状矩阵三对角化，然后，用QR算法求对称三对角矩阵的特征对．经典算法的缺点是并行实现困难，尤其是分布式并行机上难度更大．文＊3］提出的同伦分治算法速度快，并行效率高，但它仅适合对称三对角矩阵．本文推广K3］的结果，提出求解实对称带状矩阵特征值问题的一种同伦分治算法．92．算法的理论背景把矩阵A划分如下：其中A…     

解实对称矩阵特征值问题的并行算法

51．二分／多分法二分／多分法（BS／MS）是当前最常用的解实对称矩阵特征值问题的并行算法．这个算法也可解Hermitian矩阵的特征值问题、实对称矩阵和Hermitain矩阵的广义特征值问题，更适用于解实对称三对角线矩阵特征值问题．丑．1实对称三对角经矩阵特征值问题假设实对称三对角线矩阵T为T的A矩阵T－Al的各级前生子式p朴），i二01，2，…，。可用三项递推公式产生其中见由一det（T－Al）．序列只（A），i一01，…，n具有Sturm序列性质；即序列的相邻项符号不同数等于T的小于人的特征值个数．在实际计算时，因为只（A）容易上、下…     

带状线性方程组的含参交替方向并行算法

在MIMD分布式存储环境下针对系数矩阵为带状或块三对角矩阵的线性方程组提出了含三参数交替方向迭代并行算法。通过引入三参数调整,并适当分裂系数矩阵得到新算法,给出了系数矩阵为若干特殊矩阵时算法的收敛条件。在HP rx2600集群系统上实现了算法,针对不同的算例将其与多分裂方法、BSOR方法和PEk内迭代方法进行了比较。并行计算结果表明,所提算法具有较高的加速比和并行效率,明显优于多分裂方法和PEk方法,能合理分配内存,从而有效节省计算时间。针对算例1,加速比和计算效率略优于BSOR方法;而算例2的结果明显优于PEk内迭代方法。     

求实对称矩阵部分特征值的并行算法

提出了并行求解实对称稠密矩阵部分特征值的反幂法的预处理方法.该方法基于带状矩阵特征问题反幂法的信息传递复杂度低的特点,采用Householder变换并行算法约化大型实对称稠密矩阵为一定带宽的带状矩阵,针对带状矩阵用反幂法求解矩阵的在某一点的近似特征值;其中针对反幂法迭代中遇到的线性方程组,采用文献中的并行预处理共轭梯度算法求解.最后在Lenovo深腾1800集群上进行数值实验,并与预处理前反幂法的计算结果进行了比较,实验结果表明,经过预处理后的并行性远高于直接采用反幂法的并行性.     

基于曙光并行机的超大规模非线性方程组并行算法研究

该文讨论了一类求解大规模非线性方程组算法的并行性能及其在曙光并行机上的实现过程，与传统的算法不同之处是用一个块对角矩阵作为迭代矩阵，且该矩阵可由一个仅包含向量内积和矩阵与向量乘积的递推关系简便计算得到，在对算法进行描述之后，分析了算法的并行加速比和存储需求，讨论了算法在基于消息传递的MPI并行环境下的实现流程，数值计算表明理论分析与数值结果相比，算法在分布式并行环境下具有有较好的并行主攻较低的存储要求，可适用于大规模科学与工程的高性能计算。     

对称矩阵三对角化的有效并行块算法设计

在矩阵数值计算中,块算法通常比非块算法更有效,但这也增加了并行算法设计和实现的难度．在广义稠密对称矩阵特征问题并行求解器中,并行块算法的构造可应用到正定对称矩阵的Choleski分解、对称矩阵的三对角化和回代转化(back-transiation)操作中．本文将并行块算法的讨论集中在具有代表性的对称矩阵三对角化上,给出在非块存储方式下对称矩阵三对角化的并行块算法设计方法．分析块算法大小同矩阵规模和处理器数量的关系．在深腾6800上的试验表明,我们的算法具有很好的性能,并得到了比ScaLAPACK更高的性能．     

高效的带状线性方程组分布式并行算法

提出了一种新的带状线性方程组的分布式并行算法(New Distributed Parallel Algorithm for Banded Linear Equations,简称为NDPAB算法)。当带状线性方程组的系数矩阵满足对角占优时,算法在运行过程中不会中断,算法的加速比接近于处理器数目。给出了基于局域网的MPI异构环境下数值实验结果,数值实验结果表明算法是高效的。     

PARALLEL ALGORITHMS TO COMPUTE THE EIGENVALUES AND EIGENVECTORS OFSYMMETRIC TOEPLITZ MATRICES∗

Abstract

In this paper we present two parallel versions of bisection method to compute the spectrum of symmetric Toeplitz matrices. Both parallel algorithms have been implemented and analysed on a virtual shared memory multiprocessor using a portable message-passing environment. The algorithms very efficiently parallelize the sequential method, and the application of a dynamic strategy to distribute the computations produces better results than the use of a static method. We also improve the performance of the original sequential algorithm by applying Newton's method for the final approximation of the eigenvalues. However, the bad results of the sequential algorithm produce low speedups when we compare the parallel methods with the best available sequential algorithm.     

计算实对称矩阵广义特征值问题的并行算法

矩阵广义特征值问题是科学计算与工程应用中的一个重要的研究课题。文章探讨了近年来计算对称矩阵广义特征值问题的并行算法,并着重介绍了二分法、分治算法、同伦连续法和迭代算法。     

用割线法迭代求解对称三对角矩阵特征值问题

为对称三对角矩阵特征值问题，提出一种新的分而治之的算法。新算法以二分法，割线法迭代为基础，不同于Ｃｕｐｐｅｎ的方法和Ｌａｎｇｕｅｒｒｅ迭代法。理论分析和数据实验的结果表明：新算法的收敛速度明显比文［１］中的Ｌａｇｕｅｒｒｅ迭代法快。     

A parallel Lanczos method for symmetric generalized eigenvalue problems

The Lanczos algorithm is a very effective method for finding extreme eigenvalues of symmetric matrices. In this paper, we present our parallel version of the Lanczos method for symmetric generalized eigenvalue problem, PLANSO. PLANSO is based on a sequential package called LANSO which implements the Lanczos algorithm with partial reorthogonalization. It is portable to all parallel machines that support MPI and it is easy to interface with most parallel computing packages. Through numerical experiments, we demonstrate that it achieves similar parallel efficiency as PARPACK, but uses considerably less time. Received: 21 January 1998 / Accepted: 10 June 1999     

求对称方阵特征值的一种快速并行算法

该文针对经典雅可比算法求对称矩阵特征值不但要选主元素,而且还要同时进行行、列旋转变换、数据相关关系复杂、额外计算开销大、不易并行的缺点,提出了一种基于矩阵单侧旋转的算法并对此算法进行分析。最后通过该算法在PC机和分布式存储的大规模并行处理机曙光1000上的实验数据对比验证了该算法的性能较雅可比算法优越。     

计算广义实对称三对角矩阵特征值问题的分治算法

关于广义实对称三对角矩阵特征值问题的计算，本文提出了一个新的分治算法。该算法以二分法、割线法迭代为基础，采用分而治之策略。理论分析和数据试验结果表明：该算法的收敛速度快，可以节省大量的计算时间。     

MPI动态负载平衡策略的研究与实现

集群环境下的并行计算越来越被广泛应用,MPI是集群系统中最重要的编程工具。在并行处理过程中,负载平衡起着很重要的作用,它直接影响到整个算法的效率。文中结合MPI编程环境下的具体特点,提出了基于负载益处估价的方法来判断是否进行任务迁移,给出了负载实时监测和调度的算法,并在每个节点机上间隔性地进行测试。最后在搭建的MPI环境下,运用并行排序方法进行了验证。实验结果表明采用负载前后有了很明显的提高,特别是随着任务量不断增大的情况下提高的效果更加明显。     

SMP集群系统上矩阵特征问题并行求解器的有效算法

对称矩阵三对角化和三对角对称矩阵的特征值求解是稠密对称矩阵特征问题并行求解器的关键步 .针对SMP集群系统的多级体系结构,基于Householder变换的矩阵三对角化和三对角矩阵特征值问题的分而治之算法,给出了它们的MPI OpenMP混合并行算法 .算法研究集中在SMP集群系统环境下的负载平衡、通信开销和性能评价 .混合并行算法的设计结合了粗粒度线程并行模式和任务共享的动态调用方法,改善了MPI算法中的负载平衡问题、降低了通信开销 .在深腾6800上的实验表明,基于混合并行算法的求解器比纯MPI版本的求解器具有更好的性能和可扩展性 .     

The extreme eigenvalues and stability of real symmetric intervalmatrices

A novel Khoritonov-like algorithm for computing the minimal and maximal eigenvalues of n×n dimensional symmetric interval matrices is presented. It is proved that the maximal eigenvalue of a given set of interval matrices coincides with the maximal eigenvalue of a special set of 2^n-1 symmetric vertex matrices, whereas its minimal eigenvalue coincides with the minimal of another special set of 2^n-1 symmetric vertex matrices. As immediate corollaries of this algorithm, weak necessary and sufficient conditions for testing the Hurwitz and Schur stability of symmetric interval matrices, where one has to test the stability of 2^n-1 and 2ⁿ symmetric vertex matrices, respectively, are obtained