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

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

一种适用于网格加密型高效算法的嵌套式数据结构

网格加密型高效算法包括多重网格法、自适应局部加密算法、外推算法等.它们是在有限元法(或差分法)基础上,借助于网格加密技术发展起来的高效算法.这些算法在理论上已基本成熟,其效率明显高于一般有限元算法.但由于缺乏相应的数据结构和软件     

一种改进的临近空间高超声速飞行器跟踪算法

针对传统的自适应网格算法在跟踪高超声速飞行器高机动目标时,会出现跟踪位置不稳定的问题,在自适应网格算法中引入了转换模式和抑制模式,得到了一种改进的变结构交互多模型算法——SAG-VSMM算法,通过转换模式和抑制模式的切换来避免了不同模型状态滤波过程中的相互干扰,具有更好的鲁棒性.仿真结果表明,改进方法在跟踪临近空间目标时,能够实现对目标的精确跟踪,并且具有计算量较小、跟踪精度高、鲁棒性强的特点,较传统自适应网格算法跟踪精度得到一定提高.     

基于RLS算法的DPSK解调方法

本文研究了一种基于自适应算法的解调差分相移键控(DPSK)信号的方法。采用常用的递归最小二乘法(RLS)自适应算法．研究了自适应解调方法对DPSK信号的解调及其性能。计算机模拟结果表明，基于这种算法的自适应DPSK解调完全可行且性能优越．而且便于用数字信号处理技术实现，期望该设想能起到一定的作用。     

一种针对大波数Helmholtz方程的高性能并行预条件迭代求解算法

针对传统串行迭代法求解大波数Helmholtz方程存在效率低下且受限于单机内存的问题,提出了一种基于消息传递接口(Message Passing Interface,MPI) 的并行预条件迭代法。该算法利用复移位拉普拉斯算子对Helmholtz方程进行预条件处理,联合稳定双共轭梯度法和基于矩阵的多重网格法来求解预条件方程离散后的大规模线性系统,在Linux集群系统上基于 MPI环境实现了求解算法的并行计算,重点解决了多重网格的并行划分、信息传递和多重网格组件的构建问题。数值实验表明,对于大波数问题,提出的算法具有良好的并行加速比,相较于串行算法极大地提高了计算效率。     

基于GPU的多重网格Navier-Stokes解算器并行优化方法研究

随着工业计算需求的激增,计算流体力学 (Computational Fluid Dynamics, CFD) 学科对计算效率问题越来越重视。作者基于自行开发的 Navier-Stokes 解算器,引入多重网格加速收敛算法,并结合NVIDIA GPU 计算平台,从数值方法和高性能计算两个方面为 CFD 实现加速。数值加速算例测试结果表明,基于多重网格算法的 GPU 解算器相对 CPU 版本代码双精度可获得 45 倍以上的加速。     

用于图像重构的代数多重网格算法

通过分析代数多重网格(algebraic multi-grid,AMG)算法中粗网格提取过程,提出了一种基于代数多重网格算法的图像重构算法.在代数多重网格算法的粗网格序列中,下一层粗网格保留上一层网格的强连接部分.将这种机制运用到图像,提取的粗网格可以较好的保留图像的有效信息部分,在图像变化剧烈的细节区域网格点分布不均匀,平滑模糊部分网格点分布均匀一致.以粗网格像素点进行插值,可以得到较好的重建结果.以均方误差为评价参数,与小波算法进行了比较,比较结果表明该算法在一定程度上优于传统的小波算法,且有一个图像融合应用实例,优于小波融合方法.     

基于MG-GMRES算法的图像超分辨率重建

提出了一种基于多层网格(MG)和广义极小残余(GMRES)算法相结合的图像超分辨率重建快速算法.首先采用正则化方法给出图像超分辨率重建模型;然后在系统介绍MG和GMRES算法的基础上,针对图像超分辨率重建中非对称线性稀疏方程的求解,提出多层网格-广义极小残余(MG-GMRES)算法;详细讨论了MG-GMRES算法的光滑、限制、插值操作以及计算复杂度.实验研究表明该算法的重建结果相当有效,与MG、GMRES和Richrdson迭代相比,具有更快的收敛速度.     

求解半线性椭圆型方程组的并行算法

本文结合区域分裂技术、多重网格方法、加速Ｓｃｈｗａｒｚ收敛方法、高低解方法、非线性Ｊａｃｏｂｉ迭代方法和Ｎｅｗｔｏｎ线性化迭代方法,设计了三种求解半线性椭圆型方程（组）的并行算法：并行Ｎｅｗｔｏｎ多重网格算法、并行非线性多重网格算法和并行加速Ｓｃｈｗａｒｚ收敛算法。数值试验说明这三种算法的并行计算是可行的。     

基于自适应阈值的网格图像行分割算法

针对网格图像文字自动识别受网格横线影响的问题,提出将网格图像按照网格横线进行行分割的自适应阈值算法。在对网格图像行分割过程中,首先对灰度图像使用类别方差自动门限法(OSTU算法)取得图像二值化的阈值,将此阈值作为全局阈值对图像进行二值化操作。然后针对图像的二值化数据进行了水平投影,利用统计法取得行分隔的阈值,并结合行分隔阈值实现了网格图像行分割的算法。最后将算法在Matlab中进行了验证和分析。     

结合代数多重网格的钻石编码隐写算法

针对隐写算法安全性的问题,提出一种结合代数多重网格（AMG）的钻石编码（DE）隐写算法。首先,通过AMG方法将图像的像素点分成粗细网格两个部分。然后,结合DE把机密信息分别嵌入到粗细网格两个像素序列中。其中,粗网格部分像素的改变对整幅图像的质量影响较小,而细网格部分像素的改变对整幅图像的质量影响较大。又因为DE的k值跟信息隐藏容量密切相关,随着k值的增加像素改变量变大,所以用DE嵌入的过程中,粗网格部分选择的k值不小于细网格。最后,选择DE的k值等于1与2,提出了三种隐写方案。与最低有效位（LSB）置换、随机LSB匹配、DE算法和自适应边缘检测算法进行比较,实验结果表明,三种隐写方案的一阶Markov安全指标皆优于其他对比隐写算法。     

Parallelism in multigrid methods: How much is too much?

Multigrid methods are powerful techniques to accelerate the solution of computationally-intensive problems arising in a broad range of applications. Used in conjunction with iterative processes for solving partial differential equations, multigrid methods speed up iterative methods by moving the computation from the original mesh covering the problem domain through a series of coarser meshes. But this hierarchical structure leaves domain-parallel versions of the standard multigrid algorithms with a deficiency of parallelism on coarser grids. To compensate, several parallel multigrid strategies with more parallelism, but also more work, have been designed. We examine these parallel strategies and compare them to simpler standard algorithms to try to determine which techniques are more efficient and practical. We consider three parallel multigrid strategies: (1) domain-parallel versions of the standard V-cycle and F-cycle algorithms; (2) a multiple coarse grid algorithm, proposed by Fredrickson and McBryan, which generates several coarse grids for each fine grid; and (3) two Rosendale algorithm, which allow computation on all grids simultaneously. We study an elliptic model problem on simple domains, discretized with finite difference techniques on block-structured meshes in two or three dimensions with up to 10⁶ or 10⁹ points, respectively. We analyze performance using three models of parallel computation: the PRAM and two bridging models. The bridging models reflect the salient characteristics of two kinds of parallel computers: SIMD fine-grain computers, which contain a large number of small (bitserial) processors, and SPMD medium-grain computers, which have a more modest number of powerful (single chip) processors. Our analysis suggests that the standard algorithms are substantially more efficient than algorithms utilizing either parallel strategy. Both parallel strategies need too much extra work to compensate for their extra parallelism. They require a highly impractical number of processors to be competitive with simpler, standard algorithms. The analysis also suggests that the F-cycle, with the appropriate optimization techniques, is more efficient than the V-cycle under a broad range of problem, implementation, and machine characteristics, despite the fact that it exhibits even less parallelism than the V-cycle. Research at Princeton University partially supported by the National Science Foundation, Grant No. CCR-8920505, and the Office of Naval Research, Contract No. N0014-91-J-1463.     

A multigrid algorithm for parallel computers: CPMG

In this article, we present a multigrid algorithm for parallel computers, the chopped parallel multigrid (CPMG) algorithm. The CPMG algorithm improves the processor utilization by reducing the work load on coarse grids without affecting the convergence rate of the algorithm. This is in contrast to earlier approaches (Gannon and van Rosendale, 1986; Frederickson and McBryan, 1989), where unutilized processors are used to improve the convergence rate. The CPMG algorithm reduces the coarse grid work bychopping the alternate cycles of multigrid. Using analytical results and simulations on sequential machines we show that the CPMG can achieve almost the same convergence rate as standard MG for many cases. Analytically we show that the advantage gained by CPMG over standard MG on a mesh connected massively parallel machine is 33% in hardware utilization, 50% in communication overheads and 38% in overall execution time. We have also evaluated the performance of CPMG on an actual massively parallel machine, the DAP-510. The advantage gained by CPMG over standard MG is 35% in overall execution time. Moreover, the CPMG can be integrated with other parallel multigrid algorithms, such as the PSMG algorithm (Frederickson and McBryan, 1989) and Decker's algorithm (Decker, 1990).     

Optimization of multigrid based elliptic solver for large scale simulations in the FLASH code

FLASH is a multiphysics multiscale adaptive mesh refinement (AMR) code originally designed for simulation of reactive flows often found in Astrophysics. With its wide user base and flexible applications configuration capability, FLASH has a dual task of maintaining scalability and portability in all its solvers. The scalability of fully explicit solvers in the code is tied very closely to that of the underlying mesh. Others such as the Poisson solver based on a multigrid method have more complex scaling behavior. Multigrid methods suffer from processor starvation and dominating communication costs at coarser grids with increase in the number of processors. In this paper, we propose a combination of uniform grid mesh with AMR mesh, and the merger of two different sets of solvers to overcome the scalability limitation of the Poisson solver in FLASH. The principal challenge in the proposed merger is the efficiency of the communication algorithm to map the mesh back and forth between uniform grid and AMR. We present two different parallel mapping algorithms and also discuss results from performance studies of the two implementations. Copyright © 2012 John Wiley & Sons, Ltd.     

Adaptive Local Postprocessing Finite Element Method for the Navier-Stokes Equations

An adaptive local postprocessing finite element method for the Navier-Stokes equations is presented in this paper. We firstly solve the problem on a relative coarse grid to get a rough approximation. Then, we correct the rough approximation by solving a series of approximate local residual equations defined on some local fine grids, which can be implemented in parallel. In addition, we also propose a reliable local a posteriori error estimator and construct an adaptive algorithm based on the corresponding a posterior error estimate. Finally, some numerical examples are presented to verify the algorithm.     

A comparison of three kinds of local and parallel finite element algorithms based on two-grid discretizations for the stationary Navier–Stokes equations

Based on two-grid discretizations, three kinds of local and parallel finite element algorithms for the stationary Navier–Stokes equations are introduced and discussed. The main technique is first to use a standard finite element discretization on a coarse grid to approximate low frequencies of the solution, then to apply some linearized discretizations on a fine grid to correct the resulted residual (which contains mostly high frequencies) by some local and parallel procedures. Three approaches to linearization are discussed. Under the uniqueness condition, error estimates of the finite element solution are derived. Numerical results show that among the three kinds of parallel algorithms, the Oseen-linearized algorithm is preferable if we both consider the computational time and the accuracy of the approximate solution.     

A modified full multigrid algorithm for the Navier-Stokes equations

A modified full multigrid (FMG) method for the solution of the Navier-Stokes equations is presented. The method proposed is based on a V-cycle omitting the restriction procedure for dependent variables but retaining it for the residuals. This modification avoids possible mismatches between the mass fluxes and the restricted velocities as well as the turbulent viscosity and the turbulence quantities on the coarse grid. In addition, the pressure on the coarse grid can be constructed in the same way as the velocities. These features simplify the multigrid strategy and corresponding programming efforts. This algorithm is applied to accelerate the convergence of the solution of the Navier-Stokes equations for both laminar and high-Reynolds number turbulent flows. Numerical simulations of academic and practical engineering problems show that the modified algorithm is much more efficient than the FMG-FAS (Full Approximation Storage) method.     

A novel hybrid algorithm based on FDTD and WCS‐FDTD methods

In this article, a hybrid algorithm based on traditional finite‐difference time‐domain (FDTD) and weakly conditionally stable finite‐difference time‐domain (WCS‐FDTD) algorithm is proposed. In this algorithm, the calculation domain is divided into fine‐grid region and coarse‐grid region. The traditional FDTD method is used to calculate the field value in the coarse‐grid region, while the WCS‐FDTD method is used in the fine‐grid region. The spatial interpolation scheme is applied to the interface of the coarse grid region and fine grid region to insure the stability and precision of the presented hybrid algorithm. As a result, a relatively large time step size, which is only determined by the spatial cell sizes in the coarse grid region, is applied to the entire calculation domain. This scheme yields a significant reduction both of computation time and memory requirement in comparison with the conventional FDTD method and WCS‐FDTD method, which are validated by using numerical results.     

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

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

Ordering Techniques for Two- and Three-Dimensional Convection-Dominated Elliptic Boundary Value Problems

Multigrid methods with simple smoothers have been proven to be very successful for elliptic problems with no or only moderate convection. In the presence of dominant convection or anisotropies as it might appear in equations of computational fluid dynamics (e.g. in the Navier-Stokes equations), the convergence rate typically decreases. This is due to a weakened smoothing property as well as to problems in the coarse grid correction. In order to obtain a multigrid method that is robust for convection-dominated problems, we construct efficient smoothers that obtain their favorable properties through an appropriate ordering of the unknowns. We propose several ordering techniques that work on the graph associated with the (convective part of the) stiffness matrix. The ordering algorithms provide a numbering together with a block structure which can be used for block iterative methods. We provide numerical results for the Stokes equations with a convective term illustrating the improved convergence properties of the multigrid algorithm when applied with an appropriate ordering of the unknowns. Received July 12, 1999; revised October 1, 1999