The effect of table expansion on the program complexity of perfect hash functions

It has been shown by various researchers that designing a perfect hashing function for a fixed set ofn elements requires (n) bits in the worst case. A possible relaxation of this scheme is to partition the set into pages, and design a hash function which maps keys to page addresses, requiring subsequent binary search of the page. We have shown elsewhere that (nk/2 ^k+1)(1 +o(1)) bits are necessary and sufficient to describe such a hash function where the pages are of size 2 ^k . In this paper we examine the additional scheme of expanding the address space of the table, which does substantially improve the hash function complexity of perfect hashing, and show that in contrast, it does not reduce the hash function complexity of the paging scheme.Research supported by NSF Grant CCR-9017125 and by a grant from Texas Instruments.     

伪辛空间F_q~(2v+2+l)中一类2-维子空间的结合方案及其结构

该文利用伪辛空间Fq(2v+2+l)中一类2-维非迷向子空间构作了具有2q-1个结合类的交换 的但非对称的结合方案,并且讨论了它的结构,证明了它是其基础域上的加法群和乘法群上的 熟知的结合方案的扩张.     

非线性对流扩散问题的差分-流线扩散法

1．引言流线扩散法（简称SD方法）是由Huzhes和Brooks在1980年前后提出的一种数值求解对流占优扩散问题的新型有限元算法．随后，Johnson和N8vert将SD方法推广到发展型对流扩散问题（［1］，［2］，［3］）．熟知，对于对流扩散问题，标准有限元法虽具有高阶精度，但常产生数值振荡；古典人工粘性Galerkin法更具有较好的稳定性，但仅具有一阶精度．而（SD方法兼具良好的数值稳定性和高阶精度，因此得到了越来越多的重视，对于发展型对流扩散问题，传统的SD方法均采用时空有限元．这样做，虽然可使时间和空间方向上的精度很好的协调起…     

Left distance binary tree representations

We present a new scheme for representing binary trees. The scheme is based on rotations as a previous scheme of Zerling. In our method the items of a representation have a natural geometric interpretation, and the algorithms related to the method are simple. We give an algorithm for enumerating all the representations for trees onn nodes, and an algorithm for building the tree corresponding to a given representation.This work was supported by the Academy of Finland.     

Energy Identities and Stability Analysis of the Yee Scheme for 3D Maxwell Equations

In this paper numerical energy identities of the Yee scheme on uniform grids for three dimensional Maxwell equations with periodic boundary conditions are proposed and expressed in terms of the $L^2$, $H^1$ and $H^2$ norms. The relations between the $H^1$ or $H^2$ semi-norms and the magnitudes of the curls or the second curls of the fields in the Yee scheme are derived. By the $L^2$ form of the identity it is shown that the solution fields of the Yee scheme is approximately energy conserved. By the $H^1$ or $H^2$ semi norm of the identities, it is proved that the curls or the second curls of the solution of the Yee scheme are approximately magnitude (or energy)-conserved. From these numerical energy identities, the Courant-Friedrichs-Lewy (CFL) stability condition is re-derived, and the stability of the Yee scheme in the $L^2$, $H^1$ and $H^2$ norms is then proved. Numerical experiments to compute the numerical energies and convergence orders in the $L^2$, $H^1$ and $H^2$ norms are carried out and the computational results confirm the analysis of the Yee scheme on energy conservation and stability analysis.     

非定常不可压Navier-Stokes方程两重网格方法的稳定性和L2误差估计

讨论了二维非定常不可压Navier-Stokes方程的两重网格方法．此方法包括在粗网格上求解一个非线性问题,在细网格上求解一个Stokes问题．采用一种新的全离散(时间离散用Crank-Nicolson格式,空间离散用混合有限元方法)格式数值求解N-S方程．证明了该全离散格式的稳定性．给出了L2误差估计．对比标准有限元方法,在保持同样精度的前提下,TGM能节省大量的计算量．     

二维对流扩散方程满足最大值原理的MMOCAA差分方法

Using FCT idea,the non-oscillation MMOCAA(The modified method of characteristics with adjusted advection) finite difference scheme satisfing the discrete maximum principle for convection-dominated diffusion equation in 2D is constructed.The scheme is free from oscillation,with which the problem is solved by the MMOCAA difference method based on 2-order Lag-range interpolation proposed by Jim.Douglas, Jr.(Numer.Math.,1999,83:353-369.). The error analysis of the new scheme and numerical example are given in the paper.The numerical example shows that the scheme has smaller numerical viscosity than the MMOCAA difference method based on bilineax Lagrange interpolation.     

Optimal dynamic multi-attribute hashing for range queries

This paper examines a partial match retrieval scheme which supports range queries for highly dynamic databases. The scheme relies on order preserving multi-attribute hashing. In general, designing optimal indexes is NP-hard. Greedy algorithms used to determine the optimal indexes for simple partial match queries are not directly applicable because there are a larger number of queries to consider in determining the optimal indexes. In this paper we present heuristic algorithms which provide near-optimal solutions. The optimisation scheme we propose can be used to design other dynamic file structures such as the grid file, BANG file and multilevel grid file to further enhance their retrieval performance taking into consideration the query distribution.     

一类对流扩散方程的特征-修正差分格式及最大模估计

1 引 言许多物理问题的数学模型都可归结为对流扩散型方程（组）,这类模型具有较强的双曲性质.为了在数值计算中更好地反映这种性质,Douglas,Russell[1]提出了特征法的思想.特征法的主要特点是将模型方程的对流项隐含在解沿特征方向的导数之中,以沿特征方向的向后差商逼近取代了通常方法中沿时间方向的向后差商逼近.由于解在特征方向上的变     

ROBUST HIGH ORDER CONVERGENCE OF AN OVERLAPPING SCHWARZ METHOD FOR SINGULARLY PERTURBED SEMILINEAR REACTION-DIFFUSION PROBLEMS

In this article we propose an overlapping Schwarz domain decomposition method for solving a singularly perturbed semilinear reaction-diffusion problem. The solution to this problem exhibits boundary layers of width O（√ε ln（1/√ε）） at both ends of the domain due to the presence of singular perturbation parameter ε. The method splits the domain into three overlapping subdomains, and uses the Numerov or Hermite scheme with a uniform mesh on two boundary layer subdomains and a hybrid scheme with a uniform mesh on the interior subdomain. The numerical approximations obtained from this method are proved to be almost fourth order uniformly convergent （in the maximum norm） with respect to the singular perturbation parameter. Furthermore, it is proved that, for small ε, one iteration is sufficient to achieve almost fourth order uniform convergence. Numerical experiments are given to illustrate the theoretical order of convergence established for the method.     

A Fast Conservative Scheme for the Space Fractional Nonlinear Schrödinger Equation with Wave Operator

A new efficient compact difference scheme is proposed for solving a space fractional nonlinear Schrödinger equation with wave operator. The scheme is proved to conserve the total mass and total energy in a discrete sense. Using the energy method, the proposed scheme is proved to be unconditionally stable and its convergence order is shown to be of $ \mathcal{O}( h^6 + \tau^2) $ in the discrete $ L_2 $ norm with mesh size $ h $ and the time step $ \tau $. Moreover, a fast difference solver is developed to speed up the numerical computation of the scheme. Numerical experiments are given to support the theoretical analysis and to verify the efficiency, accuracy, and discrete conservation laws.     

BAYESIAN ANALYSIS, LIKELIHOOD RATIO AND INFORMATION

ＢＡＹＥＳＩＡＮＡＮＡＬＹＳＩＳ，ＬＩＫＥＬＩＨＯＯＤＲＡＴＩＯＡＮＤＩＮＦＯＲＭＡＴＩＯＮ￥ＺＨＡＮＧＹＡＯＴＩＮＧＡＮＤＤＵＪＩＮＧＳＯＮＧＡｂｓｔｒａｃｔ：Ｗｅｐｒｅｓｅｎｔａｎｅｗｓｃｈｅｍｅｆｏｒｕｎｃｅｒｔａｉｎｒｅａｓｏｎｉｎｇｂａｓｅ...     

A refinement of a compression-oriented addressing scheme

Chang and Wu have proposed a letter-oriented perfect hashing scheme based on sparse matrix compression. We present a method which is a refinement of the Chang-Wu scheme. By experimental evaluation, we show that the hashing of our refinement has more efficient storage utilization than Chang-Wu's method. Our refinement is valuable in practical implementations of hashing for large sets of keys.     

ON RESIDUAL-BASED A POSTERIORI ERROR ESTIMATORS FOR LOWEST-ORDER RAVIART-THOMAS ELEMENT APPROXIMATION TO CONVECTION-DIFFUSION-REACTION EQUATIONS

A new technique of residual-type a posteriori error analysis is developed for the lowest- order Raviart-Thomas mixed finite element discretizations of convection-diffusion-reaction equations in two- or three-dimension. Both centered mixed scheme and upwind-weighted mixed scheme are considered. The a posteriori error estimators, derived for the stress variable error plus scalar displacement error in L_2-norm, can be directly computed with the solutions of the mixed schemes without any additional cost, and are proven to be reliable. Local efficiency dependent on local variations in coefficients is obtained without any saturation assumption, and holds from the cases where convection or reaction is not present to convection- or reaction-dominated problems. The main tools of the analysis are the postprocessed approximation of scalar displacement, abstract error estimates, and the property of modified Oswald interpolation. Numerical experiments are carried out to support our theoretical results and to show the competitive behavior of the proposed posteriori error estimates.     

A PRACTICAL PARALLEL DIFFERENCE SCHEME FOR PARABOLIC EQUATIONS

A practical parallel difference scheme for parabolic equations is constructed as follows: to decompose the domain Ω into some overlapping subdomains, take flux of the last time layer as Neumann boundary conditions for the time layer on inner boundary points of subdomains, solve it with the fully implicit scheme on each subdomain, then take correspondent values of its neighbor subdomains as its values for inner boundary points of each subdomain and mean of its neighbor subdomain and itself at overlapping points. The scheme is unconditionally convergent. Though its truncation error is O(τ h), the convergent order for the solution can be improved to O(τ h2).     

LONG-TIME CONVERGENCE OF GENERALIZED DIFFERENCE METHOD FOR NAVIER-STOKES EQUATIONS

1　IntroductionIn this paper,we firstprovide a generalized difference method for the two-dimension-al Navier-Stokes equations by combining the ideas of staggered scheme[6] and generalizedupwind scheme [4 ] in space,and by backward Euler time-stepping.Then we apply theabstractframework of[7] to prove its long-time convergence.The outline of this paper is as follows:In§ 2 we state the generalized differencemethod.In§ 3 we provide some lemmas.In§ 4 we study the one-sided Lipschitz condi-tio…     

An Energy Stable Filtered Backward Euler Scheme for the MBE Equation with Slope Selection

As a promising strategy to adjust the order in the variable-order BDF algorithm, a time filtered backward Euler scheme is investigated for the molecular beam epitaxial equation with slope selection. The temporal second-order convergence in the $L^2$ norm is established under a convergence-solvability-stability (CSS)-consistent time-step constraint. The CSS-consistent condition means that the maximum step-size limit required for convergence is of the same order to that for solvability and stability (in certain norms) as the small interface parameter $ε → 0^+.$ Similar to the backward Euler scheme, the time filtered backward Euler scheme preserves some physical properties of the original problem at the discrete levels, including the volume conservation, the energy dissipation law and $L^2$ norm boundedness. Numerical tests are included to support the theoretical results.     

一种多介质流体计算的三维非守恒型差分格式

Motivated by the need for three-dimensional methods for interface calculations we describe a 3D non-conservative difference scheme in Lagrange coordinates for calculating multi-component fluid dynamics, according to the thoughts of 2D non-conservative difference scheme and making use of difference method of characteristic and Upwind form. Furthermore, we give a three-dimensional numerical simulation of explosion in concrete, and the results of simulation are consistent with examination.     

一类非线性双曲-抛物耦合问题的A.D.I.Galerkin方法

1　引　言考虑三维非线性双曲 -抛物耦合初边值问题 :utt- . (a1 (X,t,u) u) +b1 (X,t,u,v) . u　　　　 +α1 e. v =f(X,t,u,v) ,X∈Ω,t∈ J.vt-a2 Δv +b2 (X,t,u,v) . v　　　　 +α2 e. ut=g(X,t,u,v) ,X∈Ω,t∈ J.u(X,t) =v(X,t) =0 , X∈ Ω ,t∈ J.u(X,0 ) =u0 (X) ,ut(X,0 ) =ut0 (X) ,v(X,0 ) =v0 (X) ,X∈Ω.(1 .1 )其中 ,X=(x1 ,x2 ,x3) ,Ω=(c1 ,d1 )× (c2 ,d2 )× (c3,d3)为 R3中矩形区域 ,边界 Ω . J=[0 ,T] ,T>0为一正常数 .b1 ,b2 ,f,g均为已知光滑函数 (其中 b1 ,b2 为向量函数 ) ,且关于 u,v满足 L…     

A compact difference scheme for fourth-order fractional sub-diffusion equations with Neumann boundary conditions

In this paper, a compact finite difference scheme with global convergence order $O(\tau^{2}+h^4)$ is derived for fourth-order fractional sub-diffusion equations subject to Neumann boundary conditions. The difficulty caused by the fourth-order derivative and Neumann boundary conditions is carefully handled. The stability and convergence of the proposed scheme are studied by the energy method. Theoretical results are supported by numerical experiments.