Shortest path planning on topographical maps

This paper introduces a new algorithm for quickly answering repetitive least-cost queries between pairs of points on the Earth's surface as represented by digital topographical maps. The algorithm uses a three-step process; preprocessing, geometrically modified Dijkstra search, and postprocessing. The preprocessing step computes and saves highly valuable global information that describes the underlying geometry of the terrain. The search step solves shortest path queries using a modified Dijkstra algorithm that takes advantage of the preprocessed information to “jump” quickly across flat terrain and decide whether a path should go over or through a high-cost region. The final step is a path improvement process that straightens and globally improves the path. Our algorithm partitions the search space into free regions and obstacle regions. However, unlike other algorithms using this approach, our algorithm keeps the option of passing through an obstacle region     

Characterization and efficient computation of the structured singular value

The concept of structured singular value was recently introduced by Doyle [1] as a tool for the analysis and synthesis of feedback systems with structured uncertainties. It is a key to the design of control systems under joint robustness and performance specifications and it very nicely complements theH^{infty}approach to control system design. in this paper, it is shown that the structured singular value can be obtained as the solution of several smooth optimization problems. Properties of these optimization problems are exhibited, leading to a fast algorithm that always yields the structured singular value for block structures of size no larger than 3, and often does for block structures of larger size.     

Scalable cache consistency for hierarchically structured multiprocessors

This paper presents a new cache consistency scheme for hierarchically structured shared-memory multiprocessors. The scheme is simple, fast and efficient, and it does not require a large amount of state information to be maintained. The scheme exploits the broadcast capability of these systems, but limits the extent of the broadcasts by means of a novel filtering mechanism. As a specific example, it is shown how the proposed cache consistency scheme can be implemented on the Hector multiprocessor architecture. Using trace-driven simulations, we demonstrate that the scheme is scalable and performs well for common applications.     

An efficient algorithms for Tate pairing computation

The Weil and Tate pairings have found several new applications in cryptography. In most of these applications, the Weil pairing or Tate pairing of supersingular elliptic curves are essential tools. Therefore efficient computation of the Weil or Tate pairings are crucial factors for practical applications of the cryptographic protocols based pairings. The Weil pairing is thought one of two applications of the Tate pairing. Thus to compute the Weil pairing is more slow than the Tate pairing. To efficiently implement these cryptosystems it is necessary to optimize the computation time for the Tate pairing. This paper presents a new algorithm for computing Tate pairing, which is faster than Miller＇s algorithm that is the best-known general method. Finally, the computation cost of the new algorithm is compared with Miller＇s algorithm.     

An efficient signature computation method

A signature generation algorithm for linear-feedback shift register (LFSR)-based compactors used in fault simulation of built-in self-test digital circuits is presented. The algorithm uses small- to medium-size lookup tables to generate signatures for internal as well as external exclusive-OR LFSRs of any length. The basic concept can be extended to general linear compactors. Algorithms that convert signatures from one form of LFSR to the other are also presented     

Approximation algorithms for a hierarchically structured bin packing problem

In this paper we study a variant of the bin packing problem in which the items to be packed are structured as the leaves of a tree. The problem is motivated by document organization and retrieval. We show that the problem is NP-hard and we give approximation algorithms for the general case and for the particular case in which all the items have the same size.     

An empirical approach to evaluating dependency locality in hierarchically structured software systems

In software development, especially component-based software development, dependency locality states that relevant software components should be at shorter distances than irrelevant components. This principle is used together with modularity and hierarchy to guide the design of large-scale complex software systems. In previous work, dependency locality and its correlation with design quality were studied by statically measuring the interactions between software components. This paper presents an empirical approach to evaluating the hierarchical structure of software systems through mining their revision history. Two metrics, spatial distance and temporal distance, are adapted to measure the dependencies between software components. The correlation of spatial distance and temporal distance between software components represents a factor that influences system design quality. More specially, a well designed system hierarchy should have a significant positive correlation while a non-significant positive correlation or a negative correlation would signify design flaws. In an application of this approach, we use Mantel test to study the dependency locality of six software systems from Apache projects.     

An efficient algorithm for computation of manipulator inertia matrix

In this article an efficient algorithm for computation of the manipulator inertia matrix is presented. The algorithm is derived based on Newton's and Euler's laws governing the motion of rigid bodies. Using spatial notations, the algorithm leads to the definition of the composite rigid-body spatial inertia which is a spatial representation of the notion of augmented body. The equations resulting from this algorithm are derived in a coordinate-free form. The choice of the coordinate frame for projection of the coordinate-free equations, that is, the intrinsic equations, is discussed by analyzing the vectors and the tensors involved in the final equations. Previously proposed algorithms, the physical interpretations leading to their derivation, and the redundancy in their computations are analyzed. The developed algorithm achieves a greater efficiency by eliminating the redundancy in the intrinsic equations as well as by a suitable choice of coordinate frame for projection of the intrinsic equations.     

An efficient method for the computation of Legendre moments

Legendre moments are continuous moments, hence, when applied to discrete-space images, numerical approximation is involved and error occurs. This paper proposes a method to compute the exact values of the moments by mathematically integrating the Legendre polynomials over the corresponding intervals of the image pixels. Experimental results show that the values obtained match those calculated theoretically, and the image reconstructed from these moments have lower error than that of the conventional methods for the same order. Although the same set of exact Legendre moments can be obtained indirectly from the set of geometric moments, the computation time taken is much longer than the proposed method.     

The MUSE machine—An architecture for structured data flow computation

Computers employing some degree of data flow organisation are now well established as providing a possible vehicle for concurrent computation. Although data-driven computation frees the architecture from the constraints of the single program counter, processor and global memory, inherent in the classic von Neumann computer, there can still be problems with the unconstrained generation of fresh result tokens if a pure data flow approach is adopted. The advantages of allowing serial processing for those parts of a program which are inherently serial, and of permitting a demand-driven, as well as data-driven, mode of operation are identified and described. The MUSE machine described here is a structured architecture supporting both serial and parallel processing which allows the abstract structure of a program to be mapped onto the machine in a logical way.     

Neural computation for collision-free path planning

Automatic path planning plays an essential role in planning of assembly or disassembly of products, motions of robot manipulators handling part, and material transfer by mobile robots in an intelligent and flexible manufacturing environment. The conventional methodologies based on geometric reasoning suffer not only from the algorithmic difficulty but also from the excessive time complexity in dealing with 3-D path planning. This paper presents a massively parallel, connectionist algorithm for collision-free path planning. The path planning algorithm is based on representing a path as a series ofvia points or beads connected by elastic strings which are subject to displacement due to a potential field or a collision penalty function generated by polyhedral obstacles. Mathematically, this is equivalent to optimizing a cost function, defined in terms of the total path length and the collision penalty function, by moving thevia points simultaneously but individually in the direction that minimizes the cost function. Massive parallelism comes mainly from: (1) the connectionist model representation of obstacles and (2) the parallel computation of individualvia-point motions with only local information. The algorithm has power to deal effectively with path planning of three-dimensional objects with translational and rotational motions. Finally, the algorithm incorporates simulated annealing to solve a local minimum problem. Simulation results are shown.     

An efficient fault-containing self-stabilizing algorithm for the shortest path problem

Shortest path finding has a variety of applications in transportation and communication. In this paper, we propose a fault-containing self-stabilizing algorithm for the shortest path problem in a distributed system. The improvement made by the proposed algorithm in stabilization times for single-fault situations can demonstrate the desirability of an efficient fault-containing self-stabilizing algorithm. For single-fault situations, the worst-case stabilization time of the proposed algorithm is O(Δ), where Δ is the maximum node degree in the system, and the contamination number of the proposed algorithm is 1.     

An efficient implementation of parallel eigenvalue computation for massively parallel processing

This paper describes an efficient implementation and evaluation of a parallel eigensolver for computing all eigenvalues of dense symmetric matrices. Our eigensolver uses a Householder tridiagonalization method, which has higher parallelism and performance than conventional methods when problem size is relatively small, e.g., the order of 10,000. This is very important for relevant practical applications, where many diagonalizations for such matrices are required so often. The routine was evaluated on the 1024 processors HITACHI SR2201, and giving speedup ratios of about 2–5 times as compared to the ScaLAPACK library on 1024 processors of the HITACHI SR2201.     

An efficient algorithm for computation of stresses due to strain measurements

An efficient and accurate algorithm for computation of stresses corresponding to measurements of strains, in materials obeying the von Mises yield criterion and perfect plasticity, is presented. The relevant formulation and computer implementation is described. Through a numerical example the accuracy, efficiency and robustness of the algorithm is verified. The listing of the source code is added for completeness.     

IG-Tree: an efficient spatial keyword index for planning best path queries on road networks

World Wide Web - Due to the popularity of Spatial Databases, many search engine providers have started to expand their text searching capability to include geographical information. Because of this...     

Determinacy and maximal parallelism in a structured model of parallel computation

The main goal of this paper is the introduction, from a theoretical point of view, of a model specifically studied for the optimization of horizontal microprograms but well suited also to the analysis of microprocessor systems. Moreover, an approach to the design of well-structured and correct parallel programs is given by studying a subset of our schemes (complex structures) and applying to it existing techniques in order to give an algorithm for the maximization of parallelism.     

Efficient fastest-path computations for road maps

Computational Visual Media - In the age of real-time online traffic information and GPS-enabled devices, fastest-path computations between two points in a road network modeled as a directed graph,...     

A hierarchically structured and constraint-based data model for intuitive and precise solid modeling in a virtual reality environment

This article proposes a hierarchically structured and constraint-based data model for intuitive and precise solid modeling in a virtual reality (VR) environment. The data model integrates a high level constraint-based model for intuitive and precise manipulation, a middle level solid model for complete and precise representation and a low-level polygon mesh model for real-time interactions and visualization in a VR environment. The solid model is based on a hybrid B-rep/CSG data structure. Constraints are embedded in the solid model and are organized at hierarchical levels as feature constraints among internal feature elements, part constraints among internal features and assembly constraints between individual parts. In addition to providing a complete and precise model representation and the support for real-time visualization, the proposed data model permits intuitive and precise interaction through constraint-based manipulations for solid modeling in a VR environment. This is a critical issue for product design in a VR environment due to the limited resolutions of today's VR input and output devices.     

A neural network for shortest path computation

This paper presents a new neural network to solve the shortest path problem for inter-network routing. The proposed solution extends the traditional single-layer recurrent Hopfield architecture introducing a two-layer architecture that automatically guarantees an entire set of constraints held by any valid solution to the shortest path problem. This new method addresses some of the limitations of previous solutions, in particular the lack of reliability in what concerns successful and valid convergence. Experimental results show that an improvement in successful convergence can be achieved in certain classes of graphs. Additionally, computation performance is also improved at the expense of slightly worse results.