For solving systems of linear algebraic equations with block fivediagonal matrices arising in geoelectrics and diffusion problems, the parallel matrix square root method, conjugate gradient method with pre-conditioner...
详细信息
For solving systems of linear algebraic equations with block fivediagonal matrices arising in geoelectrics and diffusion problems, the parallel matrix square root method, conjugate gradient method with pre-conditioner, conjugate gradient method with regularization, and parallel matrix sweep algorithm are proposed and some of them are implemented numerically on multi-core CPU Intel. Investigation of efficiency and optimization of parallel algorithms for solving the problem with quasi-model data are performed. The problem with quasi-model data is solved.
Techniques for parallel algorithms on chordal graphs are developed. An NC algorithm for recognizing chordal graphs is developed, as are NC algorithms for finding the following objects in chordal graphs: all maximal cl...
详细信息
Techniques for parallel algorithms on chordal graphs are developed. An NC algorithm for recognizing chordal graphs is developed, as are NC algorithms for finding the following objects in chordal graphs: all maximal cliques, an intersection graph representation, an optimal coloring, a perfect elimination scheme, a weighted maximum independent set, and a minimum clique cover. The recognition algorithm presented in this paper is simpler than previous algorithms given by Edenbrandt and by Chandrasekharan and Iyengar; the other problems were apparently open. The known polynomial-time algorithms for these problems seem highly sequential, and therefore a different approach to find parallel algorithms is used.
We present in this paper two parallel algorithms for the two-dimensional discrete wavelet transform. A mathematical model for the computation vs. communication tradeoff for these algorithms is presented and the scalab...
详细信息
COUPL+ is a programming environment for applications using unstructured and hybrid grids for numerical simulations. It automates parallelization by handling the partitioning of data and dependent data and maintaining ...
详细信息
COUPL+ is a programming environment for applications using unstructured and hybrid grids for numerical simulations. It automates parallelization by handling the partitioning of data and dependent data and maintaining halo interfaces and copy coherency. We explore some algorithms behind this package. A multi-level partitioning method is described which is effective in the presence of skewed data, solving the multi-set median-finding problem. Partitioning elements over a set of pre-partitioned nodes is explored and a novel method is suggested for reducing communication in the resulting distribution. (C) 2001 Elsevier Science B.V. All rights reserved.
Ranking a tree is defined as a mapping rho of the nodes to the set (1, 2,...) such that if there is a path from u to v and rho (u)= rho (v) then there is a node w on the path from u to v such that rho (w)> rho (u)....
详细信息
In this paper, we consider parallel algorithms for shortest paths and related problems on trapezoid graphs under the CREW PRAM model. Given a trapezoid graph with its corresponding trapezoid diagram, we present parall...
详细信息
One of the important problems in the use of remote sensing from satellites is three-dimensional modeling of surface—fragments both dynamic (e.g., ocean surface) and slowly varying ones. Some researchers propose the u...
详细信息
Expressed sequence tags, abbreviated as ESTs, are DNA molecules experimentally derived from expressed portions of genes. Clustering of ESTs is essential for gene recognition and for understanding important genetic var...
详细信息
Expressed sequence tags, abbreviated as ESTs, are DNA molecules experimentally derived from expressed portions of genes. Clustering of ESTs is essential for gene recognition and for understanding important genetic variations such as those resulting in diseases. In this paper, we present the algorithmic foundations and implementation of PaCE, a parallel software system we developed for large-scale EST clustering. The novel features of our approach include 1) design of space-efficient algorithms to limit the space required to linear in the size of the input data set, 2) a combination of algorithmic techniques to reduce the total work without sacrificing the quality of EST clustering, and 3) use of parallel processing to reduce runtime and facilitate clustering of large data sets. Using a combination of these techniques, we report the clustering of 327,632 rat ESTs in 47 minutes, and 420,694 Triticum aestivum ESTs in 3 hours and 15 minutes, using a 60-processor IBM xSeries cluster. These problems are well beyond the capabilities of state-of-the-art sequential software. We also present thorough experimental evaluation of our software including quality assessment using benchmark Arabidopsis EST data.
Developing parallel algorithms for intermediate and high levels of computer vision systems is addressed. Because the algorithms are complex and the nature and size of the input and output data sets vary for each appli...
详细信息
Developing parallel algorithms for intermediate and high levels of computer vision systems is addressed. Because the algorithms are complex and the nature and size of the input and output data sets vary for each application, the authors have directly developed parallel algorithms for dynamic control of both processing and communication complexity during execution. They have also examined the merits of functional prototyping and transforming programs into imperative execution code for final implementation. To evaluate and give direction to their work, they have implemented algorithms for plane detection and object recognition on a flexible transputer network.
Two novel variations on sample sort, one using only two rounds of regular all-to-all personalized communication in a scheme that yields very good load balancing with virtually no overhead and another using regular sam...
详细信息
Two novel variations on sample sort, one using only two rounds of regular all-to-all personalized communication in a scheme that yields very good load balancing with virtually no overhead and another using regular sampling for choosing splitters, were studied. The two were coded in Split-C and were run on a variety of platforms. Results were consistent with theoretical analysis and illustrated the scalability and efficiency of the algorithms.
暂无评论