Local and Parallel Finite Element Algorithms for Eigenvalue Problems

Abstract Some new local and parallel finite element algorithms are proposed and analyzed in this paper foreigenvalue problems.With these algorithms, the solution of an eigenvalue problem on a fine grid is reduced tothe solution of an eigenvalue problem on a relatively coarse grid together with solutions of some linear algebraicsystems on fine grid by using some local and parallel procedure.A theoretical tool for analyzing these algorithmsis some local error estimate that is also obtained in this paper for finite element approximations of eigenvectorson general shape-regular grids.     

基于二重网格的定常Navier-Stokes方程的局部和并行有限元算法

对二维定常的不可压缩的Navier-Stokes方程的局部和并行算法进行了研究．给出的算法是多重网格和区域分解相结合的算法,它是基于两个有限元空间:粗网格上的函数空间和子区域的细网格上的函数空间．局部算法是在粗网格上求一个非线性问题,然后在细网格上求一个线性问题,并舍掉内部边界附近的误差相对较大的解．最后,基于局部算法,通过有重叠的区域分解而构造了并行算法,并且做了算法的误差分析,得到了比标准有限元方法更好的误差估计,也对算法做了数值试验,数值结果通过比较验证了本算法的高效性和合理性．     

Local and parallel finite element algorithms based on two-grid discretizations for the transient Stokes equations

Based on two-grid discretizations, some local and parallel finite element algorithms for the d-dimensional (d = 2,3) transient Stokes equations are proposed and analyzed. Both semi- and fully discrete schemes are considered. With backward Euler scheme for the temporal discretization, the basic idea of the fully discrete finite element algorithms is to approximate the generalized Stokes equations using a coarse grid on the entire domain, then correct the resulted residue using a finer grid on overlapped subdomains by some local and parallel procedures at each time step. By the technical tool of local a priori estimate for the fully discrete finite element solution, errors of the corresponding solutions from these algorithms are estimated. Some numerical results are also given which show that the algorithms are highly efficient.     

Part I Parallel architectures and algorithms

This paper provides an introduction to algorithms for fundamental linear algebra problems on various parallel computer architectures, with the emphasis on VLSI systolic array machines. To illustrate the basic concepts and key issues, we consider the problem of the parallel solution of a nonsingular linear systems derived from the finite difference/element discretisation of anN ^th order system of differential equations.     

A Parallel Algorithm for Adaptive Local Refinement of Tetrahedral Meshes Using Bisection

Local mesh refinement is one of the key steps in the implementations of adaptive finite element methods. This paper presents a parallel algorithm for distributed memory parallel computers for adaptive local refinement of tetrahedral meshes using bisection. This algorithm is used in PHG, Parallel Hierarchical Grid (http: //lsec. cc. ac. cn/phg/J, a toolbox under active development for parallel adaptive finite element solutions of partial differential equations. The algorithm proposed is characterized by allowing simultaneous refinement of submeshes to arbitrary levels before synchronization between submeshes and without the need of a central coordinator process for managing new vertices. Using the concept of canonical refinement, a simple proof of the independence of the resulting mesh on the mesh partitioning is given, which is useful in better understanding the behaviour of the bisectioning refinement procedure.AMS subject classifications: 65Y05, 65N50     

Local and parallel finite element algorithms for the time-dependent Oseen equations

Numerical Algorithms - Based on two-grid discretizations, local and parallel finite element algorithms are proposed and analyzed for the time-dependent Oseen equations. Using conforming finite...     

一种迭代格式的有限元并行算法*

本文提出了一种求解有限元方程的迭代格式的并行算法.该方法在线性代数方程迭代解法的基础上,引进并行运算步骤;并且运用加权残数方法,通过选择适当的权函数,推导了该并行算法的有限元基本格式.该方法在西安交通大学BLXSI-6400并行计算机上程序实现.计算结果表明它能有效地提高运算速度,减少计算时间,是一种有效的求解大型结构有限元方程的并行算法.     

Towards Textbook Efficiency for Parallel Multigrid

In this work, we extend Achi Brandt's notion of textbook multigrid efficiency (TME) to massively parallel algorithms. Using a finite element based geometric multigrid implementation, we recall the classical view on TME with experiments for scalar linear equations with constant and varying coefficients as well as linear systems with saddle-point structure. To extend the idea of TME to the parallel setting, we give a new characterization of a work unit (WU) in an architecture-aware fashion by taking into account performance modeling techniques. We illustrate our newly introduced parallel TME measure by large-scale computations, solving problems with up to 200 billion unknowns on a TOP-10 supercomputer.     

A normalized sparse linear equations solver

Normalized factorization procedures for the solution of large sparse linear finite element systems have been recently introduced in [3]. In these procedures the large sparse symmetric coefficient matrix of irregular structure is factorized exactly to yield a normalized direct solution method. Additionally, approximate factorization procedures yield implicit iterative methods for the finite difference or finite element solution. The numerical implementation of these algorithms is presented here and FORTRAN subroutines for the efficient solution of the resulting large sparse symmetric linear systems of algebraic equations are given.     

A preconditioned domain decomposition algorithm for the solution of the elliptic Neumann problem

A new preconditioned conjugate gradient (PCG)-based domain decomposition method is given for the solution of linear equations arising in the finite element method applied to the elliptic Neumann problem. The novelty of the proposed method is in the recommended preconditioner which is constructed by using cyclic matrix. The resulting preconditioned algorithms are well suited to parallel computation.     

Uzawa type algorithms for nonsymmetric saddle point problems

In this paper, we consider iterative algorithms of Uzawa type for solving linear nonsymmetric saddle point problems. Specifically, we consider systems, written as usual in block form, where the upper left block is an invertible linear operator with positive definite symmetric part. Such saddle point problems arise, for example, in certain finite element and finite difference discretizations of Navier-Stokes equations, Oseen equations, and mixed finite element discretization of second order convection-diffusion problems. We consider two algorithms, each of which utilizes a preconditioner for the operator in the upper left block. Convergence results for the algorithms are established in appropriate norms. The convergence of one of the algorithms is shown assuming only that the preconditioner is spectrally equivalent to the inverse of the symmetric part of the operator. The other algorithm is shown to converge provided that the preconditioner is a sufficiently accurate approximation of the inverse of the upper left block. Applications to the solution of steady-state Navier-Stokes equations are discussed, and, finally, the results of numerical experiments involving the algorithms are presented.

     

HYBRID ALGEBRAIC MULTILEVEL PRECONDITIONING METHODS

ＨＹＢＲＩＤＡＬＧＥＢＲＡＩＣＭＵＬＴＩＬＥＶＥＬＰＲＥＣＯＮＤＩＴＩＯＮＩＮＧＭＥＴＨＯＤＳ￥ＢａｉＺｈｏｎｇｚｈｉ（白中治）（ＦｕｄａｎＵｎｉｖｅｒｓｉｔｙ，复旦大学，邮编：２００４３３）Ａｂｓｔｒａｃｔ：Ａｃｌａｓｓｏｆｈｙｂｒｉｄａｌｇｅｂｒ...     

有限元结构分析在MIMD计算机上的并行直接解法

§1.前言 并行计算是近十几年来随着并行计算机发展而发展起来的一门新兴学科,特别是对于多指令流多数据流(MIMD)的并行计算机,由于它是由多台普通计算机甚至是向量计算机相互以一定方式联结起来的新型计算机系统,因此无论是它的运算速度或存贮空     

不可压缩流动的并行数值方法

不可压缩流动的数值模拟是计算流体力学的重要组成部分. 基于有限元离散方法, 本文设计了不可压缩Navier-Stokes (N-S)方程支配流的若干并行数值算法. 这些并行算法可归为两大类: 一类是基于两重网格离散方法, 首先在粗网格上求解非线性的N-S方程, 然后在细网格的子区域上并行求解线性化的残差方程, 以校正粗网格的解; 另一类是基于新型完全重叠型区域分解技巧, 每台处理器用一局部加密的全局多尺度网格计算所负责子区域的局部有限元解. 这些并行算法实现简单, 通信需求少, 具有良好的并行性能, 能获得与标准有限元方法相同收敛阶的有限元解. 理论分析和数值试验验证了并行算法的高效性     

Fast parallel solvers for symmetric boundary element domain decomposition equations

Summary. The boundary element method (BEM) is of advantage in many applications including far-field computations in magnetostatics and solid mechanics as well as accurate computations of singularities. Since the numerical approximation is essentially reduced to the boundary of the domain under consideration, the mesh generation and handling is simpler than, for example, in a finite element discretization of the domain. In this paper, we discuss fast solution techniques for the linear systems of equations obtained by the BEM (BE-equations) utilizing the non-overlapping domain decomposition (DD). We study parallel algorithms for solving large scale Galerkin BE–equations approximating linear potential problems in plane, bounded domains with piecewise homogeneous material properties. We give an elementary spectral equivalence analysis of the BEM Schur complement that provides the tool for constructing and analysing appropriate preconditioners. Finally, we present numerical results obtained on a massively parallel machine using up to 128 processors, and we sketch further applications to elasticity problems and to the coupling of the finite element method (FEM) with the boundary element method. As shown theoretically and confirmed by the numerical experiments, the methods are of algebraic complexity and of high parallel efficiency, where denotes the usual discretization parameter. Received August 28, 1996 / Revised version received March 10, 1997     

An analysis of discontinuous Galerkin methods for elliptic problems

We study global and local behaviors for three kinds of discontinuous Galerkin schemes for elliptic equations of second order. We particularly investigate several a posteriori error estimations for the discontinuous Galerkin schemes. These theoretical results are applied to develop local/parallel and adaptive finite element methods, based on the discontinuous Galerkin methods. Dedicated to Dr. Charles A. Micchelli on the occasion of his 60th birthday with friendship and esteem Mathematics subject classifications (2000) 65N12, 65N15, 65N30. Aihui Zhou: Subsidized by the Special Funds for Major State Basic Research Projects, and also partially supported by National Science Foundation of China. Reinhold Schneider: Supported in part by DFG Sonderforschungsbereich SFB 393. Yuesheng Xu: Correspondence author. Supported in part by the US National Science Foundation under grants DMS-9973427 and CCR-0312113, by Natural Science Foundation of China under grant 10371122 and by the Chinese Academy of Sciences under program “Hundreds Distinguished Young Chinese Scientists”.     

Local and parallel finite element algorithms based on two-grid discretizations

A number of new local and parallel discretization and adaptive finite element algorithms are proposed and analyzed in this paper for elliptic boundary value problems. These algorithms are motivated by the observation that, for a solution to some elliptic problems, low frequency components can be approximated well by a relatively coarse grid and high frequency components can be computed on a fine grid by some local and parallel procedure. The theoretical tools for analyzing these methods are some local a priori and a posteriori estimates that are also obtained in this paper for finite element solutions on general shape-regular grids. Some numerical experiments are also presented to support the theory.

     

Local and Parallel Finite Element Algorithms Based on Two-Grid Discretizations for Nonlinear Problems

In this paper, some local and parallel discretizations and adaptive finite element algorithms are proposed and analyzed for nonlinear elliptic boundary value problems in both two and three dimensions. The main technique is to use a standard finite element discretization on a coarse grid to approximate low frequencies and then to apply some linearized discretization on a fine grid to correct the resulted residual (which contains mostly high frequencies) by some local/parallel procedures. The theoretical tools for analyzing these methods are some local a priori and a posteriori error estimates for finite element solutions on general shape-regular grids that are also obtained in this paper.     

Non-overlapping Domain Decomposition Method for a Nodal Finite Element Method

A new approach is proposed for constructing nonoverlapping domain decomposition procedures for solving a linear system related to a nodal finite element method. It applies to problems involving either positive semi-definite or complex indefinite local matrices. The main feature of the method is to preserve the continuity requirements on the unknowns and the finite element equations at the nodes shared by more than two subdomains and to suitably augment the local matrices. We prove that the corresponding algorithm can be seen as a converging iterative method for solving the finite element system and that it cannot break down. Each iteration is obtained by solving uncoupled local finite element systems posed in each subdomain and, in contrast to a strict domain decomposition method, is completed by solving a linear system whose unknowns are the degrees of freedom attached to the above special nodes.     

A Neumann-Neumann algorithm for a mortar discretization of elliptic problems with discontinuous coefficients

Summary. Neumann-Neumann algorithm have been well developed for standard finite element discretization of elliptic problems with discontinuous coefficients. In this paper, an algorithm of this kind is designed and analyzed for a mortar finite element discretization of problems in three dimensions. It is established that its rate of convergence is independent of the discretization parameters and jumps of coefficients between subregions. The algorithm is well suited for parallel computations.Mathematics Subject Classification (1991): 65N55, 65N10, 65N30, 65N22.The work was supported in part by the U.S. Department of Energy under contract DE-FG02-92ER25127 and in part by Polish Science Foundation under grant 2P03A00524.AcknowledgmentThe author would like to thank Olof Widlund for many fruitful discussions and valuable remarks and suggestions on how to improve the presentation of our results.