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 prewavelet-based algorithm for the solution of second-order elliptic differential equations with variable coefficients on sparse grids

We present a Ritz-Galerkin discretization on sparse grids using prewavelets, which allows us to solve elliptic differential equations with variable coefficients for dimensions d ≥ 2. The method applies multilinear finite elements. We introduce an efficient algorithm for matrix vector multiplication using a Ritz-Galerkin discretization and semi-orthogonality. This algorithm is based on standard 1-dimensional restrictions and prolongations, a simple prewavelet stencil, and the classical operator-dependent stencil for multilinear finite elements. Numerical simulation results are presented for a three-dimensional problem on a curvilinear bounded domain and for a six-dimensional problem with variable coefficients. Simulation results show a convergence of the discretization according to the approximation properties of the finite element space. The condition number of the stiffness matrix can be bounded below 10 using a standard diagonal preconditioner.     

Sparse generalized Fourier transforms

Block-diagonalization of sparse equivariant discretization matrices is studied. Such matrices typically arise when partial differential equations that evolve in symmetric geometries are discretized via the finite element method or via finite differences. By considering sparse equivariant matrices as equivariant graphs, we identify a condition for when block-diagonalization via a sparse variant of a generalized Fourier transform (GFT) becomes particularly simple and fast. Characterizations for finite element triangulations of a symmetric domain are given, and formulas for assembling the block-diagonalized matrix directly are presented. It is emphasized that the GFT preserves symmetric (Hermitian) properties of an equivariant matrix. By simulating the heat equation at the surface of a sphere discretized by an icosahedral grid, it is demonstrated that the block-diagonalization is beneficial. The gain is significant for a direct method, and modest for an iterative method. A comparison with a block-diagonalization approach based upon the continuous formulation is made. It is found that the sparse GFT method is an appropriate way to discretize the resulting continuous subsystems, since the spectrum and the symmetry are preserved. AMS subject classification (2000)  43A30, 65T99, 20B25     

瞬态动力问题的遂单元矩阵分裂和逐步积分方法

本文对瞬态动力问题,结合逐步积分方法提出了一类广义的矩阵分裂和逐单元松弛算法,摆脱了有限元法通常需形成总体刚度矩阵,总体质量矩阵和求解大型稀疏方程组的工作,理论分析和计算实例表明,本文的广义矩阵分裂是最优的分裂方案.本文的算法物理意义明确,便于编写程序推广应用.     

Two-scale sparse finite element approximations

To reduce computational cost,we study some two-scale finite element approximations on sparse grids for elliptic partial differential equations of second order in a general setting.Over any tensor product domain ?R~d with d = 2,3,we construct the two-scale finite element approximations for both boundary value and eigenvalue problems by using a Boolean sum of some existing finite element approximations on a coarse grid and some univariate fine grids and hence they are cheaper approximations.As applications,we obtain some new efficient finite element discretizations for the two classes of problem:The new two-scale finite element approximation on a sparse grid not only has the less degrees of freedom but also achieves a good accuracy of approximation.     

A scalable parallel factorization of finite element matrices with distributed Schur complements

We consider the parallel factorization of sparse finite element matrices on distributed memory machines. Our method is based on a nested dissection approach combined with a cyclic re‐distribution of the interface Schur complements. We present a detailed definition of the parallel method, and the well‐posedness and the complexity of the algorithm are analyzed. A lean and transparent functional interface to existing finite element software is defined, and the performance is demonstrated for several representative examples. Copyright © 2016 John Wiley & Sons, Ltd.     

A TWO-LEVEL FINITE ELEMENT GALERKIN METHOD FOR THE NONSTATIONARY NAVIER-STOKES EQUATIONS II： TIME DISCRETIZATION

In this article we consider the fully discrete two-level finite element Galerkin method for the two-dimensional nonstationary incompressible Navier-Stokes equations. This method consists in dealing with the fully discrete nonlinear Navier-Stokes problem on a coarse mesh with width $H$ and the fully discrete linear generalized Stokes problem on a fine mesh with width $h << H$. Our results show that if we choose $H=O(h^{1/2}$) this method is as the same stability and convergence as the fully discrete standard finite element Galerkin method which needs dealing with the fully discrete nonlinear Navier-Stokes problem on a fine mesh with width $h$. However, our method is cheaper than the standard fully discrete finite element Galerkin method.     

A multigrid compact finite difference method for solving the one‐dimensional nonlinear sine‐Gordon equation

The aim of this paper is to propose a multigrid method to obtain the numerical solution of the one‐dimensional nonlinear sine‐Gordon equation. The finite difference equations at all interior grid points form a large sparse linear system, which needs to be solved efficiently. The solution cost of this sparse linear system usually dominates the total cost of solving the discretized partial differential equation. The proposed method is based on applying a compact finite difference scheme of fourth‐order for discretizing the spatial derivative and the standard second‐order central finite difference method for the time derivative. The proposed method uses the Richardson extrapolation method in time variable. The obtained system has been solved by V‐cycle multigrid (VMG) method, where the VMG method is used for solving the large sparse linear systems. The numerical examples show the efficiency of this algorithm for solving the one‐dimensional sine‐Gordon equation. Copyright © 2014 John Wiley & Sons, Ltd.     

二阶椭圆问题的一类广义有限元法

本文提出了求解二阶椭圆问题的一类广义有限元方法,分析了广义有限元方法的优越性,证明了二阶椭圆问题的广义有限元方法具有比标准的Galerkin有限元方法更高阶的收敛速度,根据插值算子的性质,进一步证明了有限元解的亏量迭代校正收敛到广义有限元解,并用数值例子说明广义有限元方法是有效的.     

Conjugate Gradient Method for Rank Deficient Saddle Point Problems

We propose an alternative iterative method to solve rank deficient problems arising in many real applications such as the finite element approximation to the Stokes equation and computational genetics. Our main contribution is to transform the rank deficient problem into a smaller full rank problem, with structure as sparse as possible. The new system improves the condition number greatly. Numerical experiments suggest that the new iterative method works very well for large sparse rank deficient saddle point problems.     

A Characteristic Finite Volume Element Method for the Air Pollution Model

In this article, a characteristic finite volume element method is presented for solving air pollution models. The convection term is discretized using the characteristic method and diffusion term is approximated by finite volume element method. Compared with standard finite volume element method, our proposed method is more accurate and efficient, especially suitable to solve convection-dominated problems. The proposed numerical schemes are analyzed for convergence in L ₂ norm. Some numerical results are presented to demonstrate the efficiency and accuracy of the method.     

浅水环流问题的有限元分析

考虑涡流粘性,底部摩擦,Coriolis力和重力作用,以单层模型的竖直向积分建立二维流动的环流控制方程.用Galerkin加权余量法建立环流边值问题的弱形式.用有限元法和分裂时间法分别离散空间和时间进行数值近似计算.采用线性内插的“人工光滑”处理以消除短波长噪音干扰,而避免已有的大阻尼系数方法等缺陷.为节省计算内存容量,程序中建立稀疏矩阵的一维紧凑存贮格式,排除了全部“零”元素的容量要求.     

A fast and efficient two-grid method for solving d-dimensional poisson equations

The aim of this paper is to introduce a fast and efficient new two-grid method to solve the d-dimensional (d=1,2,3) Poisson elliptic equations. The finite difference equations at all interior grid points form a large sparse linear system, which needs to be solved efficiently. The solution cost of this sparse linear system usually dominates the total cost of solving the discretized partial differential equation. The finite difference equations are based on applying a finite difference scheme of two- and four-orders (compact finite difference method) for discretizing the spatial derivative. The obtained linear systems of Poisson elliptic equations have been solved by a new two-grid (NTG) method and we also note that the NTG method which is used for solving the large sparse linear systems is faster and more effective than that of the standard two-grid method. We utilize the local Fourier analysis to show that the spectral radius of the new two-grid method for 1D and 2D models is less than that of the standard two-grid method. As well as, we expand the corresponding algorithm to the new multi-grid method. The numerical examples show the efficiency of the new algorithms for solving the d-dimensional Poisson equations.     

An enhanced finite volume method to model 2D linear elastic structures

This paper details the evaluation and enhancement of the vertex-centred finite volume method for the purpose of modelling linear elastic structures undergoing bending. A matrix-free edge-based finite volume procedure is discussed and compared with the traditional isoparametric finite element method via application to a number of test-cases. It is demonstrated that the standard finite volume approach exhibits similar disadvantages to the linear Q4 finite element formulation when modelling bending. An enhanced finite volume approach is proposed to circumvent this and a rigorous error analysis conducted. It is demonstrated that the developed finite volume method is superior to both standard finite volume and Q4 finite element methods, and provides a practical alternative to the analysis of bending-dominated solid mechanics problems.     

Unstructured meshing for two asset barrier options

Discretely observed barriers introduce discontinuities in the solution of two asset option pricing partial differential equations (PDEs) at barrier observation dates. Consequently, an accurate solution of the pricing PDE requires a fine mesh spacing near the barriers. Non-rectangular barriers pose difficulties for finite difference methods using structured meshes. It is shown that the finite element method (FEM) with standard unstructured meshing techniques can lead to significant efficiency gains over structured meshes with a comparable number of vertices. The greater accuracy achieved with unstructured meshes is shown to more than compensate for a greater solve time due to an increase in sparse matrix condition number. Results are presented for a variety of barrier shapes, including rectangles, ellipses, and rotations of these shapes. It is claimed that ellipses best represent constant (risk neutral) probability regions of underlying asset price-point movement, and are thus natural two-dimensional barrier shapes.     

Weighted extended b-splines for one-dimensional electromagnetic problems

This paper considers the weighted extended b-splines as basis function for finite element method in electromagnetics and compares with the standard finite element method applied to the two-point boundary value problems with different boundary conditions. This new approach, which provides more accurate results than standard finite element method, is presented to compare other numerical techniques and applied to one-dimensional electromagnetic problems. Computed results are compared with other numerical results in literature.     

A combined finite/discrete element algorithm for delamination analysis of composites

A combined finite/discrete element method is developed to model delamination behaviour in laminated composites. A penalty based algorithm is employed to evaluate the interlaminar stress state. The failure surface for delamination is defined by a Chang-Springer criterion, and the interlaminar crack propagation is achieved by a standard discrete element contact/release algorithm. The ability of the method for simulation of this behaviour is assessed by solving standard test cases available from the literature.     

不可压混溶驱替问题的流线扩散──混合元数值模拟

采用标准元模拟不可压混溶流问题，当扩散系数矩阵小过剖分参数时，有限元格式仅能给出比最优精度低一阶的逼近解，格式稳定性差并伴有强烈的数值弥散现象．为了克服上述缺陷，本文对压力方程采用混合元，而对浓度方程采用流线扩散格式，在扩散矩阵为线性的假定下，证明了该格式具有较标准元更高的逼近精度（比最优阶低1／2）和更好的稳定性．     

Mixed finite elements on sparse grids

Summary. This paper generalizes the idea of approximation on sparse grids to discrete differential forms that include )- and -conforming mixed finite element spaces as special cases. We elaborate on the construction of the spaces, introduce suitable nodal interpolation operators on sparse grids and establish their approximation properties. We discuss how nodal interpolation operators can be approximated. The stability of -conforming finite elements on sparse grids, when used to approximate second order elliptic problems in mixed formulation, is investigated both theoretically and in numerical experiments. Received November 2, 2000 / Revised version received October 23, 2001 / Published online January 30, 2002 This work was supported by DFG. This paper is dedicated to Ch. Zenger on the occasion of his 60th birthday.     

半导体器件瞬态模拟的对称正定混合元方法

提出具有对称正定特性的混合元格式求解非稳态半导体器件瞬态模拟问题。提出一个最小二乘混合元方法、一个新的具有分裂和对称正定性质的混合元格式和一个解经典混合元方程的对称正定失窃工格式求解电场位势和电场强度方程;提出一个最小二乘混合元格式求解关于电子与空穴浓度的非稳态对流扩散方程,浓度函数和流函数被同时求解;采用标准的有限元方法求解热传导方程。建立了误差分析理论。