A multigrid accelerated hybrid unstructured mesh method for 3D compressible turbulent flow

 A cell vertex finite volume method for the solution of steady compressible turbulent flow problems on unstructured hybrid meshes of tetrahedra, prisms, pyramids and hexahedra is described. These hybrid meshes are constructed by firstly discretising the computational domain using tetrahedral elements and then by merging certain tetrahedra. A one equation turbulence model is employed and the solution of the steady flow equations is obtained by explicit relaxation. The solution process is accelerated by the addition of a multigrid method, in which the coarse meshes are generated by agglomeration, and by parallelisation. The approach is shown to be effective for the simulation of a number of 3D flows of current practical interest. Sponsored by The Research Council of Norway, project number 125676/410 Dedicated to the memory of Prof. Mike Crisfield, a respected colleague     

3-D direct current resistivity forward modeling by adaptive multigrid finite element method

Based on the fact that 3-D model discretization by artificial could not always be successfully implemented especially for large-scaled problems when high accuracy and efficiency were required, a new adaptive multigrid finite element method was proposed. In this algorithm, a-posteriori error estimator was employed to generate adaptively refined mesh on a given initial mesh. On these iterative meshes, V-cycle based multigrid method was adopted to fast solve each linear equation with each initial iterative term interpolated from last mesh. With this error estimator, the unknowns were nearly optimally distributed on the final mesh which guaranteed the accuracy. The numerical results show that the multigrid solver is faster and more stable compared with ICCG solver. Meanwhile, the numerical results obtained from the final model discretization approximate the analytical solutions with maximal relative errors less than 1%, which remarkably validates this algorithm.     

Extreme simplification and rendering of point sets using algebraic multigrid

We present a novel approach for extreme simplification of point set models, in the context of real-time rendering. Point sets are often rendered using simple point primitives, such as oriented discs. However, this requires using many primitives to render even moderately simple shapes. Often, one wishes to render a simplified model using only a few primitives, thus trading accuracy for simplicity. For this goal, we propose a more complex primitive, called a splat, that is able to approximate larger and more complex surface areas than oriented discs. We construct our primitive by decomposing the model into quasi-flat regions, using an efficient algebraic multigrid algorithm. Next, we encode these regions into splats implemented as planar support polygons textured with color and transparency information and render the splats using a special blending algorithm. Our approach combines the advantages of mesh-less point-based techniques with traditional polygon-based techniques. We demonstrate our method on various models.     

Convergence analysis of geometrical multigrid methods for solving data-sparse boundary element equations

The convergence analysis of multigrid methods for boundary element equations arising from negative-order pseudo-differential operators is quite different from the usual finite element multigrid analysis for elliptic partial differential equations. In this paper, we study the convergence of geometrical multigrid methods for solving large-scale, data-sparse boundary element equations. In particular, we investigate multigrid methods for \(\mathcal{H}\)-matrices arising from the adaptive cross approximation to the single layer potential operator.     

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

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

小波瀑布型多重网格法

为了提高偏微分方程的计算精度,由瀑布型多重网格的速度收敛快以及小波多分辨分析的性质,通过改进传统瀑布型多重网格算法中的插值算子,提出一种新的小波瀑布型多重网格方法。数值结果表明,小波瀑布型多重网格方法比传统的瀑布型多重网格方法具有更高精度。     

多重网格技术对SIMPLER算法的加速性能研究

将多重网格技术引入SIMPLER算法以加快其收敛速度,从而节约计算时间。通过计算不同雷诺数下的二维方腔顶盖驱动流,研究了多重网格方法中的V循环、W循环对SIMPLER算法的加速效果,并讨论了网格层数对加速性能的影响。研究结果表明,在不同雷诺数下,多重网格方法均可以起到良好的加速效果;在相同雷诺数和精度要求下,W循环方式的外迭代次数少于V循环方式的外迭代次数,而且网格层数对多重网格加速性能的影响并不显著。     

New architectures: Performance highlights and new algorithms

Parallel computers are having a profound impact on computational science. Recently highly parallel machines have taken the lead as the fastest supercomputers, a trend that is likely to accelerate in the future. We describe some of these new computers, and issues involved in using them. We present elliptic PDE solutions currently running at 3.8 gigaflops, and an atmospheric dynamics model running at 1.7 gigaflops, on a 65 536-processor computer.

One intrinsic disadvantage of a parallel machine is the need to perform inter-processor communication. It is important to ensure that such communication time is maintained at a small fraction of computation time. We analyze standard multigrid algorithms in two and three dimensions from this point of view, indicating that performance efficiencies in excess of 95% are attainable under suitable conditions on moderately parallel machines. We also demonstrate that such performance is not attainable for multigrid on massively parallel computers, as indicated by an example of poor multigrid efficiency on 65 536 processors. The fundamental difficulty is the inability to keep 65 536 processors busy when operating on very coarse grids.

Most algorithms used for implementing applications on parallel machines have been derived directly from algorithms designed for serial machines. The previously mentioned multigrid example indicates that such ‘parallelized’ algorithms may not always be optimal. Parallel machines open the possibility of finding totally new approaches to solving standard tasks—intrinsically parallel algorithms. In particular, we present a class of superconvergent multiple scale methods that were motivated directly by massevely parallel machines. These methods differ from standard multigrid methods in an intrinsic way, and allow all processors to be used at all times, even when processing on the coarsest grid levels. Their serial versions are not sensible algorithms. The idea that parallel hardware—the Connection Machine in this case—can lead to discovery of new mathematical algorithms was surprising for us.     

一种快速计算跨音速流动的多重网格有限元素法

非定常方法已能成功地求解跨音速流动问题,但由于收敛速度太慢[1],影响了它在实际中的应用。本文在[2,3]的基础上发展了一种快速的定常欧拉方程解法。采用混合有限元单元来处理跨音速流动中的混合问题。通过对边界条件的精心处理使问题得到很好的适定。一种多重网格有限元迭代法在本文得到了发展,使收敛速度进一步加快。计算结果表明,二元跨音速流场计算仅需数百次迭代就能达到充分收敛、捕捉激波稳定准确,适应性强。表明本方法具有较大的应用价值。     

Multigrid Convergence of Calculated Features in Image Analysis

This paper informs about number-theoretical and geometrical estimates of worst-case bounds for quantization errors in calculating features such as moments, moment based features, or perimeters in image analysis, and about probability-theoretical estimates of error bounds (e.g. standard deviations) for such digital approximations. New estimates (with proofs) and a review of previously known results are provided.