多重网格方法求解两类Helmholtz方程

详细给出了多重网格方法的实现过程,借助正定Helmholtz方程及不定Helmholtz方程的求解来探讨多重网格方法的特性。对多重网格V环、W环以及F环三种不同迭代格式的收敛效果进行了对比。通过正定Helmholtz方程的求解,发现多重网格的确有很高的计算效率。对于不定Helmholtz方程,随着波数的增加,利用多重网格方法得到结果不收敛,原因出在细网格光滑和粗网格矫正过程。如何针对此问题对多重网格进行有效改进还有待进一步研究。     

边缘海静力数值预报模式并行算法研究

边缘海静力数值模式是国内针对边缘海特点自主开发的数值预报模式,但该模式因物理求解方程较多且采用不宜并行化的SOR求解算法而程序计算时间过长。针对上述问题,提出基于三维网格和海洋模式特点的SOR并行求解算法,该算法在保留三维网格数据间依赖关系的同时,有效解决了SOR迭代算法难以并行化的问题。同时,引入通信避免算法,采用MPI非阻塞通信方式,细分计算和通信过程,利用计算有效隐藏通信开销,提高了并行程序效率。实验结果表明,并行后的边缘海静力数值模式程序的性能相对串行程序提升了60.71倍,3天(25920计算时间步)预报结果的均方根误差低于0.001,满足海洋数值预报的时效性和精度要求。     

基于光滑聚集代数多重网格的有限元 并行计算实现方法

基于光滑聚集代数多重网格法实现一种用于结构有限元并行计算的预条件共轭梯度求解方法。对计算区域进行均匀划分,将这些子区域分配给各个进程同时进行单元刚度矩阵的计算,并组合形成分布式存储的整体平衡方程。采用光滑聚集代数多重网格预条件共轭梯度法对整体平衡方程进行并行求解,在天河二号超级计算机上进行数值试验,分析代数多重网格的主要参数对算法性能的影响,测试程序的并行计算性能。试验结果表明该方法具有较好的并行性能和可扩展性,适合于大规模实际应用。     

大尺度图像编辑的泊松方程并行多重网格求解算法

随着获取设备的发展,大尺度、高分辫率数字图像已逐步进入人们的生活,大尺度图像的梯度域编辑显得更为重要,求解大规模未知数的泊松方程是大尺度图像梯度域编辑的关键。传统多重网格算法的迭代、约束和插值操作单独进行,内存和外存间通讯量大,算法效率低,为此提出了一种面向大尺度图像梯度域编辑的并行多重网格求解泊松方程的算法。该算法利用多重网格的迭代、约束和插值过程的内存数据访问局部性和更新相关性,构造滑动工作窗口,使迭代、约束和插值操作并行运行,提高了多重网格算法求解泊松方程的计算效率。全景图拼接实验表明,所提算法的运行效率高于超松弛迭代、高斯塞德尔迭代和传统多重网格算法。     

有限差分法的并行化计算实现

有限差分法是求解偏微分方程近似解的一种重要的数值方法。串行算法并不能高效的解决大规模复杂计算问题,并行化计算方法可提高复杂计算问题的效率,从而使并行机上计算有限差分问题成为可能。二维场中拉普拉斯方程的差分格式非常适合并行化方法的计算,将串行部分并行化以提高大规模计算的效率具有重要的现实意义。MPI(消息传递接口)是实现并行程序设计的标准之一。虚拟进程(MPI_PROC_NULL)的引用简化了MPI编程中的通信部分,串行算法可更改为并行化计算方法,最终实现有限差分方法的并行化计算。     

一种分布式的点球弹簧修匀法并行方案

针对非定常流体模拟中的网格变形问题,提出一种基于MPI的分布式并行的网格变形算法.算法对初始网格进行分区,并在分区之间构建共享单元层.在分区内采用点球弹簧修匀法(Vertex-Ball Spring Smoothing,VerBSS)对网格进行变形,相邻分区的边界通过通信进行同步.上述算法在求解过程中保留了节点之间的连接性和VerBSS离散求解的特征,具有较高的变形效率.算例结果表明,上述并行方案变形能力较强,并具有较高的并行效率,适合求解大变形、大规模的网格变形问题.     

一种基于PDD算法的ADI-FDTD算法研究

为提高隐含变向时域有限差分算法（ADI-FDTD）的计算效率,鉴于并行对角占优算法（PDD）求解三对角方程的高效性,引入PDD算法实现了基于MPI的ADI-FDTD的并行计算。通过对运算时间、通信时间的分析,讨论了算法的效率。分析了由于PDD算法的近似处理所引入的计算误差,研究了误差估计与子区域网格数和Courant因子的关系,该研究工作有利于合理选择子区域网格数和Courant因子,进而减小计算误差。最后,通过算例验证了结论的正确性。     

水质预报系统中垂向湍扩散并行算法实现研究

为了能更好地提高水质预报模式中物质输运方程的计算速率,以胶州湾数值预报系统中垂向扩散的串行算法为基础,提出了一种主要针对物质输运方程中的垂向扩散的MPI(message-passinginterface)并行算法。该算法将计算分解为多个子任务,并在基于MPI消息传递模式的集群系统中进行运算。与原串行算法进行比较,并行的加速比提高了33%以上,且并行效率最大可达90%,该结果表明了MPI技术在海洋数值模拟领域应用的潜力。     

预处理共轭梯度算法异构并行求解及优化

共轭梯度算法是求解对称正定线性系统的重要方法之一,该算法求解问题通常具有稀疏性.随着问题规模的不断增大,单CPU因其存储及计算能力限制已经不能满足大规模稀疏线性方程组求解的实时需求.基于此,本文提出一种基于CPU+GPU异构平台的MPI+CUDA异构并行求解算法.首先,对共轭梯度算法进行了热点性能分析,说明该算法求解时存在的计算困难及挑战;然后,根据共轭梯度算法特性进行了任务划分,实现异构并行算法设计;最后,针对异构并行算法中存在的通信开销、数据传输开销和存储器访问开销等问题,对异构并行算法进行优化以进一步提升求解效率及性能.实验结果表明,与MPI并行和CUDALib并行相比,MPI+CUDA异构混合并行在串行计算部分较少的Jacobi预处理共轭梯度算法上分别获得336%和33%的性能提升,在串行计算部分较多的ILU预处理共轭梯度算法上也能分别获得25%和7%的性能提升,同时结果还显示MPI+CUDA混合并行随着节点数目的增加具有一定可扩展性.     

求解跨音速势流的自适应并行多重网格算法

本文用并行Ｓｃｈｗａｒｚ方法求解了轴向大扰动、径向小扰动的跨音速势流方程，并用自适应多重网格算法作为整体修正。数值计算表明：自适应并行多重网格算法可使计算效率大为提高。     

Numerical performance of a parallel solution method for a heterogeneous 2D Helmholtz equation

The parallel performance of a numerical solution method for the scalar 2D Helmholtz equation written for inhomogeneous media is studied. The numerical solution is obtained by an iterative method applied to the preconditioned linear system which has been derived from a finite difference discretization. The preconditioner is approximately inverted using multigrid iterations. Parallel execution is implemented using the MPI library. Only a few iterations are required to solve numerically the so-called full Marmousi problem [Bourgeois, A., et al. in The Marmousi Experience, Proceedings of the 1990 EAEG Workshop on Practical Aspects of Seismic Data Inversion: Eur. Assoc. Expl. Geophys., pp. 5–16 (1991)] for the high frequency range.     

A parallel algebraic multigrid solver for finite element method based source localization in the human brain

Time plays an important role in medical and neuropsychological diagnosis and research. In the field of Electro- and MagnetoEncephaloGraphy (EEG/MEG) source localization, a current distribution in the human brain is reconstructed noninvasively by means of measured fields outside the head. High resolution finite element modeling for the field computation leads to a sparse, large scale, linear equation system with many different right hand sides to be solved. The presented solution process is based on a parallel algebraic multigrid method. It is shown that very short computation times can be achieved through the combination of the multigrid technique and the parallelization on distributed memory computers. A solver time comparison to a classical parallel Jacobi preconditioned conjugate gradient method is given. Received: 13 July 2001 / Accepted: 19 December 2001 RID="*" ID="*"Offprint requests: Carsten Wolters, MPI für neuropsychologische Forschung, MEG-Gruppe, Muldentalweg 9, 04828 Bennewitz, Germany (E-mail: wolters@cns.mpg.de) Communicated by G. Wittum     

A parallel preconditioned conjugate gradient solution method for finite element problems with coarse–fine mesh formulation

The object of this paper is a parallel preconditioned conjugate gradient iterative solver for finite element problems with coarse-mesh/fine-mesh formulation. An efficient preconditioner is easily derived from the multigrid stiffness matrix. The method has been implemented, for the sake of comparison, both on a IBM-RISC590 and on a Quadrics-QH1, a massive parallel SIMD machine with 128 processors. Examples of solutions of simple linear elastic problems on rectangular grids are presented and convergence and parallel performance are discussed.     

On the numerical modeling of convection-diffusion problems by finite element multigrid preconditioning methods

During the last decades, multigrid methods have been extensively used in order to solve large scale linear systems derived from the discretization of partial differential equations using the finite difference method. The effectiveness of the multigrid method can be also exploited by using the finite element method. Finite Element Approximate Inverses in conjunction with Richardon’s iterative method could be used as smoothers in the multigrid method. Thus, a new class of smoothers based on approximate inverses can be derived. Effectiveness of explicit approximate inverses relies in the fact that they are close approximants to the inverse of the coefficient matrix and are fast to compute in parallel. Furthermore, the proposed class of finite element approximate inverses in conjunction with the explicit preconditioned Richardson method yield improved results against the classic smoothers such as Jacobi method. Moreover, a dynamic relaxation scheme is proposed based on the Dynamic Over/Under Relaxation (DOUR) algorithm. Furthermore, results for multigrid preconditioned Krylov subspace methods, such as GMRES(res), IDR(s) and BiCGSTAB based on approximate inverse smoothing and a dynamic relaxation technique are presented for the steady-state convection-diffusion equation.     

A Fast Preconditioned Iterative Algorithm for the Electromagnetic Scattering from a Large Cavity

In this paper, a fast preconditioned Krylov subspace iterative algorithm is proposed for the electromagnetic scattering from a rectangular large open cavity embedded in an infinite ground plane. The scattering problem is described by the Helmholtz equation with a nonlocal artificial boundary condition on the aperture of the cavity and Dirichlet boundary conditions on the walls of the cavity. Compact fourth order finite difference schemes are employed to discretize the bounded domain problem. A much smaller interface discrete system is reduced by introducing the discrete Fourier transformation in the horizontal and a Gaussian elimination in the vertical direction, presented in Bao and Sun (SIAM J. Sci. Comput. 27:553, 2005). An effective preconditioner is developed for the Krylov subspace iterative solver to solve this interface system. Numerical results demonstrate the remarkable efficiency and accuracy of the proposed method.     

A parallel multigrid solver for incompressible flows on computing architectures with accelerators

An efficient parallel multigrid pressure correction algorithm is proposed for the solution of the incompressible Navier–Stokes equations on computing architectures with acceleration devices. The pressure correction procedure is based on the numerical solution of a Poisson-type problem, which is discretized using a fourth-order finite difference compact scheme. Since this is the most time-consuming part of the solver, we propose a parallel pressure correction algorithm using an iterative method based on a block cyclic reduction solution method combined with a multigrid technique. The grid points are numbered with respect to the red–black ordering scheme for the parallel Gauss–Seidel smoother. These parallelization techniques allow the execution of the entire simulation computations on the acceleration device, minimizing memory communication costs. The realization is developed using the OpenACC API, and the numerical method is demonstrated for the solution of two classical incompressible flow test problems. The first is the two-dimensional lid-driven cavity problem over equal mesh sizes while the other is the Stokes boundary layer, which is a decent benchmark problem for unequal mesh spacing. The effect of several multigrid components on modern and legacy acceleration architectures is examined. Eventually the performance investigation demonstrates that the proposed parallel multigrid solver achieves an acceleration of more than 10\(\times \) over the sequential solver and more than 4\(\times \) over multi-core CPU only realizations for all tested accelerators.     

GRAPES动力框架中大规模稀疏线性系统并行求解及优化

赫姆霍兹方程求解是GRAPES数值天气预报系统动力框架中的核心部分,可转换为大规模稀疏线性系统的求解问题,但受限于硬件资源和数据规模,其求解效率成为限制系统计算性能提升的瓶颈。分别通过MPI、MPI+OpenMP、CUDA三种并行方式实现求解大规模稀疏线性方程组的广义共轭余差法,并利用不完全分解LU预处理子（ILU）优化系数矩阵的条件数,加快迭代法收敛。在CPU并行方案中,MPI负责进程间粗粒度并行和通信,OpenMP结合共享内存实现进程内部的细粒度并行,而在GPU并行方案中,CUDA模型采用数据传输、访存合并及共享存储器方面的优化措施。实验结果表明,通过预处理优化减少迭代次数对计算性能提升明显,MPI+OpenMP混合并行优化较MPI并行优化性能提高约35%,CUDA并行优化较MPI+OpenMP混合并行优化性能提高约50%,优化性能最佳。     

Distributed control and constraint preconditioners

Optimization problems with constraints that involve a partial differential equation arise widely in many areas of the sciences and engineering, in particular in problems of design. The solution of such PDE-constrained optimization problems is usually a major computational task. Here we consider simple problems of this type: distributed control problems in which the 2- and 3-dimensional Poisson problem is the PDE. Large dimensional linear systems result from the discretization and need to be solved: these systems are of saddle-point type. We introduce an optimal preconditioner for these systems that leads to convergence of symmetric Krylov subspace iterative methods in a number of iterations which does not increase with the dimension of the discrete problem. These preconditioners are block structured and involve standard multigrid cycles. The optimality of the preconditioned iterative solver is proved theoretically and verified computationally in several test cases. The theoretical proof indicates that these approaches may have much broader applicability for other partial differential equations.     

A partly matrix-free solver for the gyrokinetic field equation in three-dimensional geometry

In the case of adiabatic electrons the gyrokinetic field equation for the electrostatic potential includes an averaging operator acting on flux surfaces. For realistic three-dimensional configurations, as e.g. in stellarator devices, the discretisation of this integro-differential equation leads to very large nearly dense matrices (full matrix approach) which typically cannot be stored in computer memory explicitly. A low memory consuming partly matrix-free approach, based on a preconditioned iterative matrix solver, has been developed where the Helmholtz part of the field equation is used in a matrix formulation while the averaging term is treated matrix-free. For matrices which could still be stored in memory explicitly, it is demonstrated that this approach is also much faster than the full matrix approach.     

非结构网格的并行多重网格解算器

多重网格方法作为非结构网格的高效解算器,其串行与并行实现在时空上都具有优良特性.以控制方程离散过程为切入点,说明非结构网格在并行数值模拟的流程,指出多重网格方法主要用于求解时间推进格式产生的大规模代数系统方程,简述了算法实现的基本结构,分析了其高效性原理;其次,综述性地概括了几何多重网格与代数多种网格研究动态,并对其并行化的热点问题进行重点论述.同时,针对非结构网格的实际应用,总结了多重网格解算器采用的光滑算子;随后列举了非结构网格应用的部分开源项目软件,并简要说明了其应用功能;最后,指出并行多重网格解算器在非结构网格应用中的若干关键问题和未来的研究方向.