A Proof of the Stability of the Spectral Difference Method for All Orders of Accuracy

Abstract  While second order methods for computational simulations of fluid flow provide the basis of widely used commercial software,
there is a need for higher order methods for more accurate simulations of turbulent and vortex dominated flows. The discontinuous
Galerkin (DG) method is the subject of much current research toward this goal. The spectral difference (SD) method has recently
emerged as a promising alternative which can reduce the computational costs of higher order simulations. There remains some
questions, however, about the stability of the SD method. This paper presents a proof that for the case of one dimensional
linear advection the SD method is stable for all orders of accuracy in a norm of Sobolev type, provided that the interior
fluxes collocation points are placed at the zeros of the corresponding Legendre polynomial.

• Content Type Journal Article
• DOI 10.1007/s10915-009-9339-4
• Authors
  
  
  • Antony Jameson, Stanford University Department of Aeronautics and Astronautics Stanford CA 94305 USA
  
  

• Journal Journal of Scientific Computing
• Online ISSN 1573-7691
• Print ISSN 0885-7474

Published by

Original source : http://www.springerlink.com/content/362m32855p7125...

Mathematical analysis of the Navier-Stokes/Darcy coupling

We consider a differential system based on the coupling of the Navier-Stokes and Darcy equations for modeling the interaction between surface and porous media flows. We formulate the problem as an interface equation, we analyze the associated (nonlinear) Steklov-Poincare' operators, and we prove its wellposedness. We propose and analyze iterative methods to solve a conforming finite element approximation of the coupled problem.

Published by

Original source : http://infoscience.epfl.ch/record/143748...

Quantum Computing Resource Estimate of Molecular Energy Simulation. (arXiv:1001.3855v1 [quant-ph])

Over the last century, ingenious physical and mathematical insights paired
with rapidly advancing technology have allowed the field of quantum chemistry
to advance dramatically. However, efficient methods for the exact simulation of
quantum systems on classical computers do not exist. The present paper reports
an extension of one of the authors' previous work [Aspuru-Guzik et al., Science
{309} p. 1704, (2005)] where it was shown that the chemical Hamiltonian can be
efficiently simulated using a quantum computer. In particular, we report in
detail how a set of molecular integrals can be used to create a quantum circuit
that allows the energy of a molecular system with fixed nuclear geometry to be
extracted using the phase estimation algorithm proposed by Abrams and Lloyd
[Phys. Rev. Lett. {83} p. 5165, (1999)]. We extend several known results
related to this idea and present numerical examples of the state preparation
procedure required in the algorithm. With future quantum devices in mind, we
provide a complete example using the Hydrogen molecule, of how a chemical
Hamiltonian can be simulated using a quantum computer. Some of the results we
present here represent an extension of our recent collaboration appearing in B.
P. Lanyon et al. [Nature Chem., advance online publication, doi:
10.1038/nchem.483 (2010)].

Published by

Original source : http://arxiv.org/abs/1001.3855...

Quantum Computing with Superqubits. (arXiv:1001.3753v1 [hep-th])

We analyze some aspects of quantum computing with super-qubits (squbits). We
propose the analogue of a superfield formalism, and give a physical
interpretation for the Grassmann coefficients in the squbit expansion as
fermionic creation operators of an auxiliary quantum system. In the simplest
case the squbit is a superposition of one Bose X Bose and one Fermi X Fermi
state, and its norm is invariant under a U(2) group realized with
Clifford-valued matrices. This case can be generalized to a superposition of
n_B bosonic and n_F fermionic states, with a norm invariant under U(n_B + n_F).
Entanglement between squbits, super quantum gates and teleportation are
discussed.

Published by

Original source : http://arxiv.org/abs/1001.3753...

Effective polar potential in the central force Schrodinger equation. (arXiv:1001.3693v1 [quant-ph])

The angular part of the Schrodinger equation for a central potential is
brought to the one-dimensional 'Schrodinger form' where one has a kinetic
energy plus potential energy terms. The resulting polar potential is seen to be
a family of potentials characterized by the square of the magnetic quantum
number m. It is demonstrated that this potential can be viewed as a confining
potential that attempts to confine the particle to the xy-plane, with a
strength that increases with increasing m. Linking the solutions of the
equation to the conventional solutions of the angular equation, i.e. the
associated Legendre functions, we show that the variation in the spatial
distribution of the latter for different values of the orbital angular quantum
number l can be viewed as being a result of 'squeezing' with different
strengths by the introduced 'polar potential'.

Published by

Original source : http://arxiv.org/abs/1001.3693...

The concept of minimized integrated exponential error for low dispersion and low dissipation schemes

We devise two novel techniques to optimize parameters which regulate dispersion and dissipation effects in numerical methods using the notion that dissipation neutralizes dispersion. These techniques are baptized as the minimized integrated error for low dispersion and low dissipation (MIELDLD) and the minimized integrated exponential error for low dispersion and low dissipation (MIEELDLD).These two techniques of optimization have an advantage over the concept of minimized integrated square difference error (MISDE), especially in the case when more than one optimal cfl is obtained, out of which only one of these values satisfy the shift condition. For instance, when MISDE is applied to the 1-D Fromm's scheme, we have obtained two optimal cfl numbers: 0.28 and 1.0. However, it is known that Fromm's scheme satisfies shift condition only at r=1.0. Using MIELDLD and MIEELDLD, the optimal cfl of Fromm's scheme is computed as 1.0.We show that like the MISDE concept, both the techniques MIELDLD and MIEELDLD are effective to control dissipation and dispersion. The condition [nu]2>4µ is satisfied for all these three techniques of optimization, where [nu] and µ are parameters present in the Korteweg-de-Vries-Burgers equation.The optimal cfl number for some numerical schemes namely Lax-Wendroff, Beam-Warming, Crowley and Upwind Leap-Frog when discretized by the 1-D linear advection equation is computed. The optimal cfl number obtained is in agreement with the shift condition. Some numerical experiments in 1-D have been performed which consist of discontinuities and shocks. The dissipation and dispersion errors at some different cfl numbers for these experiments are quantified. Copyright © 2010 John Wiley & Sons, Ltd.

Published by

Original source : http://dx.doi.org/10.1002%2Ffld.2206...

Compact embeddings of broken Sobolev spaces and applications

In this paper, we present several extensions of theoretical tools for the analysis of discontinuous Galerkin (DG) method beyond the linear case. We define broken Sobolev spaces for Sobolev indices in [1, ), and we prove generalizations of many techniques of classical analysis in Sobolev spaces. Our targeted application is the convergence analysis for DG discretizations of energy minimization problems of the calculus of variations. Our main tool in this analysis is a theorem which permits the extraction of a ‘weakly’ converging subsequence of a family of discrete solutions and which shows that any ‘weak limit’ is a Sobolev function. As a second application, we compute the optimal embedding constants in broken Sobolev–Poincaré inequalities.

Published by

Original source : http://imajna.oxfordjournals.org/cgi/content/short...

Improved contour integral methods for parabolic PDEs

One way of computing the matrix exponential that arises in semidiscrete parabolic partial differential equations is via the Dunford–Cauchy integral formula. The integral is approximated by the trapezoidal or midpoint rules on a Hankel contour defined by a suitable change of variables. In a recent paper by Weideman & Trefethen (2007, Math. Comput., 76, 1341–1356) two widely used contours were analysed. Estimates for the optimal parameters that define these contours were proposed. In this paper this analysis is extended in two directions. First, the effect of roundoff error is now included in the error model. Second, we extend the results to the case of a model convection–diffusion equation, where a large convective term causes the matrix to be highly non-normal.

Published by

Original source : http://imajna.oxfordjournals.org/cgi/content/short...

Discretization error and modelling error in the context of the rapid inflation of hyperelastic membranes

The computational modelling of the rapid large inflation of hyperelastic circular sheets modelled as axisymmetric membranes is treated, with the aim of estimating engineering quantities of interest and their errors. Fine (involving inertia terms) and coarse (quasi-static) models of the inflation are considered and, using goal-oriented techniques, both modelling and discretization errors are estimated. Numerical results involving only discretization errors for the quasi-static problem and both modelling and discretization errors for the dynamic problem are presented.

Published by

Original source : http://imajna.oxfordjournals.org/cgi/content/short...

On the convergence of a wide range of trust region methods for unconstrained optimization

We consider trust region methods for seeking the unconstrained minimum of an objective function F(
),
, when the gradient
(
),
, is available. The methods are iterative with
₁ being given. The new vector of variables
_k+1 is derived from a quadratic approximation to F that interpolates F(
_k) and
, where k is the iteration number. The second derivative matrix of the quadratic approximation, B_k say, can be indefinite, because the approximation is employed only if the vector of variables
satisfies
, where _k is a "trust region radius" that is adjusted automatically. Thus the approximation is useful if
is sufficiently large and if ||B_k|| and _k are sufficiently small. It is proved under mild assumptions that the condition
is achieved after a finite number of iterations, where is any given positive constant, and then it is usual to end the calculation. The assumptions include a Lipschitz condition on
and also F has to be bounded below. The termination property is established in a single theorem that applies to a wide range of trust region methods that force the sequence F(
_k), k = 1, 2, 3, ..., to decrease monotonically. Any choice of each symmetric matrix B_k is allowed, provided that ||B_k|| is bounded above by a constant multiple of k.

Published by

Original source : http://imajna.oxfordjournals.org/cgi/content/short...

A survey of results on the q-Bernstein polynomials

It is now nearly a century since S. N. Bernstein introduced his well-known polynomials. This paper is concerned with generalizations of the Bernstein polynomials, mainly with the so called q-Bernstein polynomials. These are due to the author of this paper and are based on the q integers. They reduce to the Bernstein polynomials when we put q = 1 and share the shape-preserving properties of the Bernstein polynomials when q (0, 1). This paper also describes another earlier generalization of the Bernstein polynomials, a sequence of rational functions that are also based on the q-integers, proposed by A. Lupas, and two even earlier generalizations due to D. D. Stancu. The present author summarizes various results, due to a number of authors, that are concerned with the q-Bernstein polynomials and with Stancu's two generalizations.

Published by

Original source : http://imajna.oxfordjournals.org/cgi/content/short...

ADI orthogonal spline collocation methods for parabolic partial integro-differential equations

Alternating direction implicit (ADI) orthogonal spline collocation schemes are formulated and analysed for a class of partial integro-differential equations of parabolic type. These techniques are based on the -method, for [1/2, 1], (where = 1 yields the backward Euler method and = 1/2 yields the Crank–Nicolson method) and the second-order backward differentiation formula (BDF) method. For each method, optimal estimates in various norms at each time step are derived and confirmed by results of numerical experiments.

Published by

Original source : http://imajna.oxfordjournals.org/cgi/content/short...

Asymptotic behaviour in linear least squares problems

The asymptotic behaviour of a class of least squares problems when subjected to structured perturbations is considered. It is permitted that the number of rows (observations) in the design matrix can be unbounded while the number of degrees of freedom (variables) is fixed. It is shown that for certain classes of random data the solution sensitivity depends asymptotically on the condition number of the design matrix rather than on its square, which is the generic result for inconsistent systems when the norm of the residual is not small. Extension of these results to the case where the perturbations are due to rounding errors is considered.

Published by

Original source : http://imajna.oxfordjournals.org/cgi/content/short...

The convection-diffusion Petrov-Galerkin story

The term ‘Petrov–Galerkin method’ is probably due to Ron Mitchell and his collaborators, and he was certainly very active in studying the application of finite-element methods to second-order partial differential equations ‘with significant first derivatives’. Our aim in the present paper is to trace links between such early methods and the more recent discontinuous Galerkin methods—not only the methods but also their analysis. Also as Mitchell, like the author, was initially steeped in finite-difference methods, we shall sometimes use their manipulation in our analysis.

Published by

Original source : http://imajna.oxfordjournals.org/cgi/content/short...

Maximum-norm error analysis of a numerical solution via Laplace transformation and quadrature of a fractional-order evolution equation

In a previous paper, McLean & Thomée (2009, J. Integr. Equ. Appl. (to appear)), we studied three numerical methods for the discretization in time of a fractional-order evolution equation in a Banach space framework. Each of the methods applied a quadrature rule to a contour integral representation of the solution in the complex plane, where for each quadrature point an elliptic boundary-value problem had to be solved to determine the value of the integrand. The first two methods involved the Laplace transform of the forcing term, but the third did not. We analysed both the quadrature error and the error arising from a spatial discretization by finite elements, measured in the L₂-norm. The present work extends our earlier results by proving error bounds in the technically more complicated case of the maximum norm. We also establish new regularity properties for the exact solution that are needed for our analysis.

Published by

Original source : http://imajna.oxfordjournals.org/cgi/content/short...

Periodic reordering

For many networks in nature, science and technology, it is possible to order the nodes so that most links are short-range, connecting near-neighbours, and relatively few long-range links, or shortcuts, are present. Given a network as a set of observed links (interactions), the task of finding an ordering of the nodes that reveals such a range-dependent structure is closely related to some sparse matrix reordering problems arising in scientific computation. The spectral, or Fiedler vector, approach for sparse matrix reordering has successfully been applied to biological data sets, revealing useful structures and subpatterns. In this work we argue that a periodic analogue of the standard reordering task is also highly relevant. Here, rather than encouraging nonzeros only to lie close to the diagonal of a suitably ordered adjacency matrix, we also allow them to inhabit the off-diagonal corners. Indeed, for the classic small-world model of Watts & Strogatz (1998, Collective dynamics of ‘small-world’ networks. Nature, 393, 440–442) this type of periodic structure is inherent. We therefore devise and test a new spectral algorithm for periodic reordering. By generalizing the range-dependent random graph class of Grindrod (2002, Range-dependent random graphs and their application to modeling large small-world proteome datasets. Phys. Rev. E, 66, 066702-1–066702-7) to the periodic case, we can also construct a computable likelihood ratio that suggests whether a given network is inherently linear or periodic. Tests on synthetic data show that the new algorithm can detect periodic structure, even in the presence of noise. Further experiments on real biological data sets then show that some networks are better regarded as periodic than linear. Hence, we find both qualitative (reordered networks plots) and quantitative (likelihood ratios) evidence of periodicity in biological networks.

Published by

Original source : http://imajna.oxfordjournals.org/cgi/content/short...

On the approximation and efficient evaluation of integral terms in PDE models of cell adhesion

Recently, a nonlocal term has been introduced in time-dependent partial differential equation (PDE) models of cell migration in tissue. This term is used to model adhesive effects between cells and also between cells and the extracellular matrix. We assume periodic boundary conditions for the model and that the PDE system is discretized following the method of lines and using a finite-volume scheme on a uniform grid in space. For high-resolution simulations of the PDE system an efficient evaluation of the approximation of the nonlocal term is crucial. For one and two spatial dimensions we develop suitable approximations of the nonlocal term and evaluate these using fast Fourier transform (FFT) techniques. Comprehensive numerical tests show the accuracy and efficiency of our approach. We also demonstrate the impact of the proposed scheme for the treatment of the nonlocal term on simulation times for a differential cell adhesion model. We discuss extensions and applicability of our work to systems with nonperiodic boundary conditions and for other nonlocal PDE models from mathematical biology.

Published by

Original source : http://imajna.oxfordjournals.org/cgi/content/short...

Comparisons between pseudospectral and radial basis function derivative approximations

Fourier-based pseudospectral (PS) methods have been used since the 1970s for obtaining spectrally accurate solutions to partial differential equations (PDEs) in periodic geometries. Radial basis functions (RBFs) were introduced about the same time for interpolation on scattered nodes in irregular geometries. As was later recognized, they can also be used for accurate numerical solution of PDEs. Although the main strength of RBFs lies in their outstanding geometric flexibility, also offering possibilities of spectral accuracy over irregularly shaped finite domains, it is still of interest to compare them against Fourier-based PS methods in the extremely simple geometries (infinite or periodic domains) where the latter can also be used. Mostly by means of heuristic arguments and graphical illustrations based on Fourier analysis and numerical experiments, we show that there are notable differences (more pronounced in increasing numbers of dimensions) in how the two spectral approaches approximate derivatives.

Published by

Original source : http://imajna.oxfordjournals.org/cgi/content/short...

Optimal stability for trapezoidal-backward difference split-steps

The marginal stability of the trapezoidal method makes it dangerous to use for highly non-linear oscillations. Damping is provided by backward differences. The split-step combination (t trapezoidal, (1 – )t for BDF2) retains second-order accuracy. The ‘magic choice’
allows the same Jacobian for both steps, when Newton's method solves these implicit difference equations. That choice is known to give the smallest error constant, and we prove that
also gives the largest region of linearized stability.

Published by

Original source : http://imajna.oxfordjournals.org/cgi/content/short...

Trees, B-series and exponential integrators

Questions concerning the accuracy of numerical methods for differential equations are often analysed using B-series and other formulations based on rooted trees. The analysis of numerical methods, such as Rosenbrock and certain exponential methods, requires an additional algebraic structure to represent the direct use of Jacobian matrices in the computation. It is shown how this can be done within a context containing a broad review of the existing B-series formulation.

Published by

Original source : http://imajna.oxfordjournals.org/cgi/content/short...

The spectral problem for a class of highly oscillatory Fredholm integral operators

Let
be a linear, complex-symmetric Fredholm integral operator with highly oscillatory kernel K₀(x, y)e^i|x–y|. We study the spectral problem for large , showing that the spectrum consists of infinitely many discrete (complex) eigenvalues and give a precise description of the way in which they converge to the origin. In addition, we investigate the asymptotic properties of the solutions f = f(x;) to the associated Fredholm integral equation f = µ
f + a as $$omega o mathrm{infty }$$, thus refining a classical result by Ursell. Possible extensions of these results to highly oscillatory Fredholm integral operators with more general highly oscillating kernels are also discussed.

Published by

Original source : http://imajna.oxfordjournals.org/cgi/content/short...

A preconditioned Newton algorithm for the nearest correlation matrix

Various methods have been developed for computing the correlation matrix nearest in the Frobenius norm to a given matrix. We focus on a quadratically convergent Newton algorithm recently derived by Qi and Sun. Various improvements to the efficiency and reliability of the algorithm are introduced. Several of these relate to the linear algebra: the Newton equations are solved by minres instead of the conjugate gradient method, as it more quickly satisfies the inexact Newton condition; we apply a Jacobi preconditioner, which can be computed efficiently even though the coefficient matrix is not explicitly available; an efficient choice of eigensolver is identified; and a final scaling step is introduced to ensure that the returned matrix has unit diagonal. Potential difficulties caused by rounding errors in the Armijo line search are avoided by altering the step selection strategy. These and other improvements lead to a significant speed-up over the original algorithm and allow the solution of problems of dimension a few thousand in a few tens of minutes.

Published by

Original source : http://imajna.oxfordjournals.org/cgi/content/short...