Two-level stabilized finite element method for the transient Navier–Stokes equations

In this article, a two-level stabilized finite element method based on two local Gauss integrations for the two-dimensional transient Navier–Stokes equations is analysed. This new stabilized method presents attractive features such as being parameter-free, or being defined for nonedge-based data structures. Some new a priori bounds for the stabilized finite element solution are derived. The two-level stabilized method involves solving one small Navier–Stokes problem on a coarse mesh with mesh size 0<H<1, and a large linear Stokes problem on a fine mesh with mesh size 0<h?H. A H ¹-optimal velocity approximation and a L ²-optimal pressure approximation are obtained. If we choose h=O(H ²), the two-level method gives the same order of approximation as the standard stabilized finite element method.     

Multilevel Monte Carlo method with applications to stochastic partial differential equations

In this work, the approximation of Hilbert-space-valued random variables is combined with the approximation of the expectation by a multilevel Monte Carlo (MLMC) method. The number of samples on the different levels of the multilevel approximation are chosen such that the errors are balanced. The overall work then decreases in the optimal case to O(h ^?2) if h is the error of the approximation. The MLMC method is applied to functions of solutions of parabolic and hyperbolic stochastic partial differential equations as needed, for example, for option pricing. Simulations complete the paper.     

The essential order of approximation for nearly exponential type neural networks

1 Introduction Artificial neural networks have been extensively applied in various fields of science and engineering. Why is so is mainly because the feedforward neural networks (FNNs) have the universal approximation capability[1-9]. A typical example of…     

L2–Optimal Fopdt Models of High–Order Transfer Functions

Necessary conditions for the L² optimality of a first order plus dead time (FOPDT) model of a high‐order plant are derived using classic analytic function theory. They are expressed as a set of three nonlinear equations that partly resemble the interpolation conditions valid for rational approximation. From these conditions a simple procedure to find the optimal FOPDT model is obtained. Examples taken from the relevant literature are worked out to show the performance of the method in comparison with alternative techniques.     

An A Priori Error Analysis of the hp-Version of the Continuous Galerkin FEM for Nonlinear Initial Value Problems

A continuous Galerkin finite element time-stepping method for the approximation of nonlinear initial value problems is analyzed within an hp-context. We derive a priori error bounds in the L²- and H¹-norm that are explicit with respect to the time steps and the approximation orders. In particular, it is shown that, for analytic solutions (with certain possible start-up singularities) exponential convergence rates can be achieved. Moreover, we prove that the scheme superconverges at the nodal points of the time partition. Numerical experiments illustrate the performance of the method.     

The Minimum Range Assignment Problem on Linear Radio Networks

Abstract. Given a set S of radio stations located on a line and an integer h ≥ 1 , the MIN ASSIGNMENT problem consists in finding a range assignment of minimum power consumption provided that any pair of stations can communicate in at most h hops. Previous positive results for this problem are only known when h=|S|-1 or in the uniform chain case (i.e., when the stations are equally spaced). As for the first case, Kirousis et al. [7] provided a polynomial-time algorithm while, for the second case, they derive a polynomial-time approximation algorithm. This paper presents the first polynomial-time, approximation algorithm for the MIN ASSIGNMENT problem. The algorithm guarantees a 2-approximation ratio and runs in O(hn ³ ) time. We also prove that, for fixed h and for ``well spaced' instances (a broad generalization of the uniform chain case), the problem admits a polynomial-time approximation scheme . This result significantly improves over the approximability result given by Kirousis {et al}. Both our approximation results are obtained via new algorithms that exactly solve two natural variants of the MIN ASSIGNMENT problem: the problem in which every station must reach a fixed one in at most h hops and the problem in which the goal is to select a subset of bases such that all the other stations must reach one base in at most h-1 hops. Finally, we show that for h=2 the MIN ASSIGNMENT problem can be exactly solved in O(n ³ ) time.     

<Emphasis Type="Italic">H</Emphasis><Superscript>1</Superscript>-interpolation on quadrilateral and hexahedral meshes with hanging nodes

We propose a Scott-Zhang type finite element interpolation operator of first order for the approximation of H ¹-functions by means of continuous piecewise mapped bilinear or trilinear polynomials. The novelty of the proposed interpolation operator is that it is defined for general non-affine equivalent quadrilateral and hexahedral elements and so-called 1-irregular meshes with hanging nodes. We prove optimal local approximation properties of this interpolation operator for functions in H ¹. As necessary ingredients we provide a definition of a hanging node and a rigorous analysis of the issue of constrained approximation which cover both the two- and three-dimensional case in a unified fashion.      

Fixed-Parameter Approximation: Conceptual Framework and Approximability Results

The notion of fixed-parameter approximation is introduced to investigate the approximability of optimization problems within the framework of fixed-parameter computation. This work partially aims at enhancing the world of fixed-parameter computation in parallel with the conventional theory of computation that includes both exact and approximate computations. In particular, it is proved that fixed-parameter approximability is closely related to the approximation of small-cost solutions in polynomial time. It is also demonstrated that many fixed-parameter intractable problems are not fixed-parameter approximable. On the other hand, fixed-parameter approximation appears to be a viable approach to solving some inapproximable yet important optimization problems. For instance, all problems in the class MAX SNP admit fixed-parameter approximation schemes in time O(2 ^{O((1−ε/O(1))k)} p(n)) for any small ε>0.     

A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs

In this paper we give a fully dynamic approximation scheme for maintaining all-pairs shortest paths in planar networks. Given an error parameter such that , our algorithm maintains approximate all-pairs shortest paths in an undirected planar graph G with nonnegative edge lengths. The approximate paths are guaranteed to be accurate to within a 1+ factor. The time bounds for both query and update for our algorithm is O( ^-1 n ^2/3 log ² n log D) , where n is the number of nodes in G and D is the sum of its edge lengths. The time bound for the queries is worst case, while that for the additions is amortized. Our approximation algorithm is based upon a novel technique for approximately representing all-pairs shortest paths among a selected subset of the nodes by a sparse substitute graph. Received January 1995; revised February 1997.     

An Approximation Algorithm for the Minimum Co-Path Set Problem

We present an approximation algorithm for the problem of finding a minimum set of edges in a given graph G whose removal from G leaves a graph in which each connected component is a path. It achieves a ratio of \frac 107\frac {10}{7} and runs in O(n ^1.5) time, where n is the number of vertices in the input graph. The previously best approximation algorithm for this problem achieves a ratio of 2 and runs in O(n ²) time.     

Further results on the L1 analysis of sampled-data systems via kernel approximation approach

This paper gives two methods for the L₁ analysis of sampled-data systems, by which we mean computing the L_∞-induced norm of sampled-data systems. This is achieved by developing what we call the kernel approximation approach in the setting of sampled-data systems. We first consider the lifting treatment of sampled-data systems and give an operator theoretic representation of their input/output relation. We further apply the fast-lifting technique by which the sampling interval [0, h) is divided into M subintervals with an equal width, and provide methods for computing the L_∞-induced norm. In contrast to a similar approach developed earlier called the input approximation approach, we use an idea of kernel approximation, in which the kernel function of an input operator and the hold function of an output operator are approximated by piecewise constant or piecewise linear functions. Furthermore, it is shown that the approximation errors in the piecewise constant approximation or piecewise linear approximation scheme converge to 0 at the rate of 1/M or 1/M², respectively. In comparison with the existing input approximation approach, in which the input function (rather than the kernel function) of the input operator is approximated by piecewise constant or piecewise linear functions, we show that the kernel approximation approach gives improved computation results. More precisely, even though the convergence rates in the kernel approximation approach remain qualitatively the same as those in the input approximation approach, the newly developed former approach could lead to quantitatively improved approximation errors than the latter approach particularly when the piecewise linear approximation scheme is taken. Finally, a numerical example is given to demonstrate the effectiveness of the kernel approximation approach with this scheme.     

Utilisation de la méthode des éléments finis en mécanique des fluides,I

An analysis is made of the possibility of building divergence free elements for the approximation of the Navier-Stokes equations of an incomprensible fluid. Two types of appoximation are considered. In the first real divergence free elements are considered. Many examples are given and error bounds are derived. It is shown that 0 (h ⁴) precision can be obtained using fourth degree polynomials. In the second type of approximation the incompressibility condition is satisfied only in the average. Two and three dimensional examples are given, using respectively second and third order polynomials. A possible numerical scheme is proposed for the case the steady-state linearized Stokes problem. Experimental evidence shows that it can be also used in the general non-linear case. Simple numerical results are presented for the cavity problem in two dimensions.

---

---

Ce travail a été rendu possible en partie grace à une subvention du Conseil National de la Recherche du Canada.     

Fully polynomial time approximation scheme for the weighted flow-time minimization on a single machine with a fixed non-availability interval

In a recent paper [Theoretical Computer Science 363, 257–265], He, Zhong and Gu considered the non-resumable case of the scheduling problem with a fixed non-availability interval under the non-resumable scenario. They proposed a polynomial time approximation scheme (PTAS) to minimize the total completion time.In this paper, we propose a fully polynomial-time approximation scheme to minimize the total weighted completion time. The FPTAS has O(n²/ε²) time complexity, where n is the number of jobs and ε is the required error bound. The proposed FPTAS outperforms all the previous approximation algorithms designed for this problem and its running time is strongly polynomial.     

Mixed Discontinuous Galerkin Finite Element Method for the Biharmonic Equation

In this paper, we first split the biharmonic equation Δ² u=f with nonhomogeneous essential boundary conditions into a system of two second order equations by introducing an auxiliary variable v=Δu and then apply an hp-mixed discontinuous Galerkin method to the resulting system. The unknown approximation v _h of v can easily be eliminated to reduce the discrete problem to a Schur complement system in u _h , which is an approximation of u. A direct approximation v _h of v can be obtained from the approximation u _h of u. Using piecewise polynomials of degree p≥3, a priori error estimates of u−u _h in the broken H ¹ norm as well as in L ² norm which are optimal in h and suboptimal in p are derived. Moreover, a priori error bound for v−v _h in L ² norm which is suboptimal in h and p is also discussed. When p=2, the preset method also converges, but with suboptimal convergence rate. Finally, numerical experiments are presented to illustrate the theoretical results. Supported by DST-DAAD (PPP-05) project.     

Inapproximability Results for Guarding Polygons and Terrains

Past research on art gallery problems has concentrated almost exclusively on bounds on the numbers of guards needed in the worst case in various settings. On the complexity side, fewer results are available. For instance, it has long been known that placing a smallest number of guards for a given input polygon is NP -hard. In this paper we initiate the study of the approximability of several types of art gallery problems. Motivated by a practical problem, we study the approximation properties of the three art gallery problems VERTEX GUARD, EDGE GUARD, and POINT GUARD. We prove that if the input polygon has no holes, there is a constant δ >0 such that no polynomial time algorithm can achieve an approximation ratio of 1+δ , for each of these guard problems. We obtain these results by proposing gap-preserving reductions from 5-OCCURRENCE-MAX-3-SAT. We also prove that if the input polygons are allowed to contain holes, then these problems cannot be approximated by a polynomial time algorithm with ratio ((1-ɛ)/12) \ln n for any ɛ > 0 , unless NP \subseteq TIME(n ^{O (log log n)} ) , where n is the number of vertices of the input polygon. We obtain these results by proposing gap-preserving reductions from the SET COVER problem. We show that this inapproximability for the POINT GUARD problem for polygons with holes carries over to the problem of covering a 2.5-dimensional terrain with a minimum number of guards that are placed at a certain fixed height above the terrain. The same holds if the guards may be placed on the terrain itself. Received September 22, 1999; revised December 5, 1999.     

Fast parallel solution of boundary integral equations and related problems

This article is concerned with the efficient numerical solution of Fredholm integral equations on a parallel computer with shared or distributed memory. Parallel algorithms for both, the approximation of the discrete operator by hierarchical matrices using adaptive cross approximation (ACA) and the parallel matrix-vector multiplication of such matrices by a vector, are presented. The first algorithm has a complexity of order p ^-1 N log^2d-1 N, while the latter is of order p ^-1 N log ^d N, where N, d and p are the number of unknowns, the spatial dimension and the number of processors, respectively. The approximant needs Ω(p ^-1 N log ^d N) units of storage on each processor. Dedicated to George C. Hsiao on the occasion of his 70th birthday. Mathematics Subject Classification (2000)65D05 65D15 65F05 65F30 Communicated by: U. Langer     

Hardness and approximation results for packing steiner trees

We study approximation algorithms and hardness of approximation for several versions of the problem of packing Steiner trees. For packing edge-disjoint Steiner trees of undirected graphs, we show APX-hardness for four terminals. For packing Steiner-node-disjoint Steiner trees of undirected graphs, we show a logarithmic hardness result, and give an approximation guarantee ofO (√n logn), wheren denotes the number of nodes. For the directed setting (packing edge-disjoint Steiner trees of directed graphs), we show a hardness result of Θ(m ^1/3/−ɛ) and give an approximation guarantee ofO(m ^1/2/+ɛ), wherem denotes the number of edges. We have similar results for packing Steiner-node-disjoint priority Steiner trees of undirected graphs. Supported by NSERC Grant No. OGP0138432. Supported by an NSERC postdoctoral fellowship, Department of Combinatorics and Optimization at University of Waterloo, and a University start-up fund at University of Alberta.     

Universal Approximation Theorem for Interval Neural Networks

One of the main computer-learning tools is an (artificial) neural network (NN); based on the values y ^(p) of a certain physical quantity y at several points x ^(p) =(x ₁ ^(p) ,...,x _n ^(p) ), the NN finds a dependence y = f(x₁,...,x _n ) that explains all known observations and predicts the value of y for other x = (x1,...,xn). The ability to describe an arbitrary dependence follows from the universal approximation theorem, according to which an arbitrary continuous function of a bounded set can be, within a given accuracy, approximated by an appropriate NN.The measured values of y are often only known with interval uncertainty. To describe such situations, we can allow interval parameters in a NN and thus, consider an interval NN. In this paper, we prove the universal approximation theorem for such interval NN's.     

Approximation of functions by perceptrons: a new approach

We provide a constructive proof of the theorem of function approximation by perceptrons (cf Leshno et al. [1], Hornik [2]) when the activation function ψ isC∞ with all its derivatives non 0 at 0. We deal with uniform approximation on compact sets of continuous functions on ℜ ^d ,d≥1. This approach is elementary and provides some approximation results for the derivatives along with some bounds for the hidden layer.     

Reoptimization of constraint satisfaction problems with approximation resistant predicates

If k = O(log n) and a predicate P is approximation resistant for the reoptimization of the Max-EkCSP-P problem, then, after inserting a truth-value into the predicate and imposing some constraint, there exists a polynomial algorithm with the approximation ratio q(P) = \frac12 - d(P) q(P) = \frac{1}{{2 - d(P)}} , where d(P) = 2 ^{- k}| P ^{- 1}(1) | d(P) = {2^{ - k}}\left| {{P^{ - 1}}(1)} \right| is a “random” threshold approximation ratio of the predicate P. The ratio q(P) is a threshold approximation ratio.