A monotonic projective algorithm for fractional linear programming

We demonstrate that Karmarkar's projective algorithm is fundamentally an algorithm for fractional linear programming on the simplex. Convergence for the latter problem is established assuming only an initial lower bound on the optimal objective value. We also show that the algorithm can be easily modified so as to assure monotonicity of the true objective values, while retaining all global convergence properties. Finally, we show how the monotonic algorithm can be used to obtain an initial lower bound when none is otherwise available.     

基于P2P的结构化数据存储索引算法设计

通过把数据标识和数据索引分别进行组划分后映射到节点组上,然后把树节点的索引重新分布和同步构造PB—link树。应用lazy update和active update两种节点合并、分裂策略,对连续有序数据进行索引,结果比DB—link树具有显著优势,更适应于P2P结构化数据存储环境。     

A systolic algorithm for solving dense linear systems

For an arbitrary n × n matrix A and an n × 1 column vector b, we present a systolic algorithm to solve the dense linear equations Ax = b. An important consideration is that the pivot row can be changed during the execution of our systolic algorithm. The computational model consists of n linear systolic arrays. For 1 ≤ i ≤ n, the i^th linear array is responsible to eliminate the i^th unknown variable x_i of x. This algorithm requires 4n time steps to solve the linear system. The elapsed time unit within a time step is independent of the problem size n. Since the structure of a PE is simple and the same type PE executes the identical instructions, it is very suitable for VLSI implementation. The design process and correctness proof are considered in detail. Moreover, this algorithm can detect whether A is singular or not.     

基于图的机械系统拓扑结构的数据存储

应用图论的概念和建模理论,分析了机械系统机构图和拓扑结构图的关系,提出了一种新的基于图的机械系统拓扑结构的数据存储模型.该存储模型不仅解决了复杂多体系统的存储结构问题,避免了非树形多体向树形多体的切除转换,而且使树形多体系统和非树形多体系统从数学建模到数据存储达到高度一致.     

A parallel algorithm solving a tridiagonal Toeplitz linear system

A new tridiagonal Toeplitz linear system (TTLS) solver is proposed. The solver first decomposes an n-dimensional strictly diagonally dominant TTLS equation into a number of m-dimensional subsystems employing a modified Gaussian elimination method. An analytic solution of a continued fraction is obtained to derive the solver. The solver based on the modified Gaussian elimination method fully exploits parallelism. Computation and communication complexities of the proposed algorithm are all shown to be O(n/m).     

A note on a linear time algorithm for constructing adjacency graphs of 3D FEA data

In this paper, we present an algorithm for constructing adjacency graphs of 3D finite element analysis (FEA) data. Adjacency graphs are created to represent the connectivities of FEA data cells. They are used in most visualization methods for FEA data. We stress that in many engineering applications FEA data sets do not contain the adjacency information. This is opposite to computer-aided geometric design where, e.g., the winged edge geometrical representation is usually generated and utilized. By establishing intermediate data structures and using bin-sorting, we developed an efficient algorithm for constructing such graphs. The total time complexity of the algorithm is linear in the number of data cells.     

高效的带状线性方程组分布式并行算法

提出了一种新的带状线性方程组的分布式并行算法(New Distributed Parallel Algorithm for Banded Linear Equations,简称为NDPAB算法)。当带状线性方程组的系数矩阵满足对角占优时,算法在运行过程中不会中断,算法的加速比接近于处理器数目。给出了基于局域网的MPI异构环境下数值实验结果,数值实验结果表明算法是高效的。     

传感器输出特征线性化的稳健算法

利用最小一乘估计的稳健性 ,给出了传感器输出特征线性化的特征直线的稳健估计。该方法在稳健性方面明显优于最小二乘估计 ,更有效地刻划了传感性输出特征的本质     

分布式存储系统的哈希算法研究

针对分布式存储系统中如何实现数据在物理存储上的均匀分布和高效定位的问题,对多种哈希算法展开研究,提出了衡量分布式存储系统哈希算法优劣的标准;从散列分布性、哈希冲突和计算效率等多个维度对这些哈希算法进行分析比较,指出各种哈希算法的应用场景;结合分布式存储系统的应用,给出最优的哈希算法选择。实验结果证明,Davies-Meyer算法具有很好的均匀分布性和很高的计算效率,很适合分布式存储系统的应用。     

一种线型结构无线传感器网络的时间同步算法

针对煤矿井下液压支架模糊控制监测系统网络拓扑,提出了一种适用于线型结构无线传感器网络的时间同步算法。该算法同步过程分为簇间同步和簇内同步,簇间同步采用双向同步机制修正时间偏移的方法减少同步误差,簇内同步通过最小平方线性拟合方法构造逻辑时钟函数,从而得到簇内任一节点与簇首节点的频偏和相偏估计值,以提高同步精度。仿真结果表明,该算法能有效减少时间同步误差和能量消耗。     

A new infeasible interior-point algorithm with full step for linear optimization based on a simple function

In this paper, we design and analyse an infeasible interior-point algorithm based on a simple function for linear optimization. The infeasible algorithm contains two types of search directions: the feasibility search direction and the centrality search direction. Both of the directions are determined by the simple function. The algorithm uses full step, thus no need to perform the line-search procedure. Although the proposed function is simple, as it will be shown, the induced infeasible algorithm enjoys the best-known iteration complexity for infeasible interior-point algorithm.     

基于PageRank的页面排序改进算法

首先对PageRank算法进行了一般性介绍,研究了现有的基于链接结构的改进算法.在此基础上,指出PageRank算法给不同网页分配相同的Pagegank值影响了网页的排序质量,提出了一种基于多层分类技术的改进算法HCPR,并对PageRank和HCPR算法进行了相应测试和比较.实验结果表明,HCPR的排序结果比PageRank提高了约15.3%的相关度.     

Design of a linear array antenna for shaped beam using genetic algorithm

A linear array antenna design with desired radiation pattern has been presented based on genetic algorithm (GA) approach. Examples of cosecant and flat‐topped beam patterns are illustrated to show the flexibility of GA to solve complex antenna synthesis problems by suitably selecting the fitness function, even with a simple GA. The results have been validated by IE3D electromagnetic simulation. The antenna arrays with different element geometries can also be implemented using the proposed technique. © 2008 Wiley Periodicals, Inc. Int J RF and Microwave CAE, 2008.     

一种应用于煤矿井下线型WSN的时间同步算法

针对煤矿井下线型网络结构的特殊性及传统TPSN算法存在线型网络末端节点同步误差比较大的问题,提出了基于分簇结构的线型WSN时间同步算法。该算法以传统分簇算法为基础,运用时钟漂移补偿、异常数据过滤技术,降低了网络的时间同步误差,同时平衡了整个网络的能量损耗。仿真结果证明了该算法的正确性。     

A fast algorithm for determining the linear complexity of a binary sequence with period 2~np~m

An efficient algorithm for determining the linear complexity and the minimal polynomial of a binary sequence with period 2npm is proposed and proved, where 2 is a primitive root modulo p2. The new algorithm generalizes the algorithm for computing the linear complexity of a binary sequence with period 2" and the algorithm for computing the linear complexity of a binary sequence with period pn, where 2 is a primitive root modulo p2.     

The method of elimination of unknowns for systems of linear inequalities with graph structure

The method of elimination of unknowns in a system of linear inequalities is considered. This method is used to solve systems of linear inequalities whose structure is defined by some graph. The concepts of terminal and intermediate graphs are introduced. A new system of inequalities derived by eliminating a group of unknowns that correspond to these subgraphs is described. Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 66–74, September–October, 1999.     

A new and fast implementation for null space based linear discriminant analysis

In this paper we present a new implementation for the null space based linear discriminant analysis. The main features of our implementation include: (i) the optimal transformation matrix is obtained easily by only orthogonal transformations without computing any eigendecomposition and singular value decomposition (SVD), consequently, our new implementation is eigendecomposition-free and SVD-free; (ii) its main computational complexity is from a economic QR factorization of the data matrix and a economic QR factorization of a n×n matrix with column pivoting, here n is the sample size, thus our new implementation is a fast one. The effectiveness of our new implementation is demonstrated by some real-world data sets.