To minimize the amount of computation and storage for parallel sparse factorization, sparse matrices have to be reordered prior to factorization. We show that none of the popular ordering heuristics proposed before, n...
详细信息
ISBN:
(纸本)9780897916653
To minimize the amount of computation and storage for parallel sparse factorization, sparse matrices have to be reordered prior to factorization. We show that none of the popular ordering heuristics proposed before, namely, mulitple minimum degree and nested dissection, perform consistently well over a range of matrices arising in diverse application domains. Spectral partitioning has been previously proposed as a means of generating small vertex separators for nested dissection of sparse matrices, so that the resulting ordering is amenable to efficient distributed parallel factorization with good load balance and low inter-processor communication. We show that nested dissection using spectral partitioning performs well for matrices arising from finite-element discretizations, but results in excessive fill compared to the minimum degree ordering for unstructured matrices such as power matrices and those arising from circuit simulation. The relative effectiveness of these two ordering schemes for parallel factorization is shown to vary widely for matrices arising from different application domains. We present an ordering strategy that performs consistently well for all matrix types. Its ordering is comparable or better than either minimum degree or nested dissection for all matrices evaluated. Performance results on the Intel iPSC/860 are reported.
The estimation of spectral density functions for singular Sturm-Liouville problems having continuous spectrum is a computationally intensive task. In this paper we adapt the algorithm from the software package SLEDGE,...
详细信息
Thinning algorithms are widely used in pattern recognition. This processing stage is implemented on serial machines as well as on parallel machines. We can find two classes of thinning algorithms in the literature. Th...
详细信息
Thinning algorithms are widely used in pattern recognition. This processing stage is implemented on serial machines as well as on parallel machines. We can find two classes of thinning algorithms in the literature. The first class is composed of strongly sequential algorithms, based on contour tracing of the objects to be thinned. The second class is made of iterative processes in which fully parallel mask-based operators are used at each iteration. The weakness of the contour tracing based methods is its strong dependence upon the original picture. Particularly, in the case of very complex pictures, this algorithm becomes inefficient. The second thinning class of algorithms uses strongly regular operating processes. The general speed of those methods also depends upon the shapes to be thinned. The iteration number necessary to complete these iterative processes is proportional to the maximum thickness of the objects in the picture. The complexity of the contour of the objects does not influence the efficiency of the algorithm. The goal of this paper is to keep the regularity of the second class of thinning processes, but to reduce the amount of standard parallel-operations. We use a partition of the original picture and we dynamically reduce the range of the full-parallel operator in its sub-picture.
暂无评论