适用于异构集群的混合并行流线生成系统

流线是流场可视化的主要方法之一,而针对大规模流场的流线生成由于计算量大往往需要采用高性能计算机这样的并行计算环境结合并行化算法以实现计算加速.在当前异构计算系统越来越普遍的情况下,为了充分利用并行异构计算环境的计算能力,实现更高效的并行流线生成,本文采用了基于数据并行原语结合分布式消息通讯的技术架构,设计了一套适用于异...     

Idempotent Computation over Finite Fields

In this paper, we provide an account of several new techniques for computing the primitive idempotents of a commutative artinian algebra over a finite field. Examples of such algebras include the center of a finite group algebra or any finite dimensional quotient of a polynomial ring. The computational methods described are applicable in fairly general situations and the algorithms presented are easily programmed. Both pseudocode and operation counts are provided. As an application, the problem of factoring polynomials over finite fields is discussed.     

Decomposition of algebras over finite fields and number fields

We consider the boolean complexity of the decomposition of semi-simple algebras over finite fields and number fields.We present new polynomial time algorithms for the decomposition of semi-simple algebras over these fields. Our algorithms are somewhat simpler than previous algorithms, and provide parallel reductions from semi-simple decomposition to the factorization of polynomials. As a consequence we obtain efficient parallel algorithms for the decomposition of semi-simple algebras over small finite fields. We also present efficient sequential and parallel algorithms for the decomposition of a simple algebra from a basis and a primitive idempotent. These will be applied in a subsequent paper to obtain Las Vegas polynomial time algorithms for the decomposition of matrix algebras over and .     

Stable Morse Decompositions for Piecewise Constant Vector Fields on Surfaces

Numerical simulations and experimental observations are inherently imprecise. Therefore, most vector fields of interest in scientific visualization are known only up to an error. In such cases, some topological features, especially those not stable enough, may be artifacts of the imprecision of the input. This paper introduces a technique to compute topological features of user‐prescribed stability with respect to perturbation of the input vector field. In order to make our approach simple and efficient, we develop our algorithms for the case of piecewise constant (PC) vector fields. Our approach is based on a super‐transition graph, a common graph representation of all PC vector fields whose vector value in a mesh triangle is contained in a convex set of vectors associated with that triangle. The graph is used to compute a Morse decomposition that is coarse enough to be correct for all vector fields satisfying the constraint. Apart from computing stable Morse decompositions, our technique can also be used to estimate the stability of Morse sets with respect to perturbation of the vector field or to compute topological features of continuous vector fields using the PC framework.     

Computing with algebraically closed fields

A practical computational system is described for computing with an algebraic closure of a field. The system avoids factorization of polynomials over extension fields, but gives the illusion of a genuine field to the user. All roots of an arbitrary polynomial defined over such an algebraically closed field can be constructed and are easily distinguished within the system. The difficult case of inseparable extensions of function fields of positive characteristic is also handled properly by the system. A technique of modular evaluation into a finite field critically ensures that a unique genuine field is simulated by the system but also provides fast optimizations for some fundamental operations. Fast matrix techniques are also used for several non-trivial operations. The system has been successfully implemented within the Magma Computer Algebra System, and several examples are presented, using this implementation.     

Algorithms for computing with nilpotent matrix groups over infinite domains

We develop methods for computing with matrix groups defined over a range of infinite domains, and apply those methods to the design of algorithms for nilpotent groups. In particular, we provide a practical nilpotency testing algorithm for matrix groups over an infinite field. We also provide algorithms to answer a number of structural questions for a nilpotent matrix group.The main algorithms have been implemented in GAP, for groups over the rational number field.     

Algorithms for computing a primary ideal decomposition without producing intermediate redundant components

In Noro (2010) we proposed an algorithm for computing a primary ideal decomposition by using the notion of a separating ideal and showed that it can efficiently decompose several examples which are hard to decompose using existing algorithms. In particular, the number of redundant components produced in the algorithm is zero or very small in many examples, but no theoretical explanation for the efficiency was given.In this paper we define a more sophisticated class of separating ideals: saturated separating ideals. By using this notion we modify the algorithm of Noro (2010) such that it directly outputs a minimal primary decomposition without producing any intermediate redundant component.By modifying the process of extraction of a primary component via the pseudo-primary decomposition proposed in Shimoyama and Yokoyama (1996), we find a method for intermediate decomposition of an ideal and propose a variant of the new primary decomposition algorithm based on this intermediate decomposition. Our experiment shows that this variant efficiently decomposes many examples which are still hard to decompose even if we apply the original version of the new algorithm. Furthermore, in this algorithm we can bypass the computation of primary components and obtain directly the set of all associated primes of an ideal.     

近程作用分子动力学模拟的两级并行

分子动力学作为一种重要的计算手段在许多领域有着广泛的应用，由于它的计算量比较庞大，因此并行计算方法被越来越多地引入到分子动力学的模拟中。本文在目前常见的SMP集群系统上，根据系统的结构特点，针对分子动力学的三种并行算法：区域分解法、原子分解法和力分解法，利用MPI Pthread的混合编程模型，采用节点间消息传递模式以及节点内部共享存储的编程模式，实现了近程作用分子动力学的两级并行计算。计算结果表明，不同的算法采用了两级并行的方式和原来只有消息传递的并行方式相比，具有不同的计算效率，但是从总体来说采用两级并行的计算方式可以利用更多的计算资源，从而有助于提高计算能力。     

Gröbner bases and primary decomposition of modules

In this paper I present definitions and algorithms for Gröbner bases for submodules of free modules over polynomial rings in n variables over Noetherian commutative rings with certain algorithmic properties. I then give an algorithm for computing the primary decomposition of submodules of submodules of these free modules when the base ring is also a PID, a show that under certain dimension conditions the requirement of a PID may be dropped.     

Decompositions of algebras over ℝ and ℂ

We consider the boolean complexity of the decomposition of matrix algebras over and with bases consisting of matrices over a number field. Deterministic polynomial time algorithms for the decomposition of semi-simple algebras over these fields and Las Vegas polynomial time algorithms for the decomposition of simple algebras are obtained.     

Coverage path planning algorithms for agricultural field machines

In this article, a coverage path planning problem is discussed in the case of agricultural fields and agricultural machines. Methods and algorithms to solve this problem are developed. These algorithms are applicable to both robots and human‐driven machines. The necessary condition is to cover the whole field, and the goal is to find as efficient a route as possible. As yet, there is no universal algorithm or method capable of solving the problem in all cases. Two new approaches to solve the coverage path planning problem in the case of agricultural fields and agricultural machines are presented for consideration. Both of them are greedy algorithms. In the first algorithm the view is from on top of the field, and the goal is to split a single field plot into subfields that are simple to drive or operate. This algorithm utilizes a trapezoidal decomposition algorithm, and a search is developed of the best driving direction and selection of subfields. This article also presents other practical aspects that are taken into account, such as underdrainage and laying headlands. The second algorithm is also an incremental algorithm, but the path is planned on the basis of the machine's current state and the search is on the next swath instead of the next subfield. There are advantages and disadvantages with both algorithms, neither of them solving the problem of coverage path planning problem optimally. Nevertheless, the developed algorithms are remarkable steps toward finding a way to solve the coverage path planning problem with nonomnidirectional vehicles and taking into consideration agricultural aspects. © 2009 Wiley Periodicals, Inc.     

一个新的移动Agent的可靠通信算法

移动Agent技术是近年来分布式计算领域中一项新兴的技术。其中有很多领域的研究尚不成熟，如Agent的可靠通信。Agent的可靠通信一直是Agent技术的一个难题，在现有的很多Agent系统中都未得到解决。比较了几种移动Agent可靠通信的算法，并提出了一种新的移动Agent的可靠通信算法。     

Generating a Noetherian Normalization of the Invariant Ring of a Finite Group

We improve Kemper's algorithm for the computation of a noetherian normalization of the invariant ring of a finite group. The new algorithm, which still works over arbitrary coefficient fields, no longer relies on algorithms for primary decomposition.     

基于ARMv8处理器的高性能图像处理算法实现与优化研究

色彩空间转换、图像缩放、图像滤波都是图像处理领域常见的算法,广泛应用于数字媒体、数据通信、生物医学和航空航天等领域。目前上述算法在ARM处理器上虽有开源的OpenCV库,但缺少与Intel IPP库精度相当的高性能图像处理库。为此,根据算法的计算访存特征,将上述算法分为数据无关算法、数据共享算法及非规则访存算法3类,提出了不同类别算法在ARMv8计算平台上的优化方法体系,最终构建了一个基于ARMv8计算平台的高性能图像处理算法库,精度上对标Intel IPP库,并通过算法优化、访存优化、SIMD优化及汇编指令优化等一系列优化方法的应用,大幅提升了图像处理算法的性能。实验结果表明,在华为鲲鹏920计算平台上,重点优化的CvtColor、Filter和Resize模块性能较OpenCV算法库都有显著提升。     

Towards a geometry of recursion

Any mathematical theory of algorithms striving to offer a foundation for programming needs to provide a rigorous definition for an abstract algorithm. The works reported by Girard (1988) in [10] and by Moschovakis (1989, 1995) in [29], [30] and [31] are among the best examples of such attempts. They both try to offer a mathematically precise and rigorous formulation of an abstract algorithm, intend to keep the algorithmic flavour present and take the notion of recursion as primary and central. The present work is motivated by Girard’s GoI 2 paper (Girard (1988) [10], which offers a treatment of recursion in terms of fixed points of linear functions. It is situated in the context of the geometry of interaction (GoI) program and is carried out in the concrete setting of the space of bounded linear maps on a Hilbert space. In this paper, we extend the work in Girard (1988) [10] to the context of traced unique decomposition categories, once again emphasizing the role of abstract trace in the theory of computing. We show that traced unique decomposition categories enriched over partially additive monoids or their variations suffice to axiomatize and hence extend the work in Girard’s GoI 2 paper. The theory developed here allows us to formulate an abstract notion of an algorithm as a pair of morphisms in a traced unique decomposition category, an abstract notion of computation as the execution formula (defined using the trace operator) applied to an algorithm, and finally a notion of deadlock-freeness for algorithms. In addition, we can treat recursive definitions, fixed points and fixed point operators in a uniform way in terms of traced unique decomposition categories.     

tachyon: Efficient Shared Memory Parallel Computation of Extremum Graphs

The extremum graph is a succinct representation of the Morse decomposition of a scalar field. It has increasingly become a useful data structure that supports topological feature-directed visualization of 2D/3D scalar fields, and enables dimensionality reduction together with exploratory analysis of high-dimensional scalar fields. Current methods that employ the extremum graph compute it either using a simple sequential algorithm for computing the Morse decomposition or by computing the more detailed Morse–Smale complex. Both approaches are typically limited to two and three-dimensional scalar fields. We describe a GPU–CPU hybrid parallel algorithm for computing the extremum graph of scalar fields in all dimensions. The proposed shared memory algorithm utilizes both fine-grained parallelism and task parallelism to achieve efficiency. An open source software library, tachyon , that implements the algorithm exhibits superior performance and good scaling behaviour.     

Efficient decomposition of strongly connected components on GPUs

The GPU (Graphics Processing Unit) has recently become one of the most power efficient processors in embedded and many other environments, and has been integrated into more and more SoCs (System on Chip). Thus modern GPUs play a very important role in power aware computing. Strongly Connected Component (SCC) decomposition is a fundamental graph algorithm which has wide applications in model checking, electronic design automation, social network analysis and other fields. GPUs have been shown to have great potential in accelerating many types of computations including graph algorithms. Recent work have demonstrated the plausibility of GPU SCC decomposition, but the implementation is inefficient due to insufficient consideration of the distinguishing GPU programming model, which leads to poor performance on irregular and sparse graphs.This paper presents a new GPU SCC decomposition algorithm that focuses on full utilization of the contemporary embedded and desktop GPU architecture. In particular, a subgraph numbering scheme is proposed to facilitate the safe and efficient management of the subgraph IDs and to serve as the basis of efficient source selection. Furthermore, we adopt a multi-source partition procedure that greatly reduces the recursion depth and use a vertex labeling approach that can highly optimize the GPU memory access. The evaluation results show that the proposed approach achieves up to 41× speedup over Tarjan’s algorithm, one of the most efficient sequential SCC decomposition algorithms, and up to 3.8× speedup over the previous GPU algorithms.     

Hybrid of genetic algorithm and local search to solve MAX-SAT problem using nVidia CUDA framework

General Purpose computing over Graphical Processing Units (GPGPUs) is a huge shift of paradigm in parallel computing that promises a dramatic increase in performance. But GPGPUs also bring an unprecedented level of complexity in algorithmic design and software development. In this paper we describe the challenges and design choices involved in parallelizing a hybrid of Genetic Algorithm (GA) and Local Search (LS) to solve MAXimum SATisfiability (MAX-SAT) problem on a state-of-the-art nVidia Tesla GPU using nVidia Compute Unified Device Architecture (CUDA). MAX-SAT is a problem of practical importance and is often solved by employing metaheuristics based search methods like GAs and hybrid of GA with LS. Almost all the parallel GAs (pGAs) designed in the last two decades were designed for either clusters or MPPs. Unfortunately, very little research is done on the implementation of such algorithms over commodity graphics hardware. GAs in their simple form are not suitable for implementation over the Single Instruction Multiple Thread (SIMT) architecture of a GPU, and the same is the case with conventional LS algorithms. In this paper we explore different genetic operators that can be used for an efficient implementation of GAs over nVidia GPUs. We also design and introduce new techniques/operators for an efficient implementation of GAs and LS over such architectures. We use nVidia Tesla C1060 to perform several numerical tests and performance measurements and show that in the best case we obtain a speedup of 25×. We also discuss the effects of different optimization techniques on the overall execution time.     

一种基于滑动窗口的数据流相似性查询算法

相似性查询是一种非常重要的数据挖掘应用。由于数据流具有无限、高速等特性,传统的查询算法不能直接应用于数据流。提出了一种基于小波滑动窗口的多数据流相似性查询算法。算法首先将滑动窗口划分成若干等宽基本窗口,然后对每个基本窗口内的数据进行小波分解与系数约简,从而形成小波摘要窗口。执行相似性查询时,直接基于小波摘要进行计算,而无需数据重构。由于利用了小波分解的线性处理优点,算法具有较低的时间复杂度。最后,基于实际数据对算法进行了实验,实验结果证明了算法的有效性。     

Cellular Binomial Ideals. Primary Decomposition of Binomial Ideals

Eisenbud and Sturmfels’ theoretical study assures that it is possible to find a primary decomposition of binomial ideals into binomial ideals over an algebraically closed field. In this paper we complete the algorithms in Eisenbud and Sturmfels (1996, Duke Math. J., 84, 1–45) by filling in the steps for which the authors say they have not been very precise.