求解二维半线性抛物方程的校正型显隐区域分解算法

本文研究了利用分布式并行计算系统求解二维半线性抛物方程的内边界校正型显隐区域分解（CEIDD）算法．在实际问题中通常利用简洁的直线内边界（sI）将空间区域分解成若干个相互不重叠的条状或块状子区域．利用Leray-Schauder不动点定理和离散能量方法证明了基于不交叉直线内边界的CEIDD—SI算法的唯一可解性,无条件稳定性和收敛性,并得到了一个改进的误差估计．当直线内边界在区域内部相互交叉时,这种在内边界上追加了隐式校正步的算法需要在每一个时间层进行全局通信,从而使算法的并行可扩展性大为降低．为克服这一缺点,设计了一种由直线和锯齿形接点组合而成的复合内边界（CI）．分析表明,基于复合内边界的CEIDD—CI算法无条件稳定、通信效率高、可以直接利用现有的串行算法计算子区域的隐式解,是一类可扩展的并行算法．为验证算法的稳定性和收敛性,文中给出了两个具体算例．     

基于信赖域技术的处理带线性约束优化的内点算法

基于信赖域技术,本文提出了一个求解带线性等式和非负约束优化问题的内点算法,其特点是:为了求得搜索方向,算法在每一步迭代时仅需要求解一线性方程组系统,从而避免了求解带信赖域界的子问题,然后利用非精确的Armijo线搜索法来得到下一个迭代内点. 从数值计算的观点来看,这种技巧可减少计算量.在适当的条件下,文中还证明了该算法所产生的迭代序列的每一个聚点都是原问题的KKT点.     

一个求解P_*(κ)水平线性互补问题精确极大互补解的不可行内点算法(英文)

Stoer,Wechs,和Mizuno最近提出了一个求解P_*(k)水平线性互补问题的不可行内点算法,他们的算法能在有限不内得到问题的一个精确解,但是没有讨论算法的多项式复杂性．本文提出一个能得到P_*(k)水平线性互补问题精确极大互补解的不可行内点算法,通过使用条件数和误差界理论,我们证明了所给算法是多项式有界的．     

一类大规模二次规划问题的可行下降分解算法

本文对一类大规模二次规划问题，提出了矩阵剖分的概念和方法，并将问题转化为求解一系列容易求解的小规模二次规划子问题．另外，通过施加某些约束机制，使子问题所产生的迭代点均为可行下降点．在通常的假定下，证明算法具有全局收敛性，大量数值实验表明，本文所提出的新算法是有效的。     

一个解界约束非线性方程组的无导数回溯线搜索仿射内点信赖域方法（英文）

文章给出了一个求解界约束非线性方程组的无导数回溯线搜索仿射内点信赖域方法.该方法利用非线性方程组的特点,对方程组中每一个函数建立插值模型.通过利用信赖域模型和回溯先搜索技术的结合,利用插值信赖域子问题子问题求解搜索方向,并利用回溯先搜索技术保证可行性.在合理的假设条件下,证明了算法的全局和快速局部收敛性.并且,通过数值实验表明该种无导数算法对求解界约束非线性方程组问题是有效的.     

结合有效集和多维滤子技术的拟Newton信赖域算法(英文)

针对界约束优化问题,提出一个修正的多维滤子信赖域算法.将滤子技术引入到拟Newton信赖域方法,在每步迭代,Cauchy点用于预测有效集,此时试探步借助于求解一个较小规模的信赖域子问题获得.在一定条件下,本文所提出的修正算法对于凸约束优化问题全局收敛.数值试验验证了新算法的实际运行结果.     

同伦方法求解非凸区域Brouwer不动点问题

本文构造了一个新的求解非凸区域上不动点问题的内点同伦算法,并在弱法锥(见定义2．1(2))和适当的条件下,证明了算法的全局收敛性．本文所给的条件比外法锥条件更加一般．     

定常Stokes方程一种基于完全区域分解的有限元并行算法

基于完全区域分解技巧,提出了一种求解定常Stokes方程的有限元并行算法．该算法中,所有子问题都是定义在整个求解区域上,但绝大部分自由度来自其所负责的子区域,从而使得算法稍加修改现有的串行程序即可实现相应的并行计算,实现简单,通信需求少．数值结果验证了算法的高效性．     

半定规划的一个新的宽邻域非可行内点算法

基于一种新的宽邻域,提出一个求解半定规划的新的非可行内点算法．在适当的假设条件下,证明了该算法具有较好的迭代复杂界O（√nL）,优于目前此类算法的最好的复杂性O（n√nL）,等同于可行内点算法．     

求解正定二次规划的一个全局收敛的滤子内点算法

现有的大多数分类问题都能转化成一个正定二次规划问题的求解.通过引入滤子方法,并结合求解非线性规划的原始对偶内点法,给出求解正定二次规划的滤子内点算法.该算法避免了使用效益函数时选取罚因子的困难,在较弱的假设条件下,算法具有全局收敛性.     

结构三角网上抛物方程的有限差分区域分解算法

1引言对于大型科学与工程计算问题,并行计算是必需的．构造高效率的数值并行方法一直是人们关心的问题,并且已有了大量的研究．在三层交替计算方法的研究中出现了许多既具有明显并行性又绝对稳定的差分格式(见[1]-[5])．在只涉及两个时间层的算法研究中,Dawson等人(见[6])首先发展了求解一维热传导方程的区域分解算法,并将其推广到     

Iterative methods for a forward-backward heat equation in two-dimension

A finite difference method is introduced to solve the forward-backward heat equation in two space dimensions. In this procedure, the backward and forward difference scheme in two subdomains and a coarse-mesh second-order central difference scheme at the middle interface are used. Maximum norm error estimate for the procedure is derived. Then an iterative method based on domain decomposition is presented for the numerical scheme and the convergence of the given method is established. Then numerical experiments are presented to support the theoretical analysis.     

A relaxation procedure for domain decomposition methods using finite elements

Summary We present the convergence analysis of a new domain decomposition technique for finite element approximations. This technique was introduced in [11] and is based on an iterative procedure among subdomains in which transmission conditions at interfaces are taken into account partly in one subdomain and partly in its adjacent. No global preconditioner is needed in the practice, but simply single-domain finite element solvers are required. An optimal strategy for an automatic selection of a relaxation parameter to be used at interface subdomains is indicated. Applications are given to both elliptic equations and incompressible Stokes equations.     

Parallel algorithm for the solutions of PDEs in linux clustered workstations

In this paper we propose parallel algorithm for the solution of partial differential equations over a rectangular domain using the Crank–Nicholson method by cooperation with the DuFort–Frankel method and apply it on a model problem, namely, the heat conduction equation. One of the well known parallel techniques in solving partial differential equations in cluster computing environment is the domain decomposition technique. Using this technique, the whole domain is decomposed into subdomains, each of them has its own boundaries that are called the interface points. Parallelization is realized by approximating interface values using the unconditionally stable DuFort–Frankel explicit scheme, and these values serve as Neumann boundary conditions for the Crank–Nicholson implicit scheme in the subdomains. The numerical results show that our algorithm is more accurate than the algorithm based on the forward explicit method to approximate the values of the interface points, especially, when we use a small number of time steps. Moreover, these numerical results show that increasing the number of processors which are used in the cluster, yields an increase in the algorithm speedup.     

A PARALLEL ITERATIVE DOMAIN DECOMPOSITION ALGORITHM FOR ELLIPTIC PROBLEMS

1.IntroductionNolloverlappillgdomaindecolllpositionnletllodshavereceivedalotofattentionlenlsilllldallowefficielltparallelisnl.F'Orarecentdevelopmelltofthesemethods,werefertot…     

Nonoverlapping domain decomposition and additive splitting up methods for multidimensional parabolic problem

The explicit implicit domain decomposition methods are noniterative types of methods for nonoverlapping domain decomposition but due to the use of the explicit step for the interface prediction, the methods suffer from inaccuracy of the usual explicit scheme. In this article a specific type of first‐ and second‐order splitting up method, of additive type, for the dependent variables is initially considered to solve the two‐ or three‐dimensional parabolic problem over nonoverlapping subdomains. We have also considered the parallel explicit splitting up algorithm to define (predict) the interface boundary conditions with respect to each spatial variable and for each nonoverlapping subdomains. The parallel second‐order splitting up algorithm is then considered to solve the subproblems defined over each subdomain; the correction step will then be considered for the predicted interface nodal points using the most recent solution values over the subdomains. Finally several model problems will be considered to test the efficiency of the presented algorithm. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2006     

Construction of direct and iterative decomposition methods

In order to solve boundary value problems with the Dirichlet-Dirichlet type conditions by decomposing the computational domain into subdomains joined without overlapping, the discrete Green’s functions are used to approximate the Poincaré-Steklov operator equation on the interface of the subdomains, which involves the difference of the normal derivatives of the solution on the opposite sides of the interface. Basing on this approach, some direct and iterative decomposition methods are constructed that are basically of a parallel nature. Examples of numerical computations demonstrate the accuracy and convergence of the algorithms.     

Studies of an interface relaxation domain decomposition technique using finite elements on a parallel computer

Studies are presented for an interface relaxation domain decomposition technique using finite elements on an iPSC/2 D5 Hypercube Concurrent computer. The general type of problem to be solved is one governed by a partial differential equation. The application of the approach, however, will be extended to a free boundary value problem by appropriate modification of the numerical scheme. Using the domain decomposition technique, the computation domain is subdivided into several subdomains. In addition, on the interfaces between two adjacent subdomains are imposed a continuity condition on one side and an equilibrium condition on the other side. Successive overrelaxation iterative processes are then carried out in all subdomains with a relaxation process imposed on the interfaces. With this domain decomposition technique, the problem can be solved parallelly until convergence is reached both in the interiors and on the interfaces of all subdomains. Moreover, the formulation includes a simple domain decomposer that automatically divides a finite element mesh into a list of subdomains to guarantee load balancing. Furthermore, it is shown, through numerical experiments performed on an example problem of free surface seepage through a porous dam, how the values of the relaxation parameters, the choice of imposed boundary conditions, and the number of subdomains (i.e., the number of processors used) affect the solution convergence in this parallel computing environment. © 1993 John Wiley & Sons, Inc.     

A Dual-Primal FETI method for incompressible Stokes equations

In this paper, a dual-primal FETI method is developed for incompressible Stokes equations approximated by mixed finite elements with discontinuous pressures. The domain of the problem is decomposed into nonoverlapping subdomains, and the continuity of the velocity across the subdomain interface is enforced by introducing Lagrange multipliers. By a Schur complement procedure, the solution of an indefinite Stokes problem is reduced to solving a symmetric positive definite problem for the dual variables, i.e., the Lagrange multipliers. This dual problem is solved by the conjugate gradient method with a Dirichlet preconditioner. In each iteration step, both subdomain problems and a coarse level problem are solved by a direct method. It is proved that the condition number of this preconditioned dual problem is independent of the number of subdomains and bounded from above by the square of the product of the inverse of the inf-sup constant of the discrete problem and the logarithm of the number of unknowns in the individual subdomains. Numerical experiments demonstrate the scalability of this new method. This work is based on a doctoral dissertation completed at Courant Institute of Mathematical Sciences, New York University. This work was supported in part by the National Science Foundation under Grants NSF-CCR-9732208, and in part by the U.S. Department of Energy under contract DE-FG02-92ER25127.     

Iterative solution of a coupled mixed and standard Galerkin discretization method for elliptic problems

In this paper, we consider approximation of a second‐order elliptic problem defined on a domain in two‐dimensional Euclidean space. Partitioning the domain into two subdomains, we consider a technique proposed by Wieners and Wohlmuth [9] for coupling mixed finite element approximation on one subdomain with a standard finite element approximation on the other. In this paper, we study the iterative solution of the resulting linear system of equations. This system is symmetric and indefinite (of saddle‐point type). The stability estimates for the discretization imply that the algebraic system can be preconditioned by a block diagonal operator involving a preconditioner for H (div) (on the mixed side) and one for the discrete Laplacian (on the finite element side). Alternatively, we provide iterative techniques based on domain decomposition. Utilizing subdomain solvers, the composite problem is reduced to a problem defined only on the interface between the two subdomains. We prove that the interface problem is symmetric, positive definite and well conditioned and hence can be effectively solved by a conjugate gradient iteration. Copyright © 2001 John Wiley & Sons, Ltd.