Multigrid Solution of a Lavrentiev-Regularized State-Constrained Parabolic Control Problem

A mesh-independent, robust, and accurate multigrid scheme to solve a linear state-constrained parabolic optimal control problem is presented. We first consider a Lavrentiev regularization of the state-constrained optimization problem. Then, a multigrid scheme is designed for the numerical solution of the regularized optimality system. Central to this scheme is the construction of an iterative pointwise smoother which can be formulated as a local semismooth Newton iteration. Results of numerical experiments and theoretical two-grid local Fourier analysis estimates demonstrate that the proposed scheme is able to solve parabolic state-constrained optimality systems with textbook multigrid efficiency.     

A Crank-Nicolson scheme for the Landau-Lifshitz equation without damping

An accurate and efficient numerical approach, based on a finite difference method with Crank-Nicolson time stepping, is proposed for the Landau-Lifshitz equation without damping. The phenomenological Landau-Lifshitz equation describes the dynamics of ferromagnetism. The Crank-Nicolson method is very popular in the numerical schemes for parabolic equations since it is second-order accurate in time. Although widely used, the method does not always produce accurate results when it is applied to the Landau-Lifshitz equation. The objective of this article is to enumerate the problems and then to propose an accurate and robust numerical solution algorithm. A discrete scheme and a numerical solution algorithm for the Landau-Lifshitz equation are described. A nonlinear multigrid method is used for handling the nonlinearities of the resulting discrete system of equations at each time step. We show numerically that the proposed scheme has a second-order convergence in space and time.     

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.     

Box-Line Relaxation Schemes for Solving the Steady Incompressible Navier-Stokes Equations Using Second-Order Upwind Differencing

1.Introducti0nThec0nvection-diffusionbehaviour0fthevisc0usincompressibleNavier-St0kesequati0nsisamains0urce0fdifficultiesinthenumericalsoluti0n.Whendiscretiz-ingtheequati0nsusingfinitedifferenceschemes,upwind0rhybridschemesareusuallyused0nthec0nvectiontermsforensuringthestability0fthediscretesystem[1].Thefirst-orderuPwinddifferencinghasprovedt0beinadequatef0rtheincompressibleNavier-St0kesequati0nswithlargeReynoldsnumbers,alth0ughtheresultingdiscretesystemsareverystableandeasilys0lved.In[5],…     

Fast Solvers of Fredholm Optimal Control Problems

<正>The formulation of optimal control problems governed by Fredholm integral equations of second kind and an efficient computational framework for solving these control problems is presented.Existence and uniqueness of optimal solutions is proved. A collective Gauss-Seidel scheme and a multigrid scheme are discussed.Optimal computational performance of these iterative schemes is proved by local Fourier analysis and demonstrated by results of numerical experiments.     

Newton Linearized Methods for Semilinear Parabolic Equations

In this study, Newton linearized finite element methods are presented for solving semi-linear parabolic equations in two- and three-dimensions. The proposed scheme is a one-step, linearized and second-order method in temporal direction, while the usual linearized second-order schemes require at least two starting values. By using a temporal-spatial error splitting argument, the fully discrete scheme is proved to be convergent without time-step restrictions dependent on the spatial mesh size. Numerical examples are given to demonstrate the efficiency of the methods and to confirm the theoretical results.     

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.     

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     

Flux-splitting schemes for parabolic problems

Splitting with respect to space variables can be used in solving boundary value problems for second-order parabolic equations. Classical alternating direction methods and locally one-dimensional schemes could be examples of this approach. For problems with rapidly varying coefficients, a convenient tool is the use of fluxes (directional derivatives) as independent variables. The original equation is written as a system in which not only the desired solution but also directional derivatives (fluxes) are unknowns. In this paper, locally one-dimensional additional schemes (splitting schemes) for second-order parabolic equations are examined. By writing the original equation in flux variables, certain two-level locally one-dimensional schemes are derived. The unconditional stability of locally one-dimensional flux schemes of the first and second approximation order with respect to time is proved.     

A FEM-Multigrid Scheme for Elliptic Nash-Equilibrium Multiobjective Optimal Control Problems

A finite-element multigrid scheme for elliptic Nash-equilibrium multiobjective optimal control problems with control constraints is investigated. The multigrid computational framework implements a nonlinear multigrid strategy with collective smoothing for solving the multiobjective optimality system discretized with finite elements. Error estimates for the optimal solution and two-grid local Fourier analysis of the multigrid scheme are presented. Results of numerical experiments are presented to demonstrate the effectiveness of the proposed framework.     

Comparison of two cell-centered multigrid schemes for problems with discontinuous coefficients

Two different schemes for constructing coarse-grid operators are implemented in a linear multigrid code. In the first scheme, the construction of the coarse-grid operators is done using a variational approach. Certain conservation properties of the fine-grid matrices are shown to be preserved on the coarser grids by the variational construction. In the second scheme, the diffusion coefficients for the coarse grids are calculated by a simple restriction of the coefficient from the fine grid, using a flux conservation principle. The multigrid codes are then applied to solve the linear equations from an IMPES formulation of a two-phase porous-media flow model. A standard elliptic model problem with jump discontinuous coefficients is also solved using the two multigrid schemes. In simple cases of particular elliptic equations these two schemes are identical. However, in more general cases, such as in reservoir problems, these schemes differ. It is shown that multigrid efficiency typical of the constant coefficient cases is obtained for these problems involving discontinuous coefficients. © 1993 John Wiley & Sons, Inc.     

Local Fourier Analysis for Edge-Based Discretizations on Triangular Grids

In this paper, we present a local Fourier analysis framework for analyzing the different components within multigrid solvers for edge-based discretizations on triangular grids. The different stencils associated with edges of different orientation in a triangular mesh make this analysis special. The resulting tool is demonstrated for the vector Laplace problem discretized by mimetic finite difference schemes. Results from the local Fourier analysis, as well as experimentally obtained results, are presented to validate the proposed analysis.     

Multigrid applications to three-dimensional elliptic coordinate generation

The multigrid algorithm was applied to solve the coupled set of elliptic quasilinear partial differential equations associated with three-dimensional coordinate generation. The results indicate that the multigrid scheme is more than twice as fast as conventional relaxation schemes on moderate-size grids. Convergence factors of order 0.90 per work unit were achieved on 36,000-point grids. The paper covers the form of transformation, develops the set of generation equations, and gives details on the multigrid approach used. Included are a development of the full-approximation storage scheme, details of the smoothing-rate analysis, and a section devoted to rational programming techniques applicable to the multigrid algorithm.     

Comparison of Fast Iterative Methods for Symmetric Systems

The multigrid method is compared to ICCG/MICCG methods for solvingsymmetric systems of linear equations arising from approximationsto differential equations with jump discontinuities in the coefficients.An optimal multigrid algorithm for these types of problems isdeveloped. It includes pattern relaxation and acceleration.Optimization of ICCG/MICCG algorithms is investigated. Thisincludes the effect of adding extra (up to ten) bands to theapproximate factorization and of different grid ordering schemes.Numerical results are presented comparing the scalar work ofthe algorithms. For large problems the multigrid algorithm issuperior. The optimal multigrid scheme can be highly vectorized.     

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.     

Convergence of a step-doubling Galerkin method for parabolic problems

We analyze a single step method for solving second-order parabolic initial-boundary value problems. The method uses a step-doubling extrapolation scheme in time based on backward Euler and a Galerkin approximation in space. The technique is shown to be a second-order correct approximation in time. Since step-doubling can be used as a mechanism for step-size control, the analysis is done for variable time steps. The stability properties of step-doubling are contrasted with those of Crank-Nicolson, as well as those of more general extrapolated theta-weighted schemes. We provide an example computation that illustrates both the use of step-doubling for adaptive time step control and the application of step-doubling to a nonlinear system.

     

High Accuracy Solution of Three-Dimensional Biharmonic Equations

In this paper, we consider several finite-difference approximations for the three-dimensional biharmonic equation. A symbolic algebra package is utilized to derive a family of finite-difference approximations for the biharmonic equation on a 27 point compact stencil. The unknown solution and its first derivatives are carried as unknowns at selected grid points. This formulation allows us to incorporate the Dirichlet boundary conditions automatically and there is no need to define special formulas near the boundaries, as is the case with the standard discretizations of biharmonic equations. We exhibit the standard second-order, finite-difference approximation that requires 25 grid points. We also exhibit two compact formulations of the 3D biharmonic equations; these compact formulas are defined on a 27 point cubic grid. The fourth-order approximations are used to solve a set of test problems and produce high accuracy numerical solutions. The system of linear equations is solved using a variety of iterative methods. We employ multigrid and preconditioned Krylov iterative methods to solve the system of equations. Test results from two test problems are reported. In these experiments, the multigrid method gives excellent results. The multigrid preconditioning also gives good results using Krylov methods.     

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.     

Numerical algorithm for solving diffusion-type equations on the basis of multigrid methods

A new numerical algorithm based on multigrid methods is proposed for solving equations of the parabolic type. Theoretical error estimates are obtained for the algorithm as applied to a two-dimensional initial-boundary value model problem for the heat equation. The good accuracy of the algorithm is demonstrated using model problems including ones with discontinuous coefficients. As applied to initial-boundary value problems for diffusion equations, the algorithm yields considerable savings in computational work compared to implicit schemes on fine grids or explicit schemes with a small time step on fine grids. A parallelization scheme is given for the algorithm.     

对流扩散方程的高效稳定差分格式

基于二阶修正Dennis格式 ,提出了采用时间相关法求解定常对流扩散方程的一种具有节省内存空间和提高定常解收敛速度的有理式型优化半隐和松驰半隐紧致格式 .本文建立的差分格式具有运算量小、无网格雷诺数限制的优点 ,是无条件稳定和无条件单调的。通过对非线性Burgers方程进行的数值计算结果表明 ,文中构造的有理式型优化半隐和松驰半隐紧致格式适合于非线性问题计算 ,且保持了无条件稳定和无条件单调的特性 ,尤其能使定常解收敛速度加快 ,精度提高 .