Two-level Schwarz method for unilateral variational inequalities

The numerical solution of variational inequalities of obstacletype associated with second-order elliptic operators is considered.Iterative methods based on the domain decomposition approachare proposed for discrete obstacle problems arising from thecontinuous, piecewise linear finite element approximation ofthe differential problem. A new variant of the Schwarz methodology,called the two-level Schwarz method, is developed offering thepossibility of making use of fast linear solvers (e.g., linearmultigrid and fictitious domain methods) for the genuinely nonlinearobstacle problems. Namely, by using particular monotonicityresults, the computational domain can be partitioned into (mesh)subdomains with linear and nonlinear (obstacle-type) subproblems.By taking advantage of this domain decomposition and fast linearsolvers, efficient implementation algorithms for large-scalediscrete obstacle problems can be developed. The last part ofthe paper is devoted to illustrate numerical experiments.     

Numerical Solution of Time-Dependent Problems with a Fractional-Power Elliptic Operator

A time-dependent problem in a bounded domain for a fractional diffusion equation is considered. The first-order evolution equation involves a fractional-power second-order elliptic operator with Robin boundary conditions. A finite-element spatial approximation with an additive approximation of the operator of the problem is used. The time approximation is based on a vector scheme. The transition to a new time level is ensured by solving a sequence of standard elliptic boundary value problems. Numerical results obtained for a two-dimensional model problem are presented.     

A higher order uniformly convergent method for singularly perturbed parabolic turning point problems

In this article, we study numerical approximation for a class of singularly perturbed parabolic (SPP) convection-diffusion turning point problems. The considered SPP problem exhibits a parabolic boundary layer in the neighborhood of one of the sides of the domain. Some a priori bounds are given on the exact solution and its derivatives, which are necessary for the error analysis. A numerical scheme comprising of implicit finite difference method for time discretization on a uniform mesh and a hybrid scheme for spatial discretization on a generalized Shishkin mesh is proposed. Then Richardson extrapolation method is applied to increase the order of convergence in time direction. The resulting scheme has second-order convergence up to a logarithmic factor in space and second-order convergence in time. Numerical experiments are conducted to demonstrate the theoretical results and the comparative study is done with the existing schemes in literature to show better accuracy of the proposed schemes.     

The domain decomposition method for parabolic transmission problems

An estimate of the rate of convergence is given for the domain decomposition method for the second-order parabolic transmission problem. A brief discussion of the method and some of its applications are presented.     

Domain decomposition approaches for accelerating contour integration eigenvalue solvers for symmetric eigenvalue problems

This paper discusses techniques for computing a few selected eigenvalue–eigenvector pairs of large and sparse symmetric matrices. A recently developed class of techniques to solve this type of problems is based on integrating the matrix resolvent operator along a complex contour that encloses the interval containing the eigenvalues of interest. This paper considers such contour integration techniques from a domain decomposition viewpoint and proposes two schemes. The first scheme can be seen as an extension of domain decomposition linear system solvers in the framework of contour integration methods for eigenvalue problems, such as FEAST. The second scheme focuses on integrating the resolvent operator primarily along the interface region defined by adjacent subdomains. A parallel implementation of the proposed schemes is described, and results on distributed computing environments are reported. These results show that domain decomposition approaches can lead to reduced run times and improved scalability.     

A non-overlapping DDM combined with the characteristic method for optimal control problems governed by convection–diffusion equations

In this paper, we consider a non-overlapping domain decomposition method combined with the characteristic method for solving optimal control problems governed by linear convection–diffusion equations. The whole domain is divided into non-overlapping subdomains, and the global optimal control problem is decomposed into the local problems in these subdomains. The integral mean method is utilized for the diffusion term to present an explicit flux calculation on the inter-domain boundary in order to communicate the local problems on the interfaces between subdomains. The convection term is discretized along the characteristic direction. We establish the fully parallel and discrete schemes for solving these local problems. A priori error estimates in \(L^2\)-norm are derived for the state, co-state and control variables. Finally, we present numerical experiments to show the validity of the schemes and verify the derived theoretical results.     

Domain decomposition in conjunction with sinc methods for Poisson's equation

Efforts to develop sinc domain decomposition methods for second-order two-point boundary-value problems have been successful, thus warranting further development of these methods. A logical first step is to thoroughly investigate the extension of these methods to Poisson's equation posed on a rectangle. The Sinc-Galerkin and sinc-collocation methods are, for appropriate weight choices, identical for Poisson's equation, and thus only the Sinc-Galerkin system is discussed here. Both the Sinc-Galerkin patching method and the Sinc-Galerkin overlapping method are presented in the simple case of decomposition into two subdomains. Numerical results are presented for each of these methods, showing the convergence. As an indication of the capabilities of these domain decomposition techniques, they are applied to Poisson's equation on an L-shaped domain. Restrictions due to the method by which the discrete system is developed require that this problem be solved using nonoverlapping subdomains. Thus only the Sinc-Galerkin patching method is presented. Numerical results are presented that show the convergence of the approximate solutions, even in the presence of boundary singularities. © 1996 John Wiley & Sons, Inc.     

Flux-splitting schemes for parabolic equations with mixed derivatives

Difference schemes of required quality are often difficult to construct as applied to boundary value problems for parabolic equations with mixed derivatives. Specifically, difficulties arise in the design of monotone difference schemes and unconditionally stable locally one-dimensional splitting schemes. In parabolic problems, certain opportunities are offered by restating the problem in question so that the quantities to be determined are fluxes (directional derivatives). The original problem is then rewritten as a boundary value one for a system of equations in flux variables. Weighted schemes for parabolic equations in flux coordinates are examined. Unconditionally stable locally one-dimensional flux schemes that are first- and second-order accurate in time are constructed for a parabolic equation without mixed derivatives. A feature of systems in flux variables for equations with mixed derivatives is that the terms with time derivatives are coupled with each other.     

On Second-Order Proto-Differentiability of Perturbation Maps

In this paper, second-order sensitivity analysis in vector optimization problems is considered. We prove that the efficient solution map and the efficient frontier map of a parameterized vector optimization problem are second-order proto-differentiable under some appropriate qualification conditions. Some sufficient conditions for inner and outer approximation of the second-order proto-derivative are also provided.     

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

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

Stable difference schemes for certain parabolic equations

In some applications, boundary value problems for second-order parabolic equations with a special nonself-adjoint operator have to be solved approximately. The operator of such a problem is a weighted sum of self-adjoint elliptic operators. Unconditionally stable two-level schemes are constructed taking into account that the operator of the problem is not self-adjoint. The possibilities of using explicit-implicit approximations in time and introducing a new sought variable are discussed. Splitting schemes are constructed whose numerical implementation involves the solution of auxiliary problems with self-adjoint operators.     

The unconditional stable and convergent difference methods with intrinsic parallelism for quasilinear parabolic systems

A kind of the general finite difference schemes with intrinsic parallelism forthe boundary value problem of the quasilinear parabolic system is studied without assum-ing heuristically that the original boundary value problem has the unique smooth vectorsolution. By the method of a priori estimation of the discrete solutions of the nonlineardifference systems, and the interpolation formulas of the various norms of the discretefunctions and the fixed-point technique in finite dimensional Euclidean space, the exis-tence and uniqueness of the discrete vector solutions of the nonlinear difference systemwith intrinsic parallelism are proved. Moreover the unconditional stability of the generalfinite difference schemes with intrinsic parallelism is justified in the sense of the continu-ous dependence of the discrete vector solution of the difference schemes on the discretedata of the original problems in the discrete w_2~(2,1) norms. Finally the convergence of thediscrete vector solutions of the certain differe     

对流-扩散问题的特征──块中心差分法

１．引言１９８２年,Ｄｏｕｇｌａｓ和Ｒｕｓｓｅｌｌ［１］提出解对流一扩散问题的特征一差分方法,网格节点为均匀分布,求解区域为直线Ｒ．文中讨论了基于二次插值的特征一差分格式,但其近似解按离散Ｌ２模未达到最优阶误差估计．１９８８年Ｗｅｉｓｅｒ和Ｗｈｅｅｌｅｒ［２］提出解线性椭圆型和线性抛物型方程的块中心差分法,１９９１年王申林［３］讨论了解拟线性双曲型积分微分方程的块中心差分方法,其共同特点为近似解按离散的Ｌ２模达到最优阶误差估计,解的一阶导数的近似解达到超收敛误差估计．１９９３年由同顺［４］讨论了…     

An Improved Gradient Projection-based Decomposition Technique for Support Vector Machines

In this paper we propose some improvements to a recent decomposition technique for the large quadratic program arising in training support vector machines. As standard decomposition approaches, the technique we consider is based on the idea to optimize, at each iteration, a subset of the variables through the solution of a quadratic programming subproblem. The innovative features of this approach consist in using a very effective gradient projection method for the inner subproblems and a special rule for selecting the variables to be optimized at each step. These features allow to obtain promising performance by decomposing the problem into few large subproblems instead of many small subproblems as usually done by other decomposition schemes. We improve this technique by introducing a new inner solver and a simple strategy for reducing the computational cost of each iteration. We evaluate the effectiveness of these improvements by solving large-scale benchmark problems and by comparison with a widely used decomposition package.     

解椭圆变分不等式问题的区域分裂与异步并行算法

本文给出了两类解椭圆变分不等式问题的区域分裂异步并行算法，证明了解在Ｈ＾１－模意义下的收敛性，并给出离散格式及算例。     

Three-level schemes of the alternating triangular method

In this paper, the schemes of the alternating triangular method are set out in the class of splitting methods used for the approximate solution of Cauchy problems for evolutionary problems. These schemes are based on splitting the problem operator into two operators that are conjugate transposes of each other. Economical schemes for the numerical solution of boundary value problems for parabolic equations are designed on the basis of an explicit-implicit splitting of the problem operator. The alternating triangular method is also of interest for the construction of numerical algorithms that solve boundary value problems for systems of partial differential equations and vector systems. The conventional schemes of the alternating triangular method used for first-order evolutionary equations are two-level ones. The approximation properties of such splitting methods can be improved by transiting to three-level schemes. Their construction is based on a general principle for improving the properties of difference schemes, namely, on the regularization principle of A.A. Samarskii. The analysis conducted in this paper is based on the general stability (or correctness) theory of operator-difference schemes.     

Domain Decomposition,Optimal Control of Systems Governed by Partial Differential Equations,and Synthesis of Feedback Laws

We present an iterative domain decomposition method for the optimal control of systems governed by linear partial differential equations. The equations can be of elliptic, parabolic, or hyperbolic type. The space region supporting the partial differential equations is decomposed and the original global optimal control problem is reduced to a sequence of similar local optimal control problems set on the subdomains. The local problems communicate through transmission conditions, which take the form of carefully chosen boundary conditions on the interfaces between the subdomains. This domain decomposition method can be combined with any suitable numerical procedure to solve the local optimal control problems. We remark that it offers a good potential for using feedback laws (synthesis) in the case of time-dependent partial differential equations. A test problem for the wave equation is solved using this combination of synthesis and domain decomposition methods. Numerical results are presented and discussed. Details on discretization and implementation can be found in Ref. 1.     

On parallel asynchronous high-order solutions of parabolic PDEs

In achieving significant speed-up on parallel machines, a major obstacle is the overhead associated with synchronizing the concurrent processes. This paper presents high-orderparallel asynchronous schemes, which are schemes that are specifically designed to minimize the associated synchronization overhead of a parallel machine in solving parabolic PDEs. They are asynchronous in the sense that each processor is allowed to advance at its own speed. Thus, these schemes are suitable for single (or multi) user shared memory or (message passing) MIMD multiprocessors. Our approach is demonstrated for the solution of the multidimensional heat equation, of which we present a spatial second-order Parametric Asynchronous Finite-Difference (PAFD) scheme. The well-known synchronous schemes are obtained as its special cases. This is a generalization and expansion of the results in [5] and [7]. The consistency, stability and convergence of this scheme are investigated in detail. Numerical tests show that although PAFD provides the desired order of accuracy, its efficiency is inadequate when performed on each grid point.In an alternative approach that uses domain decomposition, the problem domain is divided among the processors. Each processor computes its subdomain mostly independently, while the PAFD scheme provides the solutions at the subdomains' boundaries. We use high-order finite-difference implicit scheme within each subdomain and determine the values at subdomains' boundaries by the PAFD scheme. Moreover, in order to allow larger time-step, we use remote neighbors' values rather than those of the immediate neighbors. Numerical tests show that this approach provides high efficiency and in the case which uses remote neighbors' values an almost linear speedup is achieved. Schemes similar to the PAFD can be developed for other types of equations [3].This research was supported by the fund for promotion of research at the Technion.     

Nonlinear fourth-order elliptic equations with nonlocal boundary conditions

This paper is concerned with a class of fourth-order nonlinear elliptic equations with nonlocal boundary conditions, including a multi-point boundary condition in a bounded domain of Rn. Also considered is a second-order elliptic equation with nonlocal boundary condition, and the usual multi-point boundary problem in ordinary differential equations. The aim of the paper is to show the existence of maximal and minimal solutions, the uniqueness of a positive solution, and the method of construction for these solutions. Our approach to the above problems is by the method of upper and lower solutions and its associated monotone iterations. The monotone iterative schemes can be developed into computational algorithms for numerical solutions of the problem by either the finite difference method or the finite element method.     

Implicit Solution of a Two-Dimensional Parabolic Inverse Problem with Temperature Overspecification

Three different implicit finite difference schemes for solving the two-dimensional parabolic inverse problem with temperature overspecification are considered. These schemes are developed for indentifying the control parameter which produces, at any given time, a desired temperature distribution at a given point in the spatial domain. The numerical methods discussed, are based on the second-order (5,1) Backward Time Centered Space (BTCS) implicit formula, and the second-order (5,5) Crank-Nicolson implicit finite difference formula and the fourth-order (9,9) implicit scheme. These finite difference schemes are unconditionally stable. The (9,9) implicit formula takes a huge amount of CPU time, but its fourth-order accuracy is significant. The results of a numerical experiment are presented, and the accuracy and central processor (CPU) times needed for each of the methods are discussed and compared. The implicit finite difference schemes use more central processor times than the explicit finite difference techniques, but they are stable for every diffusion number.