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

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

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

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

近似三对角Toeplitz方程组的快速分布式并行算法

利用近似三对角Toeplitz矩阵的特殊结构,提出了一种新的求解近似三对角Toeplitz方程组的快速算法．在三对角Toeplitz矩阵的近似LU分解的基础上,利用“分而治之”的思想,并结合秦九韶技术和特殊的数学技巧减少大量的冗余计算,提出了求解近似Toeplitz三对角方程组的快速分布式并行算法,并在理论上证明了算法具有近似于线性的加速比．最后通过数值实验证明,新的并行算法具有较高的并行效率,并且当矩阵阶数n足够大时,算法的加速比趋近于线性加速比．     

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

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

基于瓦片算法的并行 QR 分解及其实现

本文介绍了一种基于瓦片算法的稠密矩阵并行 QR 分解及其实现方法。瓦片算法的思想是将完整的矩阵分块,并使每个块内的数据连续存储。各个瓦片块先独立进行分解,其他块接收当前块分解产生的数据,来更新自身块内的矩阵。我们分别实现了串行瓦片算法和并行瓦片算法,采用基于 MPI 和 OpenMP 混合并行编程模型,在“元”超级计算机上验证了该并行算法,并与 PLASMA 软件包进行对比,程序效率和可扩展性优于 PLASMA。 在多个节点上运行时,展现了良好的扩展性。     

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

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

A Parallel Genetic Algorithm for Solving the Container Loading Problem

This paper presents a parallel genetic algorithm (PGA) for the container loading problem with a single container to be loaded. The emphasis is on the case of a strongly heterogeneous load. The PGA follows a migration model. Several separate sub-populations are subjected to an evolutionary process independently of each other. At the same time the best individuals are exchanged between the sub-populations. The evolution of the different sub-populations is carried out on a corresponding number of LAN workstations. The quality of the PGA is demonstrated by an extensive comparative test including well-known reference problems and loading procedures from other authors.     

一种求解TSP问题的并行遗传算法

遗传算法(GA)是一种基于自然群体遗传机制的有效搜索算法,由于它在搜索空间中同时考虑许多点,这样就减少了收敛于局部极小的可能,也增加了处理的并行性。因此可以利用并行遗传算法(PGA)研究典型的组合优化实例-TSP问题的求解问题。该文提出一种有效的并行算法求解旅行商(TSP)问题,实验结果表明,该方法在解的精度上优于以前的算法。     

A Coarse-Grained Parallel Algorithm for the All-Substrings Longest Common Subsequence Problem

Given two strings A and B of lengths n_a and n_b, respectively, the All-substrings Longest Common Subsequence (ALCS) problem obtains, for any substring B' of B, the length of the longest string that is a subsequence of both A and B'. The sequential algorithm for this problem takes O(n_a n_b) time and O(n_b) space. We present a parallel algorithm for the ALCS problem on the Coarse-Grained Multicomputer (BSP/CGM) model with p < √n_a processors, that takes O(n_a n_b/p) time, O(log p) communication rounds and O(n_b √n_a) space per processor. The proposed algorithm also solves the basic Longest Common Subsequence (LCS) problem that finds the longest string (and not only its length) that is a subsequence of both A and B. To our knowledge, this is the best BSP/CGM algorithm in the literature for the LCS and ALCS problems.     

三对角矩阵的行列式的并行计算方法

文章针对三对角矩阵,利用矩阵的Schur余子式求矩阵行列式的方法,提出了一种并行求解三对角矩阵及其逆的行列式的算法,应用该算法可以得到较好的加速度。     

背包问题无存储冲突的并行三表算法

背包问题属于经典的NP难问题，在信息密码学和数论等研究中具有极重要的应用，将求解背包问题著名的二表算法的设计思想应用于三表搜索中，利用分治策略和无存储冲突的最优归并算法，提出一种基于EREW-SIMD共享存储模型的并行三表算法，算法使用O（2^n/4）个处理机单元和O（2^3n/8）的共享存储空间，在O（2^3n/8）时间内求解n维背包问题．将提出的算法与已有文献结论进行的对比分析表明：文中算法明显改进了现有文献的研究结果，是一种可在小于O（2^n/2）的硬件资源上，以小于O（2n/2）的计算时问求解背包问题的无存储冲突并行算法。     

背包问题的最优并行算法

利用分治策略,提出一种基于SIMD共享存储计算机模型的并行背包问题求解算法.算法允许使用O(2^n/4)^1-ε个并行处理机单元,0≤ε≤1,O(2^n/2)个存储单元,在O(2^n/4(2^n/4)^ε)时间内求解n维背包问题,算法的成本为O(2^n/2).将提出的算法与已有文献结论进行对比表明,该算法改进了已有文献的相应结果,是求解背包问题的成本最优并行算法.同时还指出了相关文献主要结论的错误.     

A Parallel Implementation of the Push-Relabel Algorithm for the Maximum Flow Problem

We describe an efficient parallel implementation of the push-relabel maximum flow algorithm for a shared-memory multiprocessor. Our main technical innovation is a method that allows the "global relabeling" heuristic to be executed concurrently with the main algorithm; this heuristic is essential for good performance in practice. We present performance results from a Sequent Symmetry for five input distributions. On these five input distributions we achieve speedups in the range 6.2-8.8 with 16 processors, relative to the parallel program with 1 processor (4.1-7.2 when compared to our best sequential program). We consider these speedups very good and we provide evidence that hardware effects and insufficient parallelism in certain inputs are the main obstacles to achieving better performance.     

A Parallel Elimination Method for "Periodic" Tridiagonal Systems

We extend the elimination method of Chawla and Khazal [1] to uncouple partitioned blocks of "periodic" tridiagonal linear systems. At each step of the elimination stage, we now need three simultaneous eliminations: within each block, one usual forward elimination and one backward elimination from across the succeeding block, and one elimination in the last row of the last block. An interesting feature of the present elimination procedure is that at the end of it, the property of periodicity of the original system is now passed on to the core system . Once the core system is solved, the blocks uncouple and the solution is obtained in parallel from each block by back substitution. For a system of size N , the classical elimination has an arithmetical operations count of 17N . A best serial algorithm, based on the Sherman-Morrison formula, has an operations count of 0 14N . The present parallel elimination algorithm, employing p partition blocks, has an operations count of O 17N p and, in comparison with the Sherman-Morrison algorithm, it can achieve an efficiency of nearly 82% on a p -processor machine.     

循环三对角线性方程组的一种分布式并行算法

１．引 言 循环三对角线性方程组的求解是诸多应用问题的重要组成部分．例如,周期的样条插值就导致对角占优的循环三对角线性方程组的求解［１］,当边界条件为周期边界条件时,一些偏微分方程的离散化也可能导致循环三对角线性方程组的求解．适应计算机体系结构发展的此类方程组的算法研究,是数值并行算法的重要问题之一．文献［２］讨论了适用于共享主存并行机的此类方程组的并行算法,在 Ｍｌｌｅｒ和 Ｓｃｈｅｅｒｅｒ［３］提出的并行化Ｈ对角线性方程组解法的划分方法基础上,Ｃｈｕｎｇ［４］等对循环块三对角线性方程组进行了研究…     

A Parallel Solver for Circulant Toeplitz Tridiagonal Systems on Hypercubes

Solving circulant Toeplitz tridiagonal systems arises in many engineering applications. This paper presents a fast parallel algorithm for solving this type of systems. The number of floating-point operations required in our algorithm is less than the previous parallel algorithm [cf. Kim and Lee (1990)] for solving the similar system. Specifically, an overlapping technique is proposed to reduce the communication steps required. In addition, an error analysis is given. The implementation of our algorithm on the nCUBE2/E with 16 processors has been carried out. The experimental results show that the speedup is almost linearly proportional to the number of processors.     

解非等同并行多机调度问题的并行遗传算法

针对最小化完工时间的非等同并行多机调度一类问题,提出了一种混合遗传算法。该算法根据问题的特点,采用一种自然编码方案,此编码与调度方案一一对应,并对初始种群、交叉和变异等方法进行了研究。在鉴于遗传算法自然的并行性特点的基础上,实现了主从式控制网络模式下并行混合遗传算法。计算结果表明,并行混合遗传算法是有效的,优于启发式算法和遗传算法,有着较高的并行性,能适用于大规模非等同并行多机调度问题。     

易腐物品车辆路径问题的并行遗传算法

本文采用并行遗传算法研究了易腐物品的车辆路径问题。通过设计粗粒度并行遗传算法和交叉、变异等算子,提高了算法的计算效率和性能。最后,以计算示例验证了算法的有效性。     

用并行遗传算法解列车控制问题

遗传算法是一种全局优化的数值计算方法,它存在自然并行性。给出一种解列车控制问题的并行遗传算法,并讨论算法中一些技术问题。