无约束最优化问题的BFGS并行算法与实现

介绍无约束最优化问题的BFGS算法及其收敛性,提出利用行卷帘格式并行Cholesky分解法、同步并行Wolfe-Powell非线性搜索和并行处理BFGS修正公式来构建BFGS的并行算法,并对该算法的时间复杂性、加速比进行分析。在PC机群数值实验的结果表明,BFGS并行算法提高了无约束最优化问题的求解速度,理论分析与实验结果相一致,并行算法具有线性加速比。     

PC机群环境下最短路径并行算法的研究

本文在PC机群环境下,研究了最短路径并行算法。在非循环图网络模型和强连通随机网络模型上对算法的加速比和并行效率进行了实验研究,讨论了在PC机群环境中提高并行性能的方法及不同网络规模和网络模型下算法的加速比和效率。     

整体异步的并行转换算法

针对Fukushima提出的求解无约束最优化问题的同步并行转换算法(PVT),提出一个整体异步并行算法,该算法去除了并行计算中同步与通信的开支。在一定的条件下,证明了该算法具有全局收敛性以及线性收敛速度。数值试验结果表明,异步PVT算法优于同步PVT算法。     

一种改进的全区域覆盖算法

针对Fukushima提出的求解无约束最优化问题的同步并行转换算法(PVT),提出一个整体异步并行算法,该算法去除了并行计算中同步与通信的开支.在一定的条件下,证明,该算法具有全局收敛性以及线性收敛速度.数值试验结果表明,异步PVT算法优于同步PVT算法.     

一种基于并行遗传算法的网格资源分配方法

提出了基于并行遗传算法的网格资源分配方法,并采用粗粒度模型设计了该并行算法。为了评估该并行算法的性能,在PC集群上实现了该并行算法和一个串行遗传算法。通过比较两个算法的执行时间和解的质量,说明了并行算法极大地提高了求解的速度和质量,是一种高效的资源分配方法。     

基于牛顿法的并行优化算法

针对非线性数值优化问题,提出一种在分布式环境下的基于牛顿法的并行算法。引入松弛变量,将不等式约束转换为等式约束,利用广义拉格朗日乘子将约束优化问题转换为无约束子优化问题。为了并行地求解这些子优化问题,将Newton迭代法中的Hessian矩阵进行适当的分裂,采用简单迭代法求解Newton法中的线性方程组。在理论上对该算法进行了收敛性分析。在HP rx2600集群上进行的数值实验结果表明并行效率达90%以上。     

并行环境下的同步异步PSO算法

并行计算能够有效地缩减求解大规模问题的时间.文中在介绍了粒子群算法(Particle Swarm Optimization algo rithm)的基础上,对PSO算法的同步异步模型进行分析,给出了并行环境下的同步异步PSO算法.该并行算法在联想深腾1800大型汁算机上测试.实验证明PSO算法具有较高的并行性,并行算法明显提高了求解的速度.     

基于有效并行求解策略的显式有限元分析并行算法

针对大规模结构非线性动力问题的有限元分析非常耗时,基于消息传递接口（MPI）机群环境,提出多种基于并行求解策略的显式有限元并行算法。基于显式消息传递的区域分解技术,采取重叠、非重叠区域分解技术及动态任务分配方法,通过将计算与通信重叠,优化处理器间的通信,对非重叠通信区域分解并行算法、重叠通信区域分解并行算法、群动态任务分配算法、动态任务分配算法及动态负载平衡算法进行研究。为在机群环境下实现非线性动力有限元分析,开发了基于有效并行求解策略的显式有限元并行算法。编写了基于消息传递编程模式的并行有限元程序,在工作站机群上实现了数值算例,分析了算法的性能,并与传统的Newmark算法进行了比较。算例表明：群动态任务分配算法的性能优于动态任务分配算法,低于区域分解算法的性能,动态负载平衡算法最优。对相同规模的问题提出的算法比Newmark算法快,优于Newmark算法。对结构非线性动力问题的有限元分析,所提出的并行算法是可行有效的。     

多处理机系统上求解非线性方程组的异步并行拟牛顿法

异步并行算法由于在任何时刻它的进程不等待输入,因而异步并行算法与同步并行算法相比效率高得多,但往往算法分析极为困难,本文给出了多处理系统上求解非线性方程组的一种异步并行拟牛顿算法,证明了其收敛性,数值试验例子表明该算法有较好的收敛速度。     

基于GEP的分形图像压缩并行算法

传统图像压缩算法存在图像压缩率不高、寻找最优分形图像压缩编码速度慢的不足。为此,提出一种基于基因表达式编程(GEP)的分形图像压缩并行算法。分析二值图像压缩变换的求解过程,给出分形图像基因和染色体的编码表示,设计适应度函数,研究GEP遗传进化操作的编码步骤。在PC机群上的实验结果表明,与串行算法相比,该算法的图像压缩率较高、运行速度较快,具有线性加速比。     

Parallel genetic algorithm for N-Queens problem based on message passing interface-compute unified device architecture

N-Queens problem derives three variants: obtaining a specific solution, obtaining a set of solutions and obtaining all solutions. The purpose of the variant I is to find a constructive solution, which has been solved. Variant III is aiming to find all solutions and the largest number of queens currently being resolved is 26. Variant II whose purpose is to obtain a set of solutions for larger-scale problems relies on various intelligent algorithms. In this paper, we use a master-slave model genetic algorithm that combines the idea of the evolutionary algorithm and simulated annealing algorithm to solve Variant III, and use a parallel fitness function based on compute unified device architecture. Experimental results show that our scheme achieved a maximum 60-fold speedup over the single-CPU counterpart. On this basis, a two-level parallel genetic algorithm based on the island model and master-slave model is implemented on the GPU cluster by using message passing interface technology. Using two-node and three-node GPU cluster, speedup of 1.46 and 2.01 are obtained on average over single-node, respectively. Compared with the sequential genetic algorithm, the two-level parallel genetic algorithm makes full use of the parallel computing power of GPU cluster in solving N-Queen variant II and improves the performance by 99.19 times in the best case.     

基于MIC集群平台的GMRES算法并行加速

广义极小残量法(GMRES)是最常用的求解非对称大规模稀疏线性方程组的方法之一,其收敛速度快且稳定性良好。Intel Xeon Phi众核协处理器(MIC)具有计算能力强、易编程、易移植等特点。采用MPI+OpenMP+offload混合编程模型将GMRES算法移植到MIC集群平台上。采用进程间集合通信异步隐藏、数据传输优化、向量化以及线程亲和性优化等多种手段,大幅提升了GMRES算法的求解效率。最后将并行算法应用到“局部径向基函数求解高维偏微分方程”问题的求解中。测试表明,CPU节点集群上开启32个进程,并行效率高达71.74%,4块MIC卡的最高加速性能可达单颗CPU的7倍。     

Asynchronous multisplitting relaxation methods for linear complementarity problems

To solve the linear complementarity problems efficiently on the high-speed multiprocessor systems, we set up a class of asynchronous parallel matrix multisplitting accelerated over-relaxation (AOR) method by technical combination of the matrix multisplitting and the accelerated overrelaxation techniques. The convergence theory of this new method is thoroughly established under the condition that the system matrix of the linear complementarity problem is an H-matrix with positive diagonal elements. At last, we also make multi-parameter extension for this new asynchronous multisplitting AOR method, and investigate the convergence property of the resulted asynchronous multisplitting unsymmetric AOR method. Thereby, an extensive sequence of asynchronous parallel relaxed iteration methods in the sense of multisplitting is presented for solving the large scale linear complementarity problems in the asynchronous parallel computing environments. This not only affords various choices, but also presents systematic convergence theories about the asynchronous parallel relaxation methods for solving the linear complementarity problems.     

Solving Linear Unconstrained Problems of Combinatorial Optimization on Arrangements Under Stochastic Uncertainty

Linear unconstrained problem of combinatorial optimization on arrangements under stochastic uncertainty is being solved. The minimum is defined as the result of sequential comparison of numerical characteristics of random variables. The properties of the solution of the optimization problem under study are obtained. These properties use the properties of special constructed deterministic problems. The authors also propose the reduction method to solve linear unconstrained problem of combinatorial stochastic optimization, which is based on obtained solution’s properties.     

基于BSP模型的大规模线性规划并行算法研究

在许多实际工程问题中经常遇到一些大型线形规划问题，通常的计算过程需要占用大量的计算时间，效率低下。文中提出了一种基于BSP模型的大规模线性规划并行算法——修正单纯形并行算法，分析了其代价函数和加速比，在所研制的集群计算机上进行了实现和测试。结果表明：当问题规模比较大时，此并行算法能获得较好的加速比。     

基于Spark的并行化头脑风暴优化算法及复杂多峰函数优化

头脑风暴优化BSO算法是一种新型的群体智能优化算法,启发于众人集思广益求解问题的模式,适合求解复杂多峰函数优化问题。但是,BSO求解多峰极值时需进行重复的迭代运算,面对大规模数据集时会出现计算效率与求解精度过低的现象。为解决上述问题,设计并实现了一种基于Spark的并行化头脑风暴优化算法,通过将BSO算法中计算复杂度最高的聚类与新解产生过程并行化,以提高算法的加速比与计算效率。特别地,基于并行化思想,将种群划分为多个子群进行协同演化,每个子群独立产生新解来保持种群多样性,提高算法的收敛速度。最后,利用并行化BSO算法求解多峰函数。实验表明,在并行节点的总核心数为10的情况下,并行化BSO算法计算时间节省一半,计算精度和串行BSO算法基本持平,收敛速度明显提高,实验结果说明了并行化BSO的有效性。     

Sequential and parallel algorithms for global minimizing functions with Lipschitzian derivatives

In this paper, sequential and parallel algorithms using derivatives for solving unconstrained one-dimensional global optimization problems are described. Sufficient conditions of convergence to all global minimizers are established for both methods. Parallel algorithm conditions, which guarantee significant speed up in comparison to the sequential version of the method, are presented. The sequential method is numerically compared with the algorithms of Breiman and Cutler, Pijavskii, and Strongin on a set of 20 test functions taken from literature. We also present results of numerical experiments illustrating the performance of the parallel method. All experiments have been executed on the parallel computer ALLIANT FX/80.     

A Parallel Block Scaled Gradient Method With Decentralized Step‐Size For Block Additive Unconstrained Optimization Problems Of Large Distributed Systems

In this paper, we propose a modified parallel block scaled gradient method for solving block additive unconstrained optimization problems of large distributed systems. Our method makes two major modifications to the typical parallel block scaled gradient method: First, we include a pre‐processing step which reduces the computational time; second, we propose a decentralized Armijo‐type step‐size rule. This rule circumvents the difficulty of determining a step‐size in a distributed computing environment and enables the proposed parallel algorithm to execute in a distributed computer network with a limited amount of data transfer. We have applied our method to the weighted‐least‐square problems of power system state estimation and demonstrated the convergence of our method by testing numerous examples on a PC network. The speedup ratio of the distributed version of our method tends to increase proportionally with the number of subsystems (or computers).