Abstract
In this work, we show the deficiencies of the graph model for decomposing sparse matrices for parallel matrix-vector multiplication. Then, we propose two hypergraph models which avoid all deficiencies of the graph model. The proposed models reduce the decomposition problem to the well-known hypergraph partitioning problem widely encountered in circuit partitioning in VLSI. We have implemented fast Kernighan-Lin based graph and hypergraph partitioning heuristics and used the successful multilevel graph partitioning tool (Metis) for the experimental evaluation of the validity of the proposed hypergraph models. We have also developed a multilevel hypergraph partitioning heuristic for experimenting the performance of the multilevel approach on hypergraph partitioning. Experimental results on sparse matrices, selected from Harwell-Boeing collection and NETLIB suite, confirm both the validity of our proposed hypergraph models and appropriateness of the multilevel approach to hypergraph partitioning.
This work is partially supported by the Commission of the European Communities, Directorate General for Industry under contract ITDC 204-82166, and Turkish Science and Research Council under grant EEEAG-160.
Preview
Unable to display preview. Download preview PDF.
References
C. J. Alpert, L. W. Hagen, and A. B. Kahng. A hybrid multilevel/genetic approach for circuit partitioning. Technical report, UCLA CS Dept., 1996.
C. J. Alpert and A. B. Kahng. Recent directions in netlist partitioning: A survey. VLSI Journal, 19(1–2):1–81, 1995.
Ü. V. Çatalyürek and C. Aykanat. A hypergraph model for mapping repeated sparse matrix-vector product computations onto multicomputers. In Proceedings of International Conference on Hyperformance Computing, December 1995.
I. S. Duff, R. Grimes, and J. Lewis. Sparse matrix test problems. ACM Transactions on Mathematical Software, 15(1):1–14, march 1989.
F. Erçal, C. Aykanat, F. Özgüner and P. Sadayappan. Iterative algorithms for solution of large sparse systems of linear equations on hypercubes. IEEE Transactions on Computers, 37:1554–1567, 1988.
C. M. Fiduccia and R. M. Mattheyses. A linear-time heuristic for improving network partitions. In Proceedings of the 19th ACM/IEEE Design Automation Conference, pages 175–181, 1982.
D. M. Gay. Electronic mail distribution of linear programming test problems. Mathematical Programming Society COAL Newsletter, 1985.
B. Hendrickson and R. Leland. A multilevel algorithm for partitioning graphs. Technical report, Sandia National Laboratories, 1993.
B. A. Hendrickson, W. Camp, S. J. Plimpton and R. W. Leland. Massively parallel methods for engineering and science problems. Communication of ACM, 37(4):31–41, April 1994.
G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. Tech. report, CS Dept., University of Minnesota, 1995.
B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 49(2):291–307, February 1970.
C. Pommerell, M. Annaratone, and W. Fichtner. A set of new mapping and colloring heuristics for distributed-memory parallel processors. SIAM Journal of Scientific and Statistical Computing, 13(1):194–226, January 1992.
J. Ramanujam, F. Erçal and P. Sadayappan. Task allocation onto a hypercube by recursive mincut bipartitioning. J. Parallel and Bist. Comput., 10:35–44, 1990.
D. G. Schweikert and B. W. Kernighan. A proper model for the partitioning of electrical circuits. In Proceedings of the 9th ACM/IEEE Design Automation Conference, pages 57–62, 1972.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Çatalyürek, Ü.V., Aykanat, C. (1996). Decomposing irregularly sparse matrices for parallel matrix-vector multiplication. In: Ferreira, A., Rolim, J., Saad, Y., Yang, T. (eds) Parallel Algorithms for Irregularly Structured Problems. IRREGULAR 1996. Lecture Notes in Computer Science, vol 1117. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0030098
Download citation
DOI: https://doi.org/10.1007/BFb0030098
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61549-1
Online ISBN: 978-3-540-68808-2
eBook Packages: Springer Book Archive