A Dirichlet–Neumann type algorithm for contact problems with friction

Domain decomposition techniques provide a powerful tool for the numerical approximation of partial differential equations. We introduce a new algorithm for the numerical solution of a nonlinear contact problem with Coulomb friction between linear elastic bodies. The discretization of the nonlinear problem is based on mortar techniques. We use a dual basis Lagrange multiplier space for the coupling of the different bodies. The boundary data transfer at the contact zone is essential for the algorithm. It is realized by a scaled mass matrix which results from the mortar discretization on non-matching triangulations. We apply a nonlinear block Gauss–Seidel method as iterative solver which can be interpreted as a Dirichlet–Neumann algorithm for the nonlinear problem. In each iteration step, we have to solve a linear Neumann problem and a nonlinear Signorini problem. The solution of the Signorini problem is realized in terms of monotone multigrid methods. Numerical results illustrate the performance of our approach in 2D and 3D. Received: 20 March 2001 / Accepted: 1 February 2002 Communicated by P. Deuflhard     

The Fourier-Nitsche-mortaring for elliptic problems with reentrant edges

The Fourier method is combined with the Nitsche-finite-element method (as a mortar method) and applied to the Dirichlet problem of the Poisson equation in three-dimensional axisymmetric domains with reentrant edges generating singularities. The approximating Fourier method yields a splitting of the 3D problem into a set of 2D problems on the meridian plane of the given domain. For solving the 2D problems bearing corner singularities, the Nitsche-finite-element method with non-matching meshes and mesh grading near reentrant corners is applied. Using the explicit representation of some singularity function of non-tensor product type, the rate of convergence of the Fourier-Nitsche-mortaring is estimated in some H ¹-like norm as well as in the L ₂-norm for weak regularity of the solution. Finally, some numerical results are presented.      

A Solution Method for a Certain Nonlinear Interface Problem in Unbounded Domains

In this paper, we consider a kind of nonlinear interface problem in unbounded domains. To solve this problem, we discuss a new coupling of finite element and boundary element by adding an auxiliary circle. We first derive the optimal error estimate of finite element approximation to the coupled FEM-BEM problem. Then we introduce a preconditioning steepest descent method for solving the discrete system by constructing a cheap domain decomposition preconditioner. Moreover, we give a complete analysis to the convergence speed of this iterative method. Received March 30, 2000; revised November 29, 2000     

A Matrix-free Two-grid Preconditioner for Solving Boundary Integral Equations in Electromagnetism

In this paper, we describe a matrix-free iterative algorithm based on the GMRES method for solving electromagnetic scattering problems expressed in an integral formulation. Integral methods are an interesting alternative to differential equation solvers for this problem class since they do not require absorbing boundary conditions and they mesh only the surface of the radiating object giving rise to dense and smaller linear systems of equations. However, in realistic applications the discretized systems can be very large and for some integral formulations, like the popular Electric Field Integral Equation, they become ill-conditioned when the frequency increases. This means that iterative Krylov solvers have to be combined with fast methods for the matrix-vector products and robust preconditioning to be affordable in terms of CPU time. In this work we describe a matrix-free two-grid preconditioner for the GMRES solver combined with the Fast Multipole Method. The preconditioner is an algebraic two-grid cycle built on top of a sparse approximate inverse that is used as smoother, while the grid transfer operators are defined using spectral information of the preconditioned matrix. Experiments on a set of linear systems arising from real radar cross section calculation in industry illustrate the potential of the proposed approach for solving large-scale problems in electromagnetism.     

Variationally derived algorithms in the ABS class for linear systems

Algorithms in the ABS class of direct methods for linear systems are considered where the correction to the projection matrix minimizes a weighted Frobenius norm. These algorithms define implicit factorizations of the coefficient matrix which do not require pivoting. The implicit Gram-Schmidt algorithm is obtained when using the unweighted norm.     

A Numerical Method to Verify the Invertibility of Linear Elliptic Operators with Applications to Nonlinear Problems

In this paper, we propose a numerical method to verify the invertibility of second-order linear elliptic operators. By using the projection and the constructive a priori error estimates, the invertibility condition is formulated as a numerical inequality based upon the existing verification method originally developed by one of the authors. As a useful application of the result, we present a new verification method of solutions for nonlinear elliptic problems, which enables us to simplify the verification process. Several numerical examples that confirm the actual effectiveness of the method are presented.     

An Efficient Direct Solver for the Boundary Concentrated FEM in 2D

The boundary concentrated FEM, a variant of the hp-version of the finite element method, is proposed for the numerical treatment of elliptic boundary value problems. It is particularly suited for equations with smooth coefficients and non-smooth boundary conditions. In the two-dimensional case it is shown that the Cholesky factorization of the resulting stiffness matrix requires O(Nlog⁴ N) units of storage and can be computed with O(Nlog⁸ N) work, where N denotes the problem size. Numerical results confirm theoretical estimates. Received October 4, 2001; revised August 19, 2002 Published online: October 24, 2002     

Remarks on a formula for the pseudoinverse by the modified huang algorithm

We present and prove an alternative formula of the Moore-Penrose pseudoinverse for a matrix by the modified Huang algorithm. The results correct a formula in the book entitled ‘ABS projection Algorithms: mathematical techniques for linear and nonlinear equations’. Supported by the National Natural Science Foundation of China.     

A Semi-smooth Newton Method for Regularized State-constrained Optimal Control of the Navier-Stokes Equations

In this paper, we study semi-smooth Newton methods for the numerical solution of regularized pointwise state-constrained optimal control problems governed by the Navier-Stokes equations. After deriving an appropriate optimality system for the original problem, a class of Moreau-Yosida regularized problems is introduced and the convergence of their solutions to the original optimal one is proved. For each regularized problem a semi-smooth Newton method is applied and its local superlinear convergence verified. Finally, selected numerical results illustrate the behavior of the method and a comparison between the max-min and the Fischer-Burmeister as complementarity functionals is carried out.     

改进的正则化模型在图像恢复中的应用

目的 由拟合项与正则项组成的海森矩阵,如果不具有特殊结构,其逆矩阵计算比较困难,为克服此缺点,提出一种海森矩阵可分块对角化的牛顿投影迭代算法。方法 首先,用L₂范数描述拟合项,用自变量是有界变差函数的复合函数刻画正则项,建立能量泛函正则化模型。其次,引入势函数,将正则化模型转化为增广能量泛函。再次,构造预条件矩阵,使得海森矩阵可分块对角化。最后,为防止牛顿投影迭代算法收敛到局部最优解,采用回溯线性搜索算法和改进的Barzilai-Borwein步长更新准则使得算法全局收敛。结果 针对图像去模糊正则化模型容易使边缘平滑和产生阶梯效应“两难”问题,提出一种新的正则化模型和牛顿投影迭代算法。仿真结果表明,“两难”问题通过本文算法得到了很好的解决。结论 与其他正则化图像去模糊模型相比,本文算法明显改善图像的质量,如有效地保护图像的边缘,抑制阶梯效应,相对偏差和误差较小,较高的峰值信噪比和结构相似测度。     

Arbitrary-level hanging nodes and automatic adaptivity in the hp-FEM

In this paper we present a new automatic adaptivity algorithm for the hp-FEM which is based on arbitrary-level hanging nodes and local element projections. The method is very simple to implement compared to other existing hp-adaptive strategies, while its performance is comparable or superior. This is demonstrated on several numerical examples which include the L-shape domain problem, a problem with internal layer, and the Girkmann problem of linear elasticity. With appropriate simplifications, the proposed technique can be applied to standard lower-order and spectral finite element methods.     

Using integral equations and the immersed interface method to solve immersed boundary problems with stiff forces

We propose a fast, explicit numerical method for computing approximations for the immersed boundary problem in which the boundaries that separate the fluid into two regions are stiff. In the numerical computations of such problems, one frequently has to contend with numerical instability, as the stiff immersed boundaries exert large forces on the local fluid. When the boundary forces are treated explicitly, prohibitively small time-steps may be required to maintain numerical stability. On the other hand, when the boundary forces are treated implicitly, the restriction on the time-step size is reduced, but the solution of a large system of coupled non-linear equations may be required. In this work, we develop an efficient method that combines an integral equation approach with the immersed interface method. The present method treats the boundary forces explicitly. To reduce computational costs, the method uses an operator-splitting approach: large time-steps are used to update the non-stiff advection terms, and smaller substeps are used to advance the stiff boundary. At each substep, an integral equation is computed to yield fluid velocity local to the boundary; those velocity values are then used to update the boundary configuration. Fluid variables are computed over the entire domain, using the immersed interface method, only at the end of the large advection time-steps. Numerical results suggest that the present method compares favorably with an implementation of the immersed interface method that employs an explicit time-stepping and no fractional stepping.     

h-p Spectral Element Method for Elliptic Problems on Non-smooth Domains Using Parallel Computers

We propose a new h-p spectral element method to solve elliptic boundary value problems with mixed Neumann and Dirichlet boundary conditions on non-smooth domains. The method is shown to be exponentially accurate and asymptotically faster than the standard h-p finite element method. The spectral element functions are fully non-conforming for pure Dirichlet problems and conforming only at the vertices of the elements for mixed problems, and hence, the dimension of the resulting Schur complement matrix is quite small. The method is a least-squares collocation method and the resulting normal equations are solved using preconditioned conjugate gradient method with an almost optimal preconditioner. The algorithm is suitable for a distributed memory parallel computer. The numerical results of a number of model problems are presented, which confirm the theoretical estimates.     

On the spectrum of the iteration operator associated to the finite element preconditioning of Chebyshev collocation calculations

An analytical investigation is performed of the spectrum of the iteration operator associated to the finite element preconditioning of Chebyshev collocation calculations, on a one-dimensional Dirichlet model problem. Use is made of the techniques developed by Haldenwang et al. for the finite difference preconditioning of the same problem. In the latter case the eigenvalues may be obtained as the diagonal elements of an upper-triangular matrix. This is not possible with finite element preconditioning, where the corresponding operator splits into two parts, one of which only is upper-triangular. Discarding the non-triangular part of the operator (which vanishes asymptotically for large values of N, partition size), this procedure yields an approximate expression of the eigenvalues in good agreement with the properties given earlier by Deville and Mund.     

A Runge-Kutta discontinuous Galerkin method for the Euler equations

This paper presents a Runge-Kutta discontinuous Galerkin (RKDG) method for the Euler equations of gas dynamics from the viewpoint of kinetic theory. Like the traditional gas-kinetic schemes, our proposed RKDG method does not need to use the characteristic decomposition or the Riemann solver in computing the numerical flux at the surface of the finite elements. The integral term containing the non-linear flux can be computed exactly at the microscopic level. A limiting procedure is carefully designed to suppress numerical oscillations. It is demonstrated by the numerical experiments that the proposed RKDG methods give higher resolution in solving problems with smooth solutions. Moreover, shock and contact discontinuities can be well captured by using the proposed methods.     

On the Numerical Solution of Some Semilinear Elliptic Problems – II

In the earlier paper [6], a Galerkin method was proposed and analyzed for the numerical solution of a Dirichlet problem for a semi-linear elliptic boundary value problem of the form –U=F(·,U). This was converted to a problem on a standard domain and then converted to an equivalent integral equation. Galerkins method was used to solve the integral equation, with the eigenfunctions of the Laplacian operator on the standard domain D as the basis functions. In this paper we consider the implementing of this scheme, and we illustrate it for some standard domains D.     

Theoretically supported scalable BETI method for variational inequalities

Summary The Boundary Element Tearing and Interconnecting (BETI) methods were recently introduced as boundary element counterparts of the well established Finite Element Tearing and Interconnecting (FETI) methods. Here we combine the BETI method preconditioned by the projector to the “natural coarse grid” with recently proposed optimal algorithms for the solution of bound and equality constrained quadratic programming problems in order to develop a theoretically supported scalable solver for elliptic multidomain boundary variational inequalities such as those describing the equilibrium of a system of bodies in mutual contact. The key observation is that the “natural coarse grid” defines a subspace that contains the solution, so that the preconditioning affects also the non-linear steps. The results are validated by numerical experiments.      

改进的变步长行加权仿射投影算法

针对带衰减因子的变步长仿射投影算法(VS-APA-FF)中加权投影矩阵容易产生病态化的问题,文献[8]提出了正则化的VS-APA-FF(vs-APA-FF-REGU)算法,但加权投影矩阵的运算量仍然较大,为此提出改进的行加权变步长仿射投影算法(VS-APA-RW)对加权投影矩阵的计算进行简化.该算法采用间歇更新的变步长策略,有效降低了的整体运算量.最后通过有色输入下的信道盲辨识表明了算法的性能.     

Hierarchical LU Decomposition-based Preconditioners for BEM

The adaptive cross approximation method can be used to efficiently approximate stiffness matrices arising from boundary element applications by hierarchical matrices. In this article an approximative LU decomposition in the same format is presented which can be used for preconditioning the resulting coefficient matrices efficiently. If the LU decomposition is computed with high precision, it may even be used as a direct yet efficient solver.     

Computation of Self-similar Solution Profiles for the Nonlinear Schrödinger Equation

We discuss the numerical computation of self-similar blow-up solutions of the classical nonlinear Schrödinger equation in three space dimensions. These solutions become unbounded in finite time at a single point at which there is a growing and increasingly narrow peak. The problem of the computation of this self-similar solution profile reduces to a nonlinear, ordinary differential equation on an unbounded domain. We show that a transformation of the independent variable to the interval [0,1] yields a well-posed boundary value problem with an essential singularity. This can be stably solved by polynomial collocation. Moreover, a Matlab solver developed by two of the authors can be applied to solve the problem efficiently and provides a reliable estimate of the global error of the collocation solution. This is possible because the boundary conditions for the transformed problem serve to eliminate undesired, rapidly oscillating solution modes and essentially reduce the problem of the computation of the physical solution of the problem to a boundary value problem with a singularity of the first kind. Furthermore, this last observation implies that our proposed solution approach is theoretically justified for the present problem.