Iterative refinement for linear systems and LAPACK

E-mail: na.nhigham{at}na-net.ornl.gov The technique of iterative refinement for improving the computedsolution to a linear system was used on desk calculators andcomputers in the 1940s and has remained popular. In the 1990siterative refinement is well supported in software libraries,notably in LAPACK. Although the behaviour of iterative refinementin floating point arithmetic is reasonably well understood,the existing theory is not sufficient to justify the use offixed precision iterative refinement in all the LAPACK routinesin which it is implemented. We present analysis that providesthe theoretical support needed for LAPACK. The analysis coversboth mixed and fixed precision iterative refinement with anarbitrary number of iterations, makes only a general assumptionon the underlying solver, and is relatively short. We identifysome remaining open problems.     

Post-processing with computable error bounds for the finite element approximation of a nonlinear heat conduction problem

Email: ain{at}mcs.le.ac.uk Email: D.Kelly{at}unsw.edu.au^* Email: I.Sloan{at}unsw.edu.au^** Email: swang{at}cs.curtin.edu.au It is shown how the finite element approximation of a nonlinearheat conduction problem may be post-processed to yield enhancedapproximations to the solution and the flux at any point inthe domain. Sharp computable bounds on the accuracy of the post-processedapproximations are derived. A criterion is identified for guidingadaptive refinements of the finite element discretization. Anumerical example is given illustrating the theoretical results.     

Newton's method on Riemannian manifolds: Smale's point estimate theory under the {gamma}-condition

^** Email: cli{at}zju.edu.cn^*** Email: wjh{at}zjut.edu.cn The -conditions for vector fields on Riemannian manifolds areintroduced. The -theory and the -theory for Newton's methodon Riemannian manifolds are established under the -conditions.Applications to analytic vector fields are provided and theresults due to Dedieu et al. (2003, IMA J. Numer. Anal., 23,395–419) are improved.     

Finite-Element Approximation of a Plasma Equilibrium Problem

The plasma problem studied is: given R⁺ find (, d, u) R ?R ? H¹() such that Let ₁ < ₂ be the first two eigenvalues of the associatedlinear eigenvalue problem: find $$\left(\lambda ,\phi \right)\in\mathrm{R;}\times {\hbox{ H }}_{0}^{1}\left(\Omega \right)$$such that For ₀(0,₂) it is well known that there exists a unique solution(₀, d₀, u₀) to the above problem. We show that the standard continuous piecewise linear Galerkinfinite-element approximatinon $$\left({\lambda }_{0},{\hbox{d }}_{0}^{k},{u}_{0}^{h}\right)$$, for ₀(0,₂), converges atthe optimal rate in the H¹, L², and L norms as h, the mesh length,tends to 0. In addition, we show that dist (, ^h)Ch² ln 1/h,where $${\Gamma }^{\left(h\right)}=\left\{x\in \Omega :{u}_{0}^{\left(h\right)}\left(x\right)=0\right\}$$.Finally we consider a more practical approximation involvingnumerical integration.     

Computation and parametrization of periodic and connecting orbits

Email: g.moore{at}ma.ic.ac.uk or na.gmoore New algorithms for the computation of periodic and connectingorbits of autonomous differential equations are developed. Previousmethods have parametrized these curves by the independent timevariable, but our procedure is based on the canonical arclengthparametrization.     

Finite-difference schemes for scalar conservation laws with source terms

Explicit and semi-implicit finite-difference schemes approximatingnon-homogeneous scalar conservation laws are analyzed. Optimalerror bounds independent of the stiffness of the underlyingequation are presented. This author has been supported by The Norwegian Research Council(NFR), program No 100284/431. e-mail: schroll{at}igpm.rwth-aachen.de This author has been supported by The Norwegian Research Council(NFR), program Nos 100284/431 and STP.29643. e-mail: ragnar{at}ifi.uio.no     

Numerical stabilization of polynomial and matrix

Email: jdhan{at}sia.cn Email: zhjiang{at}sia.cn Corresponding author Email: nyy{at}sia.cn Received on March 6, 2006; Accepted on September 4, 2006 In this paper, the conception of numerical stabilization, whichis related to mantissa digits of computer and dimensions ofsystem, is described; and several strategies for the numericalstabilization of polynomial and matrix are presented.     

Fitted and Unfitted Finite-Element Methods for Elliptic Equations with Smooth Interfaces

This paper considers the finite-element approximation of theelliptic interface problem: -?(u) + cu = f in Rⁿ (n = 2 or3), with u = 0 on , where is discontinuous across a smoothsurface in the interior of . First we show that, if the meshis isoparametrically fitted to using simplicial elements ofdegree k - 1, with k 2, then the standard Galerkin method achievesthe optimal rate of convergence in the H¹ and L² norms overthe approximations _l⁴ of _l where _{l 2}. Second, since itmay be computationally inconvenient to fit the mesh to , weanalyse a fully practical piecewise linear approximation ofa related penalized problem, as introduced by Babuska (1970),based on a mesh that is independent of . We show that, by choosingthe penalty parameter appropriately, this approximation convergesto u at the optimal rate in the H¹ norm over _l⁴ and in the L²norm over any interior domain _l^* satisfying _l^* _l^** _l⁴ for somedomain _l^**. Present address: School of Mathematical and Physical Sciences,University of Sussex, Brighton BN1 9QH     

Realistic a Priori and a Posteriori Error Bounds for Computed Eigenvalues

Permanent address: Department of Engineering Mathematics, Cairo University, Giza, Egypt. A priori and a posteriori error bounds are given for the computedeigenpair (, ) of the eigenvalue problem Ax = x, which are shownto be more realistic than some of the available ones. A simplemethod is also presented for computing the backward error. Finallya scaling procedure is explained for reducing the residual error.     

Approximation of 1/x by exponential sums in [1, {infty})

^** Email: braess{at}num.rub.de^*** Email: wh{at}mis.mpg.de Approximations of 1/x by sums of exponentials are well studiedfor finite intervals. Here the error decreases like (exp(–ck))with the order k of the exponential sum. In this paper we investigateapproximations of 1/x in the interval [1, ). We prove estimatesof the error by and confirm this asymptotic estimate by numerical results. Numericalresults lead to the conjecture that the constant in the exponentequals .     

Convergence rates for sparse chaos approximations of elliptic problems with stochastic coefficients

^** Email: todor{at}math.ethz.ch^*** Corresponding author. Email: schwab{at}math.ethz.ch A scalar, elliptic boundary-value problem in divergence formwith stochastic diffusion coefficient a(x, ) in a bounded domainD ^d is reformulated as a deterministic, infinite-dimensional,parametric problem by separation of deterministic (x D) andstochastic ( ) variables in a(x, ) via Karhúnen–Loèveor Legendre expansions of the diffusion coefficient. Deterministic,approximate solvers are obtained by projection of this probleminto a product probability space of finite dimension M and sparsediscretizations of the resulting M-dimensional parametric problem.Both Galerkin and collocation approximations are considered.Under regularity assumptions on the fluctuation of a(x, ) inthe deterministic variable x, the convergence rate of the deterministicsolution algorithm is analysed in terms of the number N of deterministicproblems to be solved as both the chaos dimension M and themultiresolution level of the sparse discretization resp. thepolynomial degree of the chaos expansion increase simultaneously.     

Discontinuous Galerkin finite element approximation of quasilinear elliptic boundary value problems I: the scalar case

^** Email: Paul.Houston{at}mcs.le.ac.uk^*** Email: Janice.Robson{at}comlab.ox.ac.uk^**** Email: Endre.Suli{at}comlab.ox.ac.uk We develop a one-parameter family of hp-version discontinuousGalerkin finite element methods, parameterised by [–1,1], for the numerical solution of quasilinear elliptic equationsin divergence form on a bounded open set ^d, d 2. In particular,we consider the analysis of the family for the equation –·{µ(x, |u|)u} = f(x) subject to mixed Dirichlet–Neumannboundary conditions on . It is assumed that µ is a real-valuedfunction, µ C( x [0, )), and thereexist positive constants m_µ and M_µ such that m_µ(t– s) µ(x, t)t – µ(x, s)s M_µ(t– s) for t s 0 and all x . Using a result from the theory of monotone operators for any valueof [–1, 1], the corresponding method is shown to havea unique solution u_DG in the finite element space. If u C¹() H^k(), k 2, then with discontinuous piecewise polynomials ofdegree p 1, the error between u and u_DG, measured in the brokenH¹()-norm, is (h^s–1/p^k–3/2), where 1 s min {p+ 1, k}.     

Estimating vaccine coverage by using computer algebra

Email: altmannd{at}rki.deEmail: altmann{at}mathematik.hu-berlin.de The approach of N Gay for estimating the coverage of a multivalentvaccine from antibody prevalence data in certain age cohortsis complemented by using computer aided elimination theory ofvariables. Hereby, Gay's usage of numerical approximation canbe replaced by exact formulae which are surprisingly nice, too.     

Properties of the weighted logarithmic matrix norms

Mingzhu Liu Department of Mathematics, Harbin Institute of Technology, Harbin 150001, China Email: ghu{at}hit.edu.cn, ghuca{at}yahoo.ca Email: mzliu{at}hit.edu.cn Received on January 31, 2006; Accepted on December 9, 2006 In this paper, we are concerned with the properties of the weightedlogarithmic matrix norms. A relation between the elliptic logarithmicmatrix norm and the weighted logarithmic matrix norm is given.Based on Lyapunov equations, two weighted logarithmic matrixnorms are constructed which are less than 1-logarithmic matrixnorm and -logarithmic matrix norm, respectively. Then, an iterativescheme is presented to obtain the logarithmically -efficientmatrix norm. Numerical examples are given to illustrate theresults.     

An analysis of the coupling of finite-element and Nystrm methods in acoustic scattering

In this paper we analyze the use of a combined Nystrm and finite-elementprocedure for approximating the scattered time-harmonic acousticfield produced when an incident wave interacts with a boundedinhomogeneity. The coupling technique uses a smooth artificialboundary and explicitly decouples the integral equation andfinite-element computations. We prove convergence of the method.One highlight of this analysis is that we prove Sobolev spaceerror estimates for the Nystrm scheme (which is usually analyzedin Hlder spaces). We also present some numerical results. E-mail: kirsch{at}am.uni-erlangen.de E-mail: monk{at}math.udel.edu     

Numerical simulations of measurements of capillary contact angles

In a recent paper, Fischer and Finn have proposed a procedureto improve the accuracy in the measurement of capillary contactangles, based on the use of vessels with canonical cross-sections.We simulate numerically the behaviour of such shapes for a numberof cross-sections and fluid contact angles. Our approximationconsists of the minimization of a suitable convex functionaldiscretized by finite elements. e-mail: bellettini{at}sns.it e-mail: paolini{at}isa.mat.unimi.it     

Set convergence for discretizations of the attractor

We consider the discretization of a dynamical system given bya C⁰-semigroup S(t), defined on a Banach space X, possessingan attractor . Under certain weak assumptions, Hale, Lin andRaugel showed that discretizations of S(t) possess local attractors,which may be considered as approximations to . Without furtherassumptions, we show that these local attractors possess convergentsubsequences in the Hausdorff or set metric, whose limit isa compact invariant subset of . Using a new construction, wealso consider the Kloeden and Lorenz concept of attracting setsin a Banach space, and show under mild assumptions that discretizationspossess attracting sets converging to in the Hausdorff metric. ath{at}maths.bath.ac.uk Endre.Suli{at}comlab.ox.ac.uk     

Total Flux Estimates for a Finite-Element Approximation of Elliptic Equations

An elliptic boundary-value problem on a domain with prescribedDirichlet data on _I is approximated using a finite-elementspace of approximation power h^K in the L² norm. It is shownthat the total flux across _I can be approximated with an errorof O(h^K) when is a curved domain in Rⁿ (n = 2 or 3) and isoparametricelements are used. When is a polyhedron, an O(h^2K–2)approximation is given. We use these results to study the finite-elementapproximation of elliptic equations when the prescribed boundarydata on _I is the total flux. Present address: School of Mathematical and Physical Sciences,University of Sussex, Brighton, Sussex BN1 9QH.     

Robust H{infty} dynamic output feedback control for 2D linear parameter-varying systems

James Lam Department of Mechanical Engineering, The University of Hong Kong, Pokfulam Road, Hong Kong Changhong Wang Space Control and Inertial Technology Research Center, Harbin Institute of Technology, Harbin 150001, People's Republic of China Corresponding author. Email: ligangwu{at}hit.edu.cn Email: james.lam{at}hku.hk Email: cwang{at}hit.edu.cn Received on June 28, 2006; Accepted on October 1, 2007 This paper is concerned with the problem of robust dynamicoutput feedback control for 2D discrete-time linear parameter-varyingsystems. Given a Fornasini–Marchesini local state-spacesystem with linear varying parameters, our attention is focussedon the design of full-order dynamic output feedback controller,which guarantees the closed-loop system to be asymptoticallystable and has a prescribed disturbance attenuation performance.A sufficient condition for the existence of a desired robustoutput feedback controller is established in terms of parameterizedlinear matrix inequalities, and the corresponding controllersynthesis is cast into a convex optimization problem which canbe efficiently handled by using standard numerical software.A numerical example is provided to illustrate the effectivenessof the proposed design method.     

Convergence of a finite-element approximation of surfactant spreading on a thin film in the presence of van der Waals forces

We consider a fully practical finite-element approximationof the following system of nonlinear degenerate parabolic equations: (u)/(t) + . (u² [(v)]) - (1)/(3) .(u³ w)= 0, w = - c u - u^-+ a u^-3 , (v)/(t) + . (u v [(v)]) - v - .(u² v w) = 0. The above models a surfactant-driven thin-film flow in the presenceof both attractive, a>0, and repulsive, >0 with >3,van der Waals forces; where u is the height of the film, v isthe concentration of the insoluble surfactant monolayer and(v):=1-v is the typical surface tension. Here 0 and c>0 arethe inverses of the surface Peclet number and the modified capillarynumber. In addition to showing stability bounds for our approximation,we prove convergence, and hence existence of a solution to thisnonlinear degenerate parabolic system, (i) in one space dimensionwhen >0; and, moreover, (ii) in two space dimensions if inaddition 7. Furthermore, iterative schemes for solving the resultingnonlinear discrete system are discussed. Finally, some numericalexperiments are presented.