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

Description:    Deckelnick and Dziuk (Math. Comput. 78(266):645–671, 2009 ) proved a stability bound for a continuous-in-time semidiscrete parametric finite element approximation of the elastic flow of closed curves in \mathbb R d , d ³ 2 . We extend these ideas in considering an alternative finite element approximation of the same flow that retains some of the features of the formulations in Barrett et al. (J Comput Phys 222(1): 441–462, 2007 ; SIAM J Sci Comput 31(1):225–253, 2008 ; IMA J Numer Anal 30(1):4–60, 2010 ), in particular an equidistribution mesh property. For this new approximation, we obtain also a stability bound for a continuous-in-time semidiscrete scheme. Apart from the isotropic situation, we also consider the case of an anisotropic elastic energy. In addition to the evolution of closed curves, we also consider the isotropic and anisotropic elastic flow of a single open curve in the plane and in higher codimension that satisfies various boundary conditions. Content Type Journal Article Pages 1-54 DOI 10.1007/s00211-011-0416-x Authors John W. Barrett, Department of Mathematics, Imperial College London, London, SW7 2AZ UK Harald Garcke, Fakultät für Mathematik, Universität Regensburg, 93040 Regensburg, Germany Robert Nürnberg, Department of Mathematics, Imperial College London, London, SW7 2AZ UK Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    We consider convergence analysis for a model reduction algorithm for a class of linear infinite dimensional systems. The algorithm computes an approximate balanced truncation of the system using solution snapshots of specific linear infinite dimensional differential equations. The algorithm is related to the proper orthogonal decomposition, and it was first proposed for systems of ordinary differential equations by Rowley (Int. J. Bifurc. Chaos Appl. Sci. Eng. 15(3):997–1013, 2005 ). For the convergence analysis, we consider the algorithm in terms of the Hankel operator of the system, rather than the product of the system Gramians as originally proposed by Rowley. For exponentially stable systems with bounded finite rank input and output operators, we prove that the balanced realization can be expressed in terms of balancing modes, which are related to the Hankel operator. The balancing modes are required to be smooth, and this can cause computational difficulties for PDE systems. We show how this smoothness requirement can be lessened for parabolic systems, and we also propose a variation of the algorithm that avoids the smoothness requirement for general systems. We prove entrywise convergence of the matrices in the approximate reduced order models in both cases, and present numerical results for two example PDE systems. Content Type Journal Article Pages 1-38 DOI 10.1007/s00211-011-0424-x Authors John R. Singler, Department of Mathematics and Statistics, Missouri University of Science and Technology, Rolla, MO 65409-0020, USA Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    We present and analyze subspace correction methods for the solution of variational inequalities of the second kind and apply these theoretical results to non smooth contact problems in linear elasticity with Tresca and non-local Coulomb friction. We introduce these methods in a reflexive Banach space, prove that they are globally convergent and give error estimates. In the context of finite element discretizations, where our methods turn out to be one- and two-level Schwarz methods, we specify their convergence rate and its dependence on the discretization parameters and conclude that our methods converge optimally. Transferring this results to frictional contact problems, we thus can overcome the mesh dependence of some fixed-point schemes which are commonly employed for contact problems with Coulomb friction. Content Type Journal Article Pages 1-27 DOI 10.1007/s00211-011-0423-y Authors L. Badea, Institute of Mathematics of the Romanian Academy, P.O. Box 1-764, 014700 Bucharest, Romania R. Krause, Institute of Computational Science, University of Lugano, via Giuseppe Buffi 13, 6900 Lugano, Switzerland Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    We discuss the full discretization of an elliptic optimal control problem with pointwise control and state constraints. We provide the first reliable a-posteriori error estimator that contains only computable quantities for this class of problems. Moreover, we show, that the error estimator converges to zero if one has convergence of the discrete solutions to the solution of the original problem. The theory is illustrated by numerical tests. Content Type Journal Article Pages 1-30 DOI 10.1007/s00211-011-0422-z Authors Arnd Rösch, Fakultät für Mathematik, Universität Duisburg-Essen, Forsthausweg 2, 47057 Duisburg, Germany Daniel Wachsmuth, Johann Radon Institute for Computational and Applied Mathematics (RICAM), Austrian Academy of Sciences, Altenbergerstraße 69, 4040 Linz, Austria Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    Invariant pairs have been proposed as a numerically robust means to represent and compute several eigenvalues along with the corresponding (generalized) eigenvectors for matrix eigenvalue problems that are nonlinear in the eigenvalue parameter. In this work, we consider nonlinear eigenvalue problems that depend on an additional parameter and our interest is to track several eigenvalues as this parameter varies. Based on the concept of invariant pairs, a theoretically sound and reliable numerical continuation procedure is developed. Particular attention is paid to the situation when the procedure approaches a singularity, that is, when eigenvalues included in the invariant pair collide with other eigenvalues. For the real generic case, it is proven that such a singularity only occurs when two eigenvalues collide on the real axis. It is shown how this situation can be handled numerically by an appropriate expansion of the invariant pair. The viability of our continuation procedure is illustrated by a numerical example. Content Type Journal Article Pages 1-28 DOI 10.1007/s00211-011-0392-1 Authors Wolf-Jürgen Beyn, Fakultät für Mathematik, Universität Bielefeld, Postfach 100131, 33501 Bielefeld, Germany Cedric Effenberger, Seminar for Applied Mathematics, D-MATH, ETH Zurich, Raemistrasse 101, 8092 Zurich, Switzerland Daniel Kressner, MATHICSE, EPF Lausanne, Station 8, 1015 Lausanne, Switzerland Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    We analyze parabolic PDEs with certain type of weakly singular or degenerate time-dependent coefficients and prove existence and uniqueness of weak solutions in an appropriate sense. A localization of the PDEs to a bounded spatial domain is justified. For the numerical solution a space–time wavelet discretization is employed. An optimality result for the iterative solution of the arising systems can be obtained. Finally, applications to fractional Brownian motion models in option pricing are presented. Content Type Journal Article Pages 1-29 DOI 10.1007/s00211-011-0432-x Authors O. Reichmann, Rämistrasse 102, 8092 Zurich, Switzerland Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    We study an implicit and discontinuous scheme for a non-local Hamilton–Jacobi equation modelling dislocation dynamics. For the evolution problem, we prove an a posteriori estimate of Crandall–Lions type for the error between continuous and discrete solutions. We deduce an a posteriori error estimate for the effective Hamiltonian associated to a stationary cell problem. In dimension one and under suitable assumptions, we also give improved a posteriori estimates. Numerical simulations are provided. Content Type Journal Article Pages 1-55 DOI 10.1007/s00211-011-0430-z Authors S. Cacace, Dipartimento di Matematica, Sapienza Università di Roma, Piazzale Aldo Moro 5, 00185 Rome, Italy A. Chambolle, CMAP, Ecole Polytechnique CNRS, Route de Saclay, 91128 Palaiseau Cedex, France R. Monneau, CERMICS, Ecole Nationale des Ponts et Chaussées, 6 et 8 avenue Blaise Pascal, Cité Descartes, Champs-sur-Marne, 77455 Marne-la-Vallée Cedex 2, France Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    We consider semi-discrete first-order finite difference schemes for a nonlinear degenerate convection–diffusion equations in one space dimension, and prove an L 1 error estimate. Precisely, we show that the L 1 loc difference between the approximate solution and the unique entropy solution converges at a rate O ( D x 1/11 ) , where D x is the spatial mesh size. If the diffusion is linear, we get the convergence rate O ( D x 1/2 ) , the point being that the O is independent of the size of the diffusion. Content Type Journal Article Pages 1-29 DOI 10.1007/s00211-011-0433-9 Authors K. H. Karlsen, Centre of Mathematics for Applications (CMA), University of Oslo, P.O. Box 1053, Blindern, Oslo, 0316 Norway U. Koley, Centre of Mathematics for Applications (CMA), University of Oslo, P.O. Box 1053, Blindern, Oslo, 0316 Norway N. H. Risebro, Centre of Mathematics for Applications (CMA), University of Oslo, P.O. Box 1053, Blindern, Oslo, 0316 Norway Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    We derive low-complexity matrix-free finite element algorithms for simplicial Bernstein polynomials on simplices. Our techniques, based on a sparse representation of differentiation and special block structure in the matrices evaluating B-form polynomials at warped Gauss points, apply to variable coefficient problems as well as constant coefficient ones, thus extending our results in Kirby (Numer Math, 2011 , in press). Content Type Journal Article Pages 1-19 DOI 10.1007/s00211-011-0431-y Authors Robert C. Kirby, Department of Mathematics and Statistics, Texas Tech University, PO Box 1042, Lubbock, TX 79409-1042, USA Kieu Tri Thinh, Department of Mathematics and Statistics, Texas Tech University, PO Box 1042, Lubbock, TX 79409-1042, USA Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    This paper is concerned with the relative perturbation theory and its entrywise relatively accurate numerical solutions of an M -matrix Algebraic Riccati Equations (MARE) XDX - AX - XB + C = 0 by which we mean the following conformally partitioned matrix ( ll B    - D - C    A ) is a nonsingular or an irreducible singular M -matrix. It is known that such an MARE has a unique minimal nonnegative solution F . It is proved that small relative perturbations to the entries of A , B , C , and D introduce small relative changes to the entries of the nonnegative solution F . Thus the smaller entries F do not suffer bigger relative errors than its larger entries, unlike the existing perturbation theory for (general) Algebraic Riccati Equations. We then discuss some minor but crucial implementation changes to three existing numerical methods so that they can be used to compute F as accurately as the input data deserve. Current study is based on a previous paper of the authors’ on M -matrix Sylvester equation for which D  = 0. Content Type Journal Article Pages 1-30 DOI 10.1007/s00211-011-0421-0 Authors Jungong Xue, School of Mathematical Science, Fudan University, Shanghai, 200433 People’s Republic of China Shufang Xu, School of Mathematical Sciences, Peking University, Beijing, 100871 People’s Republic of China Ren-Cang Li, Department of Mathematics, University of Texas at Arlington, Arlington, P.O. Box 19408, TX 76019, USA Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    This paper is concerned with a relative perturbation theory and its entrywise relatively accurate numerical solutions of an M -matrix Sylvester equation AX  +  XB  =  C by which we mean both A and B have positive diagonal entries and nonpositive off-diagonal entries and P = I m Ä A + B T Ä I n is a nonsingular M -matrix, and C is entrywise nonnegative. It is proved that small relative perturbations to the entries of A , B , and C introduce small relative errors to the entries of the solution X . Thus the smaller entries of X do not suffer bigger relative errors than its larger entries, unlikely the existing perturbation theory for (general) Sylvester equations. We then discuss some minor but crucial implementation changes to three existing numerical methods so that they can be used to compute X as accurately as the input data deserve. Content Type Journal Article Pages 1-32 DOI 10.1007/s00211-011-0420-1 Authors Jungong Xue, School of Mathematical Science, Fudan University, Shanghai, 200433 People’s Republic of China Shufang Xu, School of Mathematical Sciences, Peking University, Beijing, 100871 People’s Republic of China Ren-Cang Li, Department of Mathematics, University of Texas at Arlington, P.O. Box 19408, Arlington, TX 76019, USA Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    In this paper we propose and analyse adaptive finite element methods for computing the band structure of 2D periodic photonic crystals. The problem can be reduced to the computation of the discrete spectra of each member of a family of periodic Hermitian eigenvalue problems on a unit cell, parametrised by a two-dimensional parameter - the quasimomentum. These eigenvalue problems involve non-coercive elliptic operators with generally discontinuous coefficients and are solved by adaptive finite elements. We propose an error estimator of residual type and show it is reliable and efficient for each eigenvalue problem in the family. In particular we prove that if the error estimator converges to zero then the distance of the computed eigenfunction from the true eigenspace also converges to zero and the computed eigenvalue converges to a true eigenvalue with double the rate. We also prove that if the distance of a computed sequence of approximate eigenfunctions from the true eigenspace approaches zero, then so must the error estimator. The results hold for eigenvalues of any multiplicity. We illustrate the benefits of the resulting adaptive method in practice, both for fully periodic structures and also for the computation of eigenvalues in the band gap of structures with defect, using the supercell method. Content Type Journal Article Pages 1-34 DOI 10.1007/s00211-011-0425-9 Authors S. Giani, School of Mathematical Sciences, University of Nottingham, University Park, Nottingham, NG7 2RD UK I. G. Graham, Department of Mathematical Sciences, University of Bath, Bath, BA2 7AY UK Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    In this paper, we discuss multiscale radial basis function collocation methods for solving certain elliptic partial differential equations on the unit sphere. The approximate solution is constructed in a multi-level fashion, each level using compactly supported radial basis functions of smaller scale on an increasingly fine mesh. Two variants of the collocation method are considered (sometimes called symmetric and unsymmetric, although here both are symmetric). A convergence theory is given, which builds on recent theoretical advances for multiscale approximation using compactly supported radial basis functions. Content Type Journal Article Pages 1-27 DOI 10.1007/s00211-011-0428-6 Authors Q. T. Le Gia, School of Mathematics and Statistics, University of New South Wales, Sydney, NSW 2052, Australia I. H. Sloan, School of Mathematics and Statistics, University of New South Wales, Sydney, NSW 2052, Australia H. Wendland, Mathematical Institute, University of Oxford, 24-29 St. Giles’, Oxford, OX1 3LB UK Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    We study a class of numerical methods for a system of second-order SDE driven by a linear fast force generating high frequency oscillatory solutions. The proposed schemes permit the use of large step sizes, have uniform global error bounds in the position (i.e. independent of the large frequencies present in the SDE) and offer various additional properties. This new family of numerical integrators for SDE can be viewed as a stochastic generalisation of the trigonometric integrators for highly oscillatory deterministic problems. Content Type Journal Article Pages 1-29 DOI 10.1007/s00211-011-0426-8 Authors David Cohen, Mathematisches Institut, Universität Basel, 4051 Basel, Switzerland Magdalena Sigg, Mathematisches Institut, Universität Basel, 4051 Basel, Switzerland Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    A new iterative algorithm for solving initial data inverse problems from partial observations has been recently proposed in Ramdani et al. (Automatica 46(10), 1616–1625, 2010 ). Based on the concept of observers (also called Luenberger observers), this algorithm covers a large class of abstract evolution PDE’s. In this paper, we are concerned with the convergence analysis of this algorithm. More precisely, we provide a complete numerical analysis for semi-discrete (in space) and fully discrete approximations derived using finite elements in space and an implicit Euler method in time. The analysis is carried out for abstract Schrödinger and wave conservative systems with bounded observation (locally distributed). Content Type Journal Article Pages 1-37 DOI 10.1007/s00211-011-0408-x Authors Ghislain Haine, Université Henri Poincaré (Institut Élie Cartan), B.P. 70239, 54506 Vandoeuvre, France Karim Ramdani, INRIA Nancy Grand-Est (CORIDA), 615 rue du Jardin Botanique, 54600 Villers, France Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    In this paper, we propose some new residual-based a posteriori error estimators for the mortar finite element discretization of the second order elliptic equations with discontinuous coefficients. Reliability and efficiency of the estimators are given. Our analysis does not require any saturation assumptions and the mesh restrictions on the interface which are often needed in the literature. Numerical experiments are presented to confirm our theoretical analysis. Content Type Journal Article Pages 1-29 DOI 10.1007/s00211-011-0413-0 Authors Feng Wang, LSEC, Institute of Computational Mathematics and Scientific/Engineering Computing, Academy of Mathematics and System Sciences, Chinese Academy of Sciences, 100190 Beijing, China Xuejun Xu, LSEC, Institute of Computational Mathematics and Scientific/Engineering Computing, Academy of Mathematics and System Sciences, Chinese Academy of Sciences, 100190 Beijing, China Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    This paper presents adaptive algorithms for eigenvalue problems associated with non-selfadjoint partial differential operators. The basis for the developed algorithms is a homotopy method which departs from a well-understood selfadjoint problem. Apart from the adaptive grid refinement, the progress of the homotopy as well as the solution of the iterative method are adapted to balance the contributions of the different error sources. The first algorithm balances the homotopy, discretization and approximation errors with respect to a fixed stepsize τ in the homotopy. The second algorithm combines the adaptive stepsize control for the homotopy with an adaptation in space that ensures an error below a fixed tolerance ε . The outcome of the analysis leads to the third algorithm which allows the complete adaptivity in space, homotopy stepsize as well as the iterative algebraic eigenvalue solver. All three algorithms are compared in numerical examples. Content Type Journal Article Pages 1-27 DOI 10.1007/s00211-011-0388-x Authors C. Carstensen, Institut für Mathematik, Humboldt-Universität zu Berlin, Unter den Linden 6, 10099 Berlin, Germany J. Gedicke, Institut für Mathematik, Humboldt-Universität zu Berlin, Unter den Linden 6, 10099 Berlin, Germany V. Mehrmann, Institut für Mathematik, MA 4-5, TU Berlin, Str. des 17. Juni 136, 10623 Berlin, Germany A. Miedlar, Institut für Mathematik, MA 4-5, TU Berlin, Str. des 17. Juni 136, 10623 Berlin, Germany Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    Spherical t -designs are point sets X M ={ x 1 , ¼ , x M } Ì \mathbb S 2 which provide quadrature rules with equal weights for the sphere which are exact for polynomials up to degree t . In this paper we consider the problem of finding numerical spherical t -designs on the sphere \mathbb S 2 for high polynomial degree t Î \mathbb N . That is, we compute numerically local minimizers of a certain quadrature error A t ( X M ). The quadrature error A t was also used for a variational characterization of spherical t -designs by Sloan and Womersley (J Approx Theory 159:308–318, 2009 ). For the minimization problem we regard several nonlinear optimization methods on manifolds, like Newton and conjugate gradient methods. We show that by means of the nonequispaced fast spherical Fourier transforms we perform gradient and Hessian evaluations in O ( t 2 log t + M log 2 (1/ e )) arithmetic operations, where $${\varepsilon 〉0 }$$ is a prescribed accuracy. Using these methods we present numerical spherical t -designs for t ≤  1,000, even in the case M » \frac12 t 2 . Content Type Journal Article Pages 1-26 DOI 10.1007/s00211-011-0399-7 Authors Manuel Gräf, Faculty of Mathematics, Chemnitz University of Technology, 09107 Chemnitz, Germany Daniel Potts, Faculty of Mathematics, Chemnitz University of Technology, 09107 Chemnitz, Germany Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    The aim of this paper is to devise an adaptive timestep control in the contact-stabilized Newmark method ( ContacX ) for dynamical contact problems between two viscoelastic bodies in the framework of Signorini’s condition. In order to construct a comparative scheme of higher order accuracy, we extend extrapolation techniques. This approach demands a subtle theoretical investigation of an asymptotic error expansion of the contact-stabilized Newmark scheme. On the basis of theoretical insight and numerical observations, we suggest an error estimator and a timestep selection which also cover the presence of contact. Finally, we give a numerical example. Content Type Journal Article Pages 1-33 DOI 10.1007/s00211-011-0374-3 Authors Corinna Klapproth, Zuse Institute Berlin (ZIB), Takustrasse 7, 14195 Berlin-Dahlem, Germany Anton Schiela, Zuse Institute Berlin (ZIB), Takustrasse 7, 14195 Berlin-Dahlem, Germany Peter Deuflhard, Zuse Institute Berlin (ZIB), Takustrasse 7, 14195 Berlin-Dahlem, Germany Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    A conforming finite element method on polygonal meshes is reviewed which handles hanging nodes naturally. Trial functions are defined to fulfil the homogeneous PDE locally and they are treated by means of local boundary integral equations. Using a quasi-interpolation operator of Clément type a residual-based error estimate is obtained. This a posteriori estimator can be used to rate the accuracy of the approximation over polygonal elements or it can be applied to an adaptive BEM-based FEM. The numerical experiments confirm our results and show optimal convergence for the adaptive strategy on general meshes. Content Type Journal Article Pages 1-24 DOI 10.1007/s00211-011-0371-6 Authors Steffen Weißer, Department of Mathematics, Saarland University, 66041 Saarbrücken, Germany Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    We unify the formulation and analysis of Galerkin and Runge–Kutta methods for the time discretization of parabolic equations. This, together with the concept of reconstruction of the approximate solutions, allows us to establish a posteriori superconvergence estimates for the error at the nodes for all methods. Content Type Journal Article Pages 1-28 DOI 10.1007/s00211-011-0363-6 Authors Georgios Akrivis, Department of Computer Science, University of Ioannina, 451 10 Ioannina, Greece Charalambos Makridakis, Department of Applied Mathematics, University of Crete, 71409 Heraklion-Crete, Greece Ricardo H. Nochetto, Department of Mathematics and Institute for Physical Science and Technology, University of Maryland, College Park, MD 20742, USA Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    In this paper we consider the issue of sliding motion in Filippov systems on the intersection of two or more surfaces. To this end, we propose an extension of the Filippov sliding vector field on manifolds of co-dimension p , with p  ≥ 2. Our model passes through the use of a multivalued sign function reformulation. To justify our proposal, we will restrict to cases where the sliding manifold is attractive. For the case of co-dimension p  = 2, we will distinguish between two types of attractive sliding manifold: “node-like” and “spiral-like”. The case of node-like attractive manifold will be further extended to the case of p  ≥ 3. Finally, we compare our model to other existing methodologies on some examples. Content Type Journal Article Pages 1-33 DOI 10.1007/s00211-011-0365-4 Authors Luca Dieci, School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332, USA Luciano Lopez, Dip. di Matematica, Universitá di Bari, Via Orabona 4, 70125 Bari, Italy Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    The extended Krylov subspace method has recently arisen as a competitive method for solving large-scale Lyapunov equations. Using the theoretical framework of orthogonal rational functions, in this paper we provide a general a priori error estimate when the known term has rank-one. Special cases, such as symmetric coefficient matrix, are also treated. Numerical experiments confirm the proved theoretical assertions. Content Type Journal Article Pages 1-20 DOI 10.1007/s00211-011-0366-3 Authors L. Knizhnerman, Central Geophysical Expedition, house 38, building 3, Narodnogo opolcheniya St., 123298 Moscow, Russia V. Simoncini, Dipartimento di Matematica, CIRSA, Università di Bologna, Piazza di Porta S. Donato 5, 40127 Bologna, Ravenna Italy Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    Domain decomposition methods for solving the coupled Stokes–Darcy system with the Beavers–Joseph interface condition are proposed and analyzed. Robin boundary conditions are used to decouple the Stokes and Darcy parts of the system. Then, parallel and serial domain decomposition methods are constructed based on the two decoupled sub-problems. Convergence of the two methods is demonstrated and the results of computational experiments are presented to illustrate the convergence. Content Type Journal Article Pages 1-29 DOI 10.1007/s00211-011-0361-8 Authors Yanzhao Cao, Department of Mathematics and Statistics, Auburn University, Auburn, AL 36830, USA Max Gunzburger, Department of Scientific Computing, Florida State University, Tallahassee, FL 32306-4120, USA Xiaoming He, Department of Scientific Computing, Florida State University, Tallahassee, FL 32306-4120, USA Xiaoming Wang, Department of Mathematics, Florida State University, Tallahassee, FL 32306, USA Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    This article is concerned with the analysis of semi-discrete-in-space and fully-discrete approximations of the null controllability (and controllability to the trajectories) for parabolic equations. We propose an abstract setting for space discretizations that potentially encompasses various numerical methods and we study how the controllability problems depend on the discretization parameters. For time discretization we use θ -schemes with q Î [\frac12,1] . For the proofs of controllability we rely on the strategy introduced by Lebeau and Robbiano (Comm Partial Differ Equ 20:335–356, 1995 ) for the null-controllability of the heat equation, which is based on a spectral inequality. We obtain relaxed uniform observability estimates in both the semi-discrete and fully-discrete frameworks, and associated uniform controllability properties. For the practical computation of the control functions we follow J.-L. Lions’ Hilbert Uniqueness Method strategy, exploiting the relaxed uniform observability estimate. Algorithms for the computation of the controls are proposed and analysed in the semi-discrete and fully-discrete cases. Additionally, we prove an error bound between the fully discrete and the semi-discrete control functions. This bound is however not uniform with respect to the space discretization. The theoretical results are illustrated through numerical experimentations. Content Type Journal Article Pages 1-61 DOI 10.1007/s00211-011-0368-1 Authors Franck Boyer, Aix-Marseille Université, Laboratoire d’Analyse Topologie Probabilités (LATP), CNRS UMR 6632, 39 rue F. Joliot-Curie, 13453 Marseille cedex 13, France Florence Hubert, Aix-Marseille Université, Laboratoire d’Analyse Topologie Probabilités (LATP), CNRS UMR 6632, 39 rue F. Joliot-Curie, 13453 Marseille cedex 13, France Jérôme Le Rousseau, Laboratoire Mathématiques et Applications, Physique Mathématique d’Orléans, Université d’Orléans, CNRS UMR 6628, Fédération Denis-Poisson, FR CNRS 2964, B.P. 6759, 45067 Orléans cedex 2, France Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    In this paper we propose a stabilized conforming finite volume element method for the Stokes equations. On stating the convergence of the method, optimal a priori error estimates in different norms are obtained by establishing the adequate connection between the finite volume and stabilized finite element formulations. A superconvergence result is also derived by using a postprocessing projection method. In particular, the stabilization of the continuous lowest equal order pair finite volume element discretization is achieved by enriching the velocity space with local functions that do not necessarily vanish on the element boundaries. Finally, some numerical experiments that confirm the predicted behavior of the method are provided. Content Type Journal Article Pages 1-28 DOI 10.1007/s00211-011-0373-4 Authors Alfio Quarteroni, CMCS-MATHICSE-SB, Ecole Polytechnique Fédérale de Lausanne EPFL, Station 8, 1015 Lausanne, Switzerland Ricardo Ruiz-Baier, CMCS-MATHICSE-SB, Ecole Polytechnique Fédérale de Lausanne EPFL, Station 8, 1015 Lausanne, Switzerland Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    In this paper, we propose a palindromic quadratization approach, transforming a palindromic matrix polynomial of even degree to a palindromic quadratic pencil. Based on the ( S + S - 1 ) -transform and Patel’s algorithm, the structure-preserving algorithm can then be applied to solve the corresponding palindromic quadratic eigenvalue problem. Numerical experiments show that the relative residuals for eigenpairs of palindromic polynomial eigenvalue problems computed by palindromic quadratized eigenvalue problems are better than those via palindromic linearized eigenvalue problems or polyeig in MATLAB. Content Type Journal Article Pages 1-23 DOI 10.1007/s00211-011-0370-7 Authors Tsung-Ming Huang, Department of Mathematics, National Taiwan Normal University, Taipei, 116 Taiwan Wen-Wei Lin, Department of Mathematics, National Taiwan University, Taipei, 106 Taiwan Wei-Shuo Su, Department of Applied Mathematics, National Chiao Tung University, Hsinchu, 300 Taiwan Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    Adaptive approximation (or interpolation) takes into account local variations in the behavior of the given function, adjusts the approximant depending on it, and hence yields the smaller error of approximation. The question of constructing optimal approximating spline for each function proved to be very hard. In fact, no polynomial time algorithm of adaptive spline approximation can be designed and no exact formula for the optimal error of approximation can be given. Therefore, the next natural question would be to study the asymptotic behavior of the error and construct asymptotically optimal sequences of partitions. In this paper we provide sharp asymptotic estimates for the error of interpolation by splines on block partitions in \mathbb R d . We consider various projection operators to define the interpolant and provide the analysis of the exact constant in the asymptotics as well as its explicit form in certain cases. Content Type Journal Article Pages 1-27 DOI 10.1007/s00211-010-0355-y Authors Yuliya Babenko, Department of Mathematics and Statistics, Kennesaw State University, 1000 Chastain Road, Box 1601, Kennesaw, GA 30144-5591, USA Tatyana Leskevich, Department of Mathematical Analysis and Theory of Functions, Dnepropetrovsk National University, pr. Gagarina, 72, Dnepropetrovsk, 49050 Ukraine Jean-Marie Mirebeau, Laboratoire Jacques-Louis Lions, UPMC Univ Paris 06, UMR 7598, 75005 Paris, France Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    We present a mimetic approximation of the Reissner–Mindlin plate bending problem which uses deflections and rotations as discrete variables. The method applies to very general polygonal meshes, even with non matching or non convex elements. We prove linear convergence for the method uniformly in the plate thickness. Content Type Journal Article Pages 1-38 DOI 10.1007/s00211-010-0358-8 Authors L. Beirão da Veiga, Dipartimento di Matematica “F. Enriques”, Università degli Studi di Milano, Via Saldini 50, 20133 Milan, Italy D. Mora, Departamento de Matemática, Facultad de Ciencias, Universidad del Bío Bío, Casilla 5-C, Concepción, Chile Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    For a nonlinear functional f , and a function u from the span of a set of tensor product interpolets, it is shown how to compute the interpolant of f ( u ) from the span of this set of tensor product interpolets in linear complexity, assuming that the index set has a certain multiple tree structure. Applications are found in the field of (adaptive) tensor product solution methods for semilinear operator equations by collocation methods, or after transformations between the interpolet and (bi-) orthogonal wavelet bases, by Galerkin methods. Content Type Journal Article Pages 1-22 DOI 10.1007/s00211-011-0397-9 Authors Christoph Schwab, Seminar for Applied Mathematics, ETH Zürich, ETHZ HG G57.1, 8092 Zürich, Switzerland Rob Stevenson, Korteweg-de Vries (KdV) Institute for Mathematics, University of Amsterdam, P.O. Box 94248, 1090 GE Amsterdam, The Netherlands Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    We investigate the convergence rates for Tikhonov regularization of the problem of simultaneously estimating the coefficients q and a in the Neumann problem for the elliptic equation - div ( q Ñ u ) + au = f    in    W , q ¶ u / ¶ n = g on the boundary ¶ W , W Ì \mathbb R d , d ³ 1 , when u is imprecisely given by $${{{z^\delta} \in {H^1}(\Omega), \|u-z^\delta\|_{H^1(\Omega)}\le\delta, \delta 〉 0}}$$. We regularize this problem by minimizing the strictly convex functional of ( q , a ) lll ó õ W   ( q | Ñ ( U ( q , a ) - z d ) | 2 + a ( U ( q , a ) - z d ) 2 ) dx    + r ( || q - q * || 2 L 2 ( W ) + || a - a * || 2 L 2 ( W ) ) over the admissible set K , where ρ 〉 0 is the regularization parameter and ( q *, a *) is an a priori estimate of the true pair ( q , a ) which is identified, and consider the unique solution of these minimization problem as the regularized one to that of the inverse problem. We obtain the convergence rate O ( Ö   d   ) , as δ → 0 and ρ ~ δ, for the regularized solutions under the simple and weak source condition there    is    a    function    w * Î V *    such    that    U ¢ ( q f , a f ) * w * = ( q f - q * , a f - a * ) with ( q f , a f ) being the ( q *, a *)-minimum norm solution of the coefficient identification problem, U ′(·, ·) the Fréchet derivative of U (·, ·), V the Sobolev space on which the boundary value problem is considered. Our source condition is without the smallness requirement on the source function which is popularized in the theory of regularization of nonlinear ill-posed problems. Furthermore, some concrete cases of our source condition are proved to be simply the requirement that the sought coefficients belong to certain smooth function spaces. Content Type Journal Article Pages 1-33 DOI 10.1007/s00211-011-0406-z Authors Dinh Nho Hào, Hanoi Institute of Mathematics, 18 Hoang Quoc Viet Road, Hanoi, 10307 Vietnam Tran Nhan Tam Quyen, Da Nang University of Education, 459 Ton Duc Thang, Q. Lien Chieu, Da Nang, Vietnam Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    We show that the famous maximum angle condition in the finite element analysis is not necessary to achieve the optimal convergence rate when simplicial finite elements are used to solve elliptic problems. This condition is only sufficient. In fact, finite element approximations may converge even though some dihedral angles of simplicial elements tend to π . Content Type Journal Article Pages 1-10 DOI 10.1007/s00211-011-0403-2 Authors Antti Hannukainen, Department of Mathematics and Systems Analysis, Aalto University, P.O. Box 11100, 00076 Aalto, Finland Sergey Korotov, BCAM, Basque Center for Applied Mathematics, Bizkaia Technology Park, Building 500, 48160 Derio, Basque Country, Spain Michal Křížek, 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:    In this article we estimate the number of modes, volumes and nodes, sufficient to describe well the solution of the three dimensional primitive equations; the physical meaning of these estimates is also discussed. We also study the exponential decay of the spatial power spectrum for the three dimensional primitive equations. Content Type Journal Article Pages 1-28 DOI 10.1007/s00211-011-0405-0 Authors Madalina Petcu, The Institute of Mathematics of the Romanian Academy, P.O. Box 1-764, 014700 Bucharest, Romania Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    In recent papers the tensorisation of vectors has been discussed. In principle, this is the isomorphic representation of an \mathbb R n vector as a tensor. Black-box tensor approximation methods can be used to reduce the data size of the tensor representation. In particular, if the vector corresponds to a grid function, the resulting data size can become much smaller than n , e.g., O (log n ) 〈〈 n . In this article we discuss the convolution of two vectors which are given via a sparse tensor representation. We want to obtain the result again in the tensor representation. Furthermore, the cost of the convolution algorithm should be related to the operands’ data sizes. While \mathbb R n vectors can be considered as grid values of function, we also apply the corresponding procedure to univariate functions. Content Type Journal Article Pages 1-24 DOI 10.1007/s00211-011-0393-0 Authors Wolfgang Hackbusch, Max-Planck-Institut, Mathematik in den Naturwissenschaften, Inselstr. 22, 04103 Leipzig, Germany Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    The Shanks transformation is a powerful nonlinear extrapolation method that is used to accelerate the convergence of slowly converging, and even diverging, sequences { A n }. It generates a two-dimensional array of approximations A ( j ) n to the limit or anti-limit of { A n } defined as solutions of the linear systems A l = A ( j ) n + n å k =1   - b   k   ( D A l + k - 1 ),   j £ l £ j + n , where - b   k   are additional unknowns. In this work, we study the convergence and stability properties of A ( j ) n , as j → ∞ with n fixed, derived from general linear sequences { A n }, where A n ~ A + m å k =1   z k n ¥ å i =0   b ki n g k - i as n → ∞, where ζ k  ≠ 1 are distinct and | ζ 1 | = ... = | ζ m | =  θ , and γ k  ≠ 0, 1, 2, . . .. Here A is the limit or the anti-limit of { A n }. Such sequences arise, for example, as partial sums of Fourier series of functions that have finite jump discontinuities and/or algebraic branch singularities. We show that definitive results are obtained with those values of n for which the integer programming problems ll              max s 1 , ¼ , s m   m å k =1   [(  g k ) s k - s k ( s k - 1)], subject   to    s 1 ³ 0, ¼ , s m ³ 0    and     m å k =1   s k = n , have unique (integer) solutions for s 1 , . . . , s m . A special case of our convergence result concerns the situation in which  g 1 = ¼ =  g m = a and n = m ν with ν  = 1, 2, . . . , for which the integer programming problems above have unique solutions, and it reads A ( j ) n - A = O ( q j   j a - 2 n ) as j → ∞. When compared with A j − A  =  O ( θ j j α ) as j → ∞, this result shows that the Shanks transformation is a true convergence acceleration method for the sequences considered. In addition, we show that it is stable for the case being studied, and we also quantify its stability properties. The results of this work are the first ones pertaining to the Shanks transformation on general linear sequences with m  〉 1. Content Type Journal Article Pages 1-40 DOI 10.1007/s00211-011-0398-8 Authors Avram Sidi, Computer Science Department, Technion-Israel Institute of Technology, Haifa, 32000 Israel Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    A semilinear reaction–diffusion two-point boundary value problem, whose second-order derivative is multiplied by a small positive parameter e 2 , is considered. It can have multiple solutions. The numerical computation of solutions having interior transition layers is analysed. It is demonstrated that the accurate computation of such solutions is exceptionally difficult. To address this difficulty, we propose an artificial-diffusion stabilization. For both standard and stabilised finite difference methods on suitable Shishkin meshes, we prove existence and investigate the accuracy of computed solutions by constructing discrete sub- and super-solutions. Convergence results are deduced that depend on the relative sizes of e and N , where N is the number of mesh intervals. Numerical experiments are given in support of these theoretical results. Practical issues in using Newton’s method to compute a discrete solution are discussed. Content Type Journal Article Pages 1-24 DOI 10.1007/s00211-011-0395-y Authors Natalia Kopteva, Department of Mathematics and Statistics, University of Limerick, Limerick, Ireland Martin Stynes, Department of Mathematics, National University of Ireland, Cork, Ireland Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    We design and analyze optimal additive and multiplicative multilevel methods for solving H 1 problems on graded grids obtained by bisection. We deal with economical local smoothers: after a global smoothing in the finest mesh, local smoothing for each added node during the refinement needs to be performed only for three vertices - the new vertex and its two parent vertices. We show that our methods lead to optimal complexity for any dimensions and polynomial degree. The theory hinges on a new decomposition of bisection grids in any dimension, which is of independent interest and yields a corresponding decomposition of spaces. We use the latter to bridge the gap between graded and quasi-uniform grids, for which the multilevel theory is well-established. Content Type Journal Article Pages 1-34 DOI 10.1007/s00211-011-0401-4 Authors Long Chen, Department of Mathematics, University of California at Irvine, Irvine, CA 92697, USA Ricardo H. Nochetto, Department of Mathematics, University of Maryland, College Park, MD 20742, USA Jinchao Xu, The School of Mathematical Science, Peking University, Beijing, China Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    We present an overlapping domain decomposition technique for solving the hypersingular integral equation on the sphere with spherical splines. We prove that the condition number of the additive Schwarz operator is bounded by O ( H / δ ), where H is the size of the coarse mesh and δ is the overlap size, which is chosen to be proportional to the size of the fine mesh. In the case that the degree of the splines is even, a better bound O (1 + log 2 ( H / δ )) is proved. The method is illustrated by numerical experiments on different point sets including those taken from magsat satellite data. Content Type Journal Article Pages 1-35 DOI 10.1007/s00211-011-0404-1 Authors Duong Pham, School of Mathematics and Statistics, The University of New South Wales, Sydney, 2052 Australia Thanh Tran, School of Mathematics and Statistics, The University of New South Wales, Sydney, 2052 Australia Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    In the present work we determine all Chebyshevian spline spaces good for geometric design. By Chebyshevian spline space we mean a space of splines with sections in different Extended Chebyshev spaces and with connection matrices at the knots. We say that such a spline space is good for design when it possesses blossoms. To justify the terminology, let us recall that, in this general framework, existence of blossoms (defined on a restricted set of tuples) makes it possible to develop all the classical geometric design algorithms for splines. Furthermore, existence of blossoms is equivalent to existence of a B-spline bases both in the spline space itself and in all other spline spaces derived from it by insertion of knots. We show that Chebyshevian spline spaces good for design can be described by linear piecewise differential operators associated with systems of piecewise weight functions, with respect to which the connection matrices are identity matrices. Many interesting consequences can be drawn from the latter characterisation: as an example, all Chebsyhevian spline spaces good for design can be built by means of integral recurrence relations. Content Type Journal Article Pages 1-40 DOI 10.1007/s00211-011-0390-3 Authors Marie-Laurence Mazure, Laboratoire Jean Kuntzmann, Université Joseph Fourier, BP53, 38041 Grenoble Cedex 9, France Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    A refined a posteriori error analysis for symmetric eigenvalue problems and the convergence of the first-order adaptive finite element method (AFEM) is presented. The H 1 stability of the L 2 projection provides reliability and efficiency of the edge-contribution of standard residual-based error estimators for P 1 finite element methods. In fact, the volume contributions and even oscillations can be omitted for Courant finite element methods. This allows for a refined averaging scheme and so improves (Mao et al. in Adv Comput Math 25(1–3):135–160, 2006 ). The proposed AFEM monitors the edge-contributions in a bulk criterion and so enables a contraction property up to higher-order terms and global convergence. Numerical experiments exploit the remaining L 2 error contributions and confirm our theoretical findings. The averaging schemes show a high accuracy and the AFEM leads to optimal empirical convergence rates. Content Type Journal Article Pages 1-27 DOI 10.1007/s00211-011-0367-2 Authors Carsten Carstensen, Institut für Mathematik, Humboldt-Universität zu Berlin, Unter den Linden 6, 10099 Berlin, Germany Joscha Gedicke, Institut für Mathematik, Humboldt-Universität zu Berlin, Unter den Linden 6, 10099 Berlin, Germany Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    The force-based quasicontinuum (QCF) approximation is a non-conservative atomistic/continuum hybrid model for the simulation of defects in crystals. We present an a priori error analysis of the QCF method, applied to a one-dimensional periodic chain, that is valid for an arbitrary interaction range, large deformations, and takes coarse-graining into account. Our main tool in this analysis is a new concept of atomistic stress. Moreover, we formulate a new atomistic/continuum coupling mechanism based on coupling stresses instead of forces and extend the a priori analysis to this new method. We show that the new method has several theoretical advantages over the original QCF method. Content Type Journal Article Pages 1-39 DOI 10.1007/s00211-011-0380-5 Authors Charalambos Makridakis, Department of Applied Mathematics, University of Crete, 714 09 Heraklion, Crete, Greece Christoph Ortner, Mathematical Institute, University of Oxford, Oxford, OX1 3LB UK Endre Süli, Mathematical Institute, University of Oxford, Oxford, OX1 3LB UK Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    We consider an interior point method in function space for PDE constrained optimal control problems with state constraints. Our emphasis is on the construction and analysis of an algorithm that integrates a Newton path-following method with adaptive grid refinement. This is done in the framework of inexact Newton methods in function space, where the discretization error of each Newton step is controlled by adaptive grid refinement in the innermost loop. This allows to perform most of the required Newton steps on coarse grids, such that the overall computational time is dominated by the last few steps. For this purpose we propose an a-posteriori error estimator for a problem suited norm. Content Type Journal Article Pages 1-35 DOI 10.1007/s00211-011-0381-4 Authors Anton Schiela, Konrad-Zuse-Zentrum für Informationstechnik Berlin, Takustraße 7, 14195 Berlin, Germany Andreas Günther, Konrad-Zuse-Zentrum für Informationstechnik Berlin, Takustraße 7, 14195 Berlin, Germany Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    We present a structured perturbation theory for the LDU factorization of (row) diagonally dominant matrices and we use this theory to prove that a recent algorithm of Ye (Math Comp 77(264):2195–2230, 2008 ) computes the L , D and U factors of these matrices with relative errors less than 14 n 3 u , where u is the unit roundoff and n  × n is the size of the matrix. The relative errors for D are componentwise and for L and U are normwise with respect the “max norm” || A || M = max ij   | a ij | . These error bounds guarantee that for any diagonally dominant matrix A we can compute accurately its singular value decomposition and the solution of the linear system Ax =  b for most vectors b , independently of the magnitude of the traditional condition number of A and in O ( n 3 ) flops. Content Type Journal Article Pages 1-35 DOI 10.1007/s00211-011-0382-3 Authors Froilán M. Dopico, Instituto de Ciencias Matemáticas CSIC-UAM-UC3M-UCM and Departamento de Matemáticas, Universidad Carlos III de Madrid, Avenida de la Universidad 30, 28911 Leganés, Spain Plamen Koev, Department of Mathematics, San Jose State University, One Washington Square, San Jose, CA 95192, USA Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    BDDC algorithms have previously been extended to the saddle point problems arising from mixed formulations of elliptic and incompressible Stokes problems. In these two-level BDDC algorithms, all iterates are required to be in a benign space, a subspace in which the preconditioned operators are positive definite. This requirement can lead to large coarse problems, which have to be generated and factored by a direct solver at the beginning of the computation and they can ultimately become a bottleneck. An additional level is introduced in this paper to solve the coarse problem approximately and to remove this difficulty. This three-level BDDC algorithm keeps all iterates in the benign space and the conjugate gradient methods can therefore be used to accelerate the convergence. This work is an extension of the three-level BDDC methods for standard finite element discretization of elliptic problems and the same rate of convergence is obtained for the mixed formulation of the same problems. Estimate of the condition number for this three-level BDDC methods is provided and numerical experiments are discussed. Content Type Journal Article Pages 1-29 DOI 10.1007/s00211-011-0375-2 Authors Xuemin Tu, Department of Mathematics, University of Kansas, Lawrence, KS 66045-7594, USA Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    We analyze a finite element approximation of an elliptic optimal control problem with pointwise bounds on the gradient of the state variable. We derive convergence rates if the control space is discretized implicitly by the state equation. In contrast to prior work we obtain these results directly from classical results for the W 1,∞ -error of the finite element projection, without using adjoint information. If the control space is discretized directly, we first prove a regularity result for the optimal control to control the approximation error, based on which we then obtain analogous convergence rates. Content Type Journal Article Pages 1-14 DOI 10.1007/s00211-011-0360-9 Authors C. Ortner, Mathematical Institute, University of Oxford, 24–29 St. Giles’, Oxford, OX1 3LB UK W. Wollner, Institut für Angewandte Mathematik, Ruprecht-Karls-Universität Heidelberg, INF 294, 69120 Heidelberg, Germany Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    We discuss congruence transformations aimed at simultaneously reducing a pair of symmetric matrices to tridiagonal–tridiagonal form under the very mild assumption that the matrix pencil is regular. We outline the general principles and propose a unified framework for the problem. This allows us to gain new insights, leading to an economical approach that only uses Gauss transformations and orthogonal Householder transformations. Numerical experiments show that the approach is numerically robust and competitive. Content Type Journal Article Pages 1-18 DOI 10.1007/s00211-010-0357-9 Authors Roger B. Sidje, Department of Mathematics, The University of Alabama, P.O. Box 870350, Tuscaloosa, AL 35487, USA Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    In general, the zeros of an orthogonal rational function (ORF) on a subset of the real line, with poles among { a 1 , ¼ , a n } Ì (\mathbb C 0 È { ¥ }) , are not all real (unless a n is real), and hence, they are not suitable to construct a rational Gaussian quadrature rule (RGQ). For this reason, the zeros of a so-called quasi-ORF or a so-called para-ORF are used instead. These zeros depend on one single parameter t Î (\mathbb C È { ¥ }) , which can always be chosen in such a way that the zeros are all real and simple. In this paper we provide a generalized eigenvalue problem to compute the zeros of a quasi-ORF and the corresponding weights in the RGQ. First, we study the connection between quasi-ORFs, para-ORFs and ORFs. Next, a condition is given for the parameter τ so that the zeros are all real and simple. Finally, some illustrative and numerical examples are given. Content Type Journal Article Pages 1-44 DOI 10.1007/s00211-010-0356-x Authors K. Deckers, Department of Computer Science, Katholieke Universiteit Leuven, Heverlee, Belgium A. Bultheel, Department of Computer Science, Katholieke Universiteit Leuven, Heverlee, Belgium J. Van Deun, Department of Mathematics and Computer Science, University of Antwerp, Antwerp, Belgium Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    Termination criteria for the iterative solution of bound-constrained optimization problems are examined in the light of backward error analysis. It is shown that the problem of determining a suitable perturbation on the problem’s data corresponding to the definition of the backward error is analytically solvable under mild assumptions. Moreover, a link between existing termination criteria and this solution is clarified, indicating that some standard measures of criticality may be interpreted in the sense of backward error analysis. The backward error problem is finally considered from the multicriteria optimization point of view and some numerical illustration is provided. Content Type Journal Article Pages 1-25 DOI 10.1007/s00211-011-0376-1 Authors Serge Gratton, ENSEEIHT-IRIT, 2, rue Camichel, 31000 Toulouse, France Mélodie Mouffe, CERFACS, 42, av. G. Coriolis, 31057 Toulouse, France Philippe L. Toint, Department of Mathematics, FUNDP-University of Namur, 61, rue de Bruxelles, 5000 Namur, Belgium Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    In Monte Carlo methods quadrupling the sample size halves the error. In simulations of stochastic partial differential equations (SPDEs), the total work is the sample size times the solution cost of an instance of the partial differential equation. A Multi-level Monte Carlo method is introduced which allows, in certain cases, to reduce the overall work to that of the discretization of one instance of the deterministic PDE. The model problem is an elliptic equation with stochastic coefficients. Multi-level Monte Carlo errors and work estimates are given both for the mean of the solutions and for higher moments. The overall complexity of computing mean fields as well as k -point correlations of the random solution is proved to be of log-linear complexity in the number of unknowns of a single Multi-level solve of the deterministic elliptic problem. Numerical examples complete the theoretical analysis. Content Type Journal Article Pages 1-39 DOI 10.1007/s00211-011-0377-0 Authors Andrea Barth, ETH Zentrum, Seminar für Angewandte Mathematik, Rämistrasse 101, 8092 Zurich, Switzerland Christoph Schwab, ETH Zentrum, Seminar für Angewandte Mathematik, Rämistrasse 101, 8092 Zurich, Switzerland Nathaniel Zollinger, ETH Zentrum, Seminar für Angewandte Mathematik, Rämistrasse 101, 8092 Zurich, Switzerland Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    An error analysis of Runge–Kutta convolution quadrature is presented for a class of non-sectorial operators whose Laplace transform satisfies, besides the standard assumptions of analyticity in a half-plane Re s 〉 σ 0 and a polynomial bound \operatorname O ( | s | m 1 ) there, the stronger polynomial bound \operatorname O ( s m 2 ) in convex sectors of the form | \operatorname* arg s | £ p /2 - q for θ 〉 0. The order of convergence of the Runge–Kutta convolution quadrature is determined by  μ 2 and the underlying Runge–Kutta method, but is independent of  μ 1 . Time domain boundary integral operators for wave propagation problems have Laplace transforms that satisfy bounds of the above type. Numerical examples from acoustic scattering show that the theory describes accurately the convergence behaviour of Runge–Kutta convolution quadrature for this class of applications. Our results show in particular that the full classical order of the Runge–Kutta method is attained away from the scattering boundary. Content Type Journal Article Pages 1-20 DOI 10.1007/s00211-011-0378-z Authors Lehel Banjai, Max Planck Institute for Mathematics in the Sciences, Inselstr. 22, 04103 Leipzig, Germany Christian Lubich, Mathematisches Institut, Universität Tübingen, Auf der Morgenstelle, 72076 Tübingen, Germany Jens Markus Melenk, Institut für Analysis und Scientific Computing, TU Wien, Wiedner Hauptstrasse 8-10, 1040 Vienna, Austria Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    We study a class of symmetric discontinuous Galerkin methods on graded meshes. Optimal order error estimates are derived in both the energy norm and the L 2 norm, and we establish the uniform convergence of V -cycle, F -cycle and W -cycle multigrid algorithms for the resulting discrete problems. Numerical results that confirm the theoretical results are also presented. Content Type Journal Article Pages 1-27 DOI 10.1007/s00211-011-0379-y Authors S. C. Brenner, Department of Mathematics, Louisiana State University, Baton Rouge, LA 70803, USA J. Cui, Department of Mathematics, Louisiana State University, Baton Rouge, LA 70803, USA T. Gudi, Center for Computation and Technology, Louisiana State University, Baton Rouge, LA 70803, USA L.-Y. Sung, Department of Mathematics, Louisiana State University, Baton Rouge, LA 70803, USA Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    This paper proposes a new preconditioning scheme for a linear system with a saddle-point structure arising from a hybrid approximation scheme on the sphere, an approximation scheme that combines (local) spherical radial basis functions and (global) spherical polynomials. In principle the resulting linear system can be preconditioned by the block-diagonal preconditioner of Murphy, Golub and Wathen. Making use of a recently derived inf–sup condition and the Brezzi stability and convergence theorem for this approximation scheme, we show that in this context the Schur complement in the above preconditioner is spectrally equivalent to a certain non-constant diagonal matrix. Numerical experiments with a non-uniform distribution of data points support the theoretically proved quality of the new preconditioner. Content Type Journal Article Pages 1-17 DOI 10.1007/s00211-011-0369-0 Authors Q. T. Le Gia, School of Mathematics and Statistics, University of New South Wales, Sydney, NSW 2052, Australia I. H. Sloan, School of Mathematics and Statistics, University of New South Wales, Sydney, NSW 2052, Australia Andrew J. Wathen, Mathematical Institute, Oxford University, 24-29 St. Giles, Oxford, OX1 3LB UK Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    A fully computable upper bound for the finite element approximation error of Allen–Cahn and Cahn–Hilliard equations with logarithmic potentials is derived. Numerical experiments show that for the sharp interface limit this bound is robust past topological changes. Modifications of the abstract results to derive quasi-optimal error estimates in different norms for lowest order finite element methods are discussed and lead to weaker conditions on the residuals under which the conditional error estimates hold. Content Type Journal Article Pages 1-27 DOI 10.1007/s00211-011-0389-9 Authors Sören Bartels, Institut für Numerische Simulation, Rheinische Friedrich-Wilhelms-Universität Bonn, Wegelerstrasse 6, 53115 Bonn, Germany Rüdiger Müller, Weierstrass Institute for Applied Analysis and Stochastics, Mohrenstr 39, 10117 Berlin, Germany Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    In this paper a new framework for transforming arbitrary matrices to compressed representations is presented. The framework provides a generic way of transforming a matrix via unitary similarity transformations to, e.g., Hessenberg, Hessenberg-like form and combinations of both. The new algorithms are deduced, based on the QR -factorization of the original matrix. Relying on manipulations with rotations, all the algorithms consist of eliminating the correct set of rotations, resulting in a matrix obeying the desired structural constraints. Based on this new reduction procedure we investigate further correspondences such as irreducibility, uniqueness of the reduction procedure and the link with (rational) Krylov methods. The unitary similarity transform to Hessenberg-like form as presented here, differs significantly from the one presented in earlier work. Not only does it use less rotations to obtain the desired structure, also the convergence to rational Ritz-values is not observed in the conventional approach. Content Type Journal Article Pages 1-25 DOI 10.1007/s00211-011-0400-5 Authors Raf Vandebril, Department of Computer Science, K.U. Leuven, 3001 Louvain (Heverlee), Belgium Gianna M. Del Corso, Department of Computer Science, Università di Pisa, Largo Pontecorvo, 3, 56127 Pisa, Italy Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    We introduce modified Lagrange–Galerkin (MLG) methods of order one and two with respect to time to integrate convection–diffusion equations. As numerical tests show, the new methods are more efficient, but maintaining the same order of convergence, than the conventional Lagrange–Galerkin (LG) methods when they are used with either P 1 or P 2 finite elements. The error analysis reveals that: (1) when the problem is diffusion dominated the convergence of the modified LG methods is of the form O ( h m +1  +  h 2  + Δ t q ), q  = 1 or 2 and m being the degree of the polynomials of the finite elements; (2) when the problem is convection dominated and the time step Δ t is large enough the convergence is of the form O (\frac h m +1 D t + h 2 + D t q ) ; (3) as in case (2) but with Δ t small, then the order of convergence is now O ( h m  +  h 2  + Δ t q ); (4) when the problem is convection dominated the convergence is uniform with respect to the diffusion parameter ν ( x , t ), so that when ν → 0 and the forcing term is also equal to zero the error tends to that of the pure convection problem. Our error analysis shows that the conventional LG methods exhibit the same error behavior as the MLG methods but without the term h 2 . Numerical experiments support these theoretical results. Content Type Journal Article Pages 1-38 DOI 10.1007/s00211-011-0418-8 Authors Rodolfo Bermejo, Departamento de Matemática Aplicada, ETSII, Universidad Politécnica de Madrid, Madrid, Spain Laura Saavedra, Departamento de Matemática Aplicada, Universidad de Santiago de Compostela, A Coruña, Spain Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    Given a function f defined on a bounded polygonal domain W Ì \mathbb R 2 and a number N  〉 0, we study the properties of the triangulation T N that minimizes the distance between f and its interpolation on the associated finite element space, over all triangulations of at most N elements. The error is studied in the W 1, p semi-norm for 1 ≤ p  〈 ∞, and we consider Lagrange finite elements of arbitrary polynomial order m − 1. We establish sharp asymptotic error estimates as N → +∞ when the optimal anisotropic triangulation is used. A similar problem has been studied in Babenko et al. (East J Approx. 12(1):71–101, 2006 ), Cao (J Numer Anal. 45(6):2368–2391, 2007 ), Chen et al. (Math Comput. 76:179–204, 2007 ), Cohen (Multiscale, Nonlinear and Adaptive Approximation. Springer, Berlin, 2009 ), Mirebeau (Constr Approx. 32(2):339–383, 2010 ), but with the error measured in the L p norm. The extension of this analysis to the W 1, p norm is required in order to match more closely the needs of numerical PDE analysis, and it is not straightforward. In particular, the meshes which satisfy the optimal error estimate are characterized by a metric describing the local aspect ratio of each triangle and by a geometric constraint on their maximal angle, a second feature that does not appear for the L p error norm. Our analysis also provides with practical strategies for designing meshes such that the interpolation error satisfies the optimal estimate up to a fixed multiplicative constant. Content Type Journal Article Pages 1-35 DOI 10.1007/s00211-011-0412-1 Authors Jean-Marie Mirebeau, Laboratoire Jacques-Louis Lions, UPMC Univ Paris 06, UMR 7598, 75005 Paris, France Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    This paper shows that a class of methods for solving linear equations, including the Cauchy–Barzilai–Borwein method, can be interpreted by means of a simple geometric object, the Bézier parabola. This curve is built from the current iterate using a transformation characterizing the system to be solved. The localization of the next iterates in the plane of the parabola sheds some light on the behavior of the methods and provides some new understanding of their relative efficiency. Content Type Journal Article Pages 1-28 DOI 10.1007/s00211-011-0383-2 Authors Alain F. Berlinet, Institut de Mathématiques et de Modélisation de Montpellier, UMR CNRS 5149, Université Montpellier II, Cc 051, Place Eugène Bataillon, 34095 Montpellier Cedex 5, France Christophe Roland, Institut de Mathématiques et de Modélisation de Montpellier, UMR CNRS 5149, Université Montpellier II, Cc 051, Place Eugène Bataillon, 34095 Montpellier Cedex 5, France Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    We analyze rigourously error estimates and compare numerically temporal/spatial resolution of various numerical methods for solving the Klein–Gordon (KG) equation in the nonrelativistic limit regime, involving a small parameter 0 〈 e 〈〈 1 which is inversely proportional to the speed of light. In this regime, the solution is highly oscillating in time, i.e. there are propagating waves with wavelength of O ( e 2 ) and O (1) in time and space, respectively. We begin with four frequently used finite difference time domain (FDTD) methods and obtain their rigorous error estimates in the nonrelativistic limit regime by paying particularly attention to how error bounds depend explicitly on mesh size h and time step τ as well as the small parameter e . Based on the error bounds, in order to compute ‘correct’ solutions when 0 〈 e 〈〈 1 , the four FDTD methods share the same e -scalability: t = O ( e 3 ) . Then we propose new numerical methods by using either Fourier pseudospectral or finite difference approximation for spatial derivatives combined with the Gautschi-type exponential integrator for temporal derivatives to discretize the KG equation. The new methods are unconditionally stable and their e -scalability is improved to τ  =  O (1) and t = O ( e 2 ) for linear and nonlinear KG equations, respectively, when 0 〈 e 〈〈 1 . Numerical results are reported to support our error estimates. Content Type Journal Article Pages 1-41 DOI 10.1007/s00211-011-0411-2 Authors Weizhu Bao, Department of Mathematics and Center for Computational Science and Engineering, National University of Singapore, Singapore, 119076 Singapore Xuanchun Dong, Department of Mathematics and Center for Computational Science and Engineering, National University of Singapore, Singapore, 119076 Singapore Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    In this paper, a priori error estimates for space–time finite element discretizations of optimal control problems governed by semilinear parabolic PDEs and subject to pointwise control constraints are derived. We extend the approach from Meidner and Vexler (SIAM Control Optim 47(3):1150–1177, 2008 ; SIAM Control Optim 47(3):1301–1329, 2008 ) where linear-quadratic problems have been considered, discretizing the state equation by usual conforming finite elements in space and a discontinuous Galerkin method in time. Error estimates for controls discretized by piecewise constant functions in time and cellwise constant functions in space are derived in detail and we explain how error estimate for further discretization approaches, e.g., cellwise linear discretization in space, the postprocessing approach from Meyer and Rösch (SIAM J Control Optim 43:970–985, 2004 ), and the variationally discrete approach from Hinze (J Comput Optim Appl 30:45–63, 2005 ) can be obtained. In addition, we derive an estimate for a setting with finitely many time-dependent controls. Content Type Journal Article Pages 1-42 DOI 10.1007/s00211-011-0409-9 Authors Ira Neitzel, Institut für Mathematik, Technische Universität Berlin, Str. des 17. Juni 136, 10623 Berlin, Germany Boris Vexler, Zentrum Mathematik, Technische Universität München, Boltzmannstr. 3, 85748 Garching b. München, Germany Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    In this paper we show that the quasi-symmetric coupling of finite and boundary elements of Bielak and MacCamy can be freed of two very restricting hypotheses that appeared in the original paper: the coupling boundary can be taken polygonal/polyhedral and coupling can be done using the normal stress instead of the pseudostress. We will do this by first considering a model problem associated to the Yukawa equation, where we prove how compactness arguments can be avoided to show stability of Galerkin discretizations of a coupled system in the style of Bielak–MacCamy’s. We also show how discretization properties are robust in the continuation parameter that appears in the formulation. This analysis is carried out using a new and very simplified proof of the ellipticity of the Johnson–Nédélec BEM–FEM coupling operator. Finally, we show how to apply the techniques that we have fully developed in the model problem to the linear elasticity system. Content Type Journal Article Pages 1-23 DOI 10.1007/s00211-011-0414-z Authors Gabriel N. Gatica, Centro de Investigación en Ingeniería Matemática (CI2MA) and Departamento de Ingeniería Matemática, Universidad de Concepción, Casilla 160-C, Concepción, Chile George C. Hsiao, Department of Mathematical Sciences, University of Delaware, Newark, DE 19176-2553, USA Francisco-Javier Sayas, Department of Mathematical Sciences, University of Delaware, Newark, DE 19176-2553, USA Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    In this paper we consider the inverse problem of constructing an n  × n real nonnegative matrix A from the prescribed partial eigendata. We first give the solvability conditions for the inverse problem without the nonnegative constraint and then discuss the associated best approximation problem. To find a nonnegative solution, we reformulate the inverse problem as a monotone complementarity problem and propose a nonsmooth Newton-type method for solving its equivalent nonsmooth equation. Under some mild assumptions, the global and quadratic convergence of our method is established. We also apply our method to the symmetric nonnegative inverse problem and to the cases of prescribed lower bounds and of prescribed entries. Numerical tests demonstrate the efficiency of the proposed method and support our theoretical findings. Content Type Journal Article Pages 1-45 DOI 10.1007/s00211-011-0415-y Authors Zheng-Jian Bai, School of Mathematical Sciences, Xiamen University, Xiamen, 361005 People’s Republic of China Stefano Serra-Capizzano, Dipartimento di Fisica e Matematica, Università dell’Insubria-Sede di Como, Via Valleggio 11, 22100 Como, Italy Zhi Zhao, School of Mathematical Sciences, Xiamen University, Xiamen, 361005 People’s Republic of China Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    We study the behavior of some “truncated” Gaussian rules based on the zeros of Pollaczek-type polynomials. These formulas are stable and converge with the order of the best polynomial approximation in suitable function spaces. Moreover, we apply these results to the related Lagrange interpolation process and to prove the stability and the convergence of a Nyström method for Fredholm integral equations of the second kind. Finally, some numerical examples are shown. Content Type Journal Article Pages 1-32 DOI 10.1007/s00211-011-0417-9 Authors M. C. De Bonis, Department of Mathematics and Computer Sciences, University of Basilicata, Viale dell’Ateneo Lucano n. 10, 85100 Potenza, Italy G. Mastroianni, Department of Mathematics and Computer Sciences, University of Basilicata, Viale dell’Ateneo Lucano n. 10, 85100 Potenza, Italy I. Notarangelo, Department of Mathematics and Computer Sciences, University of Basilicata, Viale dell’Ateneo Lucano n. 10, 85100 Potenza, Italy Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    Recent results reveal that the family of barycentric rational interpolants introduced by Floater and Hormann is very well-suited for the approximation of functions as well as their derivatives, integrals and primitives. Especially in the case of equidistant interpolation nodes, these infinitely smooth interpolants offer a much better choice than their polynomial analogue. A natural and important question concerns the condition of this rational approximation method. In this paper we extend a recent study of the Lebesgue function and constant associated with Berrut’s rational interpolant at equidistant nodes to the family of Floater–Hormann interpolants, which includes the former as a special case. Content Type Journal Article Pages 1-11 DOI 10.1007/s00211-011-0442-8 Authors Len Bos, Department of Computer Science, University of Verona, Strada le Grazie 15, 37134 Verona, Italy Stefano De Marchi, Department of Pure and Applied Mathematics, University of Padua, Via Trieste 63, 35121 Padua, Italy Kai Hormann, Faculty of Informatics, University of Lugano, Via Giuseppe Buffi 13, 6904 Lugano, Switzerland Georges Klein, Department of Mathematics, University of Fribourg, Chemin du Musée 23, 1700 Fribourg, Switzerland Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    In this paper, we propose a method for the fast evaluation of integrals stemming from boundary element methods including discretisations of the classical single and double layer potential operators. Our method is based on the parametrisation of boundary elements in terms of a d -dimensional parameter tuple. We interpret the integral as a real-valued function f depending on d parameters and show that f is smooth in a d -dimensional box. A standard interpolation of f by polynomials leads to a d -dimensional tensor which is given by the values of f at the interpolation points. This tensor may be approximated in a low rank tensor format like the (CP) format or the H -Tucker format. The tensor approximation has to be done only once and allows us to evaluate interpolants in O ( dr ( m +1)) operations in the (CP) format, or O ( dk 3 + dk ( m +1)) operations in the H -Tucker format, where m denotes the interpolation order and the ranks r , k are small integers. We demonstrate that highly accurate integral values can be obtained at very moderate costs. Content Type Journal Article Pages 1-28 DOI 10.1007/s00211-011-0436-6 Authors Jonas Ballani, Max Planck Institute for Mathematics in the Sciences, Inselstraße 22–26, 04103 Leipzig, Germany Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    The effect of numerical quadrature in finite element methods for solving quasilinear elliptic problems of nonmonotone type is studied. Under similar assumption on the quadrature formula as for linear problems, optimal error estimates in the L 2 and the H 1 norms are proved. The numerical solution obtained from the finite element method with quadrature formula is shown to be unique for a sufficiently fine mesh. The analysis is valid for both simplicial and rectangular finite elements of arbitrary order. Numerical experiments corroborate the theoretical convergence rates. Content Type Journal Article Pages 1-35 DOI 10.1007/s00211-011-0438-4 Authors Assyr Abdulle, Section de Mathématiques, École Polytechnique Fédérale de Lausanne, Station 8, 1015 Lausanne, Switzerland Gilles Vilmart, Section de Mathématiques, École Polytechnique Fédérale de Lausanne, Station 8, 1015 Lausanne, Switzerland Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    This paper, devoted to sampling inequalities, provides some extensions of previous results by Arcangéli et al. (Numer Math 107(2):181–211, 2007 ; J Approx Theory 161:198–212, 2009 ). Given a function u in a suitable Sobolev space defined on a domain Ω in \mathbb R n , sampling inequalities typically yield bounds of integer order Sobolev semi-norms of u in terms of a higher order Sobolev semi-norm of u , the fill distance d between W   and a discrete set A Ì W   , and the values of u on A . The extensions established in this paper allow us to bound fractional order semi-norms and to incorporate, if available, values of partial derivatives on the discrete set. Both the cases of a bounded domain Ω and W = \mathbb R n are considered. Content Type Journal Article Pages 1-22 DOI 10.1007/s00211-011-0439-3 Authors Rémi Arcangéli, Route de Barat, 31160 Arbas, France María Cruz López de Silanes, Departamento de Matemática Aplicada e IUMA, EINA, Universidad de Zaragoza, María de Luna 3, 50018 Zaragoza, Spain Juan José Torrens, Departamento de Ingeniería Matemática e Informática, Universidad Pública de Navarra, Campus de Arrosadía, 31006 Pamplona, Spain Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    The Liouville-Green (WKB) asymptotic theory is used along with the Borůvka’s transformation theory, to obtain asymptotic approximations of “phase functions” for second-order linear differential equations, whose coefficients are asymptotically polynomial. An efficient numerical method to compute zeros of solutions or even the solutions themselves in such highly oscillatory problems is then derived. Numerical examples, where symbolic manipulations are also used, are provided to illustrate the performance of the method. Content Type Journal Article Pages 1-22 DOI 10.1007/s00211-011-0441-9 Authors Renato Spigler, Dipartimento di Matematica, Università “Roma Tre”, 1, Largo S.L. Murialdo, 00146 Rome, Italy Marco Vianello, Dipartimento di Matematica, Università di Padova, 63, Via Trieste, 35121 Padua, Italy Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    A family of continuous piecewise linear finite elements for thin plate problems is presented. We use standard linear interpolation of the deflection field to reconstruct a discontinuous piecewise quadratic deflection field. This allows us to use discontinuous Galerkin methods for the Kirchhoff–Love plate equation. Three example reconstructions of quadratic functions from linear interpolation triangles are presented: a reconstruction using Morley basis functions, a fully quadratic reconstruction, and a more general least squares approach to a fully quadratic reconstruction. The Morley reconstruction is shown to be equivalent to the basic plate triangle (BPT). Given a condition on the reconstruction operator, a priori error estimates are proved in energy norm and L 2 norm. Numerical results indicate that the Morley reconstruction/BPT does not converge on unstructured meshes while the fully quadratic reconstruction show optimal convergence. Content Type Journal Article Pages 1-33 DOI 10.1007/s00211-011-0429-5 Authors Karl Larsson, Department of Mathematics, Umeå University, Umeå, Sweden Mats G. Larson, Department of Mathematics, Umeå University, Umeå, Sweden Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    For standard eigenvalue problems, closed-form expressions for the condition numbers of a multiple eigenvalue are known. In particular, they are uniformly 1 in the Hermitian case and generally take different values in the non-Hermitian case. We consider the generalized eigenvalue problem and identify the condition numbers. Our main result is that a multiple eigenvalue generally has multiple condition numbers, even in the Hermitian definite case. The condition numbers are characterized in terms of the singular values of the outer product of the corresponding left and right eigenvectors. Content Type Journal Article Pages 1-14 DOI 10.1007/s00211-011-0440-x Authors Yuji Nakatsukasa, School of Mathematics, The University of Manchester, Manchester, M139PL UK Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    Inexact Newton regularization methods have been proposed by Hanke and Rieder for solving nonlinear ill-posed inverse problems. Every such a method consists of two components: an outer Newton iteration and an inner scheme providing increments by regularizing local linearized equations. The method is terminated by a discrepancy principle. In this paper we consider the inexact Newton regularization methods with the inner scheme defined by Landweber iteration, the implicit iteration, the asymptotic regularization and Tikhonov regularization. Under certain conditions we obtain the order optimal convergence rate result which improves the suboptimal one of Rieder. We in fact obtain a more general order optimality result by considering these inexact Newton methods in Hilbert scales. Content Type Journal Article Pages 1-24 DOI 10.1007/s00211-011-0435-7 Authors Qinian Jin, Mathematical Sciences Institute, The Australian National University, Canberra, ACT 0200, Australia Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    The entropy solutions of the compressible Euler equations satisfy a minimum principle for the specific entropy (Tadmor in Appl Numer Math 2:211–219, 1986 ). First order schemes such as Godunov-type and Lax-Friedrichs schemes and the second order kinetic schemes (Khobalatte and Perthame in Math Comput 62:119–131, 1994 ) also satisfy a discrete minimum entropy principle. In this paper, we show an extension of the positivity-preserving high order schemes for the compressible Euler equations in Zhang and Shu (J Comput Phys 229:8918–8934, 2010 ) and Zhang et al. (J Scientific Comput, in press), to enforce the minimum entropy principle for high order finite volume and discontinuous Galerkin (DG) schemes. Content Type Journal Article Pages 1-19 DOI 10.1007/s00211-011-0443-7 Authors Xiangxiong Zhang, Division of Applied Mathematics, Brown University, Providence, RI 02912, USA Chi-Wang Shu, Division of Applied Mathematics, Brown University, Providence, RI 02912, USA Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    Tensor-based methods are receiving a growing interest in scientific computing for the numerical solution of problems defined in high dimensional tensor product spaces. A family of methods called proper generalized decompositions (PGD) methods have been recently introduced for the a priori construction of tensor approximations of the solution of such problems. In this paper, we give a mathematical analysis of a family of progressive and updated PGDs for a particular class of problems associated with the minimization of a convex functional over a reflexive tensor Banach space. Content Type Journal Article Pages 1-28 DOI 10.1007/s00211-011-0437-5 Authors Antonio Falcó, Departamento de Ciencias, Físicas, Matemáticas y de la Computación, Universidad CEU Cardenal Herrera, San Bartolomé 55, 46115 Alfara del Patriarca, Valencia, Spain Anthony Nouy, LUNAM Université, GeM, UMR CNRS 6183, Ecole Centrale Nantes, Université de Nantes, 1 rue de la Noë, BP 92101, 44321 Nantes Cedex 3, France Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    In this paper, we study heat and moisture transport through porous textile materials with phase change, described by a degenerate, nonlinear and strongly coupled parabolic system. An uncoupled finite difference method with semi-implicit Euler scheme in time direction is proposed for the system. We prove the existence and uniqueness of the solution of the finite difference system. The optimal error estimates in both discrete L 2 and H 1 norms are obtained under the condition that the mesh sizes τ and h are smaller than a positive constant, which depends solely upon physical parameters involved. Numerical results are presented to confirm our theoretical analysis and compared with experimental data. Content Type Journal Article Pages 1-35 DOI 10.1007/s00211-011-0402-3 Authors Weiwei Sun, Department of Mathematics, City University of Hong Kong, Kowloon, Hong Kong Zhi-zhong Sun, Department of Mathematics, Southeast University, Nanjing, 210096 People’s Republic of China Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    This paper systematically studies numerical solution of fourth order problems in any dimensions by use of the Morley–Wang–Xu (MWX) element discretization combined with two-grid methods (Xu and Zhou (Math Comp 69:881–909, 1999 )). Since the coarse and fine finite element spaces are nonnested, two intergrid transfer operators are first constructed in any dimensions technically, based on which two classes of local and parallel algorithms are then devised for solving such problems. Following some ideas in (Xu and Zhou (Math Comp 69:881–909, 1999 )), the intrinsic derivation of error analysis for nonconforming finite element methods of fourth order problems (Huang et al. (Appl Numer Math 37:519–533, 2001 ); Huang et al. (Sci China Ser A 49:109–120, 2006 )), and the error estimates for the intergrid transfer operators, we prove that the discrete energy errors of the two classes of methods are of the sizes O ( h  +  H 2 ) and O ( h  +  H 2 ( H / h ) ( d −1)/2 ), respectively. Here, H and h denote respectively the mesh sizes of the coarse and fine finite element triangulations, and d indicates the space dimension of the solution region. Numerical results are performed to support the theory obtained and to compare the numerical performance of several local and parallel algorithms using different intergrid transfer operators. Content Type Journal Article Pages 1-31 DOI 10.1007/s00211-011-0396-x Authors Jianguo Huang, Department of Mathematics, Shanghai Jiao Tong University, Shanghai, 200240 China Xuehai Huang, Department of Mathematics, Shanghai Jiao Tong University, Shanghai, 200240 China Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    We study the linearization of three dimensional Regge calculus around Euclidean metric. We provide an explicit formula for the corresponding quadratic form and relate it to the curl t curl operator which appears in the quadratic part of the Einstein–Hilbert action and also in the linear elasticity complex. We insert Regge metrics in a discrete version of this complex, equipped with densely defined and commuting interpolators. We show that the eigenpairs of the curl t curl operator, approximated using the quadratic part of the Regge action on Regge metrics, converge to their continuous counterparts, interpreting the computation as a non-conforming finite element method. Content Type Journal Article Pages 1-28 DOI 10.1007/s00211-011-0394-z Authors Snorre H. Christiansen, CMA, University of Oslo, P.O. Box 1053, Blindern, 0316 Oslo, Norway Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    A theorem due to Stieltjes’ states that if { p n } n =0 ¥ is any orthogonal sequence then, between any two consecutive zeros of p k , there is at least one zero of p n whenever k 〈 n , a property called Stieltjes interlacing. We show that Stieltjes interlacing extends to the zeros of Gegenbauer polynomials C n +1 l and C n - 1 l + t , $${\lambda 〉 -\frac 12}$$, if 0 〈 t ≤ k  + 1, and also to the zeros of C n +1 l and C n - 2 l + k if k Î {1,2,3} . More generally, we prove that Stieltjes interlacing holds between the zeros of the k th derivative of C n l and the zeros of C n +1 l , k Î {1,2,..., n - 1} and we derive associated polynomials that play an analogous role to the de Boor–Saff polynomials in completing the interlacing process of the zeros. Content Type Journal Article Pages 1-10 DOI 10.1007/s00211-011-0407-y Authors Kathy Driver, Department of Mathematics and Applied Mathematics, University of Cape Town, Private Bag X3, Rondebosch, 7701 South Africa Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    In this paper we develop an a posteriori error analysis for an augmented discontinuous Garlerkin formulation applied to the Darcy flow. More precisely, we derive a reliable and efficient a posteriori error estimator, which consists of residual terms. Finally, we present several numerical experiments, showing the robustness of the method and the theoretical properties of the estimator, thus confirming the capability of the corresponding adaptive algorithms to localize the inner layers, the singularities and/or the large stress regions of the exact solution. Content Type Journal Article Pages 1-39 DOI 10.1007/s00211-011-0410-3 Authors Tomás P. Barrios, Departamento de Matemática y Física Aplicadas, Universidad Católica de la Santísima Concepción, Casilla 297, Concepción, Chile Rommel Bustinza, CI2MA and Departamento de Ingenierí a Matemática, Facultad de Ciencias Físicas y Matemáticas, Universidad de Concepción, Casilla 160-C, Concepción, Chile Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X

Description:    In this paper, we develop a new mixed finite element method for elliptic problems on general quadrilateral and hexahedral grids that reduces to a cell-centered finite difference scheme. A special non-symmetric quadrature rule is employed that yields a positive definite cell-centered system for the pressure by eliminating local velocities. The method is shown to be accurate on highly distorted rough quadrilateral and hexahedral grids, including hexahedra with non-planar faces. Theoretical and numerical results indicate first-order convergence for the pressure and face fluxes. Content Type Journal Article Pages 1-40 DOI 10.1007/s00211-011-0427-7 Authors Mary Wheeler, Center for Subsurface Modeling, Institute for Computational Engineering and Sciences, The University of Texas at Austin, 201 E 24th Street, Austin, TX 78712, USA Guangri Xue, Center for Subsurface Modeling, Institute for Computational Engineering and Sciences, The University of Texas at Austin, 201 E 24th Street, Austin, TX 78712, USA Ivan Yotov, Department of Mathematics, University of Pittsburgh, 301 Thackeray Hall, Pittsburgh, PA 15260, USA Journal Numerische Mathematik Online ISSN 0945-3245 Print ISSN 0029-599X