Skip to main content
SpringerLink
Log in

Graph Partitioning Algorithms with Applications to Scientific Computing

  • Chapter
Parallel Numerical Algorithms

Part of the book series: ICASE/LaRC Interdisciplinary Series in Science and Engineering ((ICAS,volume 4))

Abstract

Identifying the parallelism in a problem by partitioning its data and tasks among the processors of a parallel computer is a fundamental issue in parallel computing. This problem can be modeled as a graph partitioning problem in which the vertices of a graph are divided into a specified number of subsets such that few edges join two vertices in different subsets. Several new graph partitioning algorithms have been developed in the past few years, and we survey some of this activity.

We describe the terminology associated with graph partitioning, the complexity of computing good separators, and graphs that have good separators. We then discuss early algorithms for graph partitioning, followed by three new algorithms based on geometric, algebraic, and multilevel ideas. The algebraic algorithm relies on an eigenvector of a Laplacian matrix associated with the graph to compute the partition. The algebraic algorithm is justified by formulating graph partitioning as a quadratic assignment problem. We list several papers that describe applications of graph partitioning to parallel scientific computing and other applications. Finally we discuss the application of graph partitioning to obtain nested dissection orderings for solving sparse linear systems of equations in parallel.

This work was supported by National Science Foundation grants CCR-9412698 and DMS-9505110, by U. S. Department of Energy grant DE-FG05-94ER25216, and by the National Aeronautics and Space Administration under NASA Contract NAS 1-19480 while the author was in residence at the Institute for Computer Applications in Science and Engineering (ICASE), NASA Langley Research Center, Hampton, VA 23681-0001.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 169.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 219.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD 219.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  • Agrawal, A., Klein, P.N., and Ravi, R., 1993. “Cutting down on fill using nested dissection: Provably good elimination orderings,” in Graph Theory and Sparse Matrix Computation, A. George, J.R. Gilbert, and J.W.H. Liu, eds., IMA Volumes in Mathematics and its Applications 56, Springer Verlag, Berlin, pp. 31–55.

    Google Scholar 

  • Alon, N. and Milman, V., 1985. “λ1, isoperimetric inequalities for graphs, and superconcentrators,” J. of Combin. Theory, Series B 38, pp. 73–88.

    Google Scholar 

  • Alpert, C.J. and Kahng, A., 1995. “Recent directions in netlist partitioning: A survey,” Integration: The VLSI Journal 19, pp. 1–81.

    MATH  Google Scholar 

  • Arun, K.S. and Rao, V.B., 1993. “Constructive heuristics and lower bounds for graph partitioning based on a principal components approximation,” SIAM J. Matrix Anal. Appl. 14, pp. 991–1015.

    MathSciNet  MATH  Google Scholar 

  • Ashcraft, C. and Liu, J.W.H., 1995. “Using domain decomposition to find graph bisectors,” Tech. Report CS-95-08, Department of Computer Science, York University, North York, Ontario, Canada, M3J 1P3.

    Google Scholar 

  • Ashcraft, C. and Liu, J.W.H., 1996. “Robust ordering of sparse matrices using multisection”, Tech. Report CS-96-01, Department of Computer Science, York University, North York, Ontario, Canada, M3J 1P3.

    Google Scholar 

  • Aspvall, B. and Gilbert, J.R., 1984. “Graph coloring using eigenvalue decomposition,” SIAM J. Alg. Disc. Meth. 5, pp. 526–538.

    MathSciNet  MATH  Google Scholar 

  • Barnard, S.T., Pothen, A., and Simon, H.D., 1995. “A spectral algorithm for envelope reduction of sparse matrices,” Numer. Lin. Alg. Applics. 2, pp. 317–334.

    MathSciNet  MATH  Google Scholar 

  • Barnard, S.T. and Simon, H.D., 1994. “A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems,” Concurrency: Practice and Experience 6, pp. 101–117.

    Google Scholar 

  • Barnes, E.R., 1982. “An algorithm for partitioning the nodes of a graph,” SIAM J. Alg. Disc. Meth. 3, pp. 541–550.

    MATH  Google Scholar 

  • Berger, M. J., and Bokhari, S., 1987. “A partitioning strategy for nonuniform problems on multiprocessors,” IEEE Trans. Computers C-36, pp. 570–580.

    Google Scholar 

  • Biggs, N., 1993. Algebraic Graph Theory, second edition, Cambridge University Press, Cambridge.

    Google Scholar 

  • Bollobás, B., 1979. Graph Theory: An introductory course, Springer Verlag, Berlin.

    MATH  Google Scholar 

  • Boppana, R.B., 1987. “Eigenvalues and graph bisection: An average case analysis,” Proc. 28th Ann. Symp. Foundations of Computer Science, pp. 280–285.

    Google Scholar 

  • Bui, T.N., Fukuyama, F., and Jones, C., 1994. “The planar vertex separator problem: Complexity and algorithms,” Manuscript, Department of Computer Science, Pennsylvania State University, Harrisburg, PA.

    Google Scholar 

  • Bui, T.N. and Jones, C., 1992. “Finding good approximate vertex and edge partitions is NP-hard,” Inf. Process. Letters 42, pp. 153–159.

    MathSciNet  MATH  Google Scholar 

  • Bui, T.N. and Jones, C., 1993. “A heuristic for reducing fill-in in sparse matrix factorization,” Proc. Sixth SIAM Conf. on Parallel Processing for Scientific Computing, SIAM, Philadelphia, pp. 445–452.

    Google Scholar 

  • Bui, T.N. and Moon, B.R., 1993. “A genetic algorithm for a special class of the quadratic assignment problem,” in The Quadratic Assignment and Related Problems, P. Pardalos and H. Wolkow-icz, eds., DIMACS Series on Discrete Mathematics and Theoretical Computer Science, AMS, Providence.

    Google Scholar 

  • Chan, T.F., Ciarlet, P., Jr., and Szeto, W.K., 1993. “On the near optimality of the recursive spectral bisection method for graph partitioning,” Manuscript, Department of Computer Science, University of California at Los Angeles.

    Google Scholar 

  • Chan, T.F., Gilbert, J.R., and Teng, S.-H., 1994. “Geometric spectral bisection,” Preprint, Xerox Palo Alto Research Center.

    Google Scholar 

  • Chan, T.F. and Mathew, T.P., 1994. “Domain decomposition algorithms,” Acta Numerica 3, pp. 61–143.

    MathSciNet  Google Scholar 

  • Chrisochoides, N., Mansour, N., and Fox, G., 1994. “Mapping algorithms and software environment for data parallel PDE iterative solvers,” J. Par. Dist. Comp. 21, pp. 75–95.

    Google Scholar 

  • Chrisochoides, N., Mansour, N., and Fox, G., 1993. “Performance evaluation of data mapping algorithms for parallel single-phase iterative PDE solvers,” Preprint, Northeast Parallel Architectures Center, Syracuse University.

    Google Scholar 

  • Chu, E.G., George, J.A., Liu, J.W., and Ng, E.G., 1984. “User’s guide for SPARSPAK-A: Waterloo sparse linear equations package,” Tech. Report CS-84-36, Computer Science, University of Waterloo, Ontario, Canada.

    Google Scholar 

  • Ciarlet, P., Jr. and Lamour, F., April 1994. “Spectral partitioning methods and greedy partitioning methods: A comparison on finite element graphs,” Tech. Report 94-9, Department of Mathematics, University of California at Los Angeles.

    Google Scholar 

  • Ciarlet, P., Jr., Lamour, F., and Smith, B.F., 1995. “On the influence of the partitioning scheme on the efficiency of overlapping domain decomposition methods,” Fifth Symp. Frontiers of Massively Parallel Computation, IEEE Press, Los Alamitos, pp. 375–383.

    Google Scholar 

  • Cvetkovic, D., Doob, M., and Sachs, H., 1980. Spectra of Graphs, Academic Press, New York.

    Google Scholar 

  • Cvetkovic, D.M., Doob, M., Gutman, I., and Torgasev, A., 1988. “Recent Results in the Theory of Graph Spectra”, Annals of Discrete Mathematics 36, North Holland.

    Google Scholar 

  • Dagum, L., 1995. “Automatic partitioning of unstructured grids into connected components,” Preprint, Computer Science Corporation, NASA Ames Research Center, Moffett Field, CA.

    Google Scholar 

  • Das, R., Mavriplis, D.J., Saltz, J., Gupta, S., and Ponnusamy, R., 1992. “The design and implementation of a parallel unstructured Euler solver using software primitives,” Proc. AIAA 30th Aerospace Sciences Meeting, Paper AIAA-92-0562.

    Google Scholar 

  • Donath, W.E. and Hoffman, A.J., 1973. “Lower bounds for the partitioning of graphs,” IBM Journal of Research and Development 17, pp. 420–425.

    MathSciNet  MATH  Google Scholar 

  • Duff, I.S., Erisman, A.M., and Reid, J.K., 1986. Direct Methods for Sparse Matrices, Clarendon Press, Oxford.

    MATH  Google Scholar 

  • Duff, I.S., Grimes, R.G., and Lewis, J.G., 1989. “Sparse matrix test problems,” ACM Trans. on Math. Soft. 15, pp. 1–14.

    MATH  Google Scholar 

  • Falkner, J., Rendl, F., and Wolkowicz, H., 1994. “A computational study of graph partitioning,” Math. Programming 66, no.2 Ser. A, pp. 211–239.

    MathSciNet  MATH  Google Scholar 

  • Farhat, C., Lanteri, S., and Simon, H.D., 1995. “TOP/DOMDEC: A software tool for mesh partitioning and parallel processing,” Computing Systems in Engineering 6, pp. 13–26.

    Google Scholar 

  • Farhat, C. and Roux, F.X., 1994. “Implicit parallel processing in structural mechanics,” Computational Mechanics Advances 2, pp. 1–124.

    MathSciNet  MATH  Google Scholar 

  • Fiduccia, C. and Mattheyses, R., 1982. “A linear time heuristic for improving network partitions,” ACM — IEEE 19th Design Automation Conf., IEEE Press, Los Alamitos, pp. 175–181.

    Google Scholar 

  • Fiedler, M., 1973. “Algebraic connectivity of graphs,” Czech. Math. J. 23, pp. 298–305.

    MathSciNet  Google Scholar 

  • Fiedler, M., 1975. “A property of eigenvectors of non-negative symmetric matrices and its applications to graph theory,” Czech. Math. J. 25, pp. 619–633.

    MathSciNet  Google Scholar 

  • Garey, M.R. and Johnson, D.S., 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman.

    Google Scholar 

  • George, A. and Liu, J.W.H., 1981. Computer Solution of Large Sparse Positive Definite Systems, Prentice Hall, Englewood Cliffs.

    MATH  Google Scholar 

  • George, A., 1973. “Nested dissection of a regular finite element mesh,” SIAM J. Numer. Anal 10, pp. 345–363.

    MathSciNet  MATH  Google Scholar 

  • George, A. and Liu, J.W.H., 1989. “The evolution of the minimum degree algorithm,” SIAM Review 31, pp. 1–19.

    MathSciNet  MATH  Google Scholar 

  • George, A. and Pothen, A., 1995. “Analysis of the spectral approach to envelope reduction via a quadratic assignment formulation,” SIAM J. Matrix Anal. Appl. (to appear).

    Google Scholar 

  • Gilbert, J.R., 1980. “Graph Separator Theorems and Sparse Gaussian Elimination,” PhD thesis, Stanford University.

    Google Scholar 

  • Gilbert, J.R., Miller, G.L., and Teng, S.-H., 1994. “Geometric mesh partitioning: Implementation and experiments,” Tech. Report CSL-94-13, Xerox Palo Alto Research Center.

    Google Scholar 

  • Gilbert, J.R. and Zmijewski, E., 1987. “A parallel graph partitioning algorithm for a message-passing multiprocessor,” International Journal of Parallel Programming 16, pp. 427–449.

    MathSciNet  MATH  Google Scholar 

  • Goehring, T. and Saad, Y., 1994. “Heuristic algorithms for automatic graph partitioning,” Tech. Report, Department of Computer Science, University of Minnesota, Minneapolis.

    Google Scholar 

  • Golub, G.H. and Van Loan, C.F., 1989. Matrix Computations, second edition, Johns Hopkins University Press, Baltimore.

    MATH  Google Scholar 

  • Guattery, S. and Miller, G., 1995. “On the performance of spectral graph partitioning methods,” 6th ACM — SIAM Symp. on Discrete Algorithms, San Francisco, CA, ACM-SIAM, Philadelphia, pp. 233–242.

    Google Scholar 

  • Hagen, L. and Kahng, A., 1992. “New spectral methods for ratio cut partitioning and clustering,” IEEE Transactions on Computer-Aided Design 11, pp.1074–1085.

    Google Scholar 

  • Hall, K.M., 1970. “An r-dimensional quadratic placement algorithm,” Management Science 17, pp. 219–229.

    MATH  Google Scholar 

  • Hammond, S., 1992. “Mapping unstructured grid computations to massively parallel computers,” PhD thesis, Rensselaer Polytechnic Institute, Troy, NY, RIACS Report 92-14.

    Google Scholar 

  • Heath, M.T., Ng, E.G.Y., and Peyton, B.W., 1991. “Parallel algorithms for sparse linear systems,” SIAM Review 33, pp. 420–460.

    MathSciNet  MATH  Google Scholar 

  • Heath, M.T. and Raghavan, P., 1995. “A Cartesian parallel nested dissection algorithm,” Tech. Report 92-1772, Department of Computer Science, University of Illinois, Urbana.

    Google Scholar 

  • Hendrickson, B. and Leland, R., 1993. “The CHACO user’s guide,” Tech. Report 93-2339, Sandia National Labs, Albuquerque, NM.

    Google Scholar 

  • Hendrickson, B. and Leland, R., 1993. “Multidimensional load balancing,” Tech. Report 93-0074, Sandia National Labs, Albuquerque, NM.

    Google Scholar 

  • Hendrickson, B. and Leland, R., 1993. “A multilevel algorithm for partitioning graphs,” Tech. Report 93-1301, Sandia National Labs, Albuquerque, NM.

    Google Scholar 

  • Hendrickson, B. and Leland, R., 1995. “An improved spectral graph partitioning algorithm for mapping parallel computations,” SIAM J. Stat Comput. 16, pp. 452–469.

    MathSciNet  MATH  Google Scholar 

  • Hendrickson, B. and Rothberg, E., 1996. “Improving the runtime and quality of nested dissection ordering,” Preprint. Silicon Graphics, Inc., Mountain View, CA94043.

    Google Scholar 

  • Hodgson, D.C. and Jimack, P.K., 1993. “Efficient mesh partitioning for parallel PDE solvers on distributed memory machines,” Tech. Report 93-1, School of Computer Studies, University of Leeds.

    Google Scholar 

  • Hsieh, S.H., Paulino, G.H., and Abel, J.F., 1993. “Recursive spectral algorithms for automatic domain partitioning in parallel finite element analysis,” Preprint, Civil Engineering Department, Cornell University.

    Google Scholar 

  • Johan, Z., 1992. “Data parallel finite element techniques for large-scale Computational Fluid Dynamics,” PhD thesis, Stanford University.

    Google Scholar 

  • Johan, Z., Mathur, K.K., Johnsson, S.L., and Hughes, T.J.R., 1994. “Parallel implementation of recursive spectral bisection on the Connection Machine CM-5 system,” Tech. Report 07-94, Center for Research in Computing Technology, Harvard University.

    Google Scholar 

  • Johnson, D., Aragon, C., McGeoch, L., and Schevon, C., 1989. “Optimization by simulated annealing: An experimental evaluation, Part I, Graph Partitioning,” Operations Research 37, pp. 865–892.

    MATH  Google Scholar 

  • Jones, C., 1992. “Vertex and edge partitions of graphs,” PhD thesis, The Pennsylvania State University.

    Google Scholar 

  • Karypis, G. and Kumar, V., 1995. “A fast and high quality multilevel scheme for partitioning irregular graphs,” Tech. Report 95-035, Computer Science Department, University of Minnesota.

    Google Scholar 

  • Karypis, G. and Kumar, V., 1995. “Parallel multilevel graph partitioning,” Tech. Report 95-036, Computer Science Department, University of Minnesota.

    Google Scholar 

  • Karypis, G. and Kumar, V., 1995. “Analysis of multilevel graph partitioning,” Tech. Report 95-037, Gomputer Science Department, University of Minnesota.

    Google Scholar 

  • Kernighan, B.W. and Lin, S., 1970. “An efficient heuristic procedure for partitioning graphs,” The Bell System Technical J. 49, pp. 291–307.

    MATH  Google Scholar 

  • Keyes, D.E., 1992. “Domain decomposition: A bridge between nature and parallel computers,” in Adaptive Multilevel and Hierarchical Computational Strategies, A.K. Noor, ed., ASME, New York, pp. 293–334.

    Google Scholar 

  • Keyes, D.E., Saad, Y., and Truhlar, D.G., eds., 1995. Domain-based Parallelism and Problem Decomposition Methods in Science and Engineering, SIAM, Philadelphia.

    MATH  Google Scholar 

  • Kumfert, G. and Pothen, A., 1995. “A multilevel nested dissection algorithm,” unpublished work.

    Google Scholar 

  • Leete, C.A., Peyton, B.W., and Sincovec, R.F., 1993. “Toward a parallel recursive spectral bisection mapping tool,” in Proc. Sixth SIAM Conf. on Parallel Processing, SIAM, Philadelphia, pp. 923–928.

    Google Scholar 

  • Leighton, F.T. and Rao, S., 1988. “An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms,” in Proc. 29th Ann. Symp. on Foundations of Computer Science, IEEE, pp. 422–431.

    Google Scholar 

  • LeTallec, P.J., 1994. “Domain decomposition methods in computational mechanics,” Computational Mechanics Advances 2, pp. 121–220.

    MathSciNet  Google Scholar 

  • Lewis, J.G., Peyton, B.W., and Pothen, A., 1989. “A fast algorithm for reordering sparse matrices for parallel factorization,” SIAM J. Sci. Stat. Comput. 10, pp. 1146–1173.

    MathSciNet  MATH  Google Scholar 

  • Lipton, R.J., Rose, D.J., and Tarjan, R.E., 1979. “Generalized nested dissection,” SIAM J. Numer. Anal. 16, pp. 346–358.

    MathSciNet  MATH  Google Scholar 

  • Lipton, R.J. and Tarjan, R.E., 1979. “A separator theorem for planar graphs,” SIAM J. Appl. Math. 36, pp. 177–189.

    MathSciNet  MATH  Google Scholar 

  • Liu, J.W.H., 1985. “Modification of the minimum degree algorithm by multiple elimination,” ACM Trans. on Math. Soft. 11, pp. 141–153.

    MATH  Google Scholar 

  • Liu, J.W.H., 1989. “The minimum degree ordering with constraints,” SIAM J. Sci. Stat. Comp. 10, pp. 198–219.

    Google Scholar 

  • Liu, J.W.H., 1990. “The role of elimination trees in sparse factorization,” SIAM J. Matrix Anal. Appl. 11, pp. 134–172.

    MathSciNet  MATH  Google Scholar 

  • Miller, G.L., Teng, S.-H., Thurston, W., and Vavasis, S.A., 1993. “Automatic mesh partitioning,” in Graph Theory and Sparse Matrix Computation, A. George, J.R. Gilbert, and J.W.H. Liu, eds., IMA Volumes in Mathematics and its Applications 56, Springer Verlag, Berlin, pp. 57–84.

    Google Scholar 

  • Mohar, B., 1991. “The Laplacian spectrum of graphs,” Graph Theory Combinatorics, and Applications, John Wiley, New York, pp. 871–898.

    Google Scholar 

  • Mohar, B. and Poljak, S., 1992. “Eigenvalues in combinatorial optimization,” Preprint, Department of Mathematics, University of Ljubljana, Jadranska 19, 61 111, Ljubljana, Slovenia.

    Google Scholar 

  • Nour-Omid, B., Raefsky, A., and Lyzenga, G., 1986. “Solving finite element equations on concurrent computers,” in Parallel Computations and their Impact on Mechanics, A.K. Noor, ed., ASME, New York, pp. 209–227.

    Google Scholar 

  • Oden, J.T., Patra, A., and Feng, Y., 1994. “Domain decomposition for adaptive hp finite element methods,” in Domain Decomposition Methods in Science and Engineering, D.E. Keyes and J. Xu, eds., Contemporary Mathematics 180, AMS, Providence pp. 295–301.

    Google Scholar 

  • Ozturan, C., 1995. “Distributed environment and load balancing for adaptive unstructured meshes,” PhD thesis, Rensselaer Polytechnic Institute, Troy, NY.

    Google Scholar 

  • Parlett, B.N., 1980. The Symmetric Eigenvalue Problem, Prentice Hall, Englewood Cliffs.

    MATH  Google Scholar 

  • Pothen, A., 1994. “An analysis of spectral graph partitioning via quadratic assignment problems,” in Domain Decomposition Methods in Science and Engineering, D.E. Keyes and J. Xu, eds., Contemporary Mathematics 180, AMS, Providence, pp. 105–110.

    Google Scholar 

  • Pothen, A. and Fan, C.-J., 1990. “Computing the block triangular form of a sparse matrix,” ACM Trans. on Math. Soft. 16, pp. 303–324.

    MathSciNet  MATH  Google Scholar 

  • Pothen, A., Rothberg, E., Simon, H.D., and Wang, L., 1994. “Parallel sparse Cholesky factorization with spectral nested dissection ordering,” in Proc. of the Fifth SIAM Conf on Applied Linear Algebra, J.G.L. et al., eds., SIAM, Philadelphia, pp. 418–422.

    Google Scholar 

  • Pothen, A., Simon, H.D., and Liou, K.P., 1990. “Partitioning sparse matrices with eigenvectors of graphs,” SIAM J. Matrix Anal. Appl. 11, pp. 430–452.

    MathSciNet  MATH  Google Scholar 

  • Pothen, A., Simon, H.D., and Wang, L., 1992. “Spectral nested dissection,” Tech. Report CS-92-01, Computer Science, Pennsylvania State University, University Park, PA.

    Google Scholar 

  • Pothen, A., Wang, L., Simon, H., and Barnard, S., 1992. “Towards a fast implementation of spectral nested dissection,” in Proc. Supercomputing ′92, IEEE Computer Society Press, Los Alamitos, pp. 42–51.

    Google Scholar 

  • Rendl, F. and Wolkowicz, H., 1995. “A projection technique for partitioning the nodes of a graph,” Annals of Operations Research 58, pp. 155–179. (This paper was written in 1990, and appeared in in the special issue devoted to the Symp. on Applied Mathematical Programming and Modeling, Budapest, January1993.)

    MathSciNet  MATH  Google Scholar 

  • Roose, D. and VanDriessche, R., 1993. “Distributed memory parallel computers and Computational Fluid Dynamics,” Tech. Report TW 186, Department of Computer Science, Katholike Universiteit Leuven, Belgium.

    Google Scholar 

  • Schramm, H. and Zowe, J., 1992. “A version of the bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results,” SIAM J. Opt. 2, pp. 121–152.

    MathSciNet  MATH  Google Scholar 

  • Shephard, M.S., Flaherty, J.E., DeCougny, H.L., Özturan, C., Bot-tasso, C.L., and Beall, M., 1995. “Parallel automated adaptive procedures for unstructured meshes,” Parallel Computing in CFD, Advisory Group for Aerospace Research and Development (AGARD), Neuilly-Sur-Seine, France, Report R-807.

    Google Scholar 

  • Simon, H.D., 1991. “Partitioning of unstructured problems for parallel processing,” Computing Systems in Engineering 2, pp. 135–148.

    Google Scholar 

  • Smith, B.F., Bjørstad, P.E., and Gropp, W.D., 1996. “Domain Decomposition: Parallel Multilevel Algorithms for Elliptic Partial Differential Equations,” Cambridge University Press, Cambridge.

    MATH  Google Scholar 

  • Suaris, P. and Kedem, G., 1988. “An algorithm for quadrisection and its application to standard cell placement,” IEEE Transactions on Circuits and Systems 35, pp. 294–303.

    Google Scholar 

  • Spielman, D.A. and Teng, S-H., 1996, “Spectral partitioning works: Planar graphs and finite element meshes”, Draft manuscript, http://cs.berkeley.edu/~spielman/spect.html.

    Google Scholar 

  • Vanderstraeten, D., Farhat, C., Chen, P.S., Keunings, R., and Zone, O., 1994. “A retrofit based methodology for the fast generation and optimization of large-scale mesh partitions,” Tech. Report CAS-94-18, Center for Aerospace Structures, University of Colorado, Boulder.

    Google Scholar 

  • VanDriessche, R. and Roose, D., 1995. “A graph contraction algorithm for the fast calculation of the Fiedler vector of a graph,” Proc. Seventh SIAM Conf. on Parallel Computing for Scientific Computing, SIAM, Philadelphia, pp. 621–626.

    Google Scholar 

  • VanDriessche, R. and Roose, D., 1994. “An efficient spectral bisection algorithm for dynamic load balancing,” Tech. Report TW 215, Department of Computer Science, Katholike Universiteit Leuven, Belgium.

    Google Scholar 

  • Venkatakrishnan, V., Simon, H.D., and Barth, T., 1992. “A MIMD implementation of a parallel Euler solver for unstructured grids,” J. Supercomputing 6, pp. 117–127.

    MATH  Google Scholar 

  • Walshaw, C. and Berzins, M., 1992. “Dynamic load balancing for PDE solvers on adaptive unstructured meshes,” Tech. Report 92-32, School of Computer Studies, University of Leeds.

    Google Scholar 

  • Wang, L., 1994. “Spectral Nested Dissection Orderings for Parallel Sparse Matrix Factorization,” PhD thesis,, Computer Science Department, The Pennsylvania State University.

    Google Scholar 

  • Williams, R.D., 1991. “Performance of dynamic load balancing algorithms for unstructured mesh calculations,” Concurrency: Practice and Experience 3, pp. 457–481.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Old Dominion University, Norfolk, VA, 23529-0162, USA

    Alex Pothen

  2. ICASE, MS 132C, NASA Langley Research Center, Hampton, VA, 23681-0001, USA

    Alex Pothen

Authors
  1. Alex Pothen
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Old Dominion University, Norfolk, Virginia, USA

    David E. Keyes

  2. University of Minnesota, Minneapolis, Minnesota, USA

    Ahmed Sameh

  3. ICASE, Hampton, Virginia, USA

    David E. Keyes  & V. Venkatakrishnan  & 

Rights and permissions

Reprints and permissions

Copyright information

© 1997 Springer Science+Business Media Dordrecht

About this chapter

Cite this chapter

Pothen, A. (1997). Graph Partitioning Algorithms with Applications to Scientific Computing. In: Keyes, D.E., Sameh, A., Venkatakrishnan, V. (eds) Parallel Numerical Algorithms. ICASE/LaRC Interdisciplinary Series in Science and Engineering, vol 4. Springer, Dordrecht. https://doi.org/10.1007/978-94-011-5412-3_12

Download citation

  • DOI: https://doi.org/10.1007/978-94-011-5412-3_12

  • Publisher Name: Springer, Dordrecht

  • Print ISBN: 978-94-010-6277-0

  • Online ISBN: 978-94-011-5412-3

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation