Bit-parallel approximate string matching algorithms with transposition

Using bit-parallelism has resulted in fast and practical algorithms for approximate string matching under Levenshtein edit distance, which permits a single edit operation to insert, delete or substitute a character. Depending on the parameters of the search, currently the fastest non-filtering algorithms in practice are the O(km/wn) algorithm of Wu and Manber, the O((k+2)(m−k)/wn) algorithm of Baeza-Yates and Navarro, and the O(m/wn) algorithm of Myers, where m is the pattern length, n is the text length, k is the error threshold and w is the computer word size. In this paper we discuss a uniform way of modifying each of these algorithms to permit also a fourth type of edit operation: transposing two adjacent characters in the pattern. This type of edit distance is also known as Damerau edit distance. In the end we also present an experimental comparison of the resulting algorithms.     

A numerical experimental study of inverse preconditioning for the parallel iterative solution to 3D finite element flow equations

Integration of the subsurface flow equation by finite elements (FE) in space and finite differences (FD) in time requires the repeated solution to sparse symmetric positive definite systems of linear equations. Iterative techniques based on preconditioned conjugate gradients (PCG) are one of the most attractive tool to solve the problem on sequential computers. A present challenge is to make PCG attractive in a parallel computing environment as well. To this aim a key factor is the development of an efficient parallel preconditioner. FSAI (factorized sparse approximate inverse) and enlarged FSAI relying on the approximate inverse of the coefficient matrix appears to be a most promising parallel preconditioner. In the present paper PCG using FSAI, diagonal and pARMS (parallel algebraic recursive multilevel solvers) preconditioners is implemented on the IBM SP4/512 and CLX/768 supercomputers with up to 32 processors to solve underground flow problems of a large size. The results show that FSAI may allow for a parallel relative efficiency larger than 50% on the largest problems with p=32 processors. Moreover, FSAI turns out to be significantly less expensive and more robust than pARMS. Finally, it is shown that for p in the upper range may be much improved if PCG–FSAI is implemented on CLX.     

A parametric representation of linguistic hedges in Zadeh’s fuzzy logic

This paper proposes a model for the parametric representation of linguistic hedges in Zadeh’s fuzzy logic. In this model each linguistic truth-value, which is generated from a primary term of the linguistic truth variable, is identified by a real number r depending on the primary term. It is shown that the model yields a method of efficiently computing linguistic truth expressions accompanied with a rich algebraic structure of the linguistic truth domain, namely De Morgan algebra. Also, a fuzzy logic based on the parametric representation of linguistic truth-values is introduced.     

Approximate symmetries and conservation laws for Itô and Stratonovich dynamical systems

A new definition for the approximate symmetries of Itô dynamical system is given. Determining systems of approximate symmetries for Itô and Stratonovich dynamical systems have been obtained. It has been shown that approximate conservation laws can be found from the approximate symmetries of stochastic dynamical systems which do not arise from a Hamiltonian. The results have been applied to an example.     

Symmetries of flat rank two distributions and sub-Riemannian structures

Flat sub-Riemannian structures are local approximations -- nilpotentizations -- of sub-Riemannian structures at regular points. Lie algebras of symmetries of flat maximal growth distributions and sub-Riemannian structures of rank two are computed in dimensions 3, 4, and 5.

     

The Calogero–Bogoyavlenskii–Schiff Equation in 2+1 Dimensions

We use the classical and nonclassical methods to obtain symmetry reductions and exact solutions of the (2+1)-dimensional integrable Calogero–Bogoyavlenskii–Schiff equation. Although this (2+1)-dimensional equation arises in a nonlocal form, it can be written as a system of differential equations and, in potential form, as a fourth-order partial differential equation. The classical and nonclassical methods yield some exact solutions of the (2+1)-dimensional equation that involve several arbitrary functions and hence exhibit a rich variety of qualitative behavior.     

Classification of Integrable Divergent N-Component Evolution Systems

We use a symmetry approach to solve the classification problem for integrable N-component evolution systems having the form of conservation laws. We obtain complete lists of both isotropic and anisotropic systems of this type and find auto-Bäcklund transformations with a spectral parameter for all systems.     

具有两台专用机,两台通用机的Q4／／Cmax问题的近似算法

本文讨论具有两台专用机、两台通用机的两组工件的同种类平行机的Q4／／Cmax问题，对这类特殊的排序问题，提出一种启发式算法，得到了最差情况下性能指标的严格的界．     

Spectral distributions in nuclei: General principles and applications

The subject of spectral distribution methods where one derives and applies the locally smoothed forms of observables in nuclei is briefly reviewed. It is well understood that the local forms (with respect to energy) of the level density function, expectation values and strength densities are Gaussian, linear (or ratio of Gaussians) and a bivariate Gaussian respectively. To accomodate symmetries in the above forms, one has to deal with multivariate distributions in general; for example the angular-momentum (J) decomposition leads to a bivariate Gaussian form for the level density. These results extend to indefinitely large spaces by method of partitioning and they generate convolution forms. The origin of these remarkable spectral properties is discussed and shell model examples are given to substantiate their applicability to nuclear systems. Spectral distribution theory is a practical, usable theory because the smoothed forms are defined in terms of traces of low particle-rank operators, and the trace information propagates. Finally we discuss the application of the spectral methods for a wide range of nuclear problems; these include binding energies, orbit occupancies, electromagnetic andβ-decay sum rule quantities, analysis of operators, symmetry breaking, numerical level densities, and determination of bounds on time-reversal non-invariant part of nucleon-nucleon interaction.     

FULL DISCRETE NONLINEAR GALERKIN METHOD FOR THE NAVIER-STOKES EQUATIONS

This paper deals with the inertial manifold and the approximate inertial manifold concepts of the Navier-Stokes equations with nonhomogeneous boundary conditions and inertial algorithm. Furtheremore, we provide the error estimates of the approximate solutions of the Navier-Stokes Equations.