The Inf-Sup Condition for the Mapped Q k ?P k?1 disc Element in Arbitrary Space Dimensions

 One of the most popular pairs of finite elements for solving mixed formulations of the Stokes and Navier–Stokes problem is the Q _k −P _k−1 ^disc element. Two possible versions of the discontinuous pressure space can be considered: one can either use an unmapped version of the P _k−1 ^disc space consisting of piecewise polynomial functions of degree at most k−1 on each cell or define a mapped version where the pressure space is defined as the image of a polynomial space on a reference cell. Since the reference transformation is in general not affine but multilinear, the two variants are not equal on arbitrary meshes. It is well-known, that the inf-sup condition is satisfied for the first variant. In the present paper we show that the latter approach satisfies the inf-sup condition as well for k≥2 in any space dimension. Received January 31, 2001; revised May 2, 2002 Published online: July 26, 2002     

Approximating Local Averages of Fluid Velocities: The Stokes Problem

As a first step to developing mathematical support for finite element approximation to the large eddies in fluid motion we consider herein the Stokes problem. We show that the local average of the usual approximate flow field u ^h over radius δ provides a very accurate approximation to the flow structures of O(δ) or greater. The extra accuracy appears for quadratic or higher velocity elements and degrades to the usual finite element accuracy as the averaging radius δ→h (the local meshwidth). We give both a priori and a posteriori error estimates incorporating this effect. Received December 3, 1999; revised October 16, 2000     

Bounds for theN lowest eigenvalues of fourth-order boundary value problems

We describe a method for the calculation of theN lowest eigenvalues of fourth-order problems inH ₀ ² (Ω). In order to obtain small error bounds, we compute the defects inH ⁻²(Ω) and, to obtain a bound for the rest of the spectrum, we use a boundary homotopy method. As an example, we compute strict error bounds (using interval arithmetic to control rounding errors) for the 100 lowest eigenvalues of the clamped plate problem in the unit square. Applying symmetry properties, we prove the existence of double eigenvalues.     

Two-level Stabilized Finite Element Methods for the Steady Navier–Stokes Problem

In this article, the two-level stabilized finite element formulations of the two-dimensional steady Navier–Stokes problem are analyzed. A macroelement condition is introduced for constructing the local stabilized formulation of the steady Navier–Stokes problem. By satisfying this condition the stability of the Q₁–P₀ quadrilateral element and the P₁–P₀ triangular element are established. Moreover, the two-level stabilized finite element methods involve solving one small Navier–Stokes problem on a coarse mesh with mesh size H, a large Stokes problem for the simple two-level stabilized finite element method on a fine mesh with mesh size h=O(H²) or a large general Stokes problem for the Newton two-level stabilized finite element method on a fine mesh with mesh size h=O(|log h|^1/2H³). The methods we study provide an approximate solution (u^h,p^h) with the convergence rate of same order as the usual stabilized finite element solution, which involves solving one large Navier–Stokes problem on a fine mesh with mesh size h. Hence, our methods can save a large amount of computational time.     

A Coupled Multigrid Method for Nonconforming Finite Element Discretizations of the 2D-Stokes Equation

This paper investigates a multigrid method for the solution of the saddle point formulation of the discrete Stokes equation obtained with inf–sup stable nonconforming finite elements of lowest order. A smoother proposed by Braess and Sarazin (1997) is used and L ²-projection as well as simple averaging are considered as prolongation. The W-cycle convergence in the L ²-norm of the velocity with a rate independently of the level and linearly decreasing with increasing number of smoothing steps is proven. Numerical tests confirm the theoretically predicted results. Received January 19, 1999; revised September 13, 1999     

Two-level methods for the single layer potential in ℝ3

We consider weakly singular integral equations of the first kind on open surface pieces Γ in ℝ³. To obtain approximate solutions we use theh-version Galerkin boundary element method. Furthermore we introduce two-level additive Schwarz operators for non-overlapping domain decompositions of Γ and we estimate the conditions numbers of these operators with respect to the mesh size. Based on these operators we derive an a posteriori error estimate for the difference between the exact solution and the Galerkin solution. The estimate also involves the error which comes from an approximate solution of the Galerkin equations. For uniform meshes and under the assumption of a saturation condition we show reliability and efficiency of our estimate. Based on this estimate we introduce an adaptive multilevel algorithm with easily computable local error indicators which allows direction control of the local refinements. The theoretical results are illustrated by numerical examples for plane and curved surfaces. Supported by the German Research Foundation (DFG) under grant Ste 238/25-9.     

On the rate of convergence of 2-term recursions in ℝ d

LetG be a compact set in ℝ ^d d≥1,M=G×G andϕ:M →G a map inC ₃(M). Suppose thatϕ has a fixed pointξ, i.e.ϕ(ξ, ξ)=ξ. We investigate the rate of convergence of the iterationx ⁿ⁺²=φ(x ⁿ⁺¹,x ⁿ) withx ⁰,x ¹∈G andx ⁿ→ξ. Iff _n=Q‖x ⁿ−ξ‖ with a suitable norm and a constantQ depending onξ, an exact representation forf _n is derived. The error terms satisfyf _2m+1≍(ƒ_2m)^γ,f _2m+2≍(ƒ_2m+1)^2γ,m≥0, with 1<gg<2, andγ=γ(x ¹,x ⁰). According to our main result we have lim_n→∞{‖x ⁿ⁺²‖/(‖x ⁿ‖)²}=Q, 0<Q<∞. This paper constitutes an extension of a part of the author’s doctoral thesis realized under the direction of Prof. E. Wirsing and Prof. A. Peyerimhoff, University of Ulm (Germany).     

Polynomial algorithms for finding the asymptotically optimum plan of the multiindex axial assignment problem

To construct the asymptotically optimum plan of the p-index axial assignment problem of order n, p algorithms α₀, α₁, ..., α _p−1 with complexities equal to O(n^p+1), O(n^p), ..., O(n²) operations, respectively, are proposed and substantiated under some additional conditions imposed on the coefficients of the objective function. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 176–181, November–December 2005.     

A nonconforming finite element method¶with anisotropic mesh grading¶for the incompressible Navier–Stokes equations¶in domains with edges

Any solution of the incompressible Navier–Stokes equations in three-dimensional domains with edges has anisotropic singular behaviour which is treated numerically by using anisotropic finite element meshes. The velocity is approximated by Crouzeix–Raviart (nonconforming 𝒫₁) elements and the pressure by piecewise constants. This method is stable for general meshes since the inf-sup condition is satisfied without minimal or maximal angle condition. The existence of solutions to the discrete problems follows. Consistency error estimates for the divergence equation are obtained for anisotropic tensor product meshes. As applications, the consistency error estimate for the Navier–Stokes solution and some discrete Sobolev inequalities are derived on such meshes. These last results provide optimal error estimates in the uniqueness case by the use of appropriately refined anisotropic tensor product meshes, namely, if N _e is the number of elements of the mesh, we prove that the optimal order of convergence h∼ N _e ^{− 1/3}. Received:July 2001 / Accepted: July 2002     

Condition Numbers of Approximate Schur Complements in Two- and Three-Dimensional Discretizations on Hierarchically Ordered Grids

We investigate multilevel incomplete factorizations of M-matrices arising from finite difference discretizations. The nonzero patterns are based on special orderings of the grid points. Hence, the Schur complements that result from block elimination of unknowns refer to a sequence of hierarchical grids. Having reached the coarsest grid, Gaussian elimination yields a complete decomposition of the last Schur complement. The main focus of this paper is a generalization of the recursive five-point/nine-point factorization method (which can be applied in two-dimensional problems) to matrices that stem from discretizations on three-dimensional cartesian grids. Moreover, we present a local analysis that considers fundamental grid cells. Our analysis allows to derive sharp bounds for the condition number associated with one factorization level (two-grid estimates). A comparison in case of the Laplace operator with Dirichlet boundary conditions shows: Estimating the relative condition number of the multilevel preconditioner by multiplying corresponding two-grid values gives the asymptotic bound O(h ^−0.347) for the two- respectively O(h ^−4/5) for the three-dimensional model problem. Received October 19, 1998; revised September 27, 1999     

Two-Level Additive Schwarz Preconditioners for the h-p Version of the Galerkin Boundary Element Method for 2-d Problems

We study two-level additive Schwarz preconditioners for the h-p version of the Galerkin boundary element method when used to solve hypersingular integral equations of the first kind, which arise from the Neumann problems for the Laplacian in two dimensions. Overlapping and non-overlapping methods are considered. We prove that the non-overlapping preconditioner yields a system of equations having a condition number bounded by   where H _i is the length of the i-th subdomain, h _i is the maximum length of the elements in this subdomain, and p is the maximum polynomial degree used. For the overlapping method, we prove that the condition number is bounded by   where δ is the size of the overlap and H=max _i H _i . We also discuss the use of the non-overlapping method when the mesh is geometrically graded. The condition number in that case is bounded by clog² M, where M is the degrees of freedom. Received October 27, 2000, revised March 26, 2001     

Output-Sensitive Algorithm for Computing β-Skeletons

The β-skeleton is a measure of the internal shape of a planar set of points. We get an entire spectrum of shapes by varying the parameter β. For a fixed value of β, a β-skeleton is a geometric graph obtained by joining each pair of points whose β-neighborhood is empty. For β≥1, this neighborhood of a pair of points p _i ,p _j is the interior of the intersection of two circles of radius , centered at the points (1−β/2)p _i +(β/2)p _j and (β/2)p _i +(1−β/2)p _j , respectively. For β∈(0,1], it is the interior of the intersection of two circles of radius , passing through p _i and p _j . In this paper we present an output-sensitive algorithm for computing a β-skeleton in the metrics l ₁ and l _∞ for any β≥2. This algorithm is in O(nlogn+k), where k is size of the output graph. The complexity of the previous best known algorithm is in O(n ^5/2logn) [7]. Received April 26, 2000     

Computing multiple pitchfork bifurcation points

A point (x*,λ*) is called apitchfork bifurcation point of multiplicityp≥1 of the nonlinear systemF(x, λ)=0,F:ℝⁿ×ℝ¹→ℝⁿ, if rank∂ _xF(x*, λ*)=n−1, and if the Ljapunov-Schmidt reduced equation has the normal formg(ξ, μ)=±ξ ²⁺ p±μξ=0. It is shown that such points satisfy a minimally extended systemG(y)=0,G:ℝ ⁿ⁺²→ℝⁿ⁺² the dimensionn+2 of which is independent ofp. For solving this system, a two-stage Newton-type method is proposed. Some numerical tests show the influence of the starting point and of the bordering vectors used in the definition of the extended system on the behavior of the iteration.     

Data Mining with Sparse Grids

O (h _n ⁻¹ n ^{d −1}) instead of O(h _n ^−d ) grid points and unknowns are involved. Here d denotes the dimension of the feature space and h _n = 2 ⁻ⁿ gives the mesh size. To be precise, we suggest to use the sparse grid combination technique [42] where the classification problem is discretized and solved on a certain sequence of conventional grids with uniform mesh sizes in each coordinate direction. The sparse grid solution is then obtained from the solutions on these different grids by linear combination. In contrast to other sparse grid techniques, the combination method is simpler to use and can be parallelized in a natural and straightforward way. We describe the sparse grid combination technique for the classification problem in terms of the regularization network approach. We then give implementational details and discuss the complexity of the algorithm. It turns out that the method scales only linearly with the number of instances, i.e. the amount of data to be classified. Finally we report on the quality of the classifier built by our new method. Here we consider standard test problems from the UCI repository and problems with huge synthetical data sets in up to 9 dimensions. It turns out that our new method achieves correctness rates which are competitive to that of the best existing methods. Received April 25, 2001     

Numerical Evaluation of the Accuracy and Stability Properties of High-order Direct Stokes Solvers with or without Temporal Splitting

The temporal stability and effective order of two different direct high-order Stokes solvers are examined. Both solvers start from the primitive variables formulation of the Stokes problem, but are distinct by the numerical uncoupling they apply on the Stokes operator. One of these solvers introduces an intermediate divergence free velocity for performing a temporal splitting (J. Comput. Phys. [1991] 97, 414–443) while the other treats the whole Stokes problem through the evaluation of a divergence free acceleration field (C.R. Acad. Sci. Paris [1994] 319 Serie I, 1455–1461; SIAM J. Scient. Comput. [2000] 22(4), 1386–1410). The second uncoupling is known to be consistent with the harmonicity of the pressure field (SIAM J. Scient. Comput. [2000] 22(4), 1386–1410). Both solvers proceed by two steps, a pressure evaluation based on an extrapolated in time (of theoretical order J_e) Neumann condition, and a time implicit (of theoretical order J_i) diffusion step for the final velocity. These solvers are implemented with a Chebyshev mono-domain and a Legendre spectral element collocation schemes. The numerical stability of these four options is investigated for the sixteen combinations of (J_e,J_i), 1 ≤ J_e, J_i ≤ 4.     

On the performance of Dijkstra’s third self-stabilizing algorithm for mutual exclusion and related algorithms

In Dijkstra (Commun ACM 17(11):643–644, 1974) introduced the notion of self-stabilizing algorithms and presented three such algorithms for the problem of mutual exclusion on a ring of n processors. The third algorithm is the most interesting of these three but is rather non intuitive. In Dijkstra (Distrib Comput 1:5–6, 1986) a proof of its correctness was presented, but the question of determining its worst case complexity—that is, providing an upper bound on the number of moves of this algorithm until it stabilizes—remained open. In this paper we solve this question and prove an upper bound of 3\frac1318 n² + O(n){3\frac{13}{18} n^2 + O(n)} for the complexity of this algorithm. We also show a lower bound of 1\frac56 n² - O(n){1\frac{5}{6} n^2 - O(n)} for the worst case complexity. For computing the upper bound, we use two techniques: potential functions and amortized analysis. We also present a new-three state self-stabilizing algorithm for mutual exclusion and show a tight bound of \frac56 n² + O(n){\frac{5}{6} n^2 + O(n)} for the worst case complexity of this algorithm. In Beauquier and Debas (Proceedings of the second workshop on self-stabilizing systems, pp 17.1–17.13, 1995) presented a similar three-state algorithm, with an upper bound of 5\frac34n²+O(n){5\frac{3}{4}n^2+O(n)} and a lower bound of \frac18n²-O(n){\frac{1}{8}n^2-O(n)} for its stabilization time. For this algorithm we prove an upper bound of 1\frac12n² + O(n){1\frac{1}{2}n^2 + O(n)} and show a lower bound of n ²−O(n). As far as the worst case performance is considered, the algorithm in Beauquier and Debas (Proceedings of the second workshop on self-stabilizing systems, pp 17.1–17.13, 1995) is better than the one in Dijkstra (Commun ACM 17(11):643–644, 1974) and our algorithm is better than both.     

Gauss-Legendre elements: a stable, higher order non-conforming finite element family

We consider the non-conforming Gauss-Legendre finite element family of any even degree k≥4 and prove its inf-sup stability without assumptions on the grid. This family consists of Scott-Vogelius elements where appropriate k-th-degree non-conforming bubbles are added to the velocities – which are trianglewise polynomials of degree k.     

The Tau Method as an analytic tool in the discussion of equivalence results across numerical methods

A Tau Method approximate solution of a given differential equation defined on a compact [a, b] is obtained by adding to the right hand side of the equation a specific minimal polynomial perturbation termH _n(x), which plays the role of a representation of zero in [a,b] by elements of a given subspace of polynomials. Neither discretization nor orthogonality are involved in this process of approximation. However, there are interesting relations between the Tau Method and approximation methods based on the former techniques. In this paper we use equivalence results for collocation and the Tau Method, contributed recently by the authors together with classical results in the literature, to identify precisely the perturbation termH(x) which would generate a Tau Method approximate solution, identical to that generated by some specific discrete methods over a given mesh Π ∈ [a, b]. Finally, we discuss a technique which solves the inverse problem, that is, to find adiscrete perturbed Runge-Kutta scheme which would simulate a prescribed Tau Method. We have chosen, as an example, a Tau Method which recovers the same approximation as an orthogonal expansion method. In this way we close the diagram defined by finite difference methods, collocation schemes, spectral techniques and the Tau Method through a systematic use of the latter as an analytical tool.     

The Directed Orienteering Problem

This paper studies vehicle routing problems on asymmetric metrics. Our starting point is the directed k-TSP problem: given an asymmetric metric (V,d), a root r∈V and a target k≤|V|, compute the minimum length tour that contains r and at least k other vertices. We present a polynomial time O(\fraclog² nloglogn·logk)O(\frac{\log^{2} n}{\log\log n}\cdot\log k)-approximation algorithm for this problem. We use this algorithm for directed k-TSP to obtain an O(\fraclog² nloglogn)O(\frac{\log^{2} n}{\log\log n})-approximation algorithm for the directed orienteering problem. This answers positively, the question of poly-logarithmic approximability of directed orienteering, an open problem from Blum et al. (SIAM J. Comput. 37(2):653–670, 2007). The previously best known results were quasi-polynomial time algorithms with approximation guarantees of O(log ² k) for directed k-TSP, and O(log n) for directed orienteering (Chekuri and Pal in IEEE Symposium on Foundations in Computer Science, pp. 245–253, 2005). Using the algorithm for directed orienteering within the framework of Blum et al. (SIAM J. Comput. 37(2):653–670, 2007) and Bansal et al. (ACM Symposium on Theory of Computing, pp. 166–174, 2004), we also obtain poly-logarithmic approximation algorithms for the directed versions of discounted-reward TSP and vehicle routing problem with time-windows.     

Nonlocal quasi-Newton method for solving convex variational inequalities

Conclusion In the optimization problem [f ₀(x)│h_i(x)<-0,i=1,…,l] relaxation of the functionf ₀(x)+Nh⁺(x) does not produce, as we know [6, 7], α_k=1 in Newton's method with the auxiliary problem (5), (6), whereF(x)=f _0′(x). For this reason, Newton type methods based on relaxation off ₀(x)+Nh⁺(x) are not superlinearly convergent (so-called Maratos effect). The results of this article indicate that if (F(x)=f _0′(x), then replacement of the initial optimization problem with a larger equivalent problem (7) eliminates the Maratos effect in the proposed quasi-Newton method. This result is mainly of theoretical interest, because Newton type optimization methods in the space of the variablesx ∈R ⁿ are less complex. However to the best of our knowledge, the difficulties with nonlocal convergence arising in these methods (choice of parameters, etc.) have not been fully resolved [10, 11]. The discussion of these difficulties and comparison with the proposed method fall outside the scope of the present article, which focuses on solution of variational inequalities (1), (2) for the general caseF′(x)≠F′ ^T(x). Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 78–91, November–December, 1994.