Anisotropic mesh refinement in stabilized Galerkin methods

Summary. The numerical solution of a convection-diffusion-reaction model problem is considered in two and three dimensions. A stabilized finite element method of Galerkin/Least-square type accomodates diffusion-dominated as well as convection- and/or reaction-dominated situations. The resolution of boundary layers occuring in the singularly perturbed case is achieved using anisotropic mesh refinement in boundary layer regions. In this paper, the standard analysis of the stabilized Galerkin method on isotropic meshes is extended to more general meshes with boundary layer refinement. Simplicial Lagrangian elements of arbitrary order are used. Received March 6, 1995 / Revised version received August 18, 1995     

Planar mesh refinement cannot be both local and regular

We show that two desirable properties for planar mesh refinement techniques are incompatible. Mesh refinement is a common technique for adaptive error control in generating unstructured planar triangular meshes for piecewise polynomial representations of data. Local refinements are modifications of the mesh that involve a fixed maximum amount of computation, independent of the number of triangles in the mesh. Regular meshes are meshes for which every interior vertex has degree 6. At least for some simple model meshing problems, optimal meshes are known to be regular, hence it would be desirable to have a refinement technique that, if applied to a regular mesh, produced a larger regular mesh. We call such a technique a regular refinement. In this paper, we prove that no refinement technique can be both local and regular. Our results also have implications for non-local refinement techniques such as Delaunay insertion or Rivara's refinement. Received August 1, 1996 / Revised version received February 28, 1997     

On global and local mesh refinements by a generalized conforming bisection algorithm

We examine a generalized conforming bisection (GCB-)algorithm which allows both global and local nested refinements of the triangulations without generating hanging nodes. It is based on the notion of a mesh density function which prescribes where and how much to refine the mesh. Some regularity properties of generated sequences of refined triangulations are proved. Several numerical tests demonstrate the efficiency of the proposed bisection algorithm. It is also shown how to modify the GCB-algorithm in order to generate anisotropic meshes with high aspect ratios.     

Using machine learning to predict catastrophes in dynamical systems

Nonlinear dynamical systems, which include models of the Earth’s climate, financial markets and complex ecosystems, often undergo abrupt transitions that lead to radically different behavior. The ability to predict such qualitative and potentially disruptive changes is an important problem with far-reaching implications. Even with robust mathematical models, predicting such critical transitions prior to their occurrence is extremely difficult. In this work, we propose a machine learning method to study the parameter space of a complex system, where the dynamics is coarsely characterized using topological invariants. We show that by using a nearest neighbor algorithm to sample the parameter space in a specific manner, we are able to predict with high accuracy the locations of critical transitions in parameter space.     

On the moments and distribution of discrete Choquet integrals from continuous distributions

We study the moments and the distribution of the discrete Choquet integral when regarded as a real function of a random sample drawn from a continuous distribution. Since the discrete Choquet integral includes weighted arithmetic means, ordered weighted averaging functions, and lattice polynomial functions as particular cases, our results encompass the corresponding results for these aggregation functions. After detailing the results obtained in [J.-L. Marichal, I. Kojadinovic, Distribution functions of linear combinations of lattice polynomials from the uniform distribution, Statistics & Probability Letters 78 (2008) 985–991] in the uniform case, we present results for the standard exponential case, show how approximations of the moments can be obtained for other continuous distributions such as the standard normal, and elaborate on the asymptotic distribution of the Choquet integral. The results presented in this work can be used to improve the interpretation of discrete Choquet integrals when employed as aggregation functions.     

Equidistributed error mesh for problems with exponential boundary layers

In this paper we present a new piecewise-linear finite element mesh suitable for the discretization of the one-dimensional convection–diffusion equation -εu^″-bu^′=0$-\epsilon u^{″}-{\mathit{bu}}^{\prime }=0$, u(0)=0$u(0)=0$, u(1)=1$u(1)=1$. The solution to this equation exhibits an exponential boundary layer which occurs also in more complicated convection–diffusion problems of the form -εΔu-b∂u/∂x+cu=f$-\epsilon \mathrm{\Delta }u-b\partial u/\partial x+\mathit{cu}=f$. The new mesh is based on the equidistribution of the interpolation error and it takes into account finite computer arithmetic. It is demonstrated numerically that for the above problem, the new mesh has remarkably better convergence properties than the well-known Shishkin and Bakhvalov meshes.     

A Reduction Theorem for Capacity of Positive Maps

We prove a reduction theorem for capacity of positive unital maps of finite dimensional C*−algebras, thus reducing the computation of capacity to the case when the image of a nonscalar projection is never a projection.     

Simplicial grid refinement: on Freudenthal's algorithm and the optimal number of congruence classes

Summary. In the present paper we investigate Freudenthal's simplex refinement algorithm which can be considered to be the canonical generalization of Bank's well known red refinement strategy for triangles. Freudenthal's algorithm subdivides any given (n)-simplex into subsimplices, in such a way that recursive application results in a stable hierarchy of consistent triangulations. Our investigations concentrate in particular on the number of congruence classes generated by recursive refinements. After presentation of the method and the basic ideas behind it, we will show that Freudenthal's algorithm produces at most n!/2 congruence classes for any initial (n)-simplex, no matter how many subsequent refinements are performed. Moreover, we will show that this number is optimal in the sense that recursive application of any affine invariant refinement strategy with sons per element results in at least n!/2 congruence classes for almost all (n)-simplices. Received February 23, 1998/ Revised version received December 9, 1998 / Published online January 27, 2000     

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.     

Multi-level meshless methods based on direct multi-elliptic interpolation

A short overview on the direct multi-elliptic interpolation and the related meshless methods for solving partial differential equations is given. A new technique is proposed which produces a biharmonic interpolation along the boundary and solves the original problem inside the domain. An error estimation is also derived. To implement the method, quadtree-based multi-level methods are used. The approach avoids the use of large, dense and ill-conditioned matrices and significantly reduces the computational cost.     

A remark on fixed points of functors in topological categories

For a topological category over Set we prove that if a functor T: has a fixed cardinal (i.e. for each object K with card (UK)= we have card (UTK)), then T has a least fixed point, and if T has a successive pair of fixed cardinals and ⁺, then T has a greatest fixed point. This extends results of Adámek and Koubek.Partial financial support of the Grant Agency of the Czech Republic under Grant No. 201/93/0950 is gratefully acknowledged.     

Perfect state transfer in cubelike graphs

Suppose C is a subset of non-zero vectors from the vector space . The cubelike graphX(C) has as its vertex set, and two elements of are adjacent if their difference is in C. If M is the d×|C| matrix with the elements of C as its columns, we call the row space of M the code of X. We use this code to study perfect state transfer on cubelike graphs. Bernasconi et al. have shown that perfect state transfer occurs on X(C) at time π/2 if and only if the sum of the elements of C is not zero. Here we consider what happens when this sum is zero. We prove that if perfect state transfer occurs on a cubelike graph, then it must take place at time τ=π/2D, where D is the greatest common divisor of the weights of the code words. We show that perfect state transfer occurs at time π/4 if and only if D=2 and the code is self-orthogonal.     

A dual graph-norm refinement indicator for finite volume approximations of the Euler equations

Summary. We generalise and apply a refinement indicator of the type originally designed by Mackenzie, Süli and Warnecke in [15] and [16] for linear Friedrichs systems to the Euler equations of inviscid, compressible fluid flow. The Euler equations are symmetrized by means of entropy variables and locally linearized about a constant state to obtain a symmetric hyperbolic system to which an a posteriori error analysis of the type introduced in [15] can be applied. We discuss the details of the implementation of the refinement indicator into the DLR--Code which is based on a finite volume method of box type on an unstructured grid and present numerical results. Received May 15, 1995 / Revised version received April 17, 1996     

New Coins From Old: Computing With Unknown Bias

Suppose that we are given a function f : (0, 1)→(0,1) and, for some unknown p∈(0, 1), a sequence of independent tosses of a p-coin (i.e., a coin with probability p of “heads”). For which functions f is it possible to simulate an f(p)-coin? This question was raised by S. Asmussen and J. Propp. A simple simulation scheme for the constant function f(p)≡1/2 was described by von Neumann (1951); this scheme can be easily implemented using a finite automaton. We prove that in general, an f(p)-coin can be simulated by a finite automaton for all p ∈ (0, 1), if and only if f is a rational function over ℚ. We also show that if an f(p)-coin can be simulated by a pushdown automaton, then f is an algebraic function over ℚ; however, pushdown automata can simulate f(p)-coins for certain nonrational functions such as . These results complement the work of Keane and O’Brien (1994), who determined the functions f for which an f(p)-coin can be simulated when there are no computational restrictions on the simulation scheme. * Supported by a Miller Fellowship. † Supported in part by NSF Grant DMS-0104073 and by a Miller Professorship. ‡ This work is supported under a National Science Foundation Graduate Research Fellowship.     

A posteriori error estimator based on gradient recovery by averaging for discontinuous Galerkin methods

We consider some (anisotropic and piecewise constant) diffusion problems in domains of R², approximated by a discontinuous Galerkin method with polynomials of any fixed degree. We propose an a posteriori error estimator based on gradient recovery by averaging. It is shown that this estimator gives rise to an upper bound where the constant is one up to some additional terms that guarantee reliability. The lower bound is also established. Moreover these additional terms are negligible when the recovered gradient is superconvergent. The reliability and efficiency of the proposed estimator is confirmed by some numerical tests.     

Error estimators for advection–reaction–diffusion equations based on the solution of local problems

This paper deals with a posteriori error estimates for advection–reaction–diffusion equations. In particular, error estimators based on the solution of local problems are derived for a stabilized finite element method. These estimators are proved to be equivalent to the error, with equivalence constants eventually depending on the physical parameters. Numerical experiments illustrating the performance of this approach are reported.     

Covolume techniques for anisotropic media

Summary The covolume method, a new approach applicable on general meshes, is extended to discretize and numerically solve the div-curl system in anisotropic media. The covolume method gives simple schemes and good approximations to the solution of the div-curl system. It works directly with the system and utilizes dual pairs of meshes that are orthogonally related. Central to the approach is the introduction of field components tangent and normal to the edges of one of the meshes, and the employment of dual discretization on the dual mesh pairs. The discretization procedures, schemes and error analysis are presented. The convergence of the method is proved.The work was partially done while this author was at Carnegie Mellon University     

Gradient-enhanced surrogate modeling based on proper orthogonal decomposition

A new method for enhanced surrogate modeling of complex systems by exploiting gradient information is presented. The technique combines the proper orthogonal decomposition (POD) and interpolation methods capable of fitting both sampled input values and sampled derivative information like Kriging (aka spatial Gaussian processes). In contrast to existing POD-based interpolation approaches, the gradient-enhanced method takes both snapshots and partial derivatives of snapshots of the associated full-order model (FOM) as an input. It is proved that the resulting predictor reproduces these inputs exactly up to the standard POD truncation error. Hence, the enhanced predictor can be considered as (approximately) first-order accurate at the snapshot locations. The technique applies to all fields of application, where derivative information can be obtained efficiently, for example via solving associated primal or adjoint equations. This includes, but is not limited to Computational Fluid Dynamics (CFD). The method is demonstrated for an academic test case exhibiting the main features of reduced-order modeling of partial differential equations.     

Eigenfrequencies of fractal drums

A method for the computation of eigenfrequencies and eigenmodes of fractal drums is presented. The approach involves first conformally mapping the unit disk to a polygon approximating the fractal and then solving a weighted eigenvalue problem on the unit disk by a spectral collocation method. The numerical computation of the complicated conformal mapping was made feasible by the use of the fast multipole method as described in [L. Banjai, L.N. Trefethen, A multipole method for Schwarz–Christoffel mapping of polygons with thousands of sides, SIAM J. Sci. Comput. 25(3) (2003) 1042–1065]. The linear system arising from the spectral discretization is large and dense. To circumvent this problem we devise a fast method for the inversion of such a system. Consequently, the eigenvalue problem is solved iteratively. We obtain eight digits for the first eigenvalue of the Koch snowflake and at least five digits for eigenvalues up to the 20th. Numerical results for two more fractals are shown.     

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.