Hybrid spectral-element-low-order methods for incompressible flows

In this article we present a new formulation for coupling spectral element discretizations to finite difference and finite element discretizations addressing flow problems in very complicated geometries. A general iterative relaxation procedure (Zanolli patching) is employed that enforcesC ¹ continuity along the patching interface between the two differently discretized subdomains. In fluid flow simulations of transitional and turbulent flows the high-order discretization (spectral element) is used in the outer part of the domain where the Reynolds number is effectively very high. Near rough wall boundaries (where the flow is effectively very viscous) the use of low-order discretizations provides sufficient accuracy and allows for efficient treatment of the complex geometry. An analysis of the patching procedure is presented for elliptic problems, and extensions to incompressible Navier-Stokes equations are implemented using an efficient high-order splitting scheme. Several examples are given for elliptic and flow model problems and performance is measured on both serial and parallel processors.     

On the Hopcroft’s minimization technique for DFA and DFCA

We show that the absolute worst case time complexity for Hopcroft’s minimization algorithm applied to unary languages is reached only for deterministic automata or cover automata following the structure of the de Bruijn words. A previous paper by Berstel and Carton gave the example of de Bruijn words as a language that requires $O(nlogn)$ steps in the case of deterministic automata by carefully choosing the splitting sets and processing these sets in a FIFO mode for the list of the splitting sets in the algorithm. We refine the previous result by showing that the Berstel/Carton example is actually the absolute worst case time complexity in the case of unary languages for deterministic automata. We show that the same result is valid also for the case of cover automata and an algorithm based on the Hopcroft’s method used for minimization of cover automata. We also show that a LIFO implementation for the splitting list will not achieve the same absolute worst time complexity for the case of unary languages both in the case of regular deterministic finite automata or in the case of the deterministic finite cover automata as defined by S. Yu.     

A new operator splitting method for the numerical solution of partial differential equations II

We extend the applications of a new method for splitting operators in partial differential equations introduced by us (A. Rouhi and J. Wright, A new operator splitting method for the numerical solution of partial differential equations, Comput. Phys. Commun. 85 (1995) 18–28, and Spectral implementation of a new operator splitting method for solving partial differential equations, Comput. Phys. (1995), to be published.) to equations in two spatial dimensions, and show how the method allows the use of explicit time stepping methods in some instances when other methods require implicit time stepping. This odd-even splitting method also enables one to increase the order of accuracy of time stepping in a straightforward manner. Our main examples will be the two-dimensional Navier-Stokes equations and the shallow water equations. In the first example we show how the pressure term can be dealt with in simple geometries. We will then discuss the treatment of the diffusion term. Next we will discuss how fast waves can be treated by explicit methods using the odd-even splitting, while retaining all stability and accuracy advantages of usual implicit methods. Our example here will be the shallow water equations in two dimensions.     

Accuracy of the Richardson Extrapolation Method in Eigenvalue Problems

The accuracy of the Richardson extrapolation method is investigated for the eigenvalue problem of linear elasticity theory with zero Dirichlet boundary conditions in a three-dimensional beam. O(h ⁴)-estimates of eigenvalue and eigenfunction vector errors are obtained with the constraint that the eigenfunction belongs to the space W ₂ ⁴ ().     

Faster algorithm of string comparison

In many applications, it is necessary to determine the field similarity. Our paper introduces a package of substring-based new algorithms to determine Field Similarity. Combined together, our new algorithms not only achieves higher accuracy, but also gains the time complexity O(knm) (k<0.75) for the worst case, O( *n) where <6 for the average case and O(1) for the best case. Throughout the paper, we use the approach of comparative examples to show the higher accuracy of our algorithms compared to that proposed in Lee et al. [1]. Theoretical analysis, concrete examples and experimental results show that our algorithms can significantly improve the accuracy and time complexity of the calculation of field similarity.     

The use of Richardson extrapolation for the numerical solution of low Mach number flow in confined regions

We use artificial compressibility together with Richardson extrapolation in the Mach numberM as a method for solving the time dependent Navier-Stokes equation for very low Mach number flow and for incompressible flow. The question of what boundary conditions one should use for low Mach number flow, especially at inflow and outflow boundaries, is investigated theoretically, and boundary layer suppressing boundary conditions are derived. For the case of linearization around a constant flow we show that the low Mach number solution will converge with the rateO(M²) to the true incompressible solution, provided that we choose the boundary conditions correctly. The results of numerical calculations for the time dependent, nonlinear equations and for flow situations with time dependent inflow velocity profiles are presented. The convergence rateM ² to incompressible solution is numerically confirmed. It is also shown that using Richardson extrapolation toM ²= 0 in order to derive a solution with very small divergence can with good result be carried through withM ² as large as 0.1 and 0.05. As the time step in numerical methods must be chosen approximately such thatt · (i/(M x)–v/x ²) is in the stability region of the time stepping method, and asM ²=0.05 is sufficiently small to yield good results, the restriction on the time step due to the Mach number is not serious. Therefore the equations can be integrated very fast by explicit time stepping methods. This method for solving very low Mach number flow and incompressible flow is well suited to parallel processing.     

On the Development of a Nonprimitive Navier–Stokes Formulation Subject to Rigorous Implementation of a New Vorticity Integral Condition

In this paper, a new integral vorticity boundary condition has been developed and implemented to compute solution of nonprimitive Navier–Stokes equation. Global integral vorticity condition which is of primitive character can be considered to be of entirely different kind compared to other vorticity conditions that are used for computation in literature. The procedure realized as explicit boundary vorticity conditions imitates the original integral equation. The main purpose of this paper is to design an algorithm which is easy to implement and versatile. This algorithm based on the new vorticity integral condition captures accurate vorticity distribution on the boundary of computational flow field and can be used for both wall bounded flows as well as flows in open domain. The approach has been arrived at without utilizing any ghost grid point outside of the computational domain. Convergence analysis of this alternative vorticity integral condition in combination with semi-discrete centered difference approximation of linear Stokes equation has been carried out. We have also computed correct pressure field near the wall, for both attached and separated boundary layer flows, by using streamfunction and vorticity field variables. The competency of the proposed boundary methodology vis-a-vis other popular vorticity boundary conditions has been amply appraised by its use in a model problem that embodies the essential features of the incompressibility and viscosity. Subsequently the proposed methodology has been further validated by computing analytical solution of steady Stokes equation. Finally, it has been applied to three benchmark problems governed by the incompressible Navier–Stokes equations, viz. lid driven cavity, backward facing step and flow past a circular cylinder. The results obtained are in excellent agreement with computational and experimental results available in literature, thereby establishing efficiency and accuracy of the proposed algorithm. We were able to accurately predict both vorticity and pressure fields.     

High-order Implicit Large Eddy Simulation of gaseous fuel injection and mixing of a bluff body burner

Implicit Large Eddy Simulation (ILES) with high-resolution and high-order computational modelling was applied to a turbulent mixing fuel injector flow. In the ILES calculation, the governing equations for three dimensional, non-reactive, multi-species compressible flows were solved using a finite volume Godunov-type method. Up to ninth-order spatial accurate reconstruction methods were examined with a second order explicit Runge–Kutta time integration. Mean and root mean square velocity and mixture fraction profiles showed good agreement with experimental data, which demonstrated that ILES using high-order methods successfully captured complex turbulent flow structure without using an explicit subgrid scale model. The effects of grid resolution and the influence of order of spatial accuracy on the resolution of the kinetic energy spectrum were investigated. An k^−5/3 decay of energy could be seen in a certain range and the cut-off wavenumbers increased with grid resolution or order of spatial accuracy. The effective cut-off wavenumbers are shown to be larger than the maximum wavenumbers appearing on the given grid for all test cases, implying that the numerical dissipation represents sufficiently the energy transport between resolved and unresolved eddies. The fifth-order limiter with a 0.6 million grid points was found to be optimal in terms of the resolution of kinetic energy and reasonable computational time.     

Labelled splitting

We define a superposition calculus with explicit splitting on the basis of labelled clauses. For the first time we show a superposition calculus with an explicit non-chronological backtracking rule sound and complete. The new backtracking rule advances backtracking with branch condensing known from SPASS. An experimental evaluation of an implementation of the new rule shows that it improves considerably on the previous SPASS splitting implementation. Finally, we discuss the relationship between labelled first-order splitting and DPLL style splitting with intelligent backtracking and clause learning.     

Stability of a Hot Smoluchowski Fluid

We study coupled nonlinear parabolic equations for a fluid described by a material density and a temperature , both functions of space and time. In one dimension, we find some stationary solutions corresponding to fixing the temperature on the boundary, with no-escape boundary conditions for the material. For the special case, where the temperature on the boundary is the same at both ends, the linearized equations for small perturbations about a stationary solution at uniform temperature and density are derived; they are subject to boundary conditions, Dirichlet for and no-flow conditions for the material. The spectrum of the generator L of time evolution, regarded as an operator on L ², is shown to be real, discrete and non-positive, even though L is not self-adjoint. This result is necessary for the stability of the stationary state, but might not be sufficient. The problem lies in the fact that L is not a sectorial operator, since its numerical range is C.     

Structural natural-frequency shape-sensitivity analysis: a fixed-basis-function finite-element approach

The domain-shape-sensitivity of structural natural frequencies is determined using a new finite-element approach called the fixed-basis-function finite-element approach. The approach adopts the point of view that the finite-element grid is fixed during the sensitivity analysis; therefore it is referred to as a Fixed Basis Function Shape Sensitivity finite-element analysis. This approach avoids the requirement of explicit or approximate differentiation of finite-element matrices and vectors and the difficulty or errors resulting from such calculations. Effectively, the sensitivity to boundary shape change is determined exactly; thus the accuracy of the solution sensitivity is dictated by the accuracy of the finite-element analysis. The sensitivity analysis is undertaken within the context of Rayleighs principle and is developed in quite general terms. It is shown that the evaluation of sensitivity matrices involves only modest calculations beyond those for the finite-element analysis of the reference problem; certain boundary integrals on the reference location of the moving boundary are required. In addition, boundary reaction forces and sensitivity boundary conditions must be evaluated. The present formulation separates solution sensitivity from finite-element grid sensitivity and provides a unique representation of boundary perturbations within the context of isoparametric finite-element formulations. The work is illustrated for beam as well as plate problems. Excellent agreement is obtained for shape-sensitivity calculations that compare exact solutions, fixed-basis finite-element results, and overall finite-difference approximations to the finite-element sensitivity results. It is illustrated that the finite-element eigenvalue problem and the fixed-basis finite-element eigenvalue-sensitivity results exhibit similar accuracy and convergence characteristics.     

Numerical simulation of the three dimensional Allen–Cahn equation by the high-order compact ADI method

In this paper, a new linearized high-order compact difference method is presented for numerical simulation of three dimensional (3D) Allen–Cahn equation with three kinds of boundary conditions. The method, which is based on the Crank–Nicholson/Adams–Bashforth scheme combined with the Douglas–Gunn ADI method, is second order accurate in time and fourth order accurate in space and energy degradation. The main advantages of this method is that the nonlinear penalty term f(u)$f\left(u\right)$ is linear and an extra stabilizing term is added to alleviate the stability constraint while maintaining accuracy and simplicity. Numerical experiments are given to demonstrate the validity and applicability of the new method.     

An algorithm for geometric minimum spanning trees requiring nearly linear expected time

We describe an algorithm for finding a minimum spanning tree of the weighted complete graph induced by a set ofn points in Euclideand-space. The algorithm requires nearly linear expected time for points that are independently uniformly distributed in the unitd-cube. The first step of the algorithm is the spiral search procedure described by Bentleyet al. [BWY82] for finding a supergraph of the MST that hasO(n) edges. (The constant factor in the bound depends ond.) The next step is that of sorting the edges of the supergraph by weight using a radix distribution, or bucket, sort. These steps require linear expected time. Finally, Kruskal's algorithm is used with the sorted edges, requiringO(n(cn, n)) time in the worst case, withc>6. Since the function (cn, n) grows very slowly, this step requires linear time for all practical purposes. This result improves the previous bestO(n log log*n), and employs a much simpler algorithm. Also, this result demonstrates the robustness of bucket sorting, which requiresO(n) expected time in this case despite the probability dependency between the edge weights.     

Fast Summation of Radial Functions on the Sphere

Radial functions are a powerful tool in many areas of multi-dimensional approximation, especially when dealing with scattered data. We present a fast approximate algorithm for the evaluation of linear combinations of radial functions on the sphere . The approach is based on a particular rank approximation of the corresponding Gram matrix and fast algorithms for spherical Fourier transforms. The proposed method takes (L) arithmetic operations for L arbitrarily distributed nodes on the sphere. In contrast to other methods, we do not require the nodes to be sorted or pre-processed in any way, thus the pre-computation effort only depends on the particular radial function and the desired accuracy. We establish explicit error bounds for a range of radial functions and provide numerical examples covering approximation quality, speed measurements, and a comparison of our particular matrix approximation with a truncated singular value decomposition.     

Distributed primal–dual stochastic subgradient algorithms for multi‐agent optimization under inequality constraints

We consider the multi‐agent optimization problem where multiple agents try to cooperatively optimize the sum of their local convex objective functions, subject to global inequality constraints and a convex constraint set over a network. Through characterizing the primal and dual optimal solutions as the saddle points of the associated Lagrangian function, which can be evaluated with stochastic errors, we propose the distributed primal–dual stochastic subgradient algorithms for two cases: (i) the time model is synchronous and (ii) the time model is asynchronous. In the first case, we obtain bounds on the convergence properties of the algorithm for a diminishing step size. In the second case, for a constant step size, we establish some error bounds on the algorithm's performance. In particular, we prove that the error bounds scale as in the number of n agents. Copyright © 2012 John Wiley & Sons, Ltd.     

Comparison of region approximation techniques based on Delaunay triangulations and Voronoi diagrams

Region approximation techniques based on constructions from sample data points, i.e. points whose position is known and which are known to be inside or outside the region of interest, can be advantageous in a variety of applications. This paper compares two different constructions and presents results from a Monte Carlo model that shows that the construction based on mid points of edges in a Delaunay triangulation produces the lowest errors. These errors are some 10% less than those produced by the Voronoi diagram construction which appears to be more widely used at present. A consideration of the basic geometries of the different constructions leads to an expression for approximating the expected error in the case of a random point distribution. The expression takes the form

where S is the average point spacing, l_o is the length of region boundary being approximated (the optimum length for the construction), and l_c the length of the constructed line approximating the boundary. The constant k_d accounts for the non-uniform spacing of the points in the distribution and has a value of about 1.1 for a random distribution. Predictions from this expression agree well with the results from the Monte Carlo model.The case of finite as well as infinite radius of curvature is considered and some possible improvements on the constructions modelled are suggested.     

Provably good approximation algorithms for optimal kinodynamic planning: Robots with decoupled dynamics bounds

We consider the following problem: given a robot system, find a minimal-time trajectory that goes from a start state to a goal state while avoiding obstacles by a speed-dependent safety margin and respecting dynamics bounds. In [1] we developed a provably good approximation algorithm for the minimum-time trajectory problem for a robot system with decoupled dynamics bounds (e.g., a point robot in ³). This algorithm differs from previous work in three ways. It is possible (1) to bound the goodness of the approximation by an error term; (2) to bound the computational complexity of our algorithm polynomially; and (3) to express the complexity as a polynomial function of the error term. Hence, given the geometric obstacles, dynamics bounds, and the error term, the algorithm returns a solution that is-close to optimal and requires only a polynomial (in (1/)) amount of time.We extend the results of [1] in two ways. First, we modify it to halve the exponent in the polynomial bounds from 6d to 3d, so that the new algorithm isO(c ^d N 1/)^3d ), whereN is the geometric complexity of the obstacles andc is a robot-dependent constant. Second, the new algorithm finds a trajectory that matches the optimal in time with an factor sacrificed in the obstacle-avoidance safety margin. Similar results hold for polyhedral Cartesian manipulators in polyhedral environments.The new results indicate that an implementation of the algorithm could be reasonable, and a preliminary implementation has been done for the planar case.This paper describes research done at the Computer Science Robotics Laboratory at Cornell University. Support for our robotics research there is provided in part by the National Science Foundation under Grant Nos. IRI-8802390 and IRI-9000532, by a Presidential Young Investigator award, and in part by the Mathematical Sciences Institute, Intel Corporation, and AT&T Bell Laboratories.     

New recurrence algorithms for the nonclassic Adomian polynomials

In this article, we present new algorithms for the nonclassic Adomian polynomials, which are valuable for solving a wide range of nonlinear functional equations by the Adomian decomposition method, and introduce their symbolic implementation in MATHEMATICA. Beginning with Rach’s new definition of the Adomian polynomials, we derive the explicit expression for each class of the Adomian polynomials, e.g. for the Class II, III and IV Adomian polynomials, where the Z_m,k are called the reduced polynomials. These expressions provide a basis for developing improved algorithmic approaches. By introducing the index vectors, the recurrence algorithms for the reduced polynomials are suitably deduced, which naturally lead to new recurrence algorithms for the Class II and Class III Adomian polynomials. MATHEMATICA programs generating these classes of Adomian polynomials are subsequently presented. Computation shows that for computer generation of the Class III Adomian polynomials, the new algorithm reduces the running times compared with the definitional formula. We also consider the number of summands of these classes of Adomian polynomials and obtain the corresponding formulas. Finally, we demonstrate the versatility of the four classes of Adomian polynomials with several examples, which include the nonlinearity of the form f(t,u), explicitly depending on the argument t.     

Near conserving energy numerical schemes for two-dimensional coupled seismic wave equations

Two-dimensional coupled seismic waves, satisfying the equations of linear isotropic elasticity, on a rectangular domain with initial conditions and periodic boundary conditions, are considered. A quantity conserved by the solution of the continuous problem is used to check the numerical solution of the problem. Second order spatial derivatives, in the $x$ direction, in the $y$ direction and mixed derivative, are approximated by finite differences on a uniform grid. The ordinary second order in time system obtained is transformed into a first order in time system in the displacement and velocity vectors. For the time integration of this system, second order and fourth order exponential splitting methods, which are geometric integrators, are proposed. These explicit splitting methods are not unconditionally stable and the stability condition for time step and space step ratio is deduced. Numerical experiments displaying the good behavior in the long time integration and the efficiency of the numerical solution are provided.