Rate of Convergence for some constraint decomposition methods for nonlinear variational inequalities

Summary. Some general subspace correction algorithms are proposed for a convex optimization problem over a convex constraint subset. One of the nontrivial applications of the algorithms is the solving of some obstacle problems by multilevel domain decomposition and multigrid methods. For domain decomposition and multigrid methods, the rate of convergence for the algorithms for obstacle problems is of the same order as the rate of convergence for jump coefficient linear elliptic problems. In order to analyse the convergence rate, we need to decompose a finite element function into a sum of functions from the subspaces and also satisfying some constraints. A special nonlinear interpolation operator is introduced for decomposing the functions. Received December 13, 2001 / Revised version received February 19, 2002 / Published online June 17, 2002 This work was partially supported by the Norwegian Research Council under projects 128224/431 and SEP-115837/431.     

Updating approximate principal components with applications to template tracking

Adaptive principal component analysis is prohibitively expensive when a large‐scale data matrix must be updated frequently. Therefore, we consider the truncated URV decomposition that allows faster updates to its approximation to the singular value decomposition while still producing a good enough approximation to recover principal components. Specifically, we suggest an efficient algorithm for the truncated URV decomposition when a rank 1 matrix updates the data matrix. After the algorithm development, the truncated URV decomposition is successfully applied to the template tracking problem in a video sequence proposed by Matthews et al. [IEEE Trans. Pattern Anal. Mach. Intell., 26:810‐815 2004], which requires computation of the principal components of the augmented image matrix at every iteration. From the template tracking experiments, we show that, in adaptive applications, the truncated URV decomposition maintains a good approximation to the principal component subspace more efficiently than other procedures.     

A semidefinite algorithm for completely positive tensor decomposition

A symmetric tensor, which has a symmetric nonnegative decomposition, is called a completely positive tensor. In this paper, we characterize the completely positive tensor as a truncated moment sequence, and transform the problem of checking whether a tensor is completely positive to checking whether its corresponding truncated moment sequence admits a representing measure, then present a semidefinite algorithm to solve it. If a tensor is not completely positive, a certificate for it can be obtained; if it is completely positive, a nonnegative decomposition can be obtained.     

Convergence rate analysis of an asynchronous space decomposition method for convex minimization

We analyze the convergence rate of an asynchronous space decomposition method for constrained convex minimization in a reflexive Banach space. This method includes as special cases parallel domain decomposition methods and multigrid methods for solving elliptic partial differential equations. In particular, the method generalizes the additive Schwarz domain decomposition methods to allow for asynchronous updates. It also generalizes the BPX multigrid method to allow for use as solvers instead of as preconditioners, possibly with asynchronous updates, and is applicable to nonlinear problems. Applications to an overlapping domain decomposition for obstacle problems are also studied. The method of this work is also closely related to relaxation methods for nonlinear network flow. Accordingly, we specialize our convergence rate results to the above methods. The asynchronous method is implementable in a multiprocessor system, allowing for communication and computation delays among the processors.

     

A Multigrid Method Based on Incomplete Gaussian Elimination

In this paper we introduce and analyse a new Schur complement approximation based on incomplete Gaussian elimination. The approximate Schur complement is used to develop a multigrid method. This multigrid method has an algorithmic structure that is very similar to the algorithmic structure of classical multigrid methods. The resulting method is almost purely algebraic and has interesting properties with respect to variation in problem parameters.     

Applications of a space decomposition method to linear and nonlinear elliptic problems

This work presents some space decomposition algorithms for a convex minimization problem. The algorithms has linear rate of convergence and the rate of convergence depends only on four constants. The space decomposition could be a multigrid or domain decomposition method. We explain the detailed procedure to implement our algorithms for a two-level overlapping domain decomposition method and estimate the needed constants. Numerical tests are reported for linear as well as nonlinear elliptic problems. © 1998 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 14: 717–737, 1998     

An algebraic multigrid method for finite element systems on criss-cross grids

In this paper, we design and analyze an algebraic multigrid method for a condensed finite element system on criss-cross grids and then provide a convergence analysis. Criss-cross grid finite element systems represent a large class of finite element systems that can be reduced to a smaller system by first eliminating certain degrees of freedoms. The algebraic multigrid method that we construct is analogous to many other algebraic multigrid methods for more complicated problems such as unstructured grids, but, because of the specialty of our problem, we are able to provide a rigorous convergence analysis to our algebraic multigrid method. Dedicated to Professor Charles A. Micchelli on the occasion of his 60th birthday The work was supported in part by NSAF(10376031) and National Major Key Project for basic researches and by National High-Tech ICF Committee in China.     

板问题多重网格法收敛性的低模估计

１．引言 近年来,多重网格法已成为行之有效的偏微分方程数值解法．对板问题有限元离散系统的多重网格法,也有不少的研究工作,如［４］,［５］,［１０］,［１３－１７］．在［４］,［１４－１７］中,作者讨论了Ｃ１协调元离散板问题的多重网格法,并在能量模（即 Ｈ２模）意义下获得了最优的收敛率．在［５］,［１０］中,作者讨论了非协调元离散问题的多重网格法,并在能量模意义下获得了最优的收敛率,同时在能量模意义下证明了套迭代多重网格法一阶收敛．但对板问题多重网格法的低模估计,即 Ｈ１模估计,至今尚未见研究,本文…     

A cascadic multigrid algorithm for the Stokes equations

A variant of multigrid schemes for the Stokes problem is discussed. In particular, we propose and analyse a cascadic version for the Stokes problem. The analysis of the transfer between the grids requires special care in order to establish that the complexity is the same as that for classical multigrid algorithms. Received September 10, 1997 / Revised version received February 20, 1998     

Multigrid methods for H(div) in three dimensions with nonoverlapping domain decomposition smoothers

We design and analyze V‐cycle multigrid methods for an H(div) problem discretized by the lowest‐order Raviart–Thomas hexahedral element. The smoothers in the multigrid methods involve nonoverlapping domain decomposition preconditioners that are based on substructuring. We prove uniform convergence of the V‐cycle methods on bounded convex hexahedral domains (rectangular boxes). Numerical experiments that support the theory are also presented.     

A new Tikhonov regularization method

The numerical solution of linear discrete ill-posed problems typically requires regularization, i.e., replacement of the available ill-conditioned problem by a nearby better conditioned one. The most popular regularization methods for problems of small to moderate size, which allow evaluation of the singular value decomposition of the matrix defining the problem, are the truncated singular value decomposition and Tikhonov regularization. The present paper proposes a novel choice of regularization matrix for Tikhonov regularization that bridges the gap between Tikhonov regularization and truncated singular value decomposition. Computed examples illustrate the benefit of the proposed method.     

Exact and heuristic procedures for the material handling circular flow path design problem

In this study we develop optimization, decomposition, and heuristic procedures to design a unidirectional loop flow pattern along with the pickup and delivery station locations for unit load automated material handling vehicles. The layout of the facility is fixed, the edges on the boundary of the manufacturing cells are candidates to form the unidirectional loop flow path, and a set of nodes located at an intermediate point on each edge are candidates for pickup and delivery stations of the cell formed by those edges. The objective is to minimize the total loaded and empty vehicle trip distances. The empty vehicle dispatching policy underlying the model is the shortest trip distance first. A binary integer programming model describes the problem of determining the flow path and locations of the pickup and delivery stations in which we then provide a decomposition procedure based on a loop enumeration strategy coupled with a streamlined integer linear programming model. It is shown that only a small proportion of all loops have to be enumerated to reach an optimum. Therefore a truncated version of this algorithm should yield a good heuristic. Finally we propose a neighbourhood search heuristic method and report on its performance.     

双参数Morley有限元多重网格法

1、引言 多重网格方法是求解偏微分方程的高效快速算法,在实际中得到广泛应用．[2][6]中考察了Morley元的多重网格方法,并用于双调和方程问题。     

V-cycle convergence of some multigrid methods for ill-posed problems

For ill-posed linear operator equations we consider some V-cycle multigrid approaches, that, in the framework of Bramble, Pasciak, Wang, and Xu (1991), we prove to yield level independent contraction factor estimates. Consequently, we can incorporate these multigrid operators in a full multigrid method, that, together with a discrepancy principle, is shown to act as an iterative regularization method for the underlying infinite-dimensional ill-posed problem. Numerical experiments illustrate the theoretical results.

     

Convergence analysis of HSS-multigrid methods for second-order nonselfadjoint elliptic problems

In this paper, the multigrid methods using Hermitian/skew-Hermitian splitting (HSS) iteration as smoothers are investigated. These smoothers also include the modified additive and multiplicative smoothers which result from subspace decomposition. Without full elliptic regularity assumption, it is shown that the multigrid methods with these smoothers converge uniformly for second-order nonselfadjoint elliptic boundary value problems if the mesh size of the coarsest grid is sufficiently small (but independent of the number of the multigrid levels). Numerical results are reported to confirm the theoretical analysis.     

On Schwarz-type smoothers for saddle point problems with applications to PDE-constrained optimization problems

In this paper we consider a (one-shot) multigrid strategy for solving the discretized optimality system (KKT system) of a PDE-constrained optimization problem. In particular, we discuss the construction of an additive Schwarz-type smoother for a certain class of optimal control problems. A rigorous multigrid convergence analysis is presented. Numerical experiments are shown which confirm the theoretical results. The work was supported by the Austrian Science Fund (FWF) under grant SFB 013/F1309.     

Distributive smoothers in multigrid for problems with dominating grad–div operators

In this paper, we present efficient multigrid methods for systems of partial differential equations that are governed by a dominating grad–div operator. In particular, we show that distributive smoothing methods give multigrid convergence factors that are independent of problem parameters and of the mesh sizes in space and time. The applications range from model problems to secondary consolidation Biot's model. We focus on the smoothing issue and mainly solve academic problems on Cartesian‐staggered grids. Copyright © 2008 John Wiley & Sons, Ltd.     

平面线弹性纯位移边值问题低阶非协调矩形元的Robust多重网格方法

1引 言 对于各向同性,均匀介质的平面线弹性问题,当Lamé常数λ→∞(泊松率v→0.5)时,即对于几乎不可压介质,通常的协调有限元格式的解往往不再收敛到原问题的解,或者达不到最优收敛阶,这就是所谓的闭锁现象(见[3],[7],[8]及[10]).究其原因,在通常的有限元分析中,其误差估计的系数与λ有关,当λ→∞时,该系数将趋于无穷大.因此为克服闭锁现象就需要构造特殊的有限元格式,使得当λ→∞时,有限元逼近解仍然收敛到原问题的解.     

Multigrid methods for a parameter dependent problem in primal variables

Summary. In this paper we consider multigrid methods for the parameter dependent problem of nearly incompressible materials. We construct and analyze multilevel-projection algorithms, which can be applied to the mixed as well as to the equivalent, non-conforming finite element scheme in primal variables. For proper norms, we prove that the smoothing property and the approximation property hold with constants that are independent of the small parameter. Thus we obtain robust and optimal convergence rates for the W-cycle and the variable V-cycle multigrid methods. The numerical results pretty well conform the robustness and optimality of the multigrid methods proposed. Received June 17, 1998 / Revised version received October 26, 1998 / Published online September 7, 1999     

A characterization of mapping unstructured grids onto structured grids and using multigrid as a preconditioner

Many problems based on unstructured grids provide a natural multigrid framework due to using an adaptive gridding procedure. When the grids are saved, even starting from just a fine grid problem poses no serious theoretical difficulties in applying multigrid. A more difficult case occurs when a highly unstructured grid problem is to be solved with no hints how the grid was produced. Here, there may be no natural multigrid structure and applying such a solver may be quite difficult to do. Since unstructured grids play a vital role in scientific computing, many modifications have been proposed in order to apply a fast, robust multigrid solver. One suggested solution is to map the unstructured grid onto a structured grid and then apply multigrid to a sequence of structured grids as a preconditioner. In this paper, we derive both general upper and lower bounds on the condition number of this procedure in terms of computable grid parameters. We provide examples to illuminate when this preconditioner is a useful (e. g.,p orh-p formulated finite element problems on semi-structured grids) or should be avoided (e.g., typical computational fluid dynamics (CFD) or boundary layer problems). We show that unless great care is taken, this mapping can lead to a system with a high condition number which eliminates the advantage of the multigrid method. This work was partially supported by ONR Grant # N0014-91-J-1576.