Parallel arithmetic expression evaluation on reconfigurable meshes

In this paper we present an O(log n) time parallel algorithm for arithmetic expression evaluation, on an n × n processor array with reconfigurable bus system, where n is the sum of the number of operators and constants in the expression. The basic technique involved here is leaves-cutting (rake operation), as in the case of PRAM model algorithms available in the literature for this problem. The input to our algorithm is assumed to be the binary tree associated with a given expression (also known as expression tree with n number of nodes). Our algorithm is faster compared to the previous best time for expression evaluation on mesh connected computers which is O(√n).     

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.     

Parallel generation of permutations on systolic arrays

We present a systolic algorithm to generate all the n! permutations of n given items. The computational model used is a linear systolic array consisting of n identical PEs. This algorithm requires n! time steps to solve this problem. Since any PE is identical and executes the same program, it is suitable for VLSI implementation. The correctness of the algorithm is proved. We also consider the ranking and unranking functions of permutations in this parallel algorithm     

The 0—1 Integer Programming Problem in a finite ring with identity

We define the 0—1 Integer Programming Problem in a finite field or finite ring with identity as: given an m × n matrix A and an n × 1 vector b with entries in the ring R, find or determine the non-existence of a 0—1 vector x such that Ax = b. We give an easily implemented enumerative algorithm for solving this problem, along with conditions that spurious solutions occur with probability as small as desired. Finally, we show that the problem is NP-complete if R is the ring of integers modulo r for r ≥ 3. This result suggests that it will be difficult to improve on our algorithm.     

An optimal distributed algorithm for finding articulation points in a network

This paper presents a distributed algorithm for finding the articulation points in an n node communication network represented by a connected undirected graph. For a given graph if the deletion of a node splits the graph into two or more components then that node is called an articulation point. The output of the algorithm is available in a distributed manner, i.e., when the algorithm terminates each node knows whether it is an articulation point or not. It is shown that the algorithm requires O(n) messages and O(n) units of time and is optimal in communication complexity to within a constant factor.     

Efficient enumeration of all minimal separators in a graph

This paper presents an efficient algorithm for enumerating all minimal a-b separators separating given non-adjacent vertices a and b in an undirected connected simple graph G = (V, E), Our algorithm requires O(n³R_ab) time, which improves the known result of O(n⁴R_ab) time for solving this problem, where ¦V¦= n and R_ab is the number of minimal a-b separators. The algorithm can be generalized for enumerating all minimal A-B separators that separate non-adjacent vertex sets A, B < V, and it requires O(n²(n − n_A − n_b)R_AB) time in this case, where n_a = ¦A¦, n_B = ¦B¦ and r_AB is the number of all minimal A−B separators. Using the algorithm above as a routine, an efficient algorithm for enumerating all minimal separators of G separating G into at least two connected components is constructed. The algorithm runs in time O(n³R⁺_Σ + n⁴R_Σ), which improves the known result of O(n⁶R_Σ) time, where R_σ is the number of all minimal separators of G and R_ΣR⁺_Σ = ∑_1i, v_j) ER_vivj n − 1)/2 − m)R_Σ. Efficient parallelization of these algorithms is also discussed. It is shown that the first algorithm requires at most O((n/log n)R_ab) time and the second one runs in time O((n/log n)R⁺_Σ+n log nR_Σ) on a CREW PRAM with O(n³) processors.     

A new routing algorithm for multirate rearrangeable Clos networks

In this paper, we study the problem of finding routing algorithms on the multirate rearrangeable Clos networks which use as few number of middle-stage switches as possible. We propose a new routing algorithm called the “grouping algorithm”. This is a simple algorithm which uses fewer middle-stage switches than all known strategies, given that the number of input-stage switches and output-stage switches are relatively small compared to the size of input and output switches. In particular, the grouping algorithm implies that m = 2n+(n−1)/2^k is a sufficient number of middle-stage switches for the symmetric three-stage Clos network C(n,m,r) to be multirate rearrangeable, where k is any positive integer and rn/(2^k−1).     

面向非完全姿态约束问题的旋转矩阵群中的垂线理论

在很多机器人领域,有很多给定任务要求并不需要3维空间的完整姿态约束,而是只限定了目标姿态某一轴的方向．这类问题称为非完全姿态约束问题．针对该问题,定义了旋转矩阵群中测地线的垂足和垂线,并给出了其解析表达式．基于垂线理论,提出了沿垂线规划的点到点轨迹生成算法．最后通过仿真实验求解操作臂的轨迹规划问题,仿真以6自由度的PUMA 560为平台,并依次固定第6关节、第4关节得到5自由度和4自由度的操作臂．提出的算法不仅适用于具有功能冗余的6自由度操作臂,也可应用于不具有冗余特性的5自由度和4自由度操作臂．实验结果验证了提出的理论和算法在解决非完全姿态约束问题上的通用性．同时,该算法还能避免参数表示方法中的奇异性问题．     

A time-optimal solution for the path cover problem on cographs

We show that the notoriously difficult problem of finding and reporting the smallest number of vertex-disjoint paths that cover the vertices of a graph can be solved time- and work-optimally for cographs. Our result implies that for this class of graphs the task of finding a Hamiltonian path can be solved time- and work-optimally in parallel.

It was open for more than 10 years to find a time- and work-optimal parallel solution for this important problem. Our contribution is to offer an optimal solution to this important problem. We begin by showing that any algorithm that solves an instance of size n of the problem must take Ω(log n) time on the CREW, even if an infinite number of processors are available. We then go on to show that this time lower bound is tight by devising an EREW algorithm that, given an n-vertex cograph G represented by its cotree, finds and reports all the paths in a minimum path cover in O(log n) time using n/log n processors.     

Mean and standard deviation for the facilities design problem

An important problem in facilities design to find an assignment of n facilities to n locations so that total materials handling cost is minimized. For problems of moderate size, suboptimal solutions must be accepted since optimal algorithms are computationally infeasible. If the mean and standard deviation of the layout cost distribution is known, then statistical methods may be used to measure and compare the efficiencies of various suboptimal solutions as well as to monitor the efficiency of the same assignment under changing production environments. In this paper a new, simple algorithm to calculate the exact value of the standard deviation of the layout cost distribution is presented (the mean is easy). This algorithm has a computational efficiency of O(n²) arithmetic operations for a problem of size n × n, an improvement over previous methods which are either inexact or have a computational efficiency of O(n⁴). Results of tests verifying the accuracy and claimed efficiency of this algorithm, as implemented on a microcomputer, are also presented (about 0.85 second for a 30 × 30 problem).     

Fast median filtering algorithms for mesh computers

Two fast algorithms for median filtering of images using parallel computers having 2-D mesh interconnections are given. Both algorithms assume that an n × n image is loaded onto the mesh with one processing element per pixel. One algorithm performs median filtering over d × d neighborhoods in O(d²) time and works with pixel values in an arbitrarily large range. This algorithm, while theoretically suboptimal, achieves a lower constant than a previously published asymptotically—optimal algorithm and is simpler to program. The second algorithm assumes that the range of pixel values is limited and relatively small, and it accomplishes median filtering in O(d) time.     

Performance Optimization of Switched Systems: A Model Matching Approach

In this paper we consider a prototypical model matching problem where the various mappings involved are systems that switch arbitrarily among n stable linear time-invariant (LTI) systems. The interest is placed on optimizing the worst-case performance of this model matching system over all possible switchings with either l _infin-induced norm or H ₂ norm as the performance criterion. This optimization is performed over all Youla-Kucera parameters that switch causally in time among n stable LTI systems. For the particular setup at hand, it is shown that the optimal Youla-Kucera parameter need not depend on the switching trajectory in the cases of partially matched switching and unmatched switching, and that it can be obtained as an LTI solution to an associated standard l ₁ or H ₂ optimization. In the case of matched switching, two convergent sequences to the optimal solution from above and below are formulated in terms of linear programs and quadratic programs respectively for the l _infin-induced and H ₂ norm optimizations. An approximate solution with any given precision is possible by finite truncation. Applications of these results to sensitivity minimization, linear switched parameter systems, and cooperative control are provided.     

An order-reduction method for extraction of eigenvalues of dynamic systems

An order-reduction method is proposed by means of which a part of the eigenvalues of a given large system in n-D space can be solved conveniently. They may be: (1) the lowest r eigenvalues; or (2) the highest r eigenvalues; or (3) a few eigenvalues nearest to a simplified value by their norms. The algorithm associated with this method is applicable to many kinds of practical problems due to its simplicity and high accuracy. It will be seen that with this algorithm the problem in the original n-D space is reduced into one in much lower r-D subspace, from which the required eigenvalues of the original system can be extracted easily and accurately from the reduced model. This method could also be used conveniently in a structural elastic buckling problem.     

An h-p-n adaptive finite element scheme for shell problems

We propose an adaptive finite element algorithm for shells which, in addition to the usual h-p adaption also shows adaptivity with respect to the order n of the dimension reduction. The idea of the algorithm is to adaptively capture and resolve the various length scales that may occur in shells. The algorithm presented in the paper is limited to axisymmetric problems, which reduces the h-p part of the problem to one dimension only. The performance of the algorithm is tested in some example cases where the shell is cylindrical. For comparison, we test the algorithm also when n is limited so that n k, where K = 1, 2 or 3. Choosing k = 2 essentially corresponds to the classical shell models.     

A method of inexact steepest descent for systems of linear equations

Our approach combines the method of inexact steepest descent with the method of contractor directions to obtain an algorithm for solving systems of linear equations. In order to enhance the scope of applicability, we consider an iterative method with variable step-size iterations. We prove the convergence and given an error estimate for our method.

The algorithm is well-suited for parallel computation. In fact, for systems with m equations and n unknowns, each iteration may be computed in parallel time O(log m + log n), on an EREW PRAM with O(mn) processors.     

Deterministic parallel backtrack search

The backtrack search problem involves visiting all the nodes of an arbitrary binary tree given a pointer to its root subject to the constraint that the children of a node are revealed only after their parent is visited. We present a fast, deterministic backtrack search algorithm for a p-processor COMMON CRCW-PRAM, which visits any n-node tree of height h in time O((n/p+h)(logloglogp)²). This upper bound compares favourably with a natural Ω(n/p+h) lower bound for this problem. Our approach embodies novel, efficient techniques for dynamically assigning tree-nodes to processors to ensure that the work is shared equitably among them.     

A linear-time algorithm for solving the strong hidden-line problem in a simple polygon

A linear-time algorithm is presented for solving the strong hidden-line problem in a simple polygon P, or alternately, determining the region in P weakly visible from a specified edge of P. The algorithm combines results from visibility and shortest paths with the linear-time polygon triangulation algorithm discovered recently by Tarjan and Van Wyk. Previous published algorithms for the strong hidden-line problem require O(n logn) steps even after triangulation, where n is the cardinality of P.     

On fast planning of suboptimal paths amidst polygonal obstacles in plane

The problem of planning a path for a point robot from a source point s to a destination point d so as to avoid a set of polygonal obstacles in plane is considered. Using well-known methods, a shortest path from s to d can be computed with a time complexity of O(n²) where n is the total number of obstacle vertices. The focus here is in

1. (a) planning paths faster at the expense of setting for suboptimal path lengths and

2. (b) performance analysis of simple and/or well-known suboptimal methods.

A method that enables a hierarchical implementation of any path planning algorithm with no increase in the worst-case time complexity, is presented; this implementation enables fast planning of simple paths. Then methods are presented based on the Voronoi diagrams, trapezoidal decomposition and triangulation, which compute (suboptimal) paths in O(n√log n) time with the preprocessing costs of O(n log n), O(n²) and O(n log n), respectively. Using existing navigational algorithms for unknown terrains, algorithms that run in O(n log n) time (after preprocessing) and yield suboptimal paths, are presented. For all these algorithms, upper bounds on the path lengths are estimated in terms of the shortest of the obstacles, etc.     

Efficient algorithms for single- and two-layer linear placement of parallel graphs

This paper outlines an algorithm for optimum linear ordering (OLO) of a weighted parallel graph with O(n log k) worst-case time complexity, and O(n + k log(n/k) log k) expected-case time complexity, where n is the total number of nodes and k is the number of chains in the parallel graph. Next, the two-layer OLO problem is considered, where the goal is to place the nodes linearly in two routing layers minimizing the total wire length. The two-layer problem is shown to subsume the maxcut problem and a befitting heuristic algorithm is proposed. Experimental results on randomly generated samples show that the heuristic algorithm runs very fast and outputs optimum solutions in more than 90% instances.     

A study of neural network based inverse kinematics solution for a three-joint robot

A neural network based inverse kinematics solution of a robotic manipulator is presented in this paper. Inverse kinematics problem is generally more complex for robotic manipulators. Many traditional solutions such as geometric, iterative and algebraic are inadequate if the joint structure of the manipulator is more complex. In this study, a three-joint robotic manipulator simulation software, developed in our previous studies, is used. Firstly, we have generated many initial and final points in the work volume of the robotic manipulator by using cubic trajectory planning. Then, all of the angles according to the real-world coordinates (x, y, z) are recorded in a file named as training set of neural network. Lastly, we have used a designed neural network to solve the inverse kinematics problem. The designed neural network has given the correct angles according to the given (x, y, z) cartesian coordinates. The online working feature of neural network makes it very successful and popular in this solution.