Compatible coarsening in the multigraph algorithm

We present some heuristics incorporating the philosophy of compatible relaxation into an existing algebraic multigrid method, the so-called multigraph solver of Bank and Smith [Bank Randolph E., Kent Smith R. An algebraic multilevel multigraph algorithm. SIAM J Sci Comput 2002;25:1572–92]. In particular, approximate left and right eigenvectors of the iteration matrix for the smoother are used in computing both the sparsity pattern and the numerical values of the transfer matrices that correspond to restriction and prolongation. Some numerical examples illustrate the effectiveness of the procedure.     

A Cartesian Embedded Boundary Method for the Compressible Navier-Stokes Equations

We here generalize the embedded boundary method that was developed for boundary discretizations of the wave equation in second order formulation in Kreiss et al. (SIAM J. Numer. Anal. 40(5):1940–1967, 2002) and for the Euler equations of compressible fluid flow in Sjögreen and Peterson (Commun. Comput. Phys. 2:1199–1219, 2007), to the compressible Navier-Stokes equations. We describe the method and we implement it on a parallel computer. The implementation is tested for accuracy and correctness. The ability of the embedded boundary technique to resolve boundary layers is investigated by computing skin-friction profiles along the surfaces of the embedded objects. The accuracy is assessed by comparing the computed skin-friction profiles with those obtained by a body fitted discretization.     

A sixth-order finite difference WENO scheme for Hamilton–Jacobi equations

In this paper, a sixth-order finite difference weighted essentially non-oscillatory (WENO) scheme is developed to approximate the viscosity solution of the Hamilton–Jacobi equations. This new WENO scheme has the same spatial nodes as the classical fifth-order WENO scheme proposed by Jiang and Peng [Weighted ENO schemes for Hamilton–Jacobi equations, SIAM. J. Sci. Comput. 21 (2000), pp. 2126–2143] but can be as high as sixth-order accurate in smooth region while keeping sharp discontinuous transitions with no spurious oscillations near discontinuities. Extensive numerical experiments in one- and two-dimensional cases are carried out to illustrate the capability of the proposed scheme.     

Flux-based level-set method for two-phase flows on unstructured grids

In this paper we deal with the application of the flux-based level set method to moving interface computations on unstructured grids. The focus lies on the overcoming of the known difficulties of level set methods, e.g. accurate computations of important geometric properties, reliable and precise reinitialization of the level set function and the adaption of standard discretization methods to the moving boundary case. The basic building block of our approach is the high-resolution flux-based level set method for general advection equation (Frolkovi? and Mikula in SIAM J Sci Comput 29(2):579–597, 2007, Frolkovi? and Wehner in Comput Vis Sci 12(6):626–650, 2009). We extend this method for the problem of reinitialization of the level set function on unstructured grids by using quadratic interpolation to compute distances for nodes close to the interface. To realize numerical simulation for some applications with moving boundaries, we adapt the approach of ghost fluid method (Gibou and Fedkiw in J Comput Phys 202:577–601, 2005) for unstructured grids. The idea is to describe the development of the moving boundary with a level set formulation while the computational grid remains fixed and the boundary conditions are enforced using some extrapolation. Our main motivation is the numerical solution of two-phase incompressible flow problems. Additionally to previously mentioned steps, we introduce further numerical schemes in the framework of finite volume discretization for the flow. Possible jumps of the pressure and the directional derivative of velocity at the interface are modeled directly within the method using the approach of extended approximation spaces. Besides that, an algorithm for the computations of curvature is considered that exhibits the second order accuracy for some examples. Numerical experiments are provided for the presented methods.     

A Hybrid Second Order Scheme for Shallow Water Flows

We extend the well-balanced second order hybrid scheme developed in Donat and Martinez-Gavara (J. Sci. Comput., to appear) to the one-dimensional and two-dimensional shallow water system. We show that the scheme is exactly well-balanced for quiescent steady states, when a particular integration formula is employed, just as in the scalar models considered in Donat and Martinez-Gavara (J. Sci. Comput., to appear). A standard treatment of wet/dry fronts can easily be adapted, obtaining a robust scheme that produces well-resolved numerical solutions.     

A Comparison of Iterated Optimal Stopping and Local Policy Iteration for American Options Under Regime Switching

A theoretical analysis tool, iterated optimal stopping, has been used as the basis of a numerical algorithm for American options under regime switching (Le and Wang in SIAM J Control Optim 48(8):5193–5213, 2010). Similar methods have also been proposed for American options under jump diffusion (Bayraktar and Xing in Math Methods Oper Res 70:505–525, 2009) and Asian options under jump diffusion (Bayraktar and Xing in Math Fin 21(1):117–143, 2011). An alternative method, local policy iteration, has been suggested in Huang et al. (SIAM J Sci Comput 33(5):2144–2168, 2011), and Salmi and Toivanen (Appl Numer Math 61:821–831, 2011). Worst case upper bounds on the convergence rates of these two methods suggest that local policy iteration should be preferred over iterated optimal stopping (Huang et al. in SIAM J Sci Comput 33(5):2144–2168, 2011). In this article, numerical tests are presented which indicate that the observed performance of these two methods is consistent with the worst case upper bounds. In addition, while these two methods seem quite different, we show that either one can be converted into the other by a simple rearrangement of two loops.     

Kolmogorov random graphs only have trivial stable colorings

In this paper, we prove that random graphs only have trivial stable colorings. Our result improves Theorem 4.1 in [Proc. 20th IEEE Symp. on Foundations of Comput. Sci., 1979, pp. 39-46]. It can be viewed as an effective version of Corollary 2.13 in [SIAM J. Comput. 29 (2) (2000) 590-599]. As a byproduct, we also give an upper bound of the size of induced regular subgraphs in random graphs.     

Spatially adaptive techniques for level set methods and incompressible flow

Since the seminal work of [Sussman, M, Smereka P, Osher S. A level set approach for computing solutions to incompressible two-phase flow. J Comput Phys 1994;114:146–59] on coupling the level set method of [Osher S, Sethian J. Fronts propagating with curvature-dependent speed: algorithms based on Hamilton–Jacobi formulations. J Comput Phys 1988;79:12–49] to the equations for two-phase incompressible flow, there has been a great deal of interest in this area. That work demonstrated the most powerful aspects of the level set method, i.e. automatic handling of topological changes such as merging and pinching, as well as robust geometric information such as normals and curvature. Interestingly, this work also demonstrated the largest weakness of the level set method, i.e. mass or information loss characteristic of most Eulerian capturing techniques. In fact, [Sussman M, Smereka P, Osher S. A level set approach for computing solutions to incompressible two-phase flow. J Comput Phys 1994;114:146–59] introduced a partial differential equation for battling this weakness, without which their work would not have been possible. In this paper, we discuss both historical and most recent works focused on improving the computational accuracy of the level set method focusing in part on applications related to incompressible flow due to both of its popularity and stringent accuracy requirements. Thus, we discuss higher order accurate numerical methods such as Hamilton–Jacobi WENO [Jiang G-S, Peng D. Weighted ENO schemes for Hamilton–Jacobi equations. SIAM J Sci Comput 2000;21:2126–43], methods for maintaining a signed distance function, hybrid methods such as the particle level set method [Enright D, Fedkiw R, Ferziger J, Mitchell I. A hybrid particle level set method for improved interface capturing. J Comput Phys 2002;183:83–116] and the coupled level set volume of fluid method [Sussman M, Puckett EG. A coupled level set and volume-of-fluid method for computing 3d and axisymmetric incompressible two-phase flows. J Comput Phys 2000;162:301–37], and adaptive gridding techniques such as the octree approach to free surface flows proposed in [Losasso F, Gibou F, Fedkiw R. Simulating water and smoke with an octree data structure, ACM Trans Graph (SIGGRAPH Proc) 2004;23:457–62].     

A Fast Preconditioned Iterative Algorithm for the Electromagnetic Scattering from a Large Cavity

In this paper, a fast preconditioned Krylov subspace iterative algorithm is proposed for the electromagnetic scattering from a rectangular large open cavity embedded in an infinite ground plane. The scattering problem is described by the Helmholtz equation with a nonlocal artificial boundary condition on the aperture of the cavity and Dirichlet boundary conditions on the walls of the cavity. Compact fourth order finite difference schemes are employed to discretize the bounded domain problem. A much smaller interface discrete system is reduced by introducing the discrete Fourier transformation in the horizontal and a Gaussian elimination in the vertical direction, presented in Bao and Sun (SIAM J. Sci. Comput. 27:553, 2005). An effective preconditioner is developed for the Krylov subspace iterative solver to solve this interface system. Numerical results demonstrate the remarkable efficiency and accuracy of the proposed method.     

A finite difference real ghost fluid method on moving meshes with corner-transport upwind interpolation

The real ghost fluid method (RGFM) [Wang CW, Liu TG, Khoo BC. A real-ghost fluid method for the simulation of multi-medium compressible flow. SIAM J Sci Comput 2006;28:278–302] has been shown to be more robust than previous versions of GFM for simulating multi-medium flow problems with large density and pressure jumps. In this paper, a finite difference RGFM is combined with adaptive moving meshes for one- and two-dimensional problems. A high resolution corner-transport upwind (CTU) method is used to interpolate approximate solutions from old quadrilateral meshes to new ones. Unlike the dimensional splitting interpolation, the CTU method takes into account the transport across corner points, which is physically more sensible. Several one- and two-dimensional examples with large density and pressure jumps are computed. The results show the present moving mesh method can effectively reduce the conservative errors produced by GFM and can increase the computational efficiency.     

Block preconditioners with circulant blocks for general linear systems

Block preconditioner with circulant blocks (BPCB) has been used for solving linear systems with block Toeplitz structure since 1992 [R. Chan, X. Jin, A family of block preconditioners for block systems, SIAM J. Sci. Statist. Comput. (13) (1992) 1218–1235]. In this new paper, we use BPCBs to general linear systems (with no block structure usually). The BPCBs are constructed by partitioning a general matrix into a block matrix with blocks of the same size and then applying T. Chan’s optimal circulant preconditioner [T. Chan, An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Statist. Comput. (9) (1988) 766–771] to each block. These BPCBs can be viewed as a generalization of T. Chan’s preconditioner. It is well-known that the optimal circulant preconditioner works well for solving some structured systems such as Toeplitz systems by using the preconditioned conjugate gradient (PCG) method, but it is usually not efficient for solving general linear systems. Unlike T. Chan’s preconditioner, BPCBs used here are efficient for solving some general linear systems by the PCG method. Several basic properties of BPCBs are studied. The relations of the block partition with the cost per iteration and the convergence rate of the PCG method are discussed. Numerical tests are given to compare the cost of the PCG method with different BPCBs.     

Superconvergent Two-Grid Methods for Elliptic Eigenvalue Problems

Some numerical algorithms for elliptic eigenvalue problems are proposed, analyzed, and numerically tested. The methods combine advantages of the two-grid algorithm (Xu and Zhou in Math Comput 70(233):17–25, 2001), the two-space method (Racheva and Andreev in Comput Methods Appl Math 2:171–185, 2002), the shifted inverse power method (Hu and Cheng in Math Comput 80:1287–1301, 2011; Yang and Bi in SIAM J Numer Anal 49:1602–1624, 2011), and the polynomial preserving recovery enhancing technique (Naga et al. in SIAM J Sci Comput 28:1289–1300, 2006). Our new algorithms compare favorably with some existing methods and enjoy superconvergence property.     

$$L_2$$ Stability of Explicit Runge–Kutta Schemes

Explicit Runge–Kutta methods are standard tools in the numerical solution of ordinary differential equations (ODEs). Applying the method of lines to partial differential equations, spatial semidiscretisations result in large systems of ODEs that are solved subsequently. However, stability investigations of high-order methods for transport equations are often conducted only in the semidiscrete setting. Here, strong-stability of semidiscretisations for linear transport equations, resulting in ODEs with semibounded operators, are investigated. For the first time, it is proved that the fourth-order, ten-stage SSP method of Ketcheson (SIAM J Sci Comput 30(4):2113–2136, 2008) is strongly stable for general semibounded operators. Additionally, insights into fourth-order methods with fewer stages are presented.     

An Approximate Lax–Wendroff-Type Procedure for High Order Accurate Schemes for Hyperbolic Conservation Laws

A high order time stepping applied to spatial discretizations provided by the method of lines for hyperbolic conservations laws is presented. This procedure is related to the one proposed in Qiu and Shu (SIAM J Sci Comput 24(6):2185–2198, 2003) for numerically solving hyperbolic conservation laws. Both methods are based on the conversion of time derivatives to spatial derivatives through a Lax–Wendroff-type procedure, also known as Cauchy–Kovalevskaya process. The original approach in Qiu and Shu (2003) uses the exact expressions of the fluxes and their derivatives whereas the new procedure computes suitable finite difference approximations of them ensuring arbitrarily high order accuracy both in space and time as the original technique does, with a much simpler implementation and generically better performance, since only flux evaluations are required and no symbolic computations of flux derivatives are needed.     

Fast Matrix-Vector Multiplication in the Sparse-Grid Galerkin Method

Sparse grid discretization of higher dimensional partial differential equations is a means to break the curse of dimensionality. For classical sparse grids based on the one-dimensional hierarchical basis, a sophisticated algorithm has been devised to calculate the application of a vector to the Galerkin matrix in linear complexity, despite the fact that the matrix is not sparse. However more general sparse grid constructions have been recently introduced, e.g. based on multilevel finite elements, where the specified algorithms only have a log-linear scaling. This article extends the idea of the linear scaling algorithm to more general sparse grid spaces. This is achieved by abstracting the algorithm given in (Balder and Zenger, SIAM J. Sci. Comput. 17:631, 1996) from specific bases, thereby identifying the prerequisites for performing the algorithm. In this way one can easily adapt the algorithm to specific discretizations, leading for example to an optimal linear scaling algorithm in the case of multilevel finite element frames.     

Lattice Boltzmann simulations of impedance tube flows

An original time-domain surface acoustic impedance condition for Lattice Boltzmann methods has been developed. The basis for this method is the extension proposed by Delattre et al. [Delattre G, Manoha E, Redonnet S, Sagaut P. Time-domain simulation of sound absorption on curved wall. 13th AIAA/CEAS Aeroacoustics conference, Rome, Italy, AIAA-2007-3493; 2007] of the z-transform approach suggested by Özyörük et al. [Özyörük Y, Long LN, Jones M. Time-domain numerical simulation of a flow impedance tube. J Comput Phys 1998;146:29-57]. Using this boundary condition that links the normal velocity and the pressure, the basic idea consists in calculating the Lattice Boltzmann populations at a boundary node thanks to the gradients of the fluid velocity. This paper describes the proposed LBM boundary conditions and its assessment on the NASA Langley flow-impedance tube with a constant depth ceramic tubular liner. We performed both single and broadband-frequency simulations, without mean flow and with sheared mean flows. Excellent agreement is shown with both experimental data and other simulation results at various frequencies up to a Mach number equal to 0.5.     

A Hybridizable Discontinuous Galerkin Method for the Navier–Stokes Equations with Pointwise Divergence-Free Velocity Field

We introduce a hybridizable discontinuous Galerkin method for the incompressible Navier–Stokes equations for which the approximate velocity field is pointwise divergence-free. The method builds on the method presented by Labeur and Wells (SIAM J Sci Comput 34(2):A889–A913, 2012). We show that with modifications of the function spaces in the method of Labeur and Wells it is possible to formulate a simple method with pointwise divergence-free velocity fields which is momentum conserving, energy stable, and pressure-robust. Theoretical results are supported by two- and three-dimensional numerical examples and for different orders of polynomial approximation.     

CFL-Violating Numerical Schemes for a Two-Fluid Model

In this paper we propose a class of linearly implicit numerical schemes for a two-phase flow model, allowing for violation of the CFL-criterion for all waves. Based on the Weakly Implixit Mixture Flux (WIMF) approach [SIAM J. Sci. Comput., 26 (2005), pp. 1449–1484], we here develop an extension denoted as Strongly Implicit Mixture Flux (SIMF). Whereas the WIMF schemes are restricted by a weak CFL condition which relates time steps to the fluid velocity, the SIMF schemes are able to break the CFL conditions corresponding to both the sonic and advective velocities. The schemes possess some desirable features compared to current industrial pressure-based codes. They allow for sequential updating of the momentum and mass variables on a nonstaggered grid by solving two sparse linear systems. The schemes are conservative in all convective fluxes and consistency between the mass variables and pressure is formally maintained. Numerical experiments are presented to shed light on the inherent differences between the WIMF and SIMF families of schemes. In particular, we demonstrate that the WIMF scheme is able to give an exact resolution of a moving contact discontinuity. The SIMF schemes do not possess the “exact resolution” property of WIMF, however, the ability to take larger time steps can be exploited so that more efficient calculations can be made when accurate resolution of sharp fronts is not essential, e.g. to calculate steady state solutions.