Local Multilevel Method on Adaptively Refined Meshes for Elliptic Problems with Smooth Complex Coefficients

In this paper, a local multilevel algorithm is investigated for solving linear systems arising from adaptive finite element approximations of second order elliptic problems with smooth complex coefficients. It is shown that the abstract theory for local multilevel algorithm can also be applied to elliptic problems whose dominant coefficient is complex valued. Assuming that the coarsest mesh size is sufficiently small, we prove that this algorithm with Gauss-Seidel smoother is convergent and optimal on the adaptively refined meshes generated by the newest vertex bisection algorithm. Numerical experiments are reported to confirm the theoretical analysis.     

Deterministic solution approach for some classes of nonlinear multilevel programs with multiple followers

In this paper we investigate multilevel programming problems with multiple followers in each hierarchical decision level. It is known that such type of problems are highly non-convex and hard to solve. A solution algorithm have been proposed by reformulating the given multilevel program with multiple followers at each level that share common resources into its equivalent multilevel program having single follower at each decision level. Even though, the reformulated multilevel optimization problem may contain non-convex terms at the objective functions at each level of the decision hierarchy, we applied multi-parametric branch-and-bound algorithm to solve the resulting problem that has polyhedral constraints. The solution procedure is implemented and tested for a variety of illustrative examples.     

A multilevel decoupled method for a mixed Stokes/Darcy model

This paper studies decoupled numerical methods for a mixed Stokes/Darcy model for coupling fluid and porous media flows. A two-level algorithm is proposed and analyzed in Mu and Xu (2007) [10]. We generalize the two-level algorithm to a multilevel algorithm in this paper and present numerical analysis on the error estimates for the multilevel algorithm. The multilevel algorithm solves the mixed Stokes/Darcy system by applying efficient legacy code for single model solvers to solve two decoupled Stokes and Darcy subproblems on all the subsequently refined meshes, except for a much smaller global problem only on a very coarse initial mesh. Numerical experiments are conducted for both the two-level and multilevel algorithms to illustrate their effectiveness and efficiency, and validate the related theoretical analysis.     

Robust semi-coarsening multilevel preconditioning of biquadratic FEM systems

While a large amount of papers are dealing with robust multilevel methods and algorithms for linear FEM elliptic systems, the related higher order FEM problems are much less studied. Moreover, we know that the standard hierarchical basis two-level splittings deteriorate for strongly anisotropic problems. A first robust multilevel preconditioner for higher order FEM systems obtained after discretizations of elliptic problems with an anisotropic diffusion tensor is presented in this paper. We study the behavior of the constant in the strengthened CBS inequality for semi-coarsening mesh refinement which is a quality measure for hierarchical two-level splittings of the considered biquadratic FEM stiffness matrices. The presented new theoretical estimates are confirmed by numerically computed CBS constants for a rich set of parameters (coarsening factor and anisotropy ratio). In the paper we consider also the problem of solving efficiently systems with the pivot block matrices arising in the hierarchical basis two-level splittings. Combining the proven uniform estimates with the theory of the Algebraic MultiLevel Iteration (AMLI) methods we obtain an optimal order multilevel algorithm whose total computational cost is proportional to the size of the discrete problem with a proportionality constant independent of the anisotropy ratio.     

A multilevel successive iteration method for nonlinear elliptic problems

In this paper, a multilevel successive iteration method for solving nonlinear elliptic problems is proposed by combining a multilevel linearization technique and the cascadic multigrid approach. The error analysis and the complexity analysis for the proposed method are carried out based on the two-grid theory and its multilevel extension. A superconvergence result for the multilevel linearization algorithm is established, which, besides being interesting for its own sake, enables us to obtain the error estimates for the multilevel successive iteration method. The optimal complexity is established for nonlinear elliptic problems in 2-D provided that the number of grid levels is fixed.

     

Multilevel Schwarz methods

Summary We consider the solution of the algebraic system of equations which result from the discretization of second order elliptic equations. A class of multilevel algorithms are studied using the additive Schwarz framework. We establish that the condition number of the iteration operators are bounded independent of mesh sizes and the number of levels. This is an improvement on Dryja and Widlund's result on a multilevel additive Schwarz algorithm, as well as Bramble, Pasciak and Xu's result on the BPX algorithm. Some multiplicative variants of the multilevel methods are also considered. We establish that the energy norms of the corresponding iteration operators are bounded by a constant less than one, which is independent of the number of levels. For a proper ordering, the iteration operators correspond to the error propagation operators of certain V-cycle multigrid methods, using Gauss-Seidel and damped Jacobi methods as smoothers, respectively.This work was supported in part by the National Science Foundation under Grants NSF-CCR-8903003 at Courant Institute of Mathematical Sciences, New York University and NSF-ASC-8958544 at Department of Computer Science, University of Maryland.     

THE OPTIMAL CONTROL SYSTEM OF 3D HORIZONTAL WELL AND ITS APPLICATION

A multi-objective optimal control model for nonlinear multilevel dynamicalsystem is built in this paper. The existence of the solutions to this systemand the controllability and the polykeys of the control are discussed. In orderto obtain the global optimal solution, Uniform Design method is introducedto select initial1 feasible points, then an improved Hooke-jeeves algorithm isproposed. The new algorithm and its corresponding software we developed hasvalidated in more than 12 horizontal wells, which show their advantages suchas less length of trajectory designed, more accuracy of target hitting and lesstime-consuming comparison with present conventional method.     

Patch-adaptive multilevel iteration

Themultilevel adaptive iteration is an attempt to improve both the robustness and efficiency of iterative sparse system solvers. Unlike in most other iterative methods, the order of processing and sequence of operations is not determined a priori. The method consists of a relaxation scheme with an active set strategy and can be viewed as an efficient implementation of the Gauß-Southwell relaxation. With this strategy, computational work is focused on where it can efficiently improve the solution quality. To obtain full efficiency, the algorithm must be used on a multilevel structure. This algorithm is then closely related to multigrid or multilevel preconditioning algorithms, and can be shown to have asymptotically optimal convergence. In this paper the focus is on a variant that uses data structures with a locally uniform grid refinement. The resulting grid system consists of a collection of patches where each patch is a uniform rectangular grid and where adaptive refinement is accomplished by arranging the patches flexibly in space. This construction permits improved implementations that better exploit high performance computer designs. This will be demonstrated by numerical examples.     

Global optimization by multilevel search

A new approach to the global optimization of functions with extremely rugged graphs is introduced. This multilevel search method is both an algorithm and a meta-algorithm, a logic for regulating optimization done by other algorithms. First, it is examined in the one-dimensional case theoretically and through simple examples. Then, to deal with higher dimensions, multilevel search is combined with the Monte Carlo method; this hybrid algorithm is tested on standard problems and is found to perform extremely well for a derivative-free method.     

Hilbert尺度下求解非线性不适定问题的多水平迭代法

本文吸取了多水平方法的思想，采用多水平方法提供了离散化参数和迭代初值的合理的选择方法，提出了Hilbert尺度下求解非线性不适定问题的多水平Landweber迭代算法，并给出了算法的收敛性分析，证明了算法在整体上提高了Hilbert尺度下的Landweber迭代法的迭代效率。     

Multilevel augmentation methods for solving the sine-Gordon equation

In this paper we develop the multilevel augmentation method for solving nonlinear operator equations of the second kind and apply it to solving the one-dimensional sine-Gordon equation. We first give a general setting of the multilevel augmentation method for solving the second kind nonlinear operator equations and prove that the multilevel augmentation method preserves the optimal convergence order of the projection method while reducing computational cost significantly. Then we describe the semi-discrete scheme and the fully-discrete scheme based on multiscale methods for solving the sine-Gordon equation, and apply the multilevel augmentation method to solving the discrete equation. A complete analysis for convergence order is proposed. Finally numerical experiments are presented to confirm the theoretical results and illustrate the efficiency of the method.     

An inverse problem for the acoustics equations: A multilevel adaptive algorithm

A numerical solution to an inverse problem for the acoustic equations using an optimization method for a stratified medium is presented. With the distribution of an acoustic wave field on the medium’s surface, the 1D distributions of medium’s density, as well as the velocity and absorption coefficient of the acoustic wave, are determined. Absorption in a Voigt body model is considered. The conjugate gradients and the Newton method are used for minimization. To increase the efficiency of the numerical method, a multilevel adaptive algorithm is proposed. The algorithm is based on a division of the whole procedure of solving the inverse problem into a series of consecutive levels. Each level is characterized by the number of parameters to be determined at the level. In moving from one level to another, the number of parameters changes adaptively according to the functional minimized and the convergence rate. The minimization parameters are chosen as illustrated by results of solving the inverse problem in a spectral domain, where the desired quantities are presented as Chebyshev polynomial series and minimization is carried out with respect to the coefficients of these series. The method is compared in efficiency with a nonadaptive method. The optimal parameters of the multilevel method are chosen. It is shown that the multilevel algorithm offers several advantages over the one without partitioning into levels. The algorithm produces primarily a more accurate solution to the inverse problem.     

Geometric and algorithmic developments for a hierarchical planning problem

This paper presents a new model for multiobjective planning in hierarchical systems that explicitly takes into consideration the order in which decisions are made. Interactions and conflicts that normally exist among the levels are introduced by specifying jointly controlled feasible regions and interdependent objective functions. At each level in the system, planners attempt to maximize net benefits in light of all higher-level decisions, and thus may influence but not control the behavior of others. The resultant formulation leads to the multilevel programming problem. The geometry of an all linear case is first examined wherein it is shown that the optimal solution must lie at a vertex of the original polyhedral constraint region. Next, a set of first order optimality conditions is derived for the general case and used as the basis of an algorithm for the linear problem. A number of examples are given to highlight the results.     

非匹配网格上Stokes-Darcy 问题非协调元离散的两水平和多水平方法

本文讨论了非匹配网格上Stokes-Darcy 问题的两种低阶非协调元方法, 给出了误差估计, 对耦合的非协调元离散问题, 通过粗网格求得的界面条件, 我们提出了一个解耦的两水平算法. 并且我们将两水平方法推广到多水平情形, 其只需在一个很粗的网格上解一耦合问题, 然后在逐步加细的网格上求解解耦的问题, 理论分析和数值试验都说明方法的高效性.     

Adaptive-Additive Multilevel Methods for Hypersingular Integral Equation

In this article we present the combined adaptive-additive multilevel methods for the Galerkin approximation of hypersingular integral equation on the interval o = ( m 1,1). We also derive an efficient and reliable a posteriori error estimate for the error between the exact solution u and the approximated multilevel solution $ \tilde u_ {\cal M} $ , measuring locally the quality of $ \tilde u_ {\cal M} $ . The algorithm is carefully designed to obtain minimal complexity. A limitation of our analysis approach is that the meshes must be assumed to be quasi-uniform.     

Heuristic algorithm for generating multilevel Cartesian meshes inmultidimensional regions with moving boundaries

Universal algorithm for fully automated generation of multilevel Cartesian mesh in arbitrary planar regions with moving boundaries is developed and discussed in details. It uses multilevel tree technology and heuristic enabling flexible mesh adaptation to changes of boundaries. Efficient mixed coding for mesh storing is presented. Suggested algorithm generates meshes with properties most desirable for computing various field distribution problems. Main parts of elaborated algorithm are generalized for multidimensional meshes.     

Parallel Smoothed Aggregation Multilevel Schwarz Preconditioned Newton-Krylov Algorithms for Poisson-Boltzmann Problems

We study a multilevel Schwarz preconditioned Newton-Krylov algorithm to solve the Poisson-Boltzmann equation with applications in multi-particle colloidal simulation. The smoothed aggregation-type coarse mesh space is introduced in collaboration with the one-level Schwarz method as a composite preconditioner for accelerating the convergence of a Krylov subspace method for solving the Jacobian system at each Newton step. The important feature of the proposed solution algorithm is that the geometric mesh information needed for constructing the multilevel preconditioner is the same as the one-level Schwarz method on the fine mesh. Other components, such as the definition of the coarse mesh, all the mesh transfer operators, and the coarse mesh problem, are taken care of by the Trillinos/ML packages of the Sandia National Laboratories in the United States. After algorithmic parameter tuning, we show that the proposed smoothed aggregation multilevel Newton-Krylov-Schwarz (NKS) algorithm numerically outperforms than smoothed aggregation multigrid method and one-level version of the NKS algorithm with satisfactory parallel performances up to a few thousand cores. Besides, we investigate how the electrostatic forces between particles for the separation distance depend on the radius of spherical colloidal particles and valence ratios of cation and anion in a cubic system.     

The analysis of multigrid algorithms for cell centered finite difference methods

In this paper, we examine multigrid algorithms for cell centered finite difference approximations of second order elliptic boundary value problems. The cell centered application gives rise to one of the simplest non-variational multigrid algorithms. We shall provide an analysis which guarantees that the W-cycle and variable V-cycle multigrid algorithms converge with a rate of iterative convergence which can be bounded independently of the number of multilevel spaces. In contrast, the natural variational multigrid algorithm converges much more slowly.     

Multilevel graph partitioning: an evolutionary approach

The graph partitioning problem is defined as that of dividing the vertices of an undirected graph into a set of balanced parts through the removal of a set of edges, whose size is to be minimized. A number of researchers have investigated multilevel schemes, which coarsen the graph by collapsing vertices and edges, partition the smaller graph, and then uncoarsen it to construct a partitioning of the original graph. In this paper, a genetic algorithm for the coarsening phase of a multilevel scheme for graph partitioning is presented. The proposed approach has been demonstrated to improve the solution quality at the expense of running time.     

Solving the routing and wavelength assignment problem with a multilevel distributed memetic algorithm

The Routing and Wavelength Assignment problem is a graph optimization problem which deals with optical networks, where communication requests in a network have to be fulfilled. In this paper, we present a multilevel distributed memetic algorithm (ML-DMA) for the static RWA which finds provable optimal solutions for most benchmark instances with known lower bounds and is capable of handling large instances. Components of our ML-DMA include iterated local search, recombination, multilevel scaling, and a gossip-based distribution algorithm. Results demonstrated that our ML-DMA is among the most sophisticated heuristic RWA algorithms published so far.