[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Unstructured graph partitioning for sparse linear system solving

  • Systems and Applications
  • Conference paper
  • First Online:
Solving Irregularly Structured Problems in Parallel (IRREGULAR 1997)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1253))

Abstract

Solving large sparse linear systems is a key issue, arising in a variety of scientific and engineering applications. This paper presents the work carried out at the LaBRI on graph partitioning and its application to efficient parallel solutions of this problem.

This work was supported by the French GDR PRS

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. P. Amestoy, T. Davis, and I. Duff. An approximate minimum degree ordering algorithm. Technical Report RT/APO/95/5, ENSEEIHT-IRIT, 1995. To appear in SIAM Journal of Matrix Analysis and Applications.

    Google Scholar 

  2. C. Ashcraft, S. Eisenstat, J. W.-H. Liu, and A. Sherman. A comparison of three column based distributed sparse factorization schemes. In Proc. Fifth SIAM Conf. on Parallel Processing for Scientific Computing, 1991.

    Google Scholar 

  3. C. Ashcraft, R. Grimes, J. Lewis, B. Peyton, and H. Simon. Recent progress in sparse matrix methods for large linear systems. Intl. J. of Supercomputer Applications, 1(4):10–30, 1987.

    Google Scholar 

  4. S. T. Barnard and H. D. Simon. A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. Concurrency: Practice and Experience, 6(2):101–117, 1994.

    Google Scholar 

  5. S. W. Bollinger and S. F. Midkiff. Processor and link assignment in multicom-puters using simulated annealing. In Proceedings of the 11th Int. Conf. on Parallel Processing, pages 1–7. The Penn. State Univ. Press, August 1988.

    Google Scholar 

  6. T. N. Bui, S. Chaudhuri, F. T. Leighton, and M. Sipser. Graph bisection algorithms with good average case behavior. Combinatorica, 7(2):171–191, 1987.

    Google Scholar 

  7. F. Cao, J. R. Gilbert, and S.-H. Teng. Partitioning meshes with lines and planes. Technical Report CSL-96-01, XEROX Corporation, Palo Alto, California, 1996.

    Google Scholar 

  8. P. Charrier and J. Roman. Algorithmique et calculs de complexité pour un solveur de type dissections emboîtées. Numerische Mathematik, 55:463–476, 1989.

    Google Scholar 

  9. T. Chockalingam and S. Arunkumar. A randomized heuristics for the mapping problem: The genetic approach. Parallel Computing, 18:1157–1165, 1992.

    Google Scholar 

  10. W. Donath and A. Hoffman. Algorithms for partitioning of graphs and computer logic based on eigenvectors of connection matrices. IBM Technical Disclosure Bulletin, 15:938–944, 1972.

    Google Scholar 

  11. M. Dormanns and H.-U. Heiß. Mapping large-scale FEM-graphs to highly parallel computers with grid-like topology by self-organization. Technical Report 5/94, Fakultät für Informatik, Universität Karlsruhe, February 1994.

    Google Scholar 

  12. I. Duff. On algorithms for obtaining a maximum transversal. ACM Trans. Math. Software, 7(3):315–330, September 1981.

    Google Scholar 

  13. F. Ercal, J. Ramanujam, and P. Sadayappan. Task allocation onto a hypercube by recursive mincut bipartitioning. JPDC, 10:35–44, 1990.

    Google Scholar 

  14. C. M. Fiduccia and R. M. Mattheyses. A linear-time heuristic for improving network partitions. In Proc. 19th Design Autom. Conf., pages 175–181. IEEE, 1982.

    Google Scholar 

  15. M. Fiedler. Algebraic connectivity of graphs. Czech. Math. J., 23:298–305, 1973.

    Google Scholar 

  16. M. R. Garey and D. S. Johnson. Computers and Intractablility: A Guide to the Theory of NP-completeness. W. H. Freeman, San Francisco, 1979.

    Google Scholar 

  17. G. A. Geist and E. G.-Y. Ng. Task scheduling for parallel sparse Cholesky factorization. International Journal of Parallel Programming, 18(4):291–314, 1989.

    Google Scholar 

  18. A. George, M. T. Heath, J. W.-H. Liu, and E. G.-Y. Ng. Sparse Cholesky factorization on a local memory multiprocessor. SIAM J. Sci. Stat. Comp., 9:327–340, 1988.

    Google Scholar 

  19. J. A. George and J. W.-H. Liu. Computer solution of large sparse positive definite systems. Prentice Hall, 1981.

    Google Scholar 

  20. A. Gupta, G. Karypis, and V. Kumar. Highly scalable parallel algorithms for sparse matrix factorization. TR 94-063, University of Minnesota, 1994. To appear in IEEE Trans, on Parallel and Distributed Systems, 1997.

    Google Scholar 

  21. A. Gupta, G. Karypis, and V. Kumar. Scalable parallel algorithms for sparse linear systems. In Proc. Stratagem'96, Sophia-Antipolis, pages 97–110. INRIA, July 1996.

    Google Scholar 

  22. S. W. Hammond. Mapping unstructured grid computations to massively parallel computers. PhD thesis, Rensselaer Polytechnic Institute, February 1992.

    Google Scholar 

  23. B. Hendrickson. Mapping results. Personal communication, July 1996.

    Google Scholar 

  24. B. Hendrickson and R. Leland. Multidimensional spectral load balancing. Technical Report SAND93-0074, Sandia National Laboratories, January 1993.

    Google Scholar 

  25. B. Hendrickson and R. Leland. The CHACO user's guide — version 2.0. Technical Report SAND94-2692, Sandia National Laboratories, 1994.

    Google Scholar 

  26. B. Hendrickson and R. Leland. An empirical study of static load balancing algorithms. In Proc. SHPCC'94, Knoxville, pages 682–685. IEEE, May 1994.

    Google Scholar 

  27. B. Hendrickson, R. Leland, and R. Van Driessche. Enhancing data locality by using terminal propagation. In Proceedings of the 29 th Hawaii International Conference on System Sciences. IEEE, January 1996.

    Google Scholar 

  28. B. Hendrickson, R. Leland, and R. Van Driessche. Skewed graph partitioning. In Proceedings of the 8 th SIAM Conference on Parallel Processing for Scientific Computing. IEEE, March 1997.

    Google Scholar 

  29. B. Hendrickson and E. Rothberg. Improving the runtime and quality of nested dissection ordering. Technical Report SAND96-0868J, Sandia National Laboratories, March 1996.

    Google Scholar 

  30. J. Hopcroft and R. Karp. An n 5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal of Computing, 2(4):225–231, December 1973.

    Google Scholar 

  31. G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. TR 95-035, University of Minnesota, June 1995.

    Google Scholar 

  32. G. Karypis and V. Kumar. METIS — Unstructured Graph Partitioning and Sparse Matrix Ordering System — Version 2.0. University of Minnesota, June 1995.

    Google Scholar 

  33. G. Karypis and V. Kumar. Multilevel k-way partitioning scheme for irregular graphs. Technical Report 95-064, University of Minnesota, August 1995.

    Google Scholar 

  34. G. Karypis and V. Kumar. Parallel multilevel k-way partitioning scheme for irregular graphs. TR 96-036, University of Minnesota, 1996.

    Google Scholar 

  35. B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitionning graphs. BELL System Technical Journal, pages 291–307, February 1970.

    Google Scholar 

  36. C. Leiserson and J. Lewis. Orderings for parallel sparse symmetric factorization. In Third SIAM Conference on Parallel Processing for Scientific Computing, Tromsø. SIAM, 1987.

    Google Scholar 

  37. J. W.-H. Liu. Modification of the minimum-degree algorithm by multiple elimination. ACM Trans. Math. Software, 11(2):141–153, 1985.

    Google Scholar 

  38. T. Muntean and E.-G. Talbi. A parallel genetic algorithm for process-processors mapping. High performance computing, 2:71–82, 1991.

    Google Scholar 

  39. E. Ng and B. Peyton. Block sparse Cholesky algorithms on advanced uniprocessor computers. SIAM J. on Scientific Computing, 14:1034–1056, 1993.

    Google Scholar 

  40. D. M. Nicol. Rectilinear partitioning of irregular data parallel computations. Journal of Parallel and Distributed Computing, 23:119–134, 1994.

    Google Scholar 

  41. F. Pellegrini. Static mapping by dual recursive bipartitioning of process and architecture graphs. In Proc. SHPCC'94, Knoxville, pages 486–493. IEEE, May 1994.

    Google Scholar 

  42. F. Pellegrini. Application of graph partitioning techniques to static mapping and domain decomposition. In ETPSC 3, Faverges-de-la-Tour, August 1996. To appear in a special issue of Parallel Computing.

    Google Scholar 

  43. F. Pellegrini and J. Roman. Experimental Analysis of the Dual Recursive Bipartitioning Algorithm for Static Mapping. Research Report 1138-96, LaBRI, Université Bordeaux I, September 1996. Available at URL http://www.labri.u-bordeaux. fr/~pelegrin/papers/scotch_expanalysis.ps.gz.

    Google Scholar 

  44. F. Pellegrini and J. Roman. Sparse matrix ordering with SCOTCH. In Proc. HPCN'97, Vienna, April 1997. To appear.

    Google Scholar 

  45. A. Pothen. MMD code. Personal communication, February 1997.

    Google Scholar 

  46. A. Pothen and C.-J. Fan. Computing the block triangular form of a sparse matrix. ACM Trans. Math. Software, 16(4):303–324, December 1990.

    Google Scholar 

  47. A. Pothen, H. D. Simon, and K.-P. Liou. Partitioning sparse matrices with eigenvectors of graphs. SIAM Journal of Matrix Analysis, 11(3):430–452, July 1990.

    Google Scholar 

  48. E. Rothberg. Performance of panel and block approaches to sparse Cholesky factorization on the iPSC/860 and Paragon multicomputers. In Proceedings of SHPCC'94, Knoxville, pages 324–333. IEEE, May 1994.

    Google Scholar 

  49. E. Rothberg and A. Gupta. An efficient block-oriented approach to parallel sparse Cholesky factorization. In Supercomputing'93 Proceedings. IEEE, 1993.

    Google Scholar 

  50. E. Rothberg and R. Schreiber. Improved load distribution in parallel sparse Cholesky factorization. In Supercomputing'94 Proceedings. IEEE, 1994.

    Google Scholar 

  51. R. Schreiber. Scalability of sparse direct solvers. Technical Report TR 92.13, RIACS, NASA Ames Research Center, May 1992.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. LaBRI, URA CNRS 1304, Université Bordeaux I 351, cours de la Libération, 33405, Talence, France

    Jean Michel, François Pellegrini & Jean Roman

Authors
  1. Jean Michel
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. François Pellegrini
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jean Roman
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Gianfranco Bilardi Afonso Ferreira Reinhard Lüling José Rolim

Rights and permissions

Reprints and permissions

Copyright information

© 1997 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Michel, J., Pellegrini, F., Roman, J. (1997). Unstructured graph partitioning for sparse linear system solving. In: Bilardi, G., Ferreira, A., Lüling, R., Rolim, J. (eds) Solving Irregularly Structured Problems in Parallel. IRREGULAR 1997. Lecture Notes in Computer Science, vol 1253. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-63138-0_23

Download citation

  • DOI: https://doi.org/10.1007/3-540-63138-0_23

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-63138-5

  • Online ISBN: 978-3-540-69157-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation