ALBERT

Description:    In the present work a general theoretical framework for coupled dimensionally-heterogeneous partial differential equations is developed. This is done by recasting the variational formulation in terms of coupling interface variables. In such a general setting we analyze existence and uniqueness of solutions for both the continuous problem and its finite dimensional approximation. This approach also allows the development of different iterative substructuring solution methodologies involving dimensionally-homogeneous subproblems. Numerical experiments are carried out to test our theoretical results. Content Type Journal Article Pages 1-37 DOI 10.1007/s00211-011-0387-y Authors Pablo J. Blanco, LNCC, Laboratório Nacional de Computação Científica, Av. Getúlio Vargas 333, Quitandinha, 25651-075 Petrópolis, Brazil Marco Discacciati, MATHICSE, Chair of Modelling and Scientific Computing, Ecole Polytechnique Fédérale de Lausanne, Station 8, CH-1015 Lausanne, Switzerland Alfio Quarteroni, MATHICSE, Chair of Modelling and Scientific Computing, Ecole Polytechnique Fédérale de Lausanne, Station 8, CH-1015 Lausanne, Switzerland Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    In this paper we introduce a generalized Sobolev space by defining a semi-inner product formulated in terms of a vector distributional operator P consisting of finitely or countably many distributional operators P n , which are defined on the dual space of the Schwartz space. The types of operators we consider include not only differential operators, but also more general distributional operators such as pseudo-differential operators. We deduce that a certain appropriate full-space Green function G with respect to L :=  P * T P now becomes a conditionally positive function. In order to support this claim we ensure that the distributional adjoint operator P * of P is well-defined in the distributional sense. Under sufficient conditions, the native space (reproducing-kernel Hilbert space) associated with the Green function G can be embedded into or even be equivalent to a generalized Sobolev space. As an application, we take linear combinations of translates of the Green function with possibly added polynomial terms and construct a multivariate minimum-norm interpolant s f , X to data values sampled from an unknown generalized Sobolev function f at data sites located in some set X Ì \mathbb R d . We provide several examples, such as Matérn kernels or Gaussian kernels, that illustrate how many reproducing-kernel Hilbert spaces of well-known reproducing kernels are equivalent to a generalized Sobolev space. These examples further illustrate how we can rescale the Sobolev spaces by the vector distributional operator P . Introducing the notion of scale as part of the definition of a generalized Sobolev space may help us to choose the “best” kernel function for kernel-based approximation methods. Content Type Journal Article Pages 1-27 DOI 10.1007/s00211-011-0391-2 Authors Gregory E. Fasshauer, Department of Applied Mathematics, Illinois Institute of Technology, Chicago, IL 60616, USA Qi Ye, Department of Applied Mathematics, Illinois Institute of Technology, Chicago, IL 60616, USA Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    We are concerned with the inverse problem for an eikonal equation of determining the speed function using observations of the arrival time on a fixed surface. This is formulated as an optimisation problem for a quadratic functional with the state equation being the eikonal equation coupled to the so-called Soner boundary condition. The state equation is discretised by a suitable finite difference scheme for which we obtain existence, uniqueness and an error bound. We set up an approximate optimisation problem and show that a subsequence of the discrete mimina converges to a solution of the continuous optimisation problem as the mesh size goes to zero. The derivative of the discrete functional is calculated with the help of an adjoint equation which can be solved efficiently by using fast marching techniques. Finally we describe some numerical results. Content Type Journal Article Pages 1-25 DOI 10.1007/s00211-011-0386-z Authors Klaus Deckelnick, Institut für Analysis und Numerik, Otto-von-Guericke-Universität Magdeburg, Universitätsplatz 2, 39106 Magdeburg, Germany Charles M. Elliott, Mathematics Institute, University of Warwick, Coventry, CV4 7AL UK Vanessa Styles, Department of Mathematics, University of Sussex, Brighton, BN1 9RF UK Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    In this paper we construct polynomial lattice rules which have, in some sense, small gain coefficients using a component-by-component approach. The gain coefficients, as introduced by Owen, indicate to what degree the method improves upon Monte Carlo. We show that the variance of an estimator based on a scrambled polynomial lattice rule constructed component-by-component decays at a rate of N −(2 α +1)+ δ , for all δ  〉 0, assuming that the function under consideration has bounded variation of order α for some 0 〈 α ≤ 1, and where N denotes the number of quadrature points. An analogous result is obtained for Korobov polynomial lattice rules. It is also established that these rules are almost optimal for the function space considered in this paper. Furthermore, we discuss the implementation of the component-by-component approach and show how to reduce the computational cost associated with it. Finally, we present numerical results comparing scrambled polynomial lattice rules and scrambled digital nets. Content Type Journal Article Pages 1-27 DOI 10.1007/s00211-011-0385-0 Authors Jan Baldeaux, School of Mathematics, University of New South Wales, Sydney, 2052 Australia Josef Dick, School of Mathematics, University of New South Wales, Sydney, 2052 Australia Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    A procedure for the construction of robust, upper bounds for the error in the finite element approximation of singularly perturbed reaction–diffusion problems was presented in Ainsworth and Babuška (SIAM J Numer Anal 36(2):331–353, 1999 ) which entailed the solution of an infinite dimensional local boundary value problem. It is not possible to solve this problem exactly and this fact was recognised in the above work where it was indicated that the limitation would be addressed in a subsequent article. We view the present work as fulfilling that promise and as completing the investigation begun in Ainsworth and Babuška (SIAM J Numer Anal 36(2):331–353, 1999 ) by removing the obligation to solve a local problem exactly. The resulting new estimator is indeed fully computable and the first to provide fully computable, robust upper bounds in the setting of singularly perturbed problems discretised by the finite element method. Content Type Journal Article Pages 1-25 DOI 10.1007/s00211-011-0384-1 Authors Mark Ainsworth, Department of Mathematics, Strathclyde University, 26 Richmond St., Glasgow, G1 1XH Scotland Tomáš Vejchodský, Institute of Mathematics, Academy of Sciences, Žitná 25, 115 67 Prague 1, Czech Republic Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    We present a hierarchical a posteriori error analysis for the minimum value of the energy functional in symmetric obstacle problems. The main result is that the error in the energy minimum is, up to oscillation terms, equivalent to an appropriate hierarchical estimator. The proof does not invoke any saturation assumption. We even show that small oscillation implies a related saturation assumption. In addition, we prove efficiency and reliability of an a posteriori estimate of the discretization error and thereby cast some light on the theoretical understanding of previous hierarchical estimators. Finally, we illustrate our theoretical results by numerical computations. Content Type Journal Article Pages 1-25 DOI 10.1007/s00211-011-0364-5 Authors Qingsong Zou, Freie Universität Berlin, Berlin, Germany Andreas Veeser, Freie Universität Berlin, Berlin, Germany Ralf Kornhuber, Freie Universität Berlin, Berlin, Germany Carsten Gräser, Freie Universität Berlin, Berlin, Germany Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    In this article, we give a new rigorous condition number estimate of the finite element tearing and interconnecting (FETI) method and a variant thereof, all-floating FETI. We consider a scalar elliptic equation in a two- or three-dimensional domain with a highly heterogeneous (multiscale) diffusion coefficient. This coefficient is allowed to have large jumps not only across but also along subdomain interfaces and in the interior of the subdomains. In other words, the subdomain partitioning does not need to resolve any jumps in the coefficient. Under suitable assumptions, we derive bounds for the condition numbers of one-level and all-floating FETI that are robust with respect to strong variations in the contrast in the coefficient, and that are explicit in some geometric parameters associated with the coefficient variation. In particular, robustness holds for face, edge, and vertex islands in high-contrast media. As a central tool we prove and use new weighted Poincaré and discrete Sobolev type inequalities that are explicit in the weight. Our theoretical findings are confirmed in a series of numerical experiments. Content Type Journal Article Pages 1-45 DOI 10.1007/s00211-011-0359-2 Authors Clemens Pechstein, Institute of Computational Mathematics, Johannes Kepler University, Altenberger Str. 69, 4040 Linz, Austria Robert Scheichl, Department of Mathematical Sciences, University of Bath, Bath, BA2 7AY UK Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    We consider the Fourier analysis of multigrid methods (of Galerkin type) for symmetric positive definite and semi-positive definite linear systems arising from the discretization of scalar partial differential equations (PDEs). We relate the so-called smoothing factor to the actual two-grid convergence rate and also to the convergence rate of the V-cycle multigrid. We derive a two-sided bound that defines an interval containing both the two-grid and V-cycle convergence rate. This interval is narrow and away from 1 when both the smoothing factor and an additional parameter are small enough. Besides the smoothing factor, the convergence mainly depends on the angle between the range of the prolongation and the eigenvectors of the system matrix associated with small eigenvalues. Nice V-cycle convergence is guaranteed if the tangent of this angle has an upper bound proportional to the eigenvalue, whereas nice two-grid convergence requires a bound proportional to the square root of the eigenvalue. We also discuss the well-known rule which relates the order of the prolongation to that of the differential operator associated to the problem. We first define a frequency based order which in most cases amounts to the so-called high frequency order as defined in Hemker (J Comput Appl Math 32:423–429, 1990 ). We give a firmer basis to the related order rule by showing that, together with the requirement of having the smoothing factor away from one, it provides necessary and sufficient conditions for having the two-grid convergence rate away from 1. A stronger condition is further shown to be sufficient for optimal convergence with the V-cycle. The presented results apply to rigorous Fourier analysis for regular discrete PDEs, and also to local Fourier analysis via the discussion of semi-positive systems as may arise from the discretization of PDEs with periodic boundary conditions. Content Type Journal Article Pages 1-27 DOI 10.1007/s00211-011-0362-7 Authors Artem Napov, Service de Métrologie Nucléaire, Université Libre de Bruxelles (C.P. 165/84), 50, Av. F.D. Roosevelt, 1050 Brussels, Belgium Yvan Notay, Service de Métrologie Nucléaire, Université Libre de Bruxelles (C.P. 165/84), 50, Av. F.D. Roosevelt, 1050 Brussels, Belgium Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    Necessary and sufficient conditions for existence and uniqueness of solutions are developed for twofold saddle point problems which arise in mixed formulations of problems in continuum mechanics. This work extends the classical saddle point theory to accommodate nonlinear constitutive relations and the twofold saddle structure. Application to problems in incompressible fluid mechanics employing symmetric tensor finite elements for the stress approximation is presented. Content Type Journal Article Pages 1-31 DOI 10.1007/s00211-011-0372-5 Authors Jason S. Howell, Department of Mathematics, Clarkson University, Potsdam, NY 13676, USA Noel J. Walkington, Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    Recently, the format of TT tensors (Hackbusch and Kühn in J Fourier Anal Appl 15:706–722, 2009 ; Oseledets in SIAM J Sci Comput 2009 , submitted; Oseledets and Tyrtyshnikov in SIAM J Sci Comput 31:5, 2009 ; Oseledets and Tyrtyshnikov in Linear Algebra Appl 2009 , submitted) has turned out to be a promising new format for the approximation of solutions of high dimensional problems. In this paper, we prove some new results for the TT representation of a tensor U Î \mathbb R n 1 × ¼ × n d and for the manifold of tensors of TT-rank r . As a first result, we prove that the TT (or compression) ranks r i of a tensor U are unique and equal to the respective separation ranks of U if the components of the TT decomposition are required to fulfil a certain maximal rank condition. We then show that the set \mathbb T of TT tensors of fixed rank r locally forms an embedded manifold in \mathbb R n 1 × ¼ × n d , therefore preserving the essential theoretical properties of the Tucker format, but often showing an improved scaling behaviour. Extending a similar approach for matrices (Conte and Lubich in M2AN 44:759, 2010 ), we introduce certain gauge conditions to obtain a unique representation of the tangent space T U \mathbb T of \mathbb T and deduce a local parametrization of the TT manifold. The parametrisation of T U \mathbb T is often crucial for an algorithmic treatment of high-dimensional time-dependent PDEs and minimisation problems (Lubich in From quantum to classical molecular dynamics: reduced methods and numerical analysis, 2008 ). We conclude with remarks on those applications and present some numerical examples. Content Type Journal Article Pages 1-31 DOI 10.1007/s00211-011-0419-7 Authors Sebastian Holtz, TU Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany Thorsten Rohwedder, TU Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany Reinhold Schneider, TU Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X