Local refinement techniques for elliptic problems on cell-centered grids

Summary Algebraic multilevel analogues of the BEPS preconditioner designed for solving discrete elliptic problems on grids with local refinement are formulated, and bounds on their relative condition numbers, with respect to the composite-grid matrix, are derived. TheV-cycle and, more generally,v-foldV-cycle multilevel BEPS preconditioners are presented and studied. It is proved that for 2-D problems theV-cycle multilevel BEPS is almost optimal, whereas thev-foldV-cycle algebraic multilevel BEPS is optimal under a mild restriction on the composite cell-centered grid. For thev-fold multilevel BEPS, the variational relation between the finite difference matrix and the corresponding matrix on the next-coarser level is not necessarily required. Since they are purely algebraically derived, thev-fold (v>1) multilevel BEPS preconditioners perform without any restrictionson the shape of subregions, unless the refinement is too fast. For theV-cycle BEPS preconditioner (2-D problem), a variational relation between the matrices on two consecutive grids is required, but there is no restriction on the method of refinement on the shape, or on the size of the subdomains.     

Quadratic multiplier method convergence

In a recent paper (Ref. 1), the author briefly mentioned a variant of Hestenes' method of multipliers which would converge quadratically. This note examines that method in detail and provides some examples. In the quadratic-linear case, this algorithm converges in one iteration.     

Quadratic convergence of potential-reduction methods for degenerate problems

Global and local convergence properties of a primal-dual interior-point pure potential-reduction algorithm for linear programming problems is analyzed. This algorithm is a primal-dual variant of the Iri-Imai method and uses modified Newton search directions to minimize the Tanabe-Todd-Ye (TTY) potential function. A polynomial time complexity for the method is demonstrated. Furthermore, this method is shown to have a unique accumulation point even for degenerate problems and to have Q-quadratic convergence to this point by an appropriate choice of the step-sizes. This is, to the best of our knowledge, the first superlinear convergence result on degenerate linear programs for primal-dual interior-point algorithms that do not follow the central path. Received: February 12, 1998 / Accepted: March 3, 2000?Published online January 17, 2001     

On the convergence on nonrectangular grids

The convergence properties of a full discrete approximations to the convection-diffusion equation is the subject of this paper. The full discrete scheme considered is of Lagrangian type: Euler Implicit on time and centered finite difference on space, and is defined using nonrectangular grids. We analyse this scheme under smoothness conditions on nonrectangular space-time grid. The main result establish the convergence of the approximations and we prove that the assumptions on the discrete spatial nodes movement are achieved if we consider the equidistribution principle.     

Numerical convergence on adaptive grids for control volume methods

An adaptive technique for control‐volume methods applied to second order elliptic equations in two dimensions is presented. The discretization method applies to initially Cartesian grids aligned with the principal directions of the conductivity tensor. The convergence behavior of this method is investigated numerically. For solutions with low Sobolev regularity, the found L² convergence order is two for the potential and one for the flow density. The system of linear equations is better conditioned for the adaptive grids than for uniform grids. The test runs indicate that a pure flux‐based refinement criterion is preferable.© 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2008     

Local refinement techniques for elliptic problems on cell-centered grids; II. Optimal order two-grid iterative methods

Two preconditioning techniques for solving difference equations arising in finite difference approximation of elliptic problems on cell-centered grids are studied. It is proven that the BEPS and the FAC preconditioners are spectrally equivalent to the corresponding finite difference schemes, including a nonsymmetric one, which is of higher-order accuracy. Numerical experiments that demonstrate the fast convergence of the preconditioned iterative methods (CG and GCG-LS in the nonsymmetric case) are presented.     

Quadratic spline interpolation with coinciding interpolation and spline grids

In this paper the quadratic spline interpolation with coinciding interpolation and spline grids for continuous functions is considered. The theorems mainly concern error estimations which allow to formulate a convergence statement. To get such results it is assumed that the function to be interpolated is suitably smooth or possesses a special behavior. A best approximation property and a statement about the solution of boundary value problems using quadratic spline functions are added.     

Quadratic convergence of the Iri-Imai algorithm for degenerate linear programming problems

A local analysis of the Iri-Imai algorithm for linear programming is given to demonstrate quadratic convergence under degeneracy. Specifically, we show that the algorithm with an exact line search either terminates after a finite number of iterations yielding a point on the set of optimal solutions or converges quadratically to one of the relative analytic centers of the faces of the set of optimal solutions including vertices. Mostly, the sequence generated falls into one of the optimal vertices, and it is rare that the sequence converges to the relative analytic center of a face whose dimension is greater than or equal to one.This paper is based on Ref. 1.The author thanks Professor Kunio Tanabe of the Institute of Statistical Mathematics for valuable comments as well as stimulating discussions.     

Quadratic convergence in interval arithmetic,part I

Several procedures in interval arithmetic have been shown to have errorO(w ²), wherew is the width of the data intervals. In this paper we will give a general discussion of this quadratic convergence. Our results will allow us to give some systematic proofs of quadratic convergence.Supported in part by NSF grant GJ-797.     

Quadratic convergence of a special quasi-cyclic Jacobi method

This paper considers the ultimate asymptotic convergence of a block- oriented, quasi-cyclic Jacobi method for symmetric matrices. The conclusion applies to the new one-sided Jacobi method for computing the singular value decomposition, recently proposed by Drmač and Veselić. Using a simple qualitative analysis, the discussion indicates that a quadratic off-norm reduction per quasi-sweep is to be expected in all perceivable cases.      

Quadratic convergence in interval arithmetic,part II

The size of the error incurred by one operation in an interval arithmetic procedure depends on the extent to which the operands are dependent, i.e., depend on the same initial variables. In this part we will investigate the effect of such dependence. Our results are applied to prove the quadratic convergence of the centered form and of a method of Hansen and Smith for solving linear algebraic systems.Supported in part by NSF grant GJ-797.     

Quadratic convergence of scaled matrices in Jacobi method

Summary. A quadratic convergence bound for scaled Jacobi iterates is proved provided the initial symmetric positive definite matrix has simple eigenvalues. The bound is expressed in terms of the off-norm of the scaled initial matrix and the minimum relative gap in the spectrum. The obtained result can be used to predict the stopping moment in the two-sided and especially in the one-sided Jacobi method. Received October 31, 1997 / Revised version received March 8, 1999 / Published online July 12, 2000     

Robust convergence of multi point flux approximation on rough grids

This paper establishes the convergence of a multi point flux approximation control volume method on rough quadrilateral grids. By rough grids we refer to a family of refined quadrilateral grids where the cells are not required to approach parallelograms in the asymptotic limit. In contrast to previous convergence results for these methods we consider here a version where the flux approximation is derived directly in the physical space, and not on a reference cell. As a consequence, less regular grids are allowed. However, the extra cost is that the symmetry of the method is lost.     

Quadratic convergence of a smoothing Newton method for symmetric cone programming without strict complementarity

This paper deals with symmetric cone programming (SCP), which includes the linear programming (LP), the second-order cone programming (SOCP), the semidefinite programming (SDP) as special cases. Based on the Chen?CMangasarian smoothing function of the projection operator onto symmetric cones, we establish a smoothing Newton method for SCP. Global and quadratic convergence of the proposed algorithm is established under the primal and dual constraint nondegeneracies, but without the strict complementarity. Moreover, we show the equivalence at a Karush?CKuhn?CTucker (KKT) point among the primal and dual constraint nondegeneracies, the nonsingularity of the B-subdifferential of the smoothing counterpart of the KKT system, and the nonsingularity of the corresponding Clarke??s generalized Jacobian.     

On the convergence of nonnested multigrid methods with nested spaces on coarse grids

Multigrid methods for discretized partial differential problems using nonnested conforming and nonconforming finite elements are here defined in the general setting. The coarse‐grid corrections of these multigrid methods make use of different finite element spaces from those on the finest grid. In general, the finite element spaces on the finest grid are nonnested, while the spaces are nested on the coarse grids. An abstract convergence theory is developed for these multigrid methods for differential problems without full elliptic regularity. This theory applies to multigrid methods of nonnested conforming and nonconforming finite elements with the coarse‐grid corrections established on nested conforming finite element spaces. Uniform convergence rates (independent of the number of grid levels) are obtained for both the V and W‐cycle methods with one smoothing on all coarse grids and with a sufficiently large number of smoothings solely on the finest grid. In some cases, these uniform rates are attained even with one smoothing on all grids. The present theory also applies to multigrid methods for discretized partial differential problems using mixed finite element methods. © 2000 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 16: 265–284, 2000     

On the conservativity of cell-centered Galerkin methods

In this work we investigate the conservativity of the cell-centered Galerkin method of Di Pietro (2012) [5] and provide an analytical expression for the conservative flux. The relation with the SUSHI method of Eymard et al. (2010) [10] and with discontinuous Galerkin methods is also explored. The theoretical results are assessed on a numerical example using standard as well as general polygonal grids.     

Quadratic convergence algorithms for the problem of capture of a point by a family of convex bodies

We consider the nonlinear optimal control problem with an integral functional in which the integrand function is the characteristic function of a given closed set in the phase space. The approximation method is applied to prove the necessary conditions of optimality in the form of the Pontryagin maximum principle without any prior assumptions on the behavior of the optimal trajectory. Similarly to the case of phase-constrained problems, we derive conditions of nondegeneracy and pointwise nontriviality of the maximum principle. __________ Translated from Nelineinaya Dinamika i Upravlenie, No. 4, pp. 241–256, 2004.     

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.