Parallel characteristic finite element method for time‐dependent convection–diffusion problem

Based on the overlapping‐domain decomposition and parallel subspace correction method, a new parallel algorithm is established for solving time‐dependent convection–diffusion problem with characteristic finite element scheme. The algorithm is fully parallel. We analyze the convergence of this algorithm, and study the dependence of the convergent rate on the spacial mesh size, time increment, iteration times and sub‐domains overlapping degree. Both theoretical analysis and numerical results suggest that only one or two iterations are needed to reach to optimal accuracy at each time step. Copyright © 2010 John Wiley & Sons, Ltd.     

热传导方程的一类新型重叠型并行区域分解有限差分算法

0引言随着大规模科学工程计算的发展和计算精度要求的提高,区域分解和并行计算的发展越来越受到人们的重视.区域分解方法把复杂或大型的问题分解成若干重叠或非重叠子区域上的子问题,再在子区域上利用各种算法求解子问题.借助于区域分解,各子区域之间的计算可以并行,这引起了人们的研究兴趣和极大的应用前景.重叠型区域分解法的原始思想来源于Schwarz交替法.近年来建立在Schwarz交替法基础上的区域分解法在理论分析和实际应用中取得令人注目的发展,已成为一种有效的迭代方法.经典的Schwarz交替法本质上是串行的.随着并行计算的发展,出现了多种可完全并行化的Schwarz算法     

Perturbed fixed point iterative methods based on pattern structure

We introduce a new idea of algorithmic structure, called assigning algorithm, using a finite collection of a subclass of strictly quasi‐nonexpansive operators. This new algorithm allows the iteration vectors to take steps on a pattern which is based on a connected directed acyclic graph. The sequential, simultaneous, and string‐averaging methods for solving convex feasibility problems are the special cases of the new algorithm which may be used to reduce idle time of processors in parallel implementations. We give a convergence analysis for such algorithmic structure with perturbation. Also, we extend some existence results of the split common fixed point problem based on the new algorithm. The performance of the new algorithm is illustrated with numerical examples from computed tomography.     

New Parallel Descent-like Method for Solving a Class of Variational Inequalities

To solve a class of variational inequalities with separable structures, some classical methods such as the augmented Lagrangian method and the alternating direction methods require solving two subvariational inequalities at each iteration. The most recent work (B.S. He in Comput. Optim. Appl. 42(2):195–212, 2009) improved these classical methods by allowing the subvariational inequalities arising at each iteration to be solved in parallel, at the price of executing an additional descent step. This paper aims at developing this strategy further by refining the descent directions in the descent steps, while preserving the practical characteristics suitable for parallel computing. Convergence of the new parallel descent-like method is proved under the same mild assumptions on the problem data.     

Domain decomposition for radial basis meshless methods

Both overlapping and nonoverlapping domain decomposition methods (DDM) on matching and nonmatching grid have been developed to couple with the meshless radial basis function (RBF) method. Example shows that overlapping DDM with RBF can achieve much better accuracy with less nodal points compared to FDM and FEM. Numerical results also show that nonmatching grid DDM can achieve almost the same accuracy within almost the same iteration steps as the matching grid case; hence our method is very attractive, because it is much easier to generate nonmatching grid just by putting blocks of grids together (for both overlapping and nonoverlapping), where each block grid can be generated independently. Also our methods are showed to be able to handle discontinuous coefficient. © 2004 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 20: 450–462, 2004.     

求解一类非线性互补问题的松弛two-sweep模系矩阵分裂迭代法

本文构造了求解一类非线性互补问题的松弛two-sweep模系矩阵分裂迭代法. 理论分析建立了新方法在系数矩阵为正定矩阵或H₊矩阵时的收敛性质．数值实验结果表明新方法是行之有效的, 并且在最优参数下松弛two-sweep模系矩阵分裂迭代法在迭代步数和时间上均优于传统的模系矩阵分裂迭代法和two-sweep模系矩阵分裂迭代法.     

Block and asynchronous two-stage methods for mildly nonlinear systems

Block parallel iterative methods for the solution of mildly nonlinear systems of equations of the form are studied. Two-stage methods, where the solution of each block is approximated by an inner iteration, are treated. Both synchronous and asynchronous versions are analyzed, and both pointwise and blockwise convergence theorems provided. The case where there are overlapping blocks is also considered. The analysis of the asynchronous method when applied to linear systems includes cases not treated before in the literature. Received June 5, 1997 / Revised version received December 29, 1997     

Modulus‐based synchronous multisplitting iteration methods for linear complementarity problems

By an equivalent reformulation of the linear complementarity problem into a system of fixed‐point equations, we construct modulus‐based synchronous multisplitting iteration methods based on multiple splittings of the system matrix. These iteration methods are suitable to high‐speed parallel multiprocessor systems and include the multisplitting relaxation methods such as Jacobi, Gauss–Seidel, successive overrelaxation, and accelerated overrelaxation of the modulus type as special cases. We establish the convergence theory of these modulus‐based synchronous multisplitting iteration methods and their relaxed variants when the system matrix is an H ₊ ‐matrix. Numerical results show that these new iteration methods can achieve high parallel computational efficiency in actual implementations. Copyright © 2012 John Wiley & Sons, Ltd.     

Two-Stage Multisplitting Iteration Methods Using Modulus-Based Matrix Splitting as Inner Iteration for Linear Complementarity Problems

The matrix multisplitting iteration method is an effective tool for solving large sparse linear complementarity problems. However, at each iteration step we have to solve a sequence of linear complementarity sub-problems exactly. In this paper, we present a two-stage multisplitting iteration method, in which the modulus-based matrix splitting iteration and its relaxed variants are employed as inner iterations to solve the linear complementarity sub-problems approximately. The convergence theorems of these two-stage multisplitting iteration methods are established. Numerical experiments show that the two-stage multisplitting relaxation methods are superior to the matrix multisplitting iteration methods in computing time, and can achieve a satisfactory parallel efficiency.     

Accelerated modulus-based matrix splitting iteration methods for linear complementarity problem

For the large sparse linear complementarity problem, a class of accelerated modulus-based matrix splitting iteration methods is established by reformulating it as a general implicit fixed-point equation, which covers the known modulus-based matrix splitting iteration methods. The convergence conditions are presented when the system matrix is either a positive definite matrix or an H ₊-matrix. Numerical experiments further show that the proposed methods are efficient and accelerate the convergence performance of the modulus-based matrix splitting iteration methods with less iteration steps and CPU time.     

An infeasible interior-point algorithm based on modified Nesterov and Todd directions for symmetric linear complementarity problem

We present an infeasible interior-point algorithm for symmetric linear complementarity problem based on modified Nesterov–Todd directions by using Euclidean Jordan algebras. The algorithm decreases the duality gap and the feasibility residual at the same rate. In this algorithm, we construct strictly feasible iterates for a sequence of perturbations of the given problem. Each main iteration of the algorithm consists of a feasibility step and a number of centring steps. The starting point in the first iteration is strictly feasible for a perturbed problem. The feasibility steps lead to a strictly feasible iterate for the next perturbed problem. By using centring steps for the new perturbed problem, a strictly feasible iterate is obtained to be close to the central path of the new perturbed problem. Furthermore, giving a complexity analysis of the algorithm, we derive the currently best-known iteration bound for infeasible interior-point methods.     

Parallel multisplitting two-stage iterative methods for large sparse systems of weakly nonlinear equations

The finite difference or the finite element discretizations of many differential or integral equations often result in a class of systems of weakly nonlinear equations. In this paper, by reasonably applying both the multisplitting and the two-stage iteration techniques, and in accordance with the special properties of this system of weakly nonlinear equations, we first propose a general multisplitting two-stage iteration method through the two-stage multiple splittings of the system matrix. Then, by applying the accelerated overrelaxation (AOR) technique of the linear iterative methods, we present a multisplitting two-stage AOR method, which particularly uses the AOR-like iteration as inner iteration and is substantially a relaxed variant of the afore-presented method. These two methods have a forceful parallel computing function and are much more suitable to the high-speed multiprocessor systems. For these two classes of methods, we establish their local convergence theories, and precisely estimate their asymptotic convergence factors under some suitable assumptions when the involved nonlinear mapping is only directionally differentiable. When the system matrix is either an H-matrix or a monotone matrix, and the nonlinear mapping is a P-bounded mapping, we thoroughly set up the global convergence theories of these new methods. Moreover, under the assumptions that the system matrix is monotone and the nonlinear mapping is isotone, we discuss the monotone convergence properties of the new multisplitting two-stage iteration methods, and investigate the influence of the multiple splittings as well as the relaxation parameters upon the convergence behaviours of these methods. Numerical computations show that our new methods are feasible and efficient for parallel solving of the system of weakly nonlinear equations. This revised version was published online in August 2006 with corrections to the Cover Date.     

Parallel iterative solvers for boundary value methods

A parallel variant of the block Gauss-Seidel iteration for the solution of block-banded linear systems is presented. The coefficient matrix is partitioned among the processors as in the domain decomposition methods and then it is split so that the resulting iterative method has the same spectral properties of the block Gauss-Seidel iteration.The parallel algorithm is applied to the solution of block-banded linear systems arising from the numerical discretization of initial value problems by means of Boundary Value Methods (BVMs). BVMs define a new approach for the solution of ordinary differential equations and seem to be attractive for their interesting stability properties and a possible parallel implementation. In this paper, we refer to BVMs based on the extended trapezoidal rules.     

A CLASS OF NEW PARALLEL HYBRID ALGEBRAIC MULTILEVEL ITERATIONS

1. IntroductionConsider the large sparse system of linear equationsAx = b, (1.1)where, for a fixed positive integer cr, A e L(R") is a symmetric positive definite (SPD) matrir,having the bloCked formx,b E R" are the uDknwn and the known vectors, respectively, having the correspondingblocked formsni(ni S n, i = 1, 2,', a) are a given positthe integers, satisfying Z ni = n. This systemi= 1of linear equations often arises in sultable finite element discretizations of many secondorderseifad…     

Preconditioned Dynamic Iteration for Coupled Differential-Algebraic Systems

The network approach to the modelling of complex technical systems results frequently in a set of differential-algebraic systems that are connected by coupling conditions. A common approach to the numerical solution of such coupled problems is based on the coupling of standard time integration methods for the subsystems. As a unified framework for the convergence analysis of such multi-rate, multi-method or dynamic iteration approaches we study in the present paper the convergence of a dynamic iteration method with a (small) finite number of iteration steps in each window. Preconditioning is used to guarantee stability of the coupled numerical methods. The theoretical results are applied to quasilinear problems from electrical circuit simulation and to index-3 systems arising in multibody dynamics.     

Modulus-based synchronous two-stage multisplitting iteration methods for linear complementarity problems

In order to solve large sparse linear complementarity problems on parallel multiprocessor systems, we construct modulus-based synchronous two-stage multisplitting iteration methods based on two-stage multisplittings of the system matrices. These iteration methods include the multisplitting relaxation methods such as Jacobi, Gauss–Seidel, SOR and AOR of the modulus type as special cases. We establish the convergence theory of these modulus-based synchronous two-stage multisplitting iteration methods and their relaxed variants when the system matrix is an H _?+?-matrix. Numerical results show that in terms of computing time the modulus-based synchronous two-stage multisplitting relaxation methods are more efficient than the modulus-based synchronous multisplitting relaxation methods in actual implementations.     

具有完全并行度的SOR算法

1　引　　言Jacobi和 SOR迭代是求解线性方程组的两类基本的迭代方法 .并行计算机的出现使人们能立刻注意到它们在拥有并行处理性能上的显著差别 .Jacobi迭代因其各个分量的修正相互独立而具有十分明显的内在并行计算特性 .SOR则完全不同 ,其中诸分量的计算是逐个相关的 .由此而导致一般认为 SOR不适合并行处理 ,其内在并行性远不如 Jacobi迭代[1 ] [2 ] .由于 SOR多用于有限差分或有限元方法导致的大型稀疏方程组求解 ,因此 ,利用系数矩阵零元素或非零元素的特殊分布 ,采用红 -黑或多色排序成为实现 SOR并行处理的有效途径 .然而 ,…     

A new infeasible interior-point method based on Darvay’s technique for symmetric optimization

We present a full Nesterov and Todd step primal-dual infeasible interior-point algorithm for symmetric optimization based on Darvay’s technique by using Euclidean Jordan algebras. The search directions are obtained by an equivalent algebraic transformation of the centering equation. The algorithm decreases the duality gap and the feasibility residuals at the same rate. During this algorithm we construct strictly feasible iterates for a sequence of perturbations of the given problem and its dual problem. Each main iteration of the algorithm consists of a feasibility step and some centering steps. The starting point in the first iteration of the algorithm depends on a positive number ξ and it is strictly feasible for a perturbed pair. The feasibility steps find strictly feasible iterates for the next perturbed pair. By using centering steps for the new perturbed pair, we obtain strictly feasible iterates close to the central path of the new perturbed pair. The algorithm finds an ?-optimal solution or detects infeasibility of the given problem. Moreover, we derive the currently best known iteration bound for infeasible interior-point methods.     

Accelerated modulus-based matrix splitting iteration methods for a restricted class of nonlinear complementarity problems

To solve a class of nonlinear complementarity problems, accelerated modulus-based matrix splitting iteration methods are presented and analyzed. Convergence analysis and the choice of the parameters are given when the system matrix is either positive definite or an H ₊-matrix. Numerical experiments further demonstrate that the proposed methods are efficient and have better performance than the existing modulus-based iteration method in aspects of the number of iteration steps and CPU time.     

A space decomposition method for parabolic equations

A convergence proof is given for an abstract parabolic equation using general space decomposition techniques. The space decomposition technique may be a domain decomposition method, a multilevel method, or a multigrid method. It is shown that if the Euler or Crank–Nicolson scheme is used for the parabolic equation, then by suitably choosing the space decomposition, only O(| log τ |) steps of iteration at each time level are needed, where τ is the time-step size. Applications to overlapping domain decomposition and to a two-level method are given for a second-order parabolic equation. The analysis shows that only a one-element overlap is needed. Discussions about iterative and noniterative methods for parabolic equations are presented. A method that combines the two approaches and utilizes some of the good properties of the two approaches is tested numerically. © 1998 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 14: 27–46, 1998