Hierarchical matrix techniques for low- and high-frequency Helmholtz problems

Wolfgang Hackbusch ^{In this paper, we discuss the application of hierarchical matrixtechniques to the solution of Helmholtz problems with largewave number in 2D. We consider the Brakhage–Werner integralformulation of the problem discretized by the Galerkin boundary-elementmethod. The dense n x n Galerkin matrix arising from this approachis represented by a sum of an -matrix and an 2-matrix, two different hierarchical matrix formats.A well-known multipole expansion is used to construct the 2-matrix. We present a new approach to dealingwith the numerical instability problems of this expansion: theparts of the matrix that can cause problems are approximatedin a stable way by an -matrix. Algebraic recompression methods are used to reducethe storage and the complexity of arithmetical operations ofthe -matrix.Further, an approximate LU decomposition of such a recompressed-matrix is aneffective preconditioner. We prove that the construction ofthe matrices as well as the matrix-vector product can be performedin almost linear time in the number of unknowns. Numerical experimentsfor scattering problems in 2D are presented, where the linearsystems are solved by a preconditioned iterative method.}     

A safeguarded dual weighted residual method

Andreas Veeser ^{The dual weighted residual (DWR) method yields reliable a posteriorierror bounds for linear output functionals provided that theerror incurred by the numerical approximation of the dual solutionis negligible. In that case, its performance is generally superiorthan that of global ‘energy norm’ error estimatorswhich are ‘unconditionally’ reliable. We presenta simple numerical example for which neglecting the approximationerror leads to severe underestimation of the functional error,thus showing that the DWR method may be unreliable. We proposea remedy that preserves the original performance, namely a DWRmethod safeguarded by additional asymptotically higher ordera posteriori terms. In particular, the enhanced estimator isunconditionally reliable and asymptotically coincides with theoriginal DWR method. These properties are illustrated via theaforementioned example.}     

Vector Valued Inequalities for Hankel Transforms

The disc multiplier may be seen as a vector valued operatorwhen we consider its projections in terms of the spherical harmonics.We prove the boundedness of this operator, which in this formrepresents a vector valued Hankel Transform, on the spaces (r^n–1 dr) when 2n/(n + 1) <p, q < 2n/(n – 1).     

Predicting overflow in an emergency department

G. B. Byrnes Centre for Molecular, Environmental, Genetic and Analytic Epidemiology, Department of Public Health, The University of Melbourne, Victoria, Australia C. A. Bain Directorate Office, Western and Central Melbourne Integrated Cancer Service, Victoria, Australia M. Fackrell Department of Mathematics and Statistics, The University of Melbourne, Victoria, Australia C. Brand Clinical Epidemiology and Health Service Evaluation Unit, Melbourne Health, Victoria, Australia D. A. Campbell Department of Medicine, Southern Clinical School, Monash University, Victoria, Australia P. G. Taylor Department of Mathematics and Statistics, The University of Melbourne, Victoria, Australia Email: l.au{at}ms.unimelb.edu.au Received on 9 October 2007. Accepted on 4 February 2008. Ambulance bypass occurs when the emergency department (ED) ofa hospital becomes so busy that ambulances are requested totake their patients elsewhere, except in life-threatening cases.It is a major concern for hospitals in Victoria, Australia,and throughout most of the western world, not only from thepoint of view of patient safety but also financially—hospitalslose substantial performance bonuses if they go on ambulancebypass too often in a given period. We show that the main causeof ambulance bypass is the inability to move patients from theED to a ward. In order to predict the onset of ambulance bypass,the ED is modelled as a queue for treatment followed by a queuefor a ward bed. The queues are assumed to behave as inhomogeneousPoisson arrival processes. We calculate the probability of reachingsome designated capacity C within time t, given the currenttime and number of patients waiting.     

Variational iteration method for the Burgers’ flow with fractional derivatives—New Lagrange multipliers

The flow through porous media can be better described by fractional models than the classical ones since they include inherently memory effects caused by obstacles in the structures. The variational iteration method was extended to find approximate solutions of fractional differential equations with the Caputo derivatives, but the Lagrange multipliers of the method were not identified explicitly. In this paper, the Lagrange multiplier is determined in a more accurate way and some new variational iteration formulae are presented.     

Numerical approximation of the boundary control for the wave equation with mixed finite elements in a square

Sorin Micu ^{This paper studies the numerical approximation of the boundarycontrol for the wave equation in a square domain. It is knownthat the discrete and semi-discrete models obtained by discretizingthe wave equation with the usual finite-difference or finite-elementmethods do not provide convergent sequences of approximationsto the boundary control of the continuous wave equation as themesh size goes to zero. Here, we introduce and analyse a newsemi-discrete model based on the space discretization of thewave equation using a mixed finite-element method with two differentbasis functions for the position and velocity. The main theoreticalresult is a uniform observability inequality which allows usto construct a sequence of approximations converging to theminimal L2-norm control of the continuous wave equation. Wealso introduce a fully discrete system, obtained from our semi-discretescheme, for which we conjecture that it provides a convergentsequence of discrete approximations as both h and t, the timediscretization parameter, go to zero. We illustrate this factwith several numerical experiments.}     

A Refined Version of the Lang-Trotter Conjecture

Let E be an elliptic curve defined over the rational numbersand r a fixed integer. Using a probabilistic model consistentwith the Chebotarev density theorem for the division fieldsof E and the Sato–Tate distribution, Lang and Trotterconjectured an asymptotic formula for the number of primes upto x which have Frobenius trace equal to r, where r is a fixedinteger. However, as shown in this note, this asymptotic estimatecannot hold for all r in the interval with a uniform bound for the error term, becausean estimate of this kind would contradict the Chebotarev densitytheorem as well as the Sato–Tate conjecture. The purposeof this note is to refine the Lang–Trotter conjecture,by taking into account the "semicircular law," to an asymptoticformula that conjecturally holds for arbitrary integers r inthe interval , with auniform error term. We demonstrate consistency of our refinementwith the Chebotarev density theorem for a fixed division field,and with the Sato–Tate conjecture. We also present numericalevidence for the refined conjecture.     

On the optimality of some classes of invex problems

In this paper we define two notions: Kuhn–Tucker saddle point invex problem with inequality constraints and Mond–Weir weak duality invex one. We prove that a problem is Kuhn–Tucker saddle point invex if and only if every point, which satisfies Kuhn–Tucker optimality conditions forms together with the respective Lagrange multiplier a saddle point of the Lagrange function. We prove that a problem is Mond–Weir weak duality invex if and only if weak duality holds between the problem and its Mond–Weir dual one. Additionally, we obtain necessary and sufficient conditions, which ensure that strong duality holds between the problem with inequality constraints and its Wolfe dual. Connections with previously defined invexity notions are discussed.     

Operator–valued Fourier multiplier theorems and maximal $L_p$-regularity

We prove a Mihlin–type multiplier theorem for operator–valued multiplier functions on UMD–spaces. The essential assumption is R–boundedness of the multiplier function. As an application we give a characterization of maximal –regularity for the generator of an analytic semigroup in terms of the R–boundedness of the resolvent of A or the semigroup . Received July 19, 1999 / Revised July 13, 2000 / Published online February 5, 2001     

Appending boundary conditions by Lagrange multipliers: Analysis of the LBB condition

Summary. This paper is concerned with the analysis of discretization schemes for second order elliptic boundary value problems when essential boundary conditions are enforced with the aid of Lagrange multipliers. Specifically, we show how the validity of the Ladyškaja–Babušska–Brezzi (LBB) condition for the corresponding saddle point problems depends on the various ingredients of the involved discretizations. The main result states that the LBB condition is satisfied whenever the discretization step length on the boundary, , is somewhat bigger than the one on the domain, . This is quantified through constants stemming from the trace theorem, norm equivalences for the multiplier spaces on the boundary, and direct and inverse inequalities. In order to better understand the interplay of these constants, we then specialize the setting to wavelet discretizations. In this case the stability criteria can be stated solely in terms of spectral properties of wavelet representations of the trace operator. We conclude by illustrating our theoretical findings by some numerical experiments. We stress that the results presented here apply to any spatial dimension and to a wide selection of Lagrange multiplier spaces which, in particular, need not be traces of the trial spaces. However, we do always assume that a hierarchy of nested trial spaces is given. Received October 23, 1998 / Revised version received December 27, 1999 / Published online October 16, 2000     

Preconditioning by inverting the Laplacian: an analysis of the eigenvalues

Wolfgang Hackbusch ^{We study the eigenvalues of the operator generated by usingthe inverse of the Laplacian as a preconditioner for self-adjointsecond-order elliptic partial differential equations with smoothcoefficients. It is well-known that the spectral condition numberof the preconditioned operator can be bounded by , where k is the uniformly positive coefficientof the second-order elliptic equation. The purpose of this paperis to study the spectrum of the preconditioned operator. Wewill show that there is a strong relation between the spectrumof this operator and the range of the coefficient function.In the continuous case, we prove, both for mappings definedon Sobolev spaces and in terms of generalized functions, thatthe spectrum of the preconditioned operator contains the rangeof the coefficient function k. In the discrete case, we indicateby numerical examples that the entire discrete spectrum is approximatelygiven by values of k.}     

Geometrical Spines of Lens Manifolds

We introduce the concept of ‘geometrical spine’for 3-manifolds with natural metrics, in particular, for lensmanifolds. We show that any spine of L_p,q that is close enoughto its geometrical spine contains at least E(p,q) – 3vertices, which is exactly the conjectured value for the complexityc(L_p,q). As a byproduct, we find the minimal rotation distance(in the Sleator–Tarjan–Thurston sense) between atriangulation of a regular p-gon and its image under rotation.     

Strict contractivity of the 2-Wasserstein distance for the porous medium equation by mass-centering

We show that the Euclidean Wasserstein distance between two compactly supported solutions of the one-dimensional porous medium equation having the same center of mass decays to zero for large times. As a consequence, we detect an improved -rate of convergence of solutions of the one-dimensional porous medium equation towards well-centered self-similar Barenblatt profiles, as time goes to infinity.

     

Optimal defect corrections on composite nonmatching finite-element meshes

Ahmed-Salah Chibi ^{In this paper, we analyse the ‘defect-correction’technique on a general smooth region, via composite finite-elementmeshes (a Cartesian mesh and a polar mesh) on two overlappingsubdomains (a rectangle and an annulus). Boundary interpolatorymappings of higher degree are used, in the Schwarz method, topass from one mesh to another. An explicit relation is givenbetween the degree of these mappings and the number of optimalcorrections to be computed. Optimal convergence results forthe discrete bilinear basic solution, in higher-order discreteSobolev norms, are obtained on the subdomains. Because the successof the defect-correction technique is based on the uniformityof the discretization and the regularity of the exact solution,the defects are computed on the subdomains in the same way asfor the basic solution. Optimal O(h2) improvement per correctionis obtained. Numerical results are presented to support thetheory.}