Efficient biased random bit generation for parallel lattice gas simulations

Lattice gas methods are often used to model the kinetics of a variety of diffusive systems. One of the main advantages of these methods is the ease at which they can be parallelized using simple bit vector operations. However, to describe the kinetics of the lattice gas in a randomly biased fashion, it is necessary to efficiently generate a randomly biased bit vector. If one generates a random floating point number per bit, then this is very costly. In this paper, an efficient algorithm is developed that leads to a fully bit vector implementation of a lattice gas automation while significantly reducing the amount of needed generated random floating point numbers. The bit vector algorithm using the new random biased bit vector algorithm is tested on a lattice gas method whose solution is modeled by the solution of the 1-D Burgers' equation. This new lattice gas method is then implemented on the BBN TC2200 and CRAY 90 parallel processors.     

基于浮点DSP的航姿系统自适应滤波算法与仿真研究

介绍了在捷联式航姿系统中采用的简化Sage-Husa算法的自适应滤波原理，建立了基于该自适应滤波算法的导航系统状态方程和观测方程，给出了基于TMS320C32浮点数字信号处理器(DSP)的半物理仿真硬件原理图和软件运行流程，并进行了仿真计算。仿真分析结果表明，基于浮点DSP的航姿系统在采用自适应卡尔曼滤波算法时不仅能有效抑制滤波发散，还使系统具有优越的实时性能和较高的精度。     

A continuous Hopfield network equilibrium points algorithm

The continuous Hopfield network (CHN) is a classical neural network model. It can be used to solve some classification and optimization problems in the sense that the equilibrium points of a differential equation system associated to the CHN is the solution to those problems. The Euler method is the most widespread algorithm to obtain these CHN equilibrium points, since it is the simplest and quickest method to simulate complex differential equation systems. However, this method is highly sensitive with respect to initial conditions and it requires a lot of CPU time for medium or greater size CHN instances. In order to avoid these shortcomings, a new algorithm which obtains one equilibrium point for the CHN is introduced in this paper. It is a variable time-step method with the property that the convergence time is shortened; moreover, its robustness with respect to initial conditions will be proven and some computational experiences will be shown in order to compare it with the Euler method.     

An algorithm to solve integer linear systems exactly using numerical methods

In this paper, we present a new algorithm for the exact solutions of linear systems with integer coefficients using numerical methods. It terminates with the correct answer in well-conditioned cases or quickly aborts in ill-conditioned cases. Success of this algorithm on a linear equation requires that the linear system must be sufficiently well-conditioned for the numeric linear algebra method being used to compute a solution with sufficient accuracy. Our method is to find an initial approximate solution by using a numerical method, then amplify the approximate solution by a scalar, and adjust the amplified solution and corresponding residual to integers so that they can be computed without large integer arithmetic involved and can be stored exactly. Then we repeat these steps to refine the solution until sufficient accuracy is achieved, and finally reconstruct the rational solution. Our approximating, amplifying, and adjusting idea enables us to compute the solutions without involving high precision software floating point operations in the whole procedure or large integer arithmetic except at the final rational reconstruction step. We will expose the theoretical cost and show some experimental results.     

动态平衡运量配流问题及其稳态伴随解算法

动态平衡运量配流问题的建模和求解是发展智能车辆导驶系统的理论基础.本文对多起 点单讫点交通网络建立了连续时间最优控制模型,该模型的最优解对应于动态用户平衡解.文 中提出的稳态伴随解算法避免了解复杂的两点边界值问题,可以获得原问题的近似解.该算 法利用了交通网络和计算机网络的结构特性,计算速度较高,可用于城市交通流的实时控制.     

两种基于FFO的前导零检测算法

前导0检测(LZD)是浮点加法运算的关键步骤,设计高速的前导0检测算法对提高浮点加法器性能具有重要意义。本文针对64位高性能微处理器浮点运算部件的应用需求,设计并实现了两种基于FFO的前导0检测算法,并对其进行了分析比较。综合结果表明,改进的并行LZD算法具有更高的检测性能,并且通过提前计算出规格化字节移位量,将前导0检测和规格化中的粗粒度移位并行化,进一步减少了整个浮点运算部件的延迟。     

内部结构自支撑的三维打印浮体平衡优化算法

为了使浮体能够在熔融挤压式三维打印机中一次成型,提出一种内部结构自支撑的浮体平衡优化算法.首先在给定漂浮姿势的输入模型内部,利用递归细分方法生成自支撑的格子结构,并把输入模型与格子结构组合为初始浮体模型.然后以初始浮体模型中格子单元体积为变量构建平衡优化方程,根据方程解算结果调整初始浮体模型中每个格子单元的体积,从而生成最终的浮体模型.实验结果表明,文中算法生成的浮体模型可以使用熔融挤压式三维打印机直接打印,打印的实体不但能够按照预设的姿势漂浮在液体中,而且具有较好的抗压能力;算法中的递归细分策略能够在模型内部产生较多的格子单元,具有节省打印材料的优势.     

求解不动点方程的人工鱼群算法*

基于传统迭代算法在求解不动点方程的过程中求解结果与初始点选取有很大关系且很难满足并行性的要求,提出了一种求解不动点方程的改进人工鱼群算法。该算法实现了求解不动点方程的并行性,克服了初始点的影响,同时把Cauchy序列引入到觅食行为中,提高整个算法的求解精度和速度。仿真实验验证了该算法的有效性。     

基于条件随机场和低采样率浮动车数据的地图匹配算法

提出了一种基于条件随机场和低采样率浮动车数据的地图匹配算法。首先建立道路网络模型,在此基础上,计算GPS观测点可能匹配的候选投影点集合以及集合中每一个候选投影点的观测概率,再计算相邻GPS观测点的候选路径集合以及每两个相邻候选投影点之间的传递概率;然后根据这些候选投影点和候选路径,在滑动窗口内,基于条件随机场模型应用前后向递归算法,计算每个候选投影点的概率权重值;最后根据概率权重值,选取GPS观测点的最佳匹配投影点。该算法(FB-MM)在低采样率的情况下,综合考虑了道路网络的拓扑结构和GPS观测点之间的关联信息,实现了较好的地图匹配效果。     

Global aspects of the matrix Riccati equation

Matrix Riccati equations are interpreted as differential equations on Grassman manifolds. Necessary conditions for the Riccati equation to be a Morse-Smale system are given in the autonomous and periodic cases. Under this condition, the equation is structurally stable and has a unique asymptotically stable equilibrium point or periodic solution.     

Parallel algorithms for the rounding exact summation of floating point numbers

Pichat and Bohlender studied an algorithm for the rounding exact summation of floating point numbers which can be executed on any floating point arithmetic unit. We propose parallel versions of this algorithm, namely a pipeline version, an algorithm similar to the exchange methods for sorting and a tree-like algorithm, associating a tree to the sum. For all these algorithms we discuss the properties, a multiprocessor architecture should have for an efficient implementation of an algorithm without restricting us to a special architecture.     

Three algorithms to compute covariance matrices: Comparison of their computational complexity

Three numerical algorithms for computing the solution of the covariance matrix differential equations of states of a linear time-invariant dynamical system forced by white Gaussian noise are analyzed. Estimates of errors due to truncation and roundoff are derived for each algorithm. The error analyses are based on the assumption that computation is performed in floating point mode and that it is not numerically ill-conditioned. Computational complexity of each algorithm is also discussed. Two numerical examples are presented to evaluate the performance of each algorithm.     

New method for computing unstable equilibrium points of power systems with induction motors

The computation of the unstable equilibrium point(UEP) is a key step involved in stability region estimation of nonlinear dynamic systems.A new continuation-based method to compute the UEPs of a power system with induction motors is proposed.The mechanical torques of motors are changed to form a parameterized equation set.Then the solution curve of the equation set is traced by the continuation method from the stable equilibrium point to a UEP.The direction of mechanical torque change is varied to get multi...     

New iterative algorithm for algebraic Riccati equation related to H∞ control problem of singularly perturbed systems

We present the solution to the algebraic Riccati equation (ARE) with indefinite sign quadratic term related to the H_∞ control problem for singularly perturbed systems by means of a Kleinman type algorithm. The resulting algorithm is very efficient from the numerical point of view because the ARE is solvable even if the quadratic term has an indefinite sign. Moreover, the resulting iterative algorithm is quadratically convergent. We also present an algorithm for solving the generalized algebraic Lyapunov equation on the basis of the fixed point algorithm     

On the analysis of a recurrent neural network for solving nonlinearmonotone variational inequality problems

We investigate the qualitative properties of a recurrent neural network (RNN) for solving the general monotone variational inequality problems (VIPs), defined over a nonempty closed convex subset, which are assumed to have a nonempty solution set but need not be symmetric. The equilibrium equation of the RNN system simply coincides with the nonlinear projection equation of the VIP to be solved. We prove that the RNN system has a global and bounded solution trajectory starting at any given initial point in the above closed convex subset which is positive invariant for the RNN system. For general monotone VIPs, we show by an example that the trajectory of the RNN system can converge to a limit cycle rather than an equilibrium in the case that the monotone VIPs are not symmetric. Contrary to this, for the strictly monotone VIPs, it is shown that every solution trajectory of the RNN system starting from the above closed convex subset converges to the unique equilibrium which is also locally asymptotically stable in the sense of Lyapunov, no matter whether the VIPs are symmetric or nonsymmetric. For the uniformly monotone VIPs, the aforementioned solution trajectory of the RNN system converges to the unique equilibrium exponentially.     

Helicoseir as Shape of a Rotating String (I): 2D Theory and Simulation Using ANCF

A physically simple but mathematically cumbersome problem of rotating heavy string with one fixed top point was studied. A nonlinear equation of its two-dimensional shapes of relative equilibrium was obtained and solved numerically. A linear case of small displacements was analyzed in terms of Bessel functions. The qualitative and quantitative behavior of the problem is discussed with the help of a bifurcation diagram. Dynamics of the two-dimensional model near the equilibrium positions were studied with the help of a simulation using the absolute nodal coordinate formulation (ANCF); the equilibriums were found to be instable. The reason for instability is explained using a variational principle. The outlines for further full three-dimensional analysis are briefly proposed in this paper, and the full derivation will be explained in the next paper.     

改进进化策略求解复杂化学方程根的研究

化学问题中经常遇到需要用近似方法求解复杂化学方程(包括非线性方程,超越方程等)根的问题.传统的方法有图解法,牛顿迭代法等,但不是所有问题都可解决,因为用传统方法可能受初值选取的影响也可能求解精度不高.因此改进进化策略,把复杂化学方程求根转化成函数优化问题,并充分利用改进进化策略具有自适应性和鲁棒性的特点,从随机产生的初始可行解出发,经过优化选择、重组、突变等操作,迭代逐渐逼近最优解,同时体现并行算法的特点.最后,本文通过仿真实例表明新算法具有收敛快、求解精度高等优点.     

求解多组分化学相平衡的一种通用算法

基于Gibbs自由能最小原理,提出一种求解多组分化学相平衡的通用算法——混沌-蒙特卡罗混合算法。分别介绍了该算法的计算步骤和关键性能参数。多个计算实例表明,本文提出的方法可以不断拓展解的空间,避免假收敛,能以完全概率、高速并行搜索到全局最优解。     

The Nash Equilibrium Point of Dynamic Games Using Evolutionary Algorithms in Linear Dynamics and Quadratic System

In this paper, examining some games, we show that classical techniques are not always effective for games with not many stages and players and it can’t be claimed that these techniques of solution always obtain the optimal and actual Nash equilibrium point. For solving these problems, two evolutionary algorithms are then presented based on the population to solve general dynamic games. The first algorithm is based on the genetic algorithm and we use genetic algorithms to model the players' learning process in several models and evaluate them in terms of their convergence to the Nash Equilibrium. in the second algorithm, a Particle Swarm Intelligence Optimization (PSO) technique is presented to accelerate solutions’ convergence. It is claimed that both techniques can find the actual Nash equilibrium point of the game keeping the problem’s generality and without imposing any limitation on it and without being caught by the local Nash equilibrium point. The results clearly show the benefits of the proposed approach in terms of both the quality of solutions and efficiency.     

基于浮点数机内编码的快速排序方法

本文提出一种可对任意分布的浮点数进行排序的快速排序方法,它基于浮点数的机内编码,具有速度快、实现简单、实用的特点。其时间复杂度为O(n),在对不同分布的随机浮点数进行的排序实验中,其速度是快速排序的数倍。同时,本算法思想还可用于双精度数、整数、字符串等类型数据的排序。