A block varaint of the GMRES method for unsymmetric linear systems

Iterative methods that take advantage of efficient block operations and block communications are popular research topics in parallel computation. These methods are especially important on Massively Parallel Processors (MPP). This paper presents a block variant of the GMRES method for solving general unsymmetric linear systems. It is shown that the new algorithm with block sizes, denoted by BVGMRES (s.m), is theoretically equivalent to the GMRES (s·m) method. The numerical results show that this algorithm can be more efficient than the standard GMRES method on a cache besed single CPU computer with optimized BLAS kernels. Furthermore, the gain in efficiency is more significant on MPPs due to both efficient block operations and efficient block data communications. Our numerical results also show that in comparison to the standard GMRES method, the more PEs that are used on an MPP, the more efficient the BVGMRES(s,m) algorithm is.     

基于科学计算组件规范的高性能大地电磁正演模型研究*

为了提高基于有限元法构建的大地电磁正演模型的计算性能,以及解决模型计算的复杂性问题,提出了一种基于美国新近提出的大规模科学计算领域组件规范CCA(Common Component Architecture)构建的组件化分布式并行大地电磁正演MT模型。首先,基于CCA规范定义MT组件服务端口,定义MT组件; 其次,采用有限元方法将Maxwell方程离散为线性系统,采用GreenField算法对其求解,设计了一种频率域分解策略实现了一个分布式并行MT模型;最后,采用Babel编译生成了一个分布式并行MT模型组件。实验结果表明,该方法所构建的MT模型组件具有较高的计算性能、灵活性和可扩展性。     

大规模电力系统离散无功优化问题的解耦算法

根据节点分裂法将大规模电力系统的离散无功优化模型转化成多区域分解形式,再采用引入离散惩罚的非线性原对偶内点法求解,从而获得具有分块结构的降阶线性修正方程组。对弱耦合系统,直接将非对角子矩阵置零即可实现修正方程的完全解耦,算法具有局部线性收敛特性,且其计算速度要比非线性原对偶内点法快。对于不能实现解耦的强耦合系统,仍然可以采用与处理弱耦合系统类似的方法获得近似牛顿方向和解耦对角矩阵,以它们作为迭代初值和预处理器,采用GMRES法求解,保证算法具有良好的收敛性和较快的计算速度。以1062节点系统和一个实际538节点系统作为试验系统验证所提算法的有效性,进一步提出较实用的解耦判据,并对集中连续优化、集中离散优化及解耦离散优化结果进行了比较以及对不同分解方案下的计算结果进行了比较分析。     

多层快速多极子分析三维复杂目标的谐振区电磁散射特性

用多层快速多极子方法（MLFMA）和预优的广义最小残差法（GMRES）计算了三维复杂目标的谐振区电磁散射特性。对于在谐振区中5～10个波长目标的电磁散射体,MLMFA比矩量法（MOM）和快速多极子法（FMM）占用内存少很多,计算速度也更快;本文讨论了MLFMA中重要参数多极子数L的优化选取,同时采用了预优的GMRES方法求解MLFMA大规模矩阵方程,这比采用传统的共轭梯度（CG）法具有更大的优越性。最后对某导弹模型和典型隐身飞机模型进行了谐振区散射特性的高效求解分析。     

(2+1)维广义浅水波方程类孤子解和类周期解

在Riccati方程方法的基础上提出了新的广义投射Riccati方程展开法及其算法.该方法直接而有效,通过适当的变换将非线性发展方程转化为易于求解的微分方程组,从而可用来构造非线性发展方程更多新的精确解.利用这个方法研究了(2 1)维浅水波方程,并得到了许多新的精确解,其中包括类孤子解和类周期解.该算法可以用于构造其他更多非线性发展方程(组)的精确解.     

三维数值流形法覆盖系统并行分区生成算法

三维数值流形方法（three dimensional numerical manifold method,3D-NMM）是岩土工程数值模拟中强大的数值方法之一。但一直存在接触判断困难、计算处理数据量大,效率低等问题。将并行计算技术应用于三维数值流形方法覆盖系统生成可以有效提升其覆盖系统的生成效率。详细研究了并行编程模式下三维数值流形法覆盖系统的生成算法。基于MPI分布式内存编程原理,将分区覆盖生成作为三维数值流形法并行覆盖生成基本思路。先采用规则粗六面体网格覆盖问题域,并利用Metis划分网格形成负载基本均衡的子区域,在原有串行算法的基础上设计了子区域覆盖系统的生成算法。并基于分布式内存存储模式下不同区域间数据传递需求,对本并行算法建立了界面信息传递算法,用以并行计算过程不同区域间中数据交流。最后,使用C++开发了基于布尔运算的三维数值流形单元及覆盖系统并行生成算法。算例表明此并行覆盖系统生成算法可有效提高三维数值流形法覆盖系统的生成效率及其应用规模     

一类分数阶最优控制问题的高阶快速算法

分数阶扩散方程约束的分布式最优控制问题广泛地应用于科学和工程领域,包括优化设计、控制和参数识别;针对这类问题,提出了一种高阶的快速算法。对于求解该问题的一阶最优条件所产生的耦合两点边值问题,在空间上利用紧差分,时间上利用边值方法对该问题进行离散,离散后得到一个2×2块线性系统;然后使用带有Kronecker积分裂的迭代算法求解该线性系统,该算法是块状的Kronecker积结构,通过交替的Kronecker积分裂迭代方法得到了这个Kronecker积,并证明了该分裂迭代算法是收敛的;同时使用GMRES方法来加速Kronecker积分裂迭代的收敛;最后数值实验表明了该算法的精确性和计算效率。     

求解非对称线性方程组的预对称混合 GMRES 算法

对于非对称线性方程组Ax＝ b ,当A是正定可对称化矩阵时,利用预对称化技术和混合迭代技术,结合GM RES算法提出了一种新的预对称混合GM RES迭代算法,理论表明,新算法可以使迭代的收敛效果得到明显改善。数值例子表明该算法迭代次数要少于解非对称线性方程组的GM RES方法。     

Adomaint原理与线性方程组的网络并行计算

论证了广西大学龚仁喜教授,邓艳等基于Adom aint原理建立的线性方程组的求解方法与Jacob i迭代法理论上等价;基于其思想,给出了一种求解线性方程组的并行算法,并将1~16台PC机联网,分别安装W in-dows2000、PVM3.4和VC6.0以组建网络并行计算平台,并在该平台上编程对该算法进行了并行数值试验,算例计算结果(表1和表2)表明该算法具有较高的加速比和效率,适合大型线性方程组的并行求解.     

右端多项式预处理GMRES算法

利用GMRES(m)残量多项式的互补性理论定义矩阵M-1,对方程组进行右端预处理,建立了右端多项式预处理GMRES算法。并证明在一定条件下,M-1能有效地降低矩阵条件数,保证新算法的收敛效果。     

金字塔凸壳算法的并行化处理

提出了在金字塔凸壳算法基础上的并行算法.在由多个PC机相互连接所构成的机群并行计算系统之上,采用消息传递方式执行该算法,经过与原串行金字塔算法进行对比,验证本并行处理算法的正确性、可行性和高效性.     

加速广义极小残余新算法

研究了Krylov子空间广义极小残余算法（GMRES（m））的基本理论,特别是残余向量与Krylov子空间的关系．根据残余向量所满足的代数方程组,深入探讨算法的收敛性质与所选择的子空间的关系,指出大大量按模很小的特征值对应的特征向量的存在会降低算法的收敛速度,从而提出一种利用按模很小的特征值对应的特征向量扩充Krylov子空间的加速广义极小残余算法（AGMRES（m））、理论分析和数值结果都表明,算法是可靠和有效的．     

基于多核心工作站机群的并行介数算法

针对计算大规模复杂网络时介数的空间和时间复杂度问题,根据网络数据的存储特点,设计了减少内存占用并能提高查找速度的数据结构.根据介数计算的特点,用Python语言设计了粗粒度并行算法,在多核心工作站机群实现了并行算法.实验结果表明:并行算法不仅能够适用于上亿条边规模的网络,而且能够获得线性加速比,使120个计算核心的加速比达到了71左右,为分析大规模复杂网络数据的特性提供了易操作的方案.     

循环GMRES算法实现中的耦合分析

为了得到循环GMRES算法的高效实现方法,将循环GMRES算法的两个主要过程看作子系统,并考察子系统的不同耦合方式对整体系统的影响。给出了循环GMRES算法的弱耦合向量化实现。实验表明,在向量编程环境中循环GMRES算法的弱耦合实现效率更高,编程也更容易。     

基于多Agent协同构建分布式并行遗传算法

针对并行遗传算法中计算资源的分配问题 ,提出了分布式并行遗传算法结构。它由若干计算节点组成 ,每个节点包含若干运行子遗传算法的计算单元。节点的计算能力依照一定的并行模式映射到单元 ;各子算法则根据一定的拓扑结构进行个体交换。从多 Agent系统的观点看 ,计算单元是独立的 Agent,其并行运行涉及计算资源的分配 ,体现了算法对它们的协调 ;个体的迁移体现了它们之间的协作。并且分析了由两个单元构成的算法在不同并行模式和不同个体迁移因子下的性能。     

可靠性分析的并行不交和算法

不交和算法是计算网络可靠性的有效方法，到目前为止，基于这一方法已经开发出多种算法，提出了对这些不交和算法实行并行化的通用框架，基于这个框架，在工作站网络上实现CAREL不交和算法的并行化版本，实验结果表明，这种方法效果很好，几乎得到线性加速。     

一种基于并行计算熵迁移策略的多分辨DOM数据生成算法

数字正射影像图(digital orthophoto map,DOM)数据通常以多分辨数据形式组织,并以切片的方式存储,而海量多分辨DOM数据的生成需要大量计算和大容量存储.针对此问题,提出一种基于并行计算熵迁移策略的并行多分辨DOM数据生成算法,以减少海量多分辨DOM数据的生成时间.该算法采用并行计算熵来衡量并行计算机系统的负载平衡程度,并以此判断何时需要进行负载迁移以及如何迁移.仿真实验表明,与串行算法相比,该算法能有效减少程序执行时间,并且能获得较高的加速比和并行效率.     

多序列比对问题的并行近似算法

基于中心方法的思想,采用分治策略,在SIMD-CREW模型上设计了一个使用O(k2m)个处理器(其中k为序列个数,m为最长的序列长度),时间复杂度为O(m logk)的并行近似算法.在实际情况中,由于logk远远小于m,相对于时间复杂度为O(m2k2)的串行中心方法,该算法在理论上达到线性加速.与现有的并行算法相比,它可以适用于任意情况,且易于分析时间复杂度.利用LARPBS模型的特点和并行求前缀和的方法,调用LARPBS模型上求和与最大(小)值的并行算法,首次给出了在LARPBS模型上的多序列比对问题的并行近似算法.该算法使用O(k2m)个处理器,时间复杂度为O(m log log D),其中D为序列两两比对的代价值的最大值.该算法同样适用于任何情况,由于log log D通常远小于m,所以它在理论上也是线性加速的.     

一种网上求解线性方程组的Guass-Seidel并行迭代算法

针对基于PVM的微机网络并行计算环境下,处理机的运算速度较快而处理机间的通信相对较慢的实际情况,给出了一种网上并行求解线性方程组的Guass-Se idel迭代算法。该算法将方程组的增广矩阵按行卷帘方式分布存储在各处理机中,循环传送每一次的迭代向量以减少处理间的通信次数,同时,采用计算与通信部分重叠技术,提高并行算法的效率。并用1~12台桌面PC机联成的局域网,在PVM 3.4 on W indows2000,VC 6.0并行计算平台上编程对该算法进行了数值试验,试验结果表明,该算法较传统的基于列扫描法的Guass-Se idel并行迭代算法优越。     

基于CUDA架构并行算法的带地形AMT二维反演实现与应用

并行计算是提高音频大地电磁（audio-frequency magnetotelluric method,AMT）数据反演效率的有效途径。本文在统一计算设备架构(compute unified device architecture,CUDA) 下开展带地形的AMT数据二维反演并行算法研究,旨在利用GPU强大的计算能力及并行计算技术实现高精度、快速度的AMT数据二维反演。首先利用有限元和自适应正则化反演算法实现AMT数据二维反演的串行化计算;然后在PGI Visual Fortran+ CUDA5.5环境下编写基于CPU+GPU的CUDA并行代码,将正演中的频率循环、反演中的模型灵敏度矩阵计算和反演方程正则化求解部分进行并行化处理;通过不同复杂程度的理论模型正反演模拟验证了该并行算法的有效性和准确性。不同模型和不同模式下的数值模拟结果对比表明,基于CPU+GPU的CUDA并行算法相较于传统的CPU串行算法,在灵敏度矩阵计算和反演方程正则化方面耗时更少,加速比最高可达10倍以上。最后将该并行算法应用于某矿区实测AMT数据的二维反演中,取得了较好的应用效果。