This paper discusses microplane models from the computational point of view. The basic introduction to microplane based models will be given. The computational aspects of these models will be discussed in details and ...
详细信息
This paper discusses microplane models from the computational point of view. The basic introduction to microplane based models will be given. The computational aspects of these models will be discussed in details and an efficient parallel algorithm for explicit time integration will be proposed. The efficiency of the algorithm will be presented. (C) 2002 Civil-Comp Ltd. and Elsevier Science Ltd. All rights reserved:
parallelization of the P-complete problem is known to be difficult. In this paper, we consider the parallelizability of a stack breadth-first search (stack BFS) problem, which is proved to be P-complete. We first prop...
详细信息
parallelization of the P-complete problem is known to be difficult. In this paper, we consider the parallelizability of a stack breadth-first search (stack BFS) problem, which is proved to be P-complete. We first propose the longest path length (LPL) as a measure for the P-completeness of the stack BFS. Next, using this measure, we propose an efficient parallel algorithm for the stack BFS. Assuming the size and LPL of an input graph are n and 1, respectively, the complexity of the algorithm indicates that the stack BFS is in the class NCk+1 if l = O(log(k) n), where k is a positive integer. In addition, the algorithm is cost optimal if l = O(n(is an element of)), where 0 < is an element of < 1.
作者：
Kim, HKorea Univ
Grad Sch Informat Secur Seoul 136701 South Korea
We present parallel algorithms for the process of the biorthogonal wavelet transform(BWT). We have constructed processing elements (PEs) for the decomposition and reconstruction of the BWT to minimize computational op...
详细信息
ISBN:
(纸本)3540240136
We present parallel algorithms for the process of the biorthogonal wavelet transform(BWT). We have constructed processing elements (PEs) for the decomposition and reconstruction of the BWT to minimize computational operations. They can be performed using only integer shift and superposition operations;therefore, they may be applied to the implementation of image compression standards based on BWT, such as JPEG2000.
Based on the thought of Gauss-Seidel iteration, a parallel algorithm is proposed for solving the least-square problems, the method is proved to be convergent. The calculated amount is greatly reduced, thus calculating...
详细信息
Based on the thought of Gauss-Seidel iteration, a parallel algorithm is proposed for solving the least-square problems, the method is proved to be convergent. The calculated amount is greatly reduced, thus calculating time is saved extensively when the method is used, because only triangle decomposition is needed for one of the submatrices of Matrix Jacobi and the decomposition is not needed for the whole Jacobi.
The paper deals with the problem of analyzing fault, susceptibility of a parallel algorithm designed for multiprocessor array (MIMD structure). This algorithm realizes quite complex communication protocol in the syste...
详细信息
ISBN:
(纸本)0769517307;0769517315
The paper deals with the problem of analyzing fault, susceptibility of a parallel algorithm designed for multiprocessor array (MIMD structure). This algorithm realizes quite complex communication protocol in the system. We present an original methodology of the analysis based on the use of software implemented fault injector. The considered algorithm is modeled as a multithreaded application. The experiment set up an I results are presented and commented The performed experiments proved relatively high natural robustness of the analyzed algorithm and showed further possibilities of its improvement.
A parallel algorithm for Euclidean Distance Transform (EDT) on linear array with reconfigurable pipeline bus system (LARPBS) is presented. For an image with n x n pixels, the algorithm can complete EDT transform in O(...
详细信息
A parallel algorithm for Euclidean Distance Transform (EDT) on linear array with reconfigurable pipeline bus system (LARPBS) is presented. For an image with n x n pixels, the algorithm can complete EDT transform in O(*** n/c(n).log d(n)) time using n.d(n).c(n) processors, where c(n) and d(n) are parameters satisfying 1 less than or equal to c(n) less than or equal to n, and 1 < d(n) <= n, respectively. By selecting different c(n) and d(n), the time complexity and the number of processors used can be adjusted. This makes the algorithm highly scalable and flexible. The algorithm also provides a general framework for EDT algorithms on LARPBS, and many existing and unknown parallel EDT algorithms can be deduced from this framework. In particular, if we let c(n) = n, d(n) = n(epsilon), the algorithm can be completed in O(1) time using n(2+epsilon) processors. To the best of our knowledge, this is the most efficient constant-time EDT algorithm on LARPBS.
In this paper, a sequential algorithm is presented to find all cut-vertices on trapezoid graphs. To every trapezoid graph G there is a corresponding trapezoid representation. If all the 4n corner points of n trapezoid...
详细信息
In this paper, a sequential algorithm is presented to find all cut-vertices on trapezoid graphs. To every trapezoid graph G there is a corresponding trapezoid representation. If all the 4n corner points of n trapezoids, in a trapezoid representation of a trapezoid graph G with n vertices, are given, then the proposed sequential algorithm runs in O(n) time. parallel implementation of this algorithm can be done in O( log n) time using O(n/log n) processors on an EREW PRAM model.
The free partially commutative monoid M(A, 0) defined by a set of commutation relations 0 on an alphabet A can be viewed as a model for concurrent computing: indeed, the independence or the simultaneity of two actions...
详细信息
The free partially commutative monoid M(A, 0) defined by a set of commutation relations 0 on an alphabet A can be viewed as a model for concurrent computing: indeed, the independence or the simultaneity of two actions can be interpreted by the commutation of two letters that encode them. In this context, the commutation class C-Theta(w) of a word w of the free monoid A* plays a crucial role. The main results presented in this paper are the following: A characterization of the minimal automaton A(Theta)(w) for C-Theta(w) with the help of the new notion of Theta-dissection. A parallel algorithm which computes the minimal automaton A(Theta)(w). This algorithm is optimal if the size of A is constant. An optimal parallel algorithm for testing if a word belongs to the commutation class C-Theta(w). Our approach differs completely from the methods (based on Foata's normal form) used by Cerin and Petit (Application de la theorie des traces A l'implantation et A la mesure d'algorithmes de distribution, These Universite Paris 11, Centre d'Orsay, 1993 Proc. 6th Internal. parallel Processing Symp. (IPPS), IEEE Press, New York, 1992, pp. 374-379;Proc. MFCS'93, Lecture Notes in Computer Science, Vol. 711, Springer, Berlin, 1993, pp. 332-341) for solving similar problems. Under some assumptions the first algorithm achieves an optimal speedup. The second algorithm achieves also an optimal speedup and has a time complexity in O(log n) if the number of processors is in O(n) where n is the length of the word w, the total number of operations is in O(n) and does not depend on the size of the alphabet A as for the classical sequential algorithm. (C) 2004 Elsevier B.V. All rights reserved.
A parallel algorithm for Hough transform on a linear array with reconfigurable pipeline bus system (LARPBS) is presented. Suppose the number of theta-values to be considered is m, for an image with n x n pixels, the a...
详细信息
A parallel algorithm for Hough transform on a linear array with reconfigurable pipeline bus system (LARPBS) is presented. Suppose the number of theta-values to be considered is m, for an image with n x n pixels, the algorithm can complete Hough transform in O(1) time using mn(2) processors and achieve optimal speed and efficiency. We also illustrate how to partition data and perform the algorithm on a LARPBS with fewer than mn(2) processors, and hence show that the algorithm is highly scalable.
The free partially commutative monoid M(A, 0) defined by a set of commutation relations 0 on an alphabet A can be viewed as a model for concurrent computing: indeed, the independence or the simultaneity of two actions...
详细信息
The free partially commutative monoid M(A, 0) defined by a set of commutation relations 0 on an alphabet A can be viewed as a model for concurrent computing: indeed, the independence or the simultaneity of two actions can be interpreted by the commutation of two letters that encode them. In this context, the commutation class C-Theta(w) of a word w of the free monoid A* plays a crucial role. The main results presented in this paper are the following: A characterization of the minimal automaton A(Theta)(w) for C-Theta(w) with the help of the new notion of Theta-dissection. A parallel algorithm which computes the minimal automaton A(Theta)(w). This algorithm is optimal if the size of A is constant. An optimal parallel algorithm for testing if a word belongs to the commutation class C-Theta(w). Our approach differs completely from the methods (based on Foata's normal form) used by Cerin and Petit (Application de la theorie des traces A l'implantation et A la mesure d'algorithmes de distribution, These Universite Paris 11, Centre d'Orsay, 1993 Proc. 6th Internal. parallel Processing Symp. (IPPS), IEEE Press, New York, 1992, pp. 374-379;Proc. MFCS'93, Lecture Notes in Computer Science, Vol. 711, Springer, Berlin, 1993, pp. 332-341) for solving similar problems. Under some assumptions the first algorithm achieves an optimal speedup. The second algorithm achieves also an optimal speedup and has a time complexity in O(log n) if the number of processors is in O(n) where n is the length of the word w, the total number of operations is in O(n) and does not depend on the size of the alphabet A as for the classical sequential algorithm. (C) 2004 Elsevier B.V. All rights reserved.
暂无评论