A Deterministic Construction of Normal Bases With Complexity O(n3 + n log n log(log n) log q)

Constructing normal bases of GF(qⁿ) over GF (q) can be done by probabilistic methods as well as deterministic ones. In the following paper we consider only deterministic constructions. As far as we know, the best complexity for probabilistic algorithms is O(n² log⁴n log² (log n) + n log n log (log n) log q ) (see von zur Gathen and Shoup, 1992). For deterministic constructions, some prior ones, e.g. Lueneburg (1986), do not use the factorization of Xⁿ - 1 over GF(q). As analysed by Bach, Driscoll and Shallit (1993), the best complexity (from Lueneburg, 1986) is O(n³ log n log(log n) + n² log n log(log n) log q). For other deterministic constructions, which need such a factorization, the best complexities are O(n^3,376 + n² log n log(log n) log q) (von zur Gathen and Giesbrecht, 1990), or O(n³ log q); see Augot and Camion (1993). Here we propose a new deterministic construction that does not require the factorization of Xⁿ - 1. Its complexity is reduced to O (n³ + n log n log(log n) log q ).     

RUSPACE(log n) \subseteq DSPACE(log2 n/log log n)

We present a deterministic algorithm running in space O(log² n /log log n ) solving the connectivity problem on strongly unambiguous graphs. In addition, we present an O(log n ) time-bounded algorithm for this problem running on a parallel pointer machine. Received February 1997, and in revised form August 1997, and in final form February 1998.     

Insertion Sort is O(n log n)

Traditional Insertion Sort runs in O(n²) time because each insertion takes O(n) time. When people run Insertion Sort in the physical world, they leave gaps between items to accelerate insertions. Gaps help in computers as well. This paper shows that Gapped Insertion Sort has insertion times of O(log n) with high probability, yielding a total running time of O(n log n) with high probability.     

A Parallel Logarithmic Order Algorithm for General Multibody System Dynamics

A novel optimal order optimal resource parallel multibody algorithm with general system applicability is derived directly from the sequential recursive methods and the most recent developments in recursive constraint treatments. This new Recursive Coordinate Reduction Parallelism (RCRP) is the first optimal order parallel direct method with a sequential implementation that is exactly the efficient algorithm. Consequently, the RCRP sets new benchmarks for performance over a wide range of problem size and parallel resources. Comparisons to existing methods also demonstrate that the RCRP is presently the best general parallel method.     

Sorting Stably,in Place,with O(n log n) Comparisons and O(n) Moves

We settle a long-standing open question, namely whether it is possible to sort a sequence of n elements stably (i.e., preserving the original relative order of the equal elements), using O(1) auxiliary space and performing O(n log n) comparisons and O(n) data moves. Munro and Raman stated this problem in J. Algorithms (13, 1992) and gave an in-place but unstable sorting algorithm that performs O(n) data moves and O(n^1+ε) comparisons. Subsequently (Algorithmica, 16, 1996) they presented a stable algorithm with these same bounds. Recently, Franceschini and Geffert (FOCS 2003) presented an unstable sorting algorithm that matches the asymptotic lower bounds on all computational resources.     

具有O(n)消息复杂度的协调检查点设置算法

协调检查点设置及回卷恢复技术作为一种有效的容错手段,已广泛地运用在集群等并行/分布计算机系统中.为了进一步降低协调检查点设置的时间和空间开销,提出了一种基于消息计数的协调检查点设置算法.该算法无须对底层消息通道的FIFO特性进行假设,并使同步阶段引入的控制消息复杂度由通常的O(n2)降低到O(n),有效地提高了系统的效率和扩展性.     

An O(log n) algorithm for parallel update of minimum spanning trees

Parallel algorithms are presented for updating a minimum spanning tree when the cost of an edge changes or when a new node is inserted in the underlying graph. Our model of computation is a parallel random access machine which allows simultaneous reads but prohibits simultaneous writes into the same memory location. The algorithms described in this paper for updating a minimum spanning tree require O(log n) time and O(n²) processors. These algorithms are efficient when compared to previously known algorithms for initial construction of a minimum spanning tree that require O(log²n) time and use O(n²) processors. The two main contributions of this paper are: (i) usage of an inverted tree for updating minimum spanning trees, and (ii) discovery of an interesting property of minimum spanning trees that we exploit to develop a novel algorithm for vertex insertion update.     

A Parallel Deadlock Detection Algorithm with O(1) Overall Run-time Complexity

This article proposes a novel parallel, hardware-oriented deadlock detection algorithm for multiprocessor system-on-chips. The proposed algorithm takes full advantage of hardware parallelism in computation and maintains information needed by deadlock detection through classifying all resource allocation events and performing class specific operations, which together make the overall run-time complexity of the new method O(1). We implement the proposed algorithm in Verilog HDL and demonstrate in the simulation that each algorithm invocation takes at most four clock cycles in hardware.     

Hierarchical Hypercube Networks (HHN) for Massively Parallel Computers

The hypercube is one of the most widely used topologies because it provides small diameter and embedding of various interconnection networks. For very large systems, however, the number of links needed with the hypercube may become prohibitively large. In this paper, we propose a hierarchical interconnection network based on hypercubes called hierarchical hypercube network (HHN) for massively parallel computers. The HHN has a smaller number of links than the comparable hypercube and in particular, when we construct networks with 2^Knodes, the node degree of HHN with the minimum node degree isO([formula]) while that of hypercube isO(K). Regardless of its smaller node degree, many parallel algorithms can be executed in HHN with the same time complexity as in the hypercube.     

International Association for Multibody System Dynamics (IMSD)

Multibody System Dynamics -     

Treemap: An O(log n) algorithm for indoor simultaneous localization and mapping

This article presents a very efficient SLAM algorithm that works by hierarchically dividing a map into local regions and subregions. At each level of the hierarchy each region stores a matrix representing some of the landmarks contained in this region. To keep those matrices small, only those landmarks are represented that are observable from outside the region. A measurement is integrated into a local subregion using O(k²) computation time for k landmarks in a subregion. When the robot moves to a different subregion a full least-square estimate for that region is computed in only O(k³ log n) computation time for n landmarks. A global least square estimate needs O(kn) computation time with a very small constant (12.37 ms for n = 11300). The algorithm is evaluated for map quality, storage space and computation time using simulated and real experiments in an office environment. This article is based on the authors studies at the German Aerospace Center. Udo Frese was born in Minden, Germany in 1972. He received the Diploma degree in computer science from the University of Paderborn in 1997. From 1998 to 2003 he was a Ph.D. student at the German Aerospace Center in Oberpfaffenhofen. In 2004 he received his Ph.D. degree from University of Erlangen-Nürnberg and joined SFB/TR 8 Spatial Cognition at University of Bremen. He works on mobile robotics, SLAM and computer vision.     

背包类问题的并行O(25n/6)时间-空间-处理机折衷

将串行动态二表算法应用于并行三表算法的设计中,提出一种求解背包、精确的可满足性和集覆盖等背包类NP完全问题的并行三表六子表算法.基于EREW-PRAM模型,该算法可使用O(2n/8)的处理机在O(27n/16)的时间和O(213n/48)的空间求解n维背包类问题,其时间-空间-处理机折衷为O(25n/6).与现有文献的性能对比分析表明,该算法极大地提高了并行求解背包类问题的时间-空间-处理机折衷性能.由于该算法能够破解更高维数的背包类公钥和数字水印系统,其结论在密钥分析领域具有一定的理论和实际意义.     

A Randomized O(log2 k)-Competitive Algorithm for Metric Bipartite Matching

We consider the online metric matching problem in which we are given a metric space, k of whose points are designated as servers. Over time, up to k requests arrive at an arbitrary subset of points in the metric space, and each request must be matched to a server immediately upon arrival, subject to the constraint that at most one request is matched to any particular server. Matching decisions are irrevocable and the goal is to minimize the sum of distances between the requests and their matched servers. We give an O(log² k)-competitive randomized algorithm for the online metric matching problem. This improves upon the best known guarantee of O(log³ k) on the competitive factor due to Meyerson, Nanavati and Poplawski (SODA ’06, pp. 954–959, 2006). It is known that for this problem no deterministic algorithm can have a competitive better than 2k?1, and that no randomized algorithm can have a competitive ratio better than lnk.     

A Novel {O(n)} Parallel Banker's Algorithm for System-on-a-Chip

This article proposes a novel O(n) Parallel Banker's Algorithm (PBA), which is a parallelized version of the Banker's Algorithm (BA), a well-known O(mtimes n) deadlock avoidance algorithm. We implement the approach in hardware, which we call PBA Unit (PBAU). PBAU is not a mere Verilog HDL translation of BA, but a novel, fully hardware-oriented implementation exploiting maximum hardware parallelism of all computations in BA, resulting in O(1) runtime complexity in the best case and O(n) in the worst. PBAU is an Intellectual Property (IP) block that provides a mechanism of very fast, automatic deadlock avoidance for Multiprocessor System-on-a-Chip (MPSoC), which we predict will be the mainstream of future high performance computing environments. Furthermore, our PBAU supports multiple instance multiple resource systems. We demonstrate that PBAU not only avoids deadlock in a few clock cycles (several orders of magnitude faster than BA in software), but also achieves, in a particular example, a 19 percent speedup of application execution time over avoiding deadlock in software. Lastly, the MPSoC area overhead due to PBAU is small, less than 0.05 percent in our candidate MPSoC example.