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

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

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

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

离散H∞滤波系统最优范数计算的特征值算法

基于Riccati方程解的存在条件，建立了离散系统H∞江波问题的最优范数γopt与相关的Hamiltonian差分方程一阶特征值，以及矩阵广义特征值问题一阶特征值之间的对应关系，根据这一关系可以用求解特征值问题的算法计算最优H∞范数，由于仅需计算一阶特征值，所以可用扩展Wittrick-Williams算法求解这一问题。     

计算对称带状矩阵特征值问题的并行二分／多分法

文中提出了在分布式环境下并行求解对称带状矩阵特征值问题的并行二分．多分法及其改进,该算法利用变形高斯消去法计算对称带状矩阵的Sturm序列,并利用Rayleigh商迭代对二分／多分法加以改进,在算法的并行执行过程中,各处理机间不需通信,特别适用在分布式环境下的并行计算,最后给出了数值实验结果。     

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

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

离散H∞滤波系统最优范数计算的特征值算法

基于Riccati方程解的存在条件,建立了离散系统H_∞滤波问题的最优范数γopt与相关的Hamiltonian差分方程一阶特征值,以及矩阵广义特征值问题一阶特征值之间的对应关系.根据这一关系可以用求解特征值问题的算法计算最优H_∞范数.由于仅需计算一阶特征值,所以可用扩展Wittrick-Williams算法求解这一问题.     

基于机群的求解TSP问题的分布式演化算法

讨论一种基于PC机群的术解TSP问题的分布式演化算法．在PVM环境下进行了数值实验，结果表明该算法在一定的扩展范围内可以得到接近线性加速比的性能．     

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

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）容易上、下…     

特征值问题的算法、复杂性及并行实现

51．引言代数特征值问题是数值计算中的一个重要组成部分l‘－‘］，也是计算数学中的难点．它在许多科学与工程计算领域中有广泛的应用，如在物理中，分析晶体的电子结构，生物物理中，蛋白质和DNA的计算过程等都需要广义特征值问题的求解．因此，有效地求解此问题不仅在计算理论上有价值，而且在实际应用中更为重要．这里要讨论的广义特征值问题可以写成如下形式：＊V二＊＊D，队I）其中AB是mx。对称矩阵，且B是正定的，V是特征向量构成的矩阵，D是由特征值构成的对角矩阵．由于矩阵B是对称正定的，因此可以进行Cholesky分解，即存…     

一个基于网格服务的分布式关联规则挖掘算法

分布式关联规则挖掘在知识发现中占着不可忽视的地位，在以往分布式算法的基础上提出了一个加优先权值的PDDM算法，并将修改后的算法与抽样算法、知识网格的思想相结合形成一个GDS算法．GDS算法改善了以往分布式算法中通信量过载，算法难于扩展的问题，而且只扫描一遍数据库，减缓了大数据集挖掘中的I／O问题．理论分析和试验结果表明提出的算法是有效可行的．     

Resolving small random symmetric linear systems on graphics processing units

This paper focuses on the resolution of a large number of small random symmetric linear systems and its parallel implementation in single precision on graphics processing units (GPUs). The computations involved by each linear system are independent from the others, and the number of unknowns does not exceed 64. For this purpose, we present the adaptation to our context of largely used methods that include: LDLt factorization, Householder reduction to a tridiagonal matrix, parallel cyclic reduction (PCR) that is not a power of two and the divide and conquer algorithm for tridiagonal eigenproblems. We not only detail the implementation and optimization of each method, but we also compare the sustainability of each solution and its performance which include both parallel complexity and cache memory occupation. In the context of solving a large number of small random linear systems on GPUs with no information about their conditioning, our research indicates that the best strategy requires the use of Householder tridiagonalization + PCR followed if necessary by a divide and conquer diagonalization.     

循环赛日程表的递归和非递解

介绍了算法设计技术分治法的应用。使用分治法实现了循环赛日程表的递归和非递归解，并作了较为详细的说明，供《算法设计与分析》课程教学参考。     

循环赛日程表的递归和非递解

介绍了算法设计技术分治法的应用。使用分治法实现了循环赛日程表的递归和非递归解,并作了较为详细的说明,供《算法设计与分析》课程教学参考。     

空间叠加分析中的分而治之算法研究与应用

土地利用现状数据由CAD格式转换为GIS格式后需重新为图斑对象设置土地分类编码属性,为了提高海量空间数据情况下自动赋值的效率,研究了将分而治之算法应用于海量数据空间叠加分析以提高效率的方法。研究表明,对于所有需通过空间叠加分析来确定不同图层空间对象间的空间关系的问题,均可以采用分而治之方法来降低时间复杂度。在最小化分割的情况下,基于四叉树空间索引,分而治之算法可以使此类应用的时间复杂度降低为O（n lb n）。实际应用验证了该方法在海量空间数据处理中的效率和实用价值。     

油井管道问题的分治解法

分治算法是解决许多实际问题的重要而有效的方法。该文首先对油井的管道问题进行了分析,然后提出一种基于分治策略的解决方案,并给出了其实现算法,最后对所提出算法的复杂度进行了分析。     

基于分治法求解对称三对角矩阵特征问题的混合并行实现

基于对称三对角矩阵特征求解的分而治之方法,提出了一种改进的使用MPI/Cilk模型求解的混合并行实现,结合节点间数据并行和节点内多任务并行,实现了对分治算法中分治阶段和合并阶段的多任务划分和动态调度.节点内利用Cilk任务并行模型解决了线程级并行的数据依赖和饥饿等待等问题,提高了并行性;节点间通过改进合并过程中的通信流程,使组内进程间只进行互补的数据交换,降低了通信开销.数值实验体现了该混合并行算法在计算效率和扩展性方面的优势.     

Local learning framework for handwritten character recognition

This paper proposes a general local learning framework to effectively alleviate the complexities of classifier design by means of “divide and conquer” principle and ensemble method. The learning framework consists of a quantization layer which uses generalized learning vector quantization (GLVQ) and an ensemble layer which uses multi-layer perceptrons (MLP). The proposed method is tested on public handwritten character data sets, which obtains a promising performance consistently. In contrast to other methods, the proposed method is especially suitable for a large-scale real-world classification problems although it is easily scaled to a small training set while preserving a good performance.     

面向漏洞挖掘的基于符号分治区的测试用例生成技术

在漏洞挖掘中,符号执行技术是一种常用的测试用例生成技术。但当软件中包含加解密、校验和检验等复杂数学运算函数时,使用符号执行技术生成测试用例存在无法有效求解约束表达式的问题,导致漏洞挖掘效率低下。针对该问题,文章结合分治算法的思想提出基于符号分治区的测试用例生成技术。首先通过静态分析技术识别软件中的加解密、校验和检验等函数;然后以程序中的加解密、校验和检验函数为分界点对软件进行分区,符号执行引擎每执行到软件的一个分治区,就在本区引入一个新的符号变元进行约束构建,在约束求解时从软件最后一个分治区开始递归求解。基于该方法,文章在符号执行平台S2E上实现了漏洞挖掘原型系统Divide,并与现有的符号执行生成测试用例技术进行对比实验。实验结果表明,文章方法能够快速、有效地生成测试用例,提高漏洞挖掘的效率。     

Simultaneous band reduction of two symmetric matrices

In this paper, we consider simultaneous band reduction of two dense symmetric matrices by congruent transformations. The ideas of simultaneous tridiagonalization are generalized to propose an efficient algorithm for the simultaneous band reduction. In contrast to the algorithms of simultaneous tridiagonalization which are mainly based on matrix–vector operations, the proposed algorithm of simultaneous band reduction has the advantage that matrix–matrix operations can be fully used to achieve better performance on modern computer architecture. Numerical results are presented to illustrate the effectiveness of our proposed algorithm.