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 ₂ ⁴ ().     

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.     

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.     

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.     

A Fast Algorithm for Matrix Multiplication and Its Efficient Realization on Systolic Arrays

A new fast matrix multiplication algorithm is proposed, which, as compared to the Winograd algorithm, has a lower multiplicative complexity equal to W _M 0.437n³ multiplication operations. Based on a goal-directed transformation of its basic graph, new optimized architectures of systolic arrays are synthesized. A systolic variant of the Strassen algorithm is presented for the first time.     

A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space

We present here a new and efficient algorithm for planning collision-free motion of a line segment (a rod or a ladder) in two-dimensional space amidst polygonal obstacles. The algorithm uses a different approach than those used in previous motion-planning techniques, namely, it calculates the boundary of the (three-dimensional) space of free positions of the ladder, and then uses this boundary for determining the existence of required motions, and plans such motions whenever possible. The algorithm runs in timeO(K logn) =O(n ² logn) wheren is the number of obstacle corners and whereK is the total number of pairs of obstacle walls or corners of distance less than or equal to the length of the ladder. The algorithm has thus the same complexity as the best previously known algorithm of Leven and Sharir [5], but if the obstacles are not too cluttered together it will run much more efficiently. The algorithm also serves as an initial demonstration of the viability of the technique it uses, which we expect to be useful in obtaining efficient motion-planning algorithms for other more complex robot systems.Work on this paper has been supported in part by a grant from the Joint Ramot-Israeli Ministry of Industry Foundation.     

Numerical Algorithm With High Spatial Accuracy for the Fractional Diffusion-Wave Equation With Neumann Boundary Conditions

A fourth-order compact algorithm is discussed for solving the time fractional diffusion-wave equation with Neumann boundary conditions. The \(L1\) discretization is applied for the time-fractional derivative and the compact difference approach for the spatial discretization. The unconditional stability and the global convergence of the compact difference scheme are proved rigorously, where a new inner product is introduced for the theoretical analysis. The convergence order is \(\mathcal{O }(\tau ^{3-\alpha }+h^4)\) in the maximum norm, where \(\tau \) is the temporal grid size and \(h\) is the spatial grid size, respectively. In addition, a Crank–Nicolson scheme is presented and the corresponding error estimates are also established. Meanwhile, a compact ADI difference scheme for solving two-dimensional case is derived and the global convergence order of \(\mathcal{O }(\tau ^{3-\alpha }+h_1^4+h_2^4)\) is given. Then extension to the case with Robin boundary conditions is also discussed. Finally, several numerical experiments are included to support the theoretical results, and some comparisons with the Crank–Nicolson scheme are presented to show the effectiveness of the compact scheme.     

A fast preconditioner for the incompressible Navier Stokes Equations

The pressure matrix method is a well known scheme for the solution of the incompressible Navier–Stokes equations by splitting the computation of the velocity and the pressure fields (see, e.g., [17]). However, the set-up of effective preconditioners for the pressure matrix is mandatory in order to have an acceptable computational cost. Different strategies can be pursued (see, e.g., [6, 22 , 4, 7, 9]). Inexact block LU factorizations of the matrix obtained after the discretization and linearization of the problem, originally proposed as fractional step solvers, provide also a strategy for building effective preconditioners of the pressure matrix (see [23]). In this paper, we present numerical results about a new preconditioner, based on an inexact factorization. The new preconditioner applies to the case of the generalized Stokes problem and to the Navier–Stokes one, as well. In the former case, it improves the performances of the well known Cahouet–Chabard preconditioner (see [2]). In the latter one, numerical results presented here show an almost optimal behavior (with respect to the space discretization) and suggest that the new preconditioner is well suited also for flexible or inexact strategies, in which the systems for the preconditioner are solved inaccurately.