Adjoint-coordinated approximations and economical discrete implementations in a dynamic problem of the linear theory of elasticity

For dynamic three-dimensional problems of the elasticity theory, we construct a new class of economical implicit difference schemes with high degree of parallelism. They include difference schemes whose parallelism degree is the same as for ordinary explicit schemes. So far, even the very existence of implicit schemes with the same parallelism degree has been strongly doubted.     

对流扩散方程区域分裂特征差分方法

1引言对流扩散方程是许多物理问题的数学模型,研究其稳定的数值解法具有重要的应用价值．而标准的差分法和有限元法通常会失效,出现数值振荡．80年代,Douglas和Russel提出了特征线方法,在一定程度上克服了数值振荡,保证了数值的稳定,尤其对“对流占优”问题,更能突出特征法的优越性,并有了大量的理论成果[1,2,3]．区域分裂是一种解决大规模的科学与工程计算问题的有效方法,Dawson,Du和Dupont对热传导方程给出了非重叠区域分裂格式及分析,由于内边界的显格式,需要一定的稳定性条件Δt≤CH2;而Du等在[5]给出了抛物方程的几种区域分裂格式,对区域分裂法的     

高维抛物方程迎风区域分裂差分方法

结合迎风方法和区域分裂思想,采用一阶迎风、二阶修正迎风法逼近高维抛物方程的对流项.内边界处和子区域分别对应区域分裂显隐格式;并运用极值原理和嵌入定理给出了收敛性分析,最后给出数值试验,说明其实际意义.     

UNCONDITIONAL STABLE DIFFERENCE METHODS WITH INTRINSIC PARALLELISM FOR SEMILINEAR PARABOLIC SYSTEMS OF DIVERGENCE TYPE

The general finite difference schemes with intrinsic parallelism for the boundary value problem of the semilinear parabolic system of divergence type with bounded measurable coefficients is studied. By the approach of the discrete functional analysis, the existence and uniqueness of the discrete vector solutions of the nonlinear difference system with intrinsic parallelism are proved. Moreover the unconditional stability of the general difference schemes with intrinsic parallelism justified in the sense of the continuous dependence of the discrete vector solution of the difference schemes on the discrete initial data of the original problems in the discrete W_2~(2,1) (Q△) norms. Finally the convergence of the discrete vector solutions of the certain difference schemes with intrinsic parallelism to the unique generalized solution of the original semilinear parabolic problem is proved.     

Mono-implicit Runge-Kutta schemes for the parallel solution of initial value ODEs

Among the numerical techniques commonly considered for the efficient solution of stiff initial value ordinary differential equations are the implicit Runge-Kutta (IRK) schemes. The calculation of the stages of the IRK method involves the solution of a nonlinear system of equations usually employing some variant of Newton's method. Since the costs of the linear algebra associated with the implementation of Newton's method generally dominate the overall cost of the computation, many subclasses of IRK schemes, such as diagonally implicit Runge-Kutta schemes, singly implicit Runge-Kutta schemes, and mono-implicit (MIRK) schemes, have been developed to attempt to reduce these costs. In this paper we are concerned with the design of MIRK schemes that are inherently parallel in that smaller systems of equations are apportioned to concurrent processors. This work builds on that of an earlier investigation in which a special subclass of the MIRK formulas were implemented in parallel. While suitable parallelism was achieved, the formulas were limited to some extent because they all had only stage order 1. This is of some concern since in the application of a Runge-Kutta method to a system of stiff ODEs the phenomenon of order reduction can arise; the IRK method can behave as if its order were only its stage order (or its stage order plus one), regardless of its classical order. The formulas derived in the current paper represent an improvement over the previous investigation in that the full class of MIRK formulas is considered and therefore it is possible to derive efficient, parallel formulas of orders 2, 3, and 4, having stage orders 2 or 3.     

THE UNCONDITIONAL STABLE DIFFERENCE METHODS WITH INTRINSIC PARALLELISM FOR TWO DIMENSIONAL SEMILINEAR PARABOLIC SYSTEMS

In this paper we are going to discuss the difference schemes with intrinsic parallelism for the boundary value problem of the two dimesional semilinear parabolic systems.The unconditional stability of the general finite difference schemes with intrinsic parallelism is justified in the sense of the continuous dependence of the discrete vector solution of the difference schemes on the discrete data of the original problems in the discrete W2^(2,1) norms.Then the uniqueness of the discrete vector solution of this difference scheme follows as the consequence of the stability.     

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     

扩散方程一种无条件稳定的保正并行有限差分方法

本文针对扩散方程提出了一种保正的并行差分格式,并且这个格式为无条件稳定的.我们在每个时间层将计算区域分成许多个子区域以便于实施并行计算.格式构造中首先我们使用前两个时间层的计算结果在分区界面处通过一种非线性的保正外插来预估子区域界面值.然后在每个子区域内部使用经典的全隐格式进行计算.最后在界面处使用全隐格式进行校正（本质上这一步计算是显式计算）.我们给出了一维与二维情形下的保正并行差分格式,并相应的给出了无条件稳定性证明.数值实验显示此并行格式具有二阶数值精度,而且无条件稳定性与保正性也均在数值实验中得到验证.     

Unconditional stability of parallel alternating difference schemes for semilinear parabolic systems

The general alternating schemes with intrinsic parallelism for semilinear parabolic systems are studied. First we prove the a priori estimates in the discrete H¹ space of the difference solution for these schemes. Then the existence of the difference solution for these schemes follows from the fixed point principle. Finally the unconditional stability of the general alternating schemes is proved. The alternating group explicit scheme, the alternating segment explicit–implicit scheme and the alternating segment Crank–Nicolson scheme are the special cases of the general alternating schemes.     

三维两相渗流驱动问题迎风区域分裂显隐差分法

对三维两相渗流驱动问题提出了两种迎风区域分裂显隐差分格式．压力方程采用了七点差分格式,为了能达到实际并行计算的要求,对饱和度方程采用了迎风区域分裂差分法,内边界处和各子区域分别对应显隐格式．得到了离散l2模收敛性分析,最后给出数值试验,支撑了理论分析结果．     

Unconditional stability of alternating difference schemes with intrinsic parallelism for two‐dimensional parabolic systems

The difference method with intrinsic parallelism for two dimensional parabolic system is studied. The general alternating difference schemes, in particular those with variable time steplengthes, are constructed and proved to be unconditionally stable. The two dimensional alternating group explicit scheme, alternating block explicit‐implicit scheme, alternating block Crank‐Nicolson scheme and block ADI scheme are the special cases of the general schemes constructed here. © 1999 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 15: 625–636, 1999     

Parallel iteration schemes for implicit ODEIVP methods

In this contribution to the Proceedings of the “International Symposium on New Aspects of Numerical Analysis in the Light of Recent Technology” held at Stresa on 13 until 18 September 1993, we give a survey of recent research at CWI for solving the implicit relations arising in ODEIVP methods on parallel computers. Starting with a General Linear method as introduced by Butcher, three forms of parallelism for solving the associated implicit equations are discussed, viz. (i) parallelism across the stages within a single step (stage parallelism), (ii) parallel preconditioners, and (iii) parallelism across the steps (step parallelism). The structure of these type of parallel methods will be described.     

Alternating triangular schemes for convection–diffusion problems

Explicit–implicit approximations are used to approximate nonstationary convection–diffusion equations in time. In unconditionally stable two-level schemes, diffusion is taken from the upper time level, while convection, from the lower layer. In the case of three time levels, the resulting explicit–implicit schemes are second-order accurate in time. Explicit alternating triangular (asymmetric) schemes are used for parabolic problems with a self-adjoint elliptic operator. These schemes are unconditionally stable, but conditionally convergent. Three-level modifications of alternating triangular schemes with better approximating properties were proposed earlier. In this work, two- and three-level alternating triangular schemes for solving boundary value problems for nonstationary convection–diffusion equations are constructed. Numerical results are presented for a two-dimensional test problem on triangular meshes, such as Delaunay triangulations and Voronoi diagrams.     

Implicit difference methods for Hamilton-Jacobi functional differential equations

Classical solutions of initial boundary value problems are approximated by solutions of associated implicit difference functional equations. A stability result is proved by using a comparison technique with nonlinear estimates of the Perron type for given functions. The Newton method is used to numerically solve nonlinear equations generated by implicit difference schemes. It is shown that there are implicit difference schemes which are convergent whereas the corresponding explicit difference methods are not. The results obtained can be applied to differential integral problems and differential equations with deviated variables.     

THE UNCONDITIONAL CONVERGENT DIFFERENCE METHODS WITH INTRINSIC PARALLELISM FOR QUASILINEAR PARABOLIC SYSTEMS WITH TWO DIMENSIONS

In the present work we are going to solve the boundary value problem for the quasilinear parabolic systems of partial differential equations with two space dimensions by the finite difference method with intrinsic parallelism.Some fundamental behaviors of general finite difference schemes with intrinsic parallelism for the mentioned problems are studied.By the method of a priori estimation of the discrete solutions of the nonlinear difference systems,and the interpolation formulas of the various norms of the discrete functions and the fixed-point technique in finite dimensional Euclidean space,the existennce of the discrete vector solutions of the nonliear difference system with intrinsic parallelism are proved .Moreover the convergence of the discrete vector solutions of these difference schemes to the unique generalizd solution of the original quasilinear parabolic problem is proved.     

Implicit difference methods for evolution functional differential equations

A general theory of implicit difference schemes for nonlinear functional differential equations with initial boundary conditions is presented. A theorem on error estimates of approximate solutions for implicit functional difference equations of the Volterra type with an unknown function of several variables is given. This general result is employed to investigate the stability of implicit difference schemes generated by first-order partial differential functional equations and by parabolic problems. A comparison technique with nonlinear estimates of the Perron type for given functions with respect to the functional variable is used.     

GENERAL DIFFERENCE SCHEMES WITH INTRINSIC PARALLELISM FOR SEMILINEAR PARABOLIC SYSTEMS OFDIVERGENCE TYPE

1.IntroductionIn[1]and[2]thegeneralfinitedifferenceschemeshavingtheintrinsiccharacterofparallelismfortheboundaryvalueproblemsofthenonlinearparabolicsystemofgeneralform(i.e.,non-divergencetype)arediscussedundertheassumptionthatthereisanuniquesmoothsol...     

Nonlinear Implicit One-Step Schemes for Solving Initial Value Problems for Ordinary Differential Equation with Steep Gradients

A general theory for nonlinear implicit one-step schemes for solving initial value problems for ordinary differential equations is presented in this paper. The general expansion of "symmetric" implicit one-step schemes having second-order is derived and stability and convergence are studied. As examples, some geometric schemes are given. Based on previous work of the first author on a generalization of means, a fourth-order nonlinear implicit one-step scheme is presented for solving equations with steep gradients. Also, a hybrid method based on the GMS and a fourth-order linear scheme is discussed. Some numerical results are given.     

Numerical solving dynamic problems of elastoplastic deformation of solids

Numerical schemes for solving two-dimensional dynamic problems of elasticity theory based upon several local approximations for each of the required functions are discussed. The schemes contain free parameters (dissipation constants). An explicit form of artificial dissipation of the solutions allows us to control its size and to effectively construct both explicit and implicit schemes. The principle of producing such schemes is applied to a plane dynamic problem of elasticity theory as an example. We describe a class of problems for which numerical algorithms using several local approximations for each of the required functions are constructed. Examples of solving practical problems are given.     

Parallel iteration across the steps of high-order Runge-Kutta methods for nonstiff initial value problems

For the parallel integration of nonstiff initial value problems (IVPs), three main approaches can be distinguished: approaches based on “parallelism across the problem”, on “parallelism across the method” and on “parallelism across the steps”. The first type of parallelism does not require special integration methods and can be exploited within any available IVP solver. The method-parallelism approach received much attention, particularly within the class of explicit Runge-Kutta methods originating from fixed point iteration of implicit Runge-Kutta methods of Gaussian type. The construction and implementation on a parallel machine of such methods is extremely simple. Since the computational work per processor is modest with respect to the number of data to be exchanged between the various processors, this type of parallelism is most suitable for shared memory systems. The required number of processors is roughly half the order of the generating Runge-Kutta method and the speed-up with respect to a good sequential IVP solver is about a factor 2. The third type of parallelism (step-parallelism) can be achieved in any IVP solver based on predictor-corrector iteration and requires the processors to communicate after each full iteration. If the iterations have sufficient computational volume, then the step-parallel approach may be suitable for implementation on distributed memory systems. Most step-parallel methods proposed so far employ a large number of processors, but lack the property of robustness, due to a poor convergence behaviour in the iteration process. Hence, the effective speed-up is rather poor. The dynamic step-parallel iteration process proposed in the present paper is less massively parallel, but turns out to be sufficiently robust to achieve speed-up factors up to 15.