Forthcoming events in this series
I will describe some application areas for radial basis function, and discuss how the computational problems can be overcome by the use of preconditioning methods and fast evaluation techniques.
This Seminar has been cancelled and will now take place in Trinity Term, Week 3, 11 MAY.
Using the one-dimensional diffusion equation as an example, this seminar looks at ways of constructing approximations to the solution and coefficient functions of differential equations when the coefficients are not fully defined. There may, however, be some information about the solution. The input data, usually given as values of a small number of functionals of the coefficients and the solution, is insufficient for specifying a well-posed problem, and so various extra assumptions are needed. It is argued that looking at these inverse problems as problems in Bayesian statistics is a unifying approach. We show how the standard methods of Tikhonov Regularisation are related to special forms of random field. The numerical approximation of stochastic partial differential Langevin equations to sample generation will be discussed.
Standard finite element or boundary element methods for high frequency scattering problems, with piecewise polynomial approximation spaces, suffer from the limitation that the number of degrees of freedom required to achieve a prescribed level of accuracy grows at least linearly with respect to the frequency. Here we present a new boundary element method for which, by including in the approximation space the products of plane wave basis functions with piecewise polynomials supported on a graded mesh, we can demonstrate a computational cost that grows only logarithmically with respect to the frequency.
The main goal of this talk is to demonstrate connections between the following three big areas of research: the theory of cubature formulas (numerical integration), the discrepancy theory, and nonlinear approximation. First, I will discuss a relation between results on cubature formulas and on discrepancy. In particular, I'll show how standard in the theory of cubature formulas settings can be translated into the discrepancy problem and into a natural generalization of the discrepancy problem. This leads to a concept of the r-discrepancy. Second, I'll present results on a relation between construction of an optimal cubature formula with m knots for a given function class and best nonlinear m-term approximation of a special function determined by the function class. The nonlinear m-term approximation is taken with regard to a redundant dictionary also determined by the function class. Third, I'll give some known results on the lower and the upper estimates of errors of optimal cubature formulas for the class of functions with bounded mixed derivative. One of the important messages (well known in approximation theory) of this talk is that the theory of discrepancy is closely connected with the theory of cubature formulas for the classes of functions with bounded mixed derivative.
Parallel sparse direct solvers are an interesting alternative to iterative methods for some classes of large sparse systems of linear equations. In the context of a parallel sparse multifrontal solver (MUMPS), we describe a new dynamic scheduling strategy aiming at balancing both the workload and the memory usage. More precisely, this hybrid approach balances the workload under memory constraints. We show that the peak of memory can be significantly reduced, while we have also improved the performance of the solver.
Then, we present preliminary work concerning a parallel out-of-core extension of the solver MUMPS, enabling to solve increasingly large simulation problems.
This is joint work with P.Amestoy, A.Guermouche, S.Pralet and E.Agullo.
Through the advent of enhanced medical imaging computational modelling can now be applied to anatomically correct arterial geometries. However many flow feautures under physiological and pathological flow paraemeters, even in idealised problems, are relatively poorly understood. A commonly studied idealisation of an arterial blockage or stenosis, potentially generated by atherosclerosis, is a sinusoidally varying constricted tube. Although most physiological flow conditions are typically laminar, in this configuration turbulent flow states can arise due to the local increase in sectional Reynolds number. To examine the onset of turbulence in this geometry, under a simple non-reversing pulsatile flows, we have applied Floquet stability analysis and direct
numerical simulation.
As illustrated in the above figure, a period-doubling absolute instability mode associated with alternating tilting of the vortex rings that are ejected out of the stenosis/constriction during each pulse. This primary instability occurs for relatively large reduced velocities associated with long pulse periods (or low Womersley numbers). For lower reduced velocities the primary instability typically manifests itself as azimuthal waves (Widnall instability modes) of low wavenumber that grow on each vortex ring. We have also observed the shear layer of the steady axisymmetric flow is convectively unstable at still shorter temporal periods.
In this presentation we shall outline the challenges of modelling vascular flow problems with a particular focus on idealised stenotic flow. After briefly outlining the numerical analysis methods we shall discuss the flow investigations outlined above and their relation to more classical vortex instabilities.
Image Inpainting turns the art of image restoration, retouching, and disocclusion into a computer-automated trade. Mathematically, it may be viewed as an interpolation problem in BV, SBV, or other fancy function spaces thought suitable for digital images. It has recently drawn the attention of the numerical PDE community, which has led to some impressive results. However, stability restrictions of the suggested explicit schemes so far yield computing times that are next to prohibitive in the realm of interactive digital image processing. We address this issue by constructing an appropriatecontinuous energy functional that combines the possibility of a fast discrete minimization with high perceptible quality of the resulting inpainted images.
The talk will survey the background of the inpainting problem and prominent PDE-based methods before entering the discussion of the suggested new energy functional. Many images will be shown along the way, in parts with online demonstrations.
This is joint work with my student Thomas März.
Alan Turing introduced the sensitivity of the solution of a numerical problem to changes in its data as a way to measure the difficulty of solving the problem accurately. Condition numbers are now considered fundamental to sensitivity analysis. They have been used to measure the mathematical difficulty of many linear algebra problems, including linear systems, linear least-squares, and eigenvalue problems. By definition, unless exact arithmetic is used, it is expected to be difficultto accurately solve an ill-conditioned problem.
In this talk we focus on least-squares problems. After a historical overview of condition number for least-squares, we introduce two related condition numbers. The first is the partial condition number, which measures the sensitivity of a linear combination of the components of the solution. The second is related the truncated SVD solution of the problem, which is often used when the matrix is nearly rank deficient.
Throughout the talk we are interested in three types of results :closed formulas for condition numbers, sharp bounds and statistical estimates.
Direct methods for solving large sparse linear systems of equations are popular because of their generality and robustness. As the requirements of computational scientists for more accurate models increases, so inevitably do the sizes of the systems that must be solved and the amount of memory needed by direct solvers.
For many users, the option of using a computer with a sufficiently large memory is either not available or is too expensive. Using a preconditioned iterative solver may be possible but for the "tough" systems that arise from many practical applications, the difficulties involved in finding and computing a good preconditioner can make iterative methods infeasible. An alternative is to use a direct solver that is able to hold its data structures on disk, that is, an out-of-core solver.
In this talk, we will explain the multifrontal algorithm and discuss the design and development of a new HSL sparse symmetric out-of-core solver that uses it. Both the system matrix A and its factors are stored externally. For the indefinite case, numerical pivoting using 1x1 and 2x2 pivots is incorporated. To minimise storage for the system data, a reverse communication interface is used. Input of A is either by rows or by elements.
An important feature of the package is that all input and output to disk is performed through a set of Fortran subroutines that manage a virtual memory system so that actual i/o occurs only when really necessary. Also important is to design in-core data structures that avoid expensive searches. All these aspects will be discussed.
At the time of writing, we are tuning the code for the positive-definite case and have performance figures for real problems. By the time of the seminar, we hope to have developed the indefinite case, too.
It is well known that the computation of a few extreme eigenvalues, and the corresponding eigenvectors, of a symmetric matrix A can be rewritten as computing extrema of the Rayleigh quotient of A. However, since the Rayleigh quotient is a homogeneous function of degree zero, its extremizers are not isolated. This difficulty can be remedied by restricting the search space to a well-chosen manifold, which brings the extreme eigenvalue problem into the realm of optimization on manifolds. In this presentation, I will show how a recently-proposed generalization of trust-region methods to Riemannian manifolds applies to this problem, and how the resulting algorithms compare with existing ones.
I will also show how the Joint Diagonalization problem (that is, approximately diagonalizing a collection of symmetric matrices via a congruence transformation) can be tackled by a differential geometric approach. This problem has an important application in Independent Component Analysis.
We discuss a method for solving very large structured symmetric indefinite equation systems arising in optimization with interior point methods.
Many real-life economic models involve system dynamics, spatial distribution or uncertainty and lead to large-scale optimization problems. Such problems usually have a hidden structure: they are constructed by replication of some small generic block. The linear algebra subproblems which arise in optimization algorithms for such problems involve matrices which are not only sparse, but they additionally display a block-structure with many smaller blocks sparsely distributed in the large matrix.
We have developed a structure-exploiting parallel interior point solver for optimization problems. Its design uses object-orientated programming techniques. The progress OOPS (Object-Orientated Parallel Solver: http://www.maths.ed.ac.uk/~gondzio/parallel/solver.html) on a number of different computing platforms and achieves scalability on a number of different computing platforms. We illustrate its performance on a collection of problems with sizes reaching 109 variables arising from asset liability management and portfolio optimization.
This is a joint work with Andreas Grothey.
A scale-invariant moving finite element method is proposed for the
adaptive solution of nonlinear partial differential equations. The mesh
movement is based on a finite element discretisation of a scale-invariant
conservation principle incorporating a monitor function, while the time
discretisation of the resulting system of ordinary differential equations
may be carried out using a scale-invariant time-stepping. The accuracy and
reliability of the algorithm is tested against exact self-similar
solutions, where available, and a state-of-the-art $h$-refinement scheme
for a range of second and fourth order problems with moving boundaries.
The monitor functions used are the dependent variable and a monitor
related to the surface area of the solution manifold.
First, I'll give a very brief update on our nonlinear Krylov accelerator for the usual Modified Newton's method. This simple accelerator, which I devised and Neil Carlson implemented as a simple two page Fortran add-on to our implicit stiff ODEs solver, has been robust, simple, cheap, and automatic on all our moving node computations since 1990. I publicize further experience with it here, by us and by others in diverse fields, because it is proving to be of great general usefulness, especially for solving nonlinear evolutionary PDEs or a smooth succession of steady states.
Second, I'll report on some recent work in computerized tomography from X-rays. With colored computer graphics I'll explain how the standard "filtered backprojection" method works for the classical 2D parallel beam problem. Then with that backprojection kernel function H(t) we'll use an integral "change of variables" approach for the 2D fan-beam geometry. Finally, we turn to the tomographic reconstruction of a 3D object f(x,y,z) from a wrapped around cylindical 2D array of detectors opposite a 2D array of sources, such as occurs in PET (positron-emission tomography) or in very-wide-cone-beam tomography with a finely spaced source spiral.
The famous Eckart-Young Theorem states that the (normwise) condition number of a matrix is equal to the reciprocal of its distance to the nearest singular matrix. In a recent paper we proved an extension of this to a number of structures common in matrix analysis, i.e. the structured condition number is equal to the reciprocal of the structured distance to the nearest singular matrix. In this talk we present a number of related results on structured eigenvalue perturbations and structured pseudospectra, for normwise and for componentwise perturbations.
Current methods for globalizing Newton's Method for solving systems of nonlinear equations fall back on steps biased towards the steepest descent direction (e.g. Levenberg/Marquardt, Trust regions, Cauchy point dog-legs etc.), when there is difficulty in making progress. This can occasionally lead to very slow convergence when short steps are repeatedly taken.
This talk looks at alternative strategies based on searching curved arcs related to Davidenko trajectories. Near to manifolds on which the Jacobian matrix is singular, certain conjugate steps are also interleaved, based on identifying a Pareto optimal solution.
Preliminary limited numerical experiments indicate that this approach is very effective, with rapid and ultimately second order convergence in almost all cases. It is hoped to present more detailed numerical evidence when the talk is given. The new ideas can also be incorporated with more recent ideas such as multifilters or nonmonotonic line searches without difficulty, although it may be that there is no longer much to gain by doing this.
Abstract 1 Another Orthogonal Matrix
A householder reflection and a suitable product of Givens rotations are two well known examples of an
orthogonal matrix with given first column. We present another way to produce such a matrix and apply
it to produce a "fast Givens" method to compute the R factor of A, A = QR. This approach avoids the danger
of under/overflow.
(joint work with Eric Barszcz)
Abstract 2 An application of Pfaff's Theorem (on skew-symmetric matrices)
There are no constraints on the eigenvalues of a product of two real symmetric matrices but what about the
product of two real skew-symmetric matrices?
(joint work with A Dubrulle)
When studying invariant quantities and stability of discretization schemes for time-dependent differential equations(ODEs), Backward error analysis (BEA) has proven itself an invaluable tool. Although the established results give very accurate estimates, the known results are generally given for "worst case" scenarios. By taking into account the structure of the differential equations themselves further improvements on the estimates can be established, and sharper estimates on invariant quantities and stability can be established. In the talk I will give an overview of BEA, and its applications as it stands emphasizing the shortcoming in the estimates. An alternative strategy is then proposed overcoming these shortcomings, resulting in a tool which when used in connection with results from dynamical systems theory gives a very good insight into the dynamics of discretized differential equations.
The convergence of iterative methods for solving the linear system Ax = b with a Hermitian positive definite matrix A depends on the condition number of A: the smaller the latter the faster the former. Hence the idea to multiply the equation by a matrix T such that the condition number of TA is much smaller than that of A. The above is a common interpretation of the technique known as preconditioning, the matrix T being referred to as the preconditioner for A.
The eigenvalue computation does not seem to benefit from the direct application of such a technique. Indeed, what is the point in replacing the standard eigenvalue problem Ax = λx with the generalized one TAx = λTx that does not appear to be any easier to solve? It is hardly surprising then that modern eigensolvers, such as ARPACK, do not use preconditioning directly. Instead, an option is provided to accelerate the convergence to the sought eigenpairs by applying spectral transformation, which generally requires the user to supply a subroutine that solves the system (A−σI)y = z, and it is entirely up to the user to employ preconditioning if they opt to solve this system iteratively.
In this talk we discuss some alternative views on the preconditioning technique that are more general and more useful in the convergence analysis of iterative methods and that show, in particular, that the direct preconditioning approach does make sense in eigenvalue computation. We review some iterative algorithms that can benefit from the direct preconditioning, present available convergence results and demonstrate both theoretically and numerically that the direct preconditioning approach has advantages over the two-level approach. Finally, we discuss the role that preconditioning can play in the a posteriori error analysis, present some a posteriori error estimates that use preconditioning and compare them with commonly used estimates in terms of the Euclidean norm of residual.
We consider the problem of computing ratings using the results of games (such as chess) played between a set of n players, and show how this problem can be reduced to computing the positive eigenvectors corresponding to the dominant eigenvalues of certain n by n matrices. There is a close connection with the stationary probability distributions of certain Markov chains. In practice, if n is large, then the matrices involved will be sparse, and the power method may be used to solve the eigenvalue problems efficiently.
Many industrial flow problems, expecially in the minerals and process
industries, are very complex, with strong interactions between phases
and components, and with very different length and time scales. This
presentation outlines the algorithms used in the CFX-5 software, and
describes the extension of its coupled solver approach to some
multi-scale industrial problems. including Population Balance modelling
to predict size distributions of a disperse phase. These results will be
illustrated on some practical industrial problems.
Spectral projections enjoy high order convergence for globally smooth functions. However, a single discontinuity introduces O(1) spurious oscillations near the discontinuity and reduces the high order convergence rate to first order, Gibbs' Phenomena. Although a direct expansion of the function in terms of its global moments yields this low order approximation, high resolution information is retained in the global moments. Two techniques for the resolution of the Gibbs' phenomenon are discussed, filtering and reprojection methods. An adaptive filter with optimal joint time-frequency localization is presented, which recovers a function from its N term Fourier projection within the error bound \exp(-Nd(x)), where d(x) is the distance from the point being recovered to the nearest discontinuity. Symmetric filtering, however, must sacrifice accuracy when approaching a discontinuity. To overcome this limitation, Gegenbauer postprocessing was introduced by Gottlieb, Shu, et al, which recovers a function from its N term Fourier projection within the error bound \exp(-N). An extension of Gegenbauer postprocessing with improved convergence and robustness properties is presented, the robust Gibbs complements. Filtering and reprojection methods will be put in a unifying framework, and their properties such as robustness and computational cost contrasted. This research was conducted jointly with Eitan Tadmor and Anne Gelb.
The use of weighted matchings is becoming increasingly standard in the
solution of sparse linear systems. While non-symmetric permutations based on these
matchings have been the state-of-the-art for
several years (especially for direct solvers), approaches for symmetric
matrices have only recently gained attention.
\\
In this talk we discuss results of our work on using weighted matchings in
the preconditioning of symmetric indefinite linear systems, following ideas
introduced by Duff and Gilbert. In order to maintain symmetry,
the weighted matching is symmetrized and the cycle structure of the
resulting matching is used to build reorderings that form small diagonal
blocks from the matched entries.
\\
For the preconditioning we investigated two approaches. One is an
incomplete $LDL^{T}$ preconditioning, that chooses 1x1 or 2x2 diagonal pivots
based on a simple tridiagonal pivoting criterion. The second approach
targets distributed computing, and is based on factorized sparse approximate
inverses, whose existence, in turn, is based on the existence of an $LDL^{T}$
factorization. Results for a number of comprehensive test sets are given,
including comparisons with sparse direct solvers and other preconditioning
approaches.
An interior-point method for solving mathematical programs with
equilibrium constraints (MPECs) is proposed. At each iteration of the
algorithm, a single primal-dual step is computed from each subproblem of
a sequence. Each subproblem is defined as a relaxation of the MPEC with
a nonempty strictly feasible region. In contrast to previous
approaches, the proposed relaxation scheme preserves the nonempty strict
feasibility of each subproblem even in the limit. Local and superlinear
convergence of the algorithm is proved even with a less restrictive
strict complementarity condition than the standard one. Moreover,
mechanisms for inducing global convergence in practice are proposed.
Numerical results on the MacMPEC test problem set demonstrate the
fast-local convergence properties of the algorithm.
The trapezoidal rule for numerical integration is remarkably accurate when
the integrand under consideration is smooth and periodic. In this
situation it is superior to more sophisticated methods like Simpson's rule
and even the Gauss-Legendre rule. In the first part of the talk we
discuss this phenomenon and give a few elementary examples. In the second
part of the talk we discuss the application of this idea to the numerical
evaluation of contour integrals in the complex plane.
Demonstrations involving numerical differentiation, the computation
of special functions, and the inversion of the Laplace transform will be
presented.
Plane Couette flow - the flow between two infinite parallel plates moving in opposite directions -
undergoes a discontinuous transition from laminar flow to turbulence as the Reynolds number is
increased. Due to its simplicity, this flow has long served as one of the canonical examples for understanding shear turbulence and the subcritical transition process typical of channel and pipe flows. Only recently was it discovered in very large aspect ratio experiments that this flow also exhibits remarkable pattern formation near transition. Steady, spatially periodic patterns of distinct regions of turbulent and laminar flow emerges spontaneously from uniform turbulence as the Reynolds number is decreased. The length scale of these patterns is more than an order of magnitude larger than the plate separation. It now appears that turbulent-laminar patterns are inevitable intermediate states on the route from turbulent to laminar flow in many shear flows. I will explain how we have overcome the difficulty of simulating these large scale patterns and show results from studies of three types of patterns: periodic, localized, and intermittent.
Sparse grids yield numerical solutions to PDEs with a
significantly reduced number of degrees of freedom. The relative
benefit increases with the dimensionality of the problem, which makes
multi-factor models for financial derivatives computationally tractable.
An outline of a convergence proof for the so called combination
technique will be given for a finite difference discretisation of the
heat equation, for which sharp error bounds can be shown.
Numerical examples demonstrate that by an adaptive (heuristic)
choice of the subspaces European and American options with up to thirty
(and most likely many more) independent variables can be priced with
high accuracy.
The computation of flows of compressible fluids will be
discussed, exploiting the symmetric form of the equations describing
compressible flow.
A cell is a wonderously complex object. In this talk I will
give an overview of some of the mathematical frameworks that are needed
in order to make progress to understanding the complex dynamics of a
cell. The talk will consist of a directed random walk through discrete
Markov processes, stochastic differential equations, anomalous diffusion
and fractional differential equations.
An essential first step in many problems of numerical analysis and
computer graphics is to cover a region with a reasonably regular mesh.
We describe a short MATLAB code that begins with a "distance function"
to describe the region: $d(x)$ is the distance to the boundary
(with d
The talk will start with an introduction to recent development in Mathematica, with emphasis on numerical computing. This will be followed by a discussion of graph drawing algorithms for the display of relational information, in particular force directed algorithms. The talk will show that by employing multilevel approach and octree data structure, it is possible to achieve fast display of very large relational information, without compromising the quality.
We consider the solution of a linear system of equations using the GMRES iterative method. In some applications, performing inexact matrix-vector products in this method may be interesting, provided that a reasonable convergence of GMRES is achieved. A GMRES algorithm where the matrix vector product is performed inexactly is termed ”inexact GMRES algorithm”. An application of this idea occurs in computational electromagnetics, where the fast multipole method provides approximations of the matrix-vector product within a user-defined precision, and where these inaccurate matrix-vector products are all the more cheaper (in terms of CPU time) as the user-defined precision is low. The key point is then to design a control strategy of the accuracy of the matrix-vector product so that the GMRES converges better in the sense that 1) the inexact method achieves a satisfactory limiting accuracy, 2) within a reasonable number of steps.
\\
In [1], a relaxation strategy is proposed for general systems and validated on a large set of numerical experiments. This work is based on heuristic considerations and proposes a strategy that enables a convergence of the GMRES iterates $x_{k}$ within a relative normwise backward error $\frac{\|b−Ax_{k}\|}{\|A\| \|x_{k}\| + \|b\|}$ less than a prescribed quantity $\eta$ > 0, on a significant number of numerical experiments. Similar strategies have been applied to the solution of device simulation problems using domain decomposition [2] and to the preconditioning of a radiation diffusion problem in [5].
\\
A step toward a theoretical explanation of the observed behaviour of the inexact GMRES is proposed in [3, 4]. In this talk, we show that in spite of this considerable theoretical study, the experimental work of [1] is not fully understood yet. We give an overview of the questions that still remains open both in exact arithmetic and in floating-point arithmetic, and we provide some insights into the solution of some of them. Possible applications of this work for the preconditioned GMRES method, when the matrix-vector product is accurate but the preconditioning operation is approximate, are also investigated, based on [3].
\\
\\
References
\\
[1] A. Bouras and V. Frayss´e. Inexact matrix-vector products in Krylov methods for solving linear systems: a relaxation strategy. SIAM Journal on Matrix Analysis and Applications, 2004. To appear.
\\
[2] A. Bouras, V. Frayss´e, and L. Giraud. A relaxation strategy for inner-outer linear solvers in domain decomposition methods. Technical Report TR/PA/00/17, CERFACS, Toulouse, France, 2000.
\\
[3] V. Simoncini and D. B. Szyld. Theory of inexact Krylov subspace methods and applications to scientific computing. SIAM Journal Scientific Computing, 25:454–477, 2003.
\\
[4] J. van den Eshof and G. L. G. Sleijpen. Inexact Krylov subspace methods for linear systems. SIAM Journal on Matrix Analysis and Applications, February 2004. To appear.
\\
[5] J. S. Warsa, M. Benzi, T. A. Warein, and J. E. Morel. Preconditioning a mixed discontinuous finite element method for radiation diffusion. Numerical Linear Algebra with Applications, 2004. To appear.
In recent years, there has been considerable interest, especially in the context of
fluid-dynamics, in nonconforming finite element methods that are based on discontinuous
piecewise polynomial approximation spaces; such approaches are referred to as discontinuous
Galerkin (DG) methods. The main advantages of these methods lie in their conservation properties, their ability to treat a wide range of problems within the same unified framework, and their great flexibility in the mesh-design. Indeed, DG methods can easily handle non-matching grids and non-uniform, even anisotropic, polynomial approximation degrees. Moreover, orthogonal bases can easily be constructed which lead to diagonal mass matrices; this is particularly advantageous in unsteady problems. Finally, in combination with block-type preconditioners, DG methods can easily be parallelized.
\\
\\
In this talk, we introduce DG discretizations of mixed field and potential-based formulations of
eddy current problems in the time-harmonic regime. For the electric field formulation, the
divergence-free constraint within non-conductive regions is imposed by means of a Lagrange
multiplier. This allows for the correct capturing of edge and corner singularities in polyhedral domains; in contrast, additional Sobolev regularity must be assumed in the DG formulation, and their conforming counterparts, when regularization techniques are employed. In particular, we present a mixed method involving discontinuous $P^\ell-P^\ell$ elements, which includes a normal jump stabilization term, and a non-stabilized variant employing discontinuous $P^\ell-P^{\ell+1}$ elements.The first formulation delivers optimal convergence rates for the vector-valued unknowns in a suitable energy norm, while the second (non-stabilized) formulation is designed to yield optimal convergence rates in both the $L^2$--norm, as well as in a suitable energy norm. For this latter method, we also develop the {\em a posteriori} error estimation of the mixed DG approximation of the Maxwell operator. Indeed, by employing suitable Helmholtz decompositions of the error, together with the conservation properties of the underlying method, computable upper bounds on the error, measured in terms of the energy norm, are derived.
\\
\\
Numerical examples illustrating the performance of the proposed methods will be presented; here,
both conforming and non-conforming (irregular) meshes will be employed. Our theoretical and
numerical results indicate that the proposed DG methods provide promising alternatives to standard conforming schemes based on edge finite elements.
The satisfiability (SAT) problem is a central problem in mathematical
logic, computing theory, and artificial intelligence. We consider
instances of SAT specified by a set of boolean variables and a
propositional formula in conjunctive normal form. Given such an instance,
the SAT problem asks whether there is a truth assignment to the variables
such that the formula is satisfied. It is well known that SAT is in
general NP-complete, although several important special cases can be
solved in polynomial time. Extending the work of de Klerk, Warners and van
Maaren, we present new linearly sized semidefinite programming (SDP)
relaxations arising from a recently introduced paradigm of higher
semidefinite liftings for discrete optimization problems. These
relaxations yield truth assignments satisfying the SAT instance if a
feasible matrix of sufficiently low rank is computed. The sufficient rank
values differ between relaxations and can be viewed as a measure of the
relative strength of each relaxation. The SDP relaxations also have the
ability to prove that a given SAT formula is unsatisfiable. Computational
results on hard instances from the SAT Competition 2003 show that the SDP
approach has the potential to complement existing techniques for SAT.
We calculate an analytic value for the correlation coefficient between a geometric, or exponential, Brownian motion and its time-average, a novelty being our use of divided differences to elucidate formulae. This provides a simple approximation for the value of certain Asian options regarding them as exchange options. We also illustrate that the higher moments of the time-average can be expressed neatly as divided differences of the exponential function via the Hermite-Genocchi integral relation, as well as demonstrating that these expressions agree with those obtained by Oshanin and Yor when the drift term vanishes.
The formation of steady patterns in one space dimension is generically
governed, at small amplitude, by the Ginzburg-Landau equation.
But in systems with a conserved quantity, there is a large-scale neutral
mode that must be included in the asymptotic analysis for pattern
formation near onset. The usual Ginzburg-Landau equation for the amplitude
of the pattern is then coupled to an equation for the large-scale mode.
\\
These amplitude equations show that for certain parameters all regular
periodic patterns are unstable. Beyond the stability boundary, there
exist stable stationary solutions in the form of spatially modulated
patterns or localised patterns. Many more exotic localised states are
found for patterns in two dimensions.
\\
Applications of the theory include convection in a magnetic field,
providing an understanding of localised states seen in numerical
simulations.
The lattice Boltzmann equation has been used successfully used to simulate
nearly incompressible flows using an isothermal equation of state, but
much less work has been done to determine stable implementations for other
equations of state. The commonly used nine velocity lattice Boltzmann
equation supports three non-hydrodynamic or "ghost'' modes in addition to
the macroscopic density, momentum, and stress modes. The equilibrium value
of one non-hydrodynamic mode is not constrained by the continuum equations
at Navier-Stokes order in the Chapman-Enskog expansion. Instead, we show
that it must be chosen to eliminate a high wavenumber instability. For
general barotropic equations of state the resulting stable equilibria do
not coincide with a truncated expansion in Hermite polynomials, and need
not be positive or even sign-definite as one would expect from arguments
based on entropy extremisation. An alternative approach tries to suppress
the instability by enhancing the damping the non-hydrodynamic modes using
a collision operator with multiple relaxation times instead of the common
single relaxation time BGK collision operator. However, the resulting
scheme fails to converge to the correct incompressible limit if the
non-hydrodynamic relaxation times are fixed in lattice units. Instead we
show that they must scale with the Mach number in the same way as the
stress relaxation time.
Consider approximating a set of discretely defined values $f_{1}, \ldots , f_{m}$ say at $x=x_{1}, x_{2}, \ldots, x_{m}$, with a chosen approximating form. Given prior knowledge that noise is present and that some might be outliers, a standard least squares approach based on $l_{2}$ norm of the error $\epsilon$ may well provide poor estimates. We instead consider a least squares approach based on a modified measure of the form $\tilde{\epsilon} = \epsilon (1+c^{2}\epsilon^{2})^{-\frac{1}{2}}$, where $c$ is a constant to be fixed.
\\
The choice of the constant $c$ in this estimator has a significant effect on the performance of the estimator both in terms of its algorithmic convergence to a solution and its ability to cope effectively with outliers. Given a prior estimate of the likely standard deviation of the noise in the data, we wish to determine a value of $c$ such that the estimator behaves like a robust estimator when outliers are present but like a least squares estimator otherwise.
\\
We describe approaches to determining suitable values of $c$ and illustrate their effectiveness on approximation with polynomial and radial basis functions. We also describe algorithms for computing the estimates based on an iteratively weighted linear least squares scheme.