Fast multiplication of matrices over a finitely generated semiring

In this paper we show that n×n matrices with entries from a semiring R which is generated additively by q generators can be multiplied in time O(q²nω), where nω is the complexity for matrix multiplication over a ring (Strassen: ω<2.807, Coppersmith and Winograd: ω<2.376).We first present a combinatorial matrix multiplication algorithm for the case of semirings with q elements, with complexity , matching the best known methods in this class.Next we show how the ideas used can be combined with those of the fastest known boolean matrix multiplication algorithms to give an O(q²nω) algorithm for matrices of, not necessarily finite, semirings with q additive generators.For finite semirings our combinatorial algorithm is simple enough to be a practical algorithm and is expected to be faster than the O(q²nω) algorithm for matrices of practically relevant sizes.     

BOUT++: A framework for parallel plasma fluid simulations

A new modular code called BOUT++ is presented, which simulates 3D fluid equations in curvilinear coordinates. Although aimed at simulating Edge Localised Modes (ELMs) in tokamak x-point geometry, the code is able to simulate a wide range of fluid models (magnetised and unmagnetised) involving an arbitrary number of scalar and vector fields, in a wide range of geometries. Time evolution is fully implicit, and 3rd-order WENO schemes are implemented. Benchmarks are presented for linear and non-linear problems (the Orszag-Tang vortex) showing good agreement. Performance of the code is tested by scaling with problem size and processor number, showing efficient scaling to thousands of processors.Linear initial-value simulations of ELMs using reduced ideal MHD are presented, and the results compared to the ELITE linear MHD eigenvalue code. The resulting mode-structures and growth-rate are found to be in good agreement (γBOUT++=0.245ωA, γELITE=0.239ωA, with Alfvénic timescale 1/ωA=R/VA). To our knowledge, this is the first time dissipationless, initial-value simulations of ELMs have been successfully demonstrated.     

A highly accurate Helmholtz scheme for modeling scattering wave

We present in this paper a compact scheme for modelling underwater wave propagation in large-coastal areas. The proposed Helmholtz scheme relates the derivative terms u_xxxx and u_xx to u itself at four adjacent nodal points to yield a five-point stencil implicit scheme with eighth-order accuracy. Besides enjoying high-order accuracy and good stability properties, the proposed scheme can provide oscillation-free solutions provided that the grid size is appropriately chosen. The underlying theory is the M-matrix theory. Computations have been carried out for several problems which are amenable to exact solutions. Agreement with the exact solutions is generally good even in a grid system involving fewer mesh points, thus demonstrating the efficiency of the proposed scheme implemented within the alternating direction context. The compact scheme has been applied to problems bounded partly by a scatter surface. Both incident and scattering wave propagation problems have been studied with great success.     

三维Euler方程的隐式间断有限元算法

为了求解三维欧拉方程,对隐式时间离散格式间断有限元方法进行了研究。根据间断Galerkin有限元方法思想,构造内迭代SOR-LU-SGS隐式时间离散格式,结合当地时间步长技术、多重网格方法,实现了三维流场的计算。数值计算了ONERAM6机翼、大攻角尖前缘三角翼以及DLR-F4翼身组合体的亚声速绕流问题。结果表明,加入SOR内迭代步的LU-SGS隐式算法具有较大的优势,相较于GMRES算法所占用的内存少且收敛速度相当,是LU-SGS算法的三倍以上。针对三维算例,具有较好的稳定性和较高的收敛速度,能够给出准确的流场信息。与原方法相比,SOR-LU-SGS方法无论是在迭代步数上还是在CPU时间上,效率均有明显提高,适合于三维复杂流场计算。     

A Generalized Peaceman–Rachford ADI Scheme for Solving Two-Dimensional Parabolic Differential Equations

A generalized Peaceman–Rachford alternating-direction implicit (ADI) scheme for solving two-dimensional parabolic differential equations has been developed based on the idea of regularized difference scheme. It is to be very well to simulate fast transient phenomena and to efficiently capture steady state solutions of parabolic differential equations. Numerical example is illustrated.     

Third-order temporal discrete scheme for the non-stationary Navier–Stokes equations

In this article, we suggest a new third-order time discrete scheme for the two-dimensional non-stationary Navier–Stokes equations. After presenting the Galerkin finite element approximation for the spatial discretization, we consider an implicit/explicit time discrete scheme for the problem, which is based on the two-step Adams–Moulton scheme (implicit scheme) for the linear term and the three-step Adams–Bashforth scheme (explicit scheme) for the nonlinear term. In this method, we only need to solve a linearized discrete system at each time step, so the scheme can converge fast and the computational cost can be reduced. Moreover, under some assumptions, we deduce the stability and optimal error estimate for the velocity in L ²-norm.     

Practical aspects of numerical time integration

This paper examines some practical aspects in the numerical time integration of structural equations of motion. The concept of stability region in the complex frequency/time-step (ω · Δt) plane is proposed as the basis of stability evaluation, as opposed to the concept of conditional (or unconditional) stability. Stabilization of numerical computations via the introduction of artificial damping and the composition of existing schemes is discussed. It is shown that stabilization by artificial damping fails for any explicit scheme contrary to the notion that a frequency-proportional damping would suppress the high-frequency components. It is also shown that among explicit schemes examined in this paper, the central difference scheme is preferred from the stability considerations. For nonlinear problems, the linearly extrapolated pseudo-force solution procedure is adopted to assess how nonlinearities affect the stability of implicit schemes. Finally, the impact of stability and accuracy characteristics upon numerical computation is discussed.     

Finite difference method for time-space-fractional Schrödinger equation

In this paper, an implicit finite difference scheme for the nonlinear time-space-fractional Schrödinger equation is presented. It is shown that the implicit scheme is unconditionally stable with experimental convergence order of O(τ^2?α+h²), where τ and h are time and space stepsizes, respectively, and α (0<α<1) is the fractional-order in time. In order to reduce the computational cost, the explicit–implicit scheme is proposed such that the nonlinear term is easily treated. Meanwhile, the implicit finite difference scheme for the coupled time-space-fractional Schrödinger system is also presented, which is unconditionally stable too. Numerical examples are given to support the theoretical analysis.     

Application of normalized flux in pressure-based algorithm

The paper describes an implementation of normalized flux diagram (NFD) scheme into a pressure-based implicit finite-volume procedure to solve the Euler and Navier-Stokes equations on a non-orthogonal mesh with collocated finite-volume formulation. The newly developed algorithm has two new features: (i) the use of the normalized flux and space formulation (NFSF) methodology to bound the convective fluxes and (ii) the use of a high-resolution scheme in calculating interface density values to enhance the shock-capturing property of the algorithm. The procedure incorporates the k-ε eddy-viscosity turbulence model. The algorithm is first tested for inviscid flows at different Mach numbers ranging from subsonic to supersonic on a bump in channel geometry and inside a planar convergent-divergent nozzle. The results have been compared with those using the same scheme in conjunction with primitive variable limiter (NVD). Also, there has been comparison between the results and predicted data using TVD scheme on the basis of characteristic variable. After these comparison, it was found that the limiter on flux, predicted a sharper shock and there was better boundedness here than limiter on primitive variables in coarse mesh. The method is then validated against experimental data for the case of turbulent transonic flow passing via a gas turbine rotor blade cascade for which wind-tunnel experimental data exist. Findings show a remarkable quality of resolution when NFD scheme is used.     

C3: A finite volume-finite difference hybrid model for tsunami propagation and runup

A numerical model that couples Finite Difference and Finite Volume schemes has been developed for tsunami propagation and runup study. An explicit leap-frog scheme and a first order upwind scheme has been considered in the Finite Difference module, while in the Finite Volume scheme a Godunov Type method based on the f-waves approach has been used. The Riemann solver included in the model corresponds to an approximate augmented solver for the Shallow Water Equations (SWE) in the presence of variable bottom surface. With this hybrid model some of the problems inherent to the Godunov type schemes are avoided in the offshore region, while in the coastal area the use of a conservative method ensures the correct computation of the runup and wave breaking. The model has been tested and validated using different problems with a known analytical solution and also with laboratory experiments, considering both non breaking and breaking waves. The results are very satisfactory, showing that the hybrid approach is a useful technique for practical usages.     

An Implicit Eulerian–Lagrangian WENO3 Scheme for Nonlinear Conservation Laws

We present a new, formally third order, implicit Weighted Essentially Non-Oscillatory (iWENO3) finite volume scheme for solving systems of nonlinear conservation laws. We then generalize it to define an implicit Eulerian–Lagrangian WENO (iEL-WENO) scheme. Implicitness comes from the use of an implicit Runge–Kutta (RK) time integrator. A specially chosen two-stage RK method allows us to drastically simplify the computation of the intermediate RK fluxes, leading to a computationally tractable scheme. The iEL-WENO3 scheme has two main steps. The first accounts for particles being transported within a grid element in a Lagrangian sense along the particle paths. Since this particle velocity is unknown (in a nonlinear problem), a fixed trace velocity v is used. The second step of the scheme accounts for the inaccuracy of the trace velocity v by computing the flux of particles crossing the incorrect tracelines. The CFL condition is relaxed when v is chosen to approximate the characteristic velocity. A new Roe solver for the Euler system is developed to account for the Lagrangian tracings, which could be useful even for explicit EL-WENO schemes. Numerical results show that iEL-WENO3 is both less numerically diffusive and can take on the order of about 2–3 times longer time steps than standard WENO3 for challenging nonlinear problems. An extension is made to the advection–diffusion equation. When advection dominates, the scheme retains its third order accuracy.     

A versatile implicit iterative approach for fully resolved simulation of self-propulsion

We present a computational approach for fully resolved simulation of self-propulsion of organisms through a fluid. A new implicit iterative algorithm is developed that solves for the swimming velocities of the organism with prescribed deformation kinematics. A solution for the surrounding flow field is also obtained. This approach uses a constraint-based formulation of the problem of self-propulsion developed by Shirgaonkar et al. [1]. The approach in this paper is unlike the previous work [1] where a fractional time stepping scheme was used. Fractional time stepping schemes, while efficient for moderate to high Reynolds number problems, are not suitable for zero or low Reynolds number problems where the inertia term in the governing equation is absent or negligible. In such cases the implicit iterative algorithm presented here is more appropriate. We validate the method by simulating self-propulsion of bacterial flagellum, jellyfish (Aurelia aurita), and larval zebrafish (Danio rerio). Comparison of the computational results with theoretical and experimental results for the test cases is found to be very good.     

An implicit gas-kinetic scheme for turbulent flow on unstructured hybrid mesh

In this study, an implicit scheme for the gas-kinetic scheme (GKS) on the unstructured hybrid mesh is proposed. The Spalart–Allmaras (SA) one equation turbulence model is incorporated into the implicit gas-kinetic scheme (IGKS) to predict the effects of turbulence. The implicit macroscopic governing equations are constructed and solved by the matrix-free lower-upper symmetric-Gauss–Seidel (LU-SGS) method. To reduce the number of cells and computational cost, the hybrid mesh is applied. A modified non-manifold hybrid mesh data(NHMD) is used for both unstructured hybrid mesh and uniform grid. Numerical investigations are performed on different 2D laminar and turbulent flows. The convergence property and the computational efficiency of the present IGKS method are investigated. Much better performance is obtained compared with the standard explicit gas-kinetic scheme. Also, our numerical results are found to be in good agreement with experiment data and other numerical solutions, demonstrating the good applicability and high efficiency of the present IGKS for the simulations of laminar and turbulent flows.     

A new kind of discretization scheme for solving a two-dimensional time-independent Schrödinger equation

In this paper we present a new kind of discretization scheme for solving a two-dimensional time-independent Schrödinger equation. The scheme uses a symmetrical multi-point difference formula to represent the partial differentials of the two-dimensional variables, which can improve the accuracy of the numerical solutions to the order of Δx2Nq+2 when a (2Nq+1)-point formula is used for any positive integer Nq with Δx=Δy, while Nq=1 equivalent to the traditional scheme. On the other hand, the new scheme keeps the same form of the traditional matrix equation so that the standard algebraic eigenvalue algorithm with a real, symmetric, large sparse matrix is still applicable. Therefore, for the same dimension, only a little more CPU time than the traditional one should be used for diagonalizing the matrix. The numerical examples of the two-dimensional harmonic oscillator and the two-dimensional Henon-Heiles potential demonstrate that by using the new method, the error in the numerical solutions can be reduced steadily and extensively through the increase of Nq, which is more efficient than the traditional methods through the decrease of the step size.     

Upper and lower estimates for the number of some <Emphasis Type="Italic">k</Emphasis>-dimensional subspaces of a given weight over a finite field

A fast simulation method is proposed that makes it possible to construct upper and lower estimates for the number of k-measurable subspaces (of arbitrary weight ω) of an n-measurable vector space over a Galois field containing q elements. Numerical examples demonstrate the accuracy of the estimates.     

Modeling old-age mortality risk for the populations of Australia and New Zealand: An extreme value approach

Old-age mortality for populations of developed countries has been improving rapidly since the 1950s. This phenomenon, which is often referred to as ‘rectangularization’ of mortality, implies an increased survival at advanced ages. With this increase comes different challenges to actuaries, economists and policy planners. A reliable estimate of old-age mortality would definitely help them develop various demographic and financial projections. Unfortunately, data quality issues have made the modeling of old-age mortality difficult and we need a method that can extrapolate a survival distribution to extreme ages without requiring accurate mortality data for the centenarian population. In this paper, we focus on a method called the threshold life table which systematically integrates extreme value theory to the parametric modeling of mortality. We apply the threshold life table to model the most recent period (static) mortality rates for the populations of Australia and New Zealand. We observe a good fit to the raw data for both populations. We then extend the model to predict the highest attained age, which is commonly referred to as ‘omega’ or ω in the actuarial literature, for the populations of Australia and New Zealand. On the basis of the threshold life table, the central estimates of ω for Australia and New Zealand are 112.20 and 109.43, respectively. Our estimates of ω are reasonably consistent with the validated supercentenarian in these countries.     

A pseudo-random sequence generation scheme based on RNS and permutation polynomials

Long period pseudo-random sequence plays an important role in modern information processing systems. Base on residue number system (RNS) and permutation polynomials over finite fields, a pseudorandom sequence generation scheme is proposed in this paper. It extends several short period random sequences to a long period pseudo-random sequence by using RNS. The short period random sequences are generated parallel by the iterations of permutation polynomials over finite fields. Due to the small dynamic range of each iterative calculation, the bit width in hardware implementation is reduced. As a result, we can use full look-up table (LUT) architecture to achieve high-speed sequence output. The methods to find proper permutation polynomials to generate long period sequences and the optimization algorithm of Chinese remainder theorem (CRT) mapping are also proposed in this paper. The period of generated pseudorandom sequence can exceed 2¹⁰⁰ easily based on common used field programmable gate array (FPGA) chips. Meanwhile, this scheme has extensive freedom in choosing permutation polynomials. For example, 10905 permutation polynomials meet the long period requirement over the finite field F _q with q ? 1(mod 3) and q ? 503. The hardware implementation architecture is simple and multiplier free. Using Xilinx XC7020 FPGA chip, we implement a sequence generator with the period over 2⁵⁰, which only costs 20 18kb-BRAMs (block RAM) and a small amount of logics. And the speed can reach 449.236 Mbps. The National Institute of Standards and Technology (NIST) test results show that the sequence has good random properties.