Universitatsbibliothek Bremen Click here to activate Remote Access
Previous Up Next
Publications results for "MR Number=(2294342)"

Citations

From References: 35

From Reviews: 0

MR2294342 (2008h:15011) Reviewed
Spielman, Daniel A. (1-YALE-C)
Department of Computer Science, Yale UniversityNew Haven, Connecticut, 06520
; Teng, Shang-Hua (1-BOST-C)
Department of Computer Science, Boston UniversityBoston, Massachusetts, 02215

Spectral partitioning works: planar graphs and finite element meshes. (English summary)
Linear Algebra Appl. 421 (2007), no. 2-3, 284–305.
15A18 (05C50 05C70 05C90)
Review PDF Clipboard Journal Article Make Link
The paper deals with spectral partition techniques for partitioning graphs and matrices. Interesting applications arise in domain decomposition methods, linear solvers for sparse linear systems, VLSI circuit design and simulation. In this paper the authors show that spectral partitioning methods are efficient when applied to finite element meshes and to bounded degree planar graphs, which often appear in the relevant applications.
   As main results the authors prove that by means of the technique considered it is possible to produce separators whose ratio of vertices removed to edges cut is O(n(1/2)) when considering bounded-degree planar graphs and O(n(1/d)) for well-shaped d-dimensional meshes.
   The key instrument used in the analysis is an estimate (from above) of the second smallest eigenvalue of the Laplacian matrices of these graphs (which is known—according to Fiedler—as the algebraic connectivity of a graph).
   The paper is quite interesting and well written and has a very rich bibliography, which allows a complete overview—historically as well—on the subject.
Reviewed by Nicola Guglielmi

    References
  1. P. Agarwal, J. Pach, Combinatorial Geometry, Wiley-Interscience, 1995. MR1354145
  2. C.J. Alpert, A.B. Kahng, Recent directions in netlist partitioning: a survey, Integration: The VLSI J. 19 (1995) 1–81.
  3. N. Alon, Eigenvalues and expanders, Combinatorica 6 (2) (1986) 83–96. MR0875835
  4. N. Alon, V.D. Milman, λ1, isoperimetric inequalities for graphs, and superconcentrators, J. Combin. Theory Series B 38 (1985) 73–88. MR0782626
  5. E.M. Andreev, On convex polyhedra in lobacevskii space, Math. USSR Sbornik 10 (3) (1970) 413–440. MR0259734
  6. E.M. Andreev, On convex polyhedra of finite volume in lobacevskii space, Math. USSR Sbornik 12 (2) (1970) 259–270. MR0273510
  7. Noga Alon, Paul Seymour, Robin Thomas, A separator theorem for graphs with an excluded minor and its applications, Proceedings of the 22th Annual ACM Symposium on Theory of Computing, ACM, 1990, pp. 293–299.
  8. S. Arora, S. Rao, U. Vazirani, Expander flows, geometric embeddings and graph partitioning, in: Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing, 2004, pp. 222–231. MR2121604
  9. I. Babuška, A.K. Aziz, On the angle condition in the finite element method, SIAM J. Numer. Anal. 13 (2) (1976) 214–226. MR0455462
  10. E.R. Barnes, An algorithm for partitioning of nodes of a graph, SIAM J. Algebraic Discrete Methods 4 (3) (1982) 541–550. MR0679649
  11. M.J. Berger, S. Bokhari, A partitioning strategy for nonuniform problems on multiprocessors, IEEE Trans. Comp. C-36 (1987) 570–580.
  12. M. Bern, D. Eppstein, Mesh generation and optimal triangulation, in: F.K. Hwang, D.-Z. Du (Eds.), Computing in Euclidean Geometry, World Scientific, 1992, pp. 23–90. MR1239190
  13. M. Bern, D. Eppstein, J.R. Gilbert, Provably good mesh generation, J. Comput. Syst. Sci. 48 (1994) 384–409. MR1279408
  14. E.R. Barnes, A.J. Hoffman, Partitioning, spectra and linear programming, Progr. Combin. Optim. (1984) 13–25. MR0771867
  15. J. Barnes, P. Hut, A hierarchical O(nlogn) force calculation algorithm, Nature 324 (1986) 446–449.
  16. Norman Biggs, Algebraic Graph Theory, second ed., Cambridge University Press, New York, NY, 1993. MR1271140
  17. R. Boppana, Eigenvalues and graph bisection: an average-case analysis, 28th Annual Symposium on Foundations of Computer Science, Los Angeles, October 1987, IEEE, 1987, pp. 280–285.
  18. S.T. Barnard, H.D. Simon, A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems, Technical Report RNR-92–033, NASA Ames Research Center, 1992.
  19. Dragos M. Cvetkovic, Michael Doob, Horst Sachs, Spectra of Graphs: Theory and Application, Academic Press, New York, 1990. MR0572262
  20. J. Cheeger, A lower bound for the smallest eigenvalue of the laplacian, in: R.C. Gunning (Ed.), Problems in Analysis, Princeton University Press, 1970, pp. 195–199. MR0402831
  21. T.F. Chan, D.C. Resasco, A framework for the analysis and construction of domain decomposition preconditioners, Technical Report CAM-87–09, UCLA, 1987. MR0881372
  22. F.R.K. Chung, Diameters and eigenvalues, J. Amer. Math. Soc. 2 (2) (1989) 187–196. MR0965008
  23. F.R.K. Chung, Spectral Graph Theory, Amer. Math. Soc., Providence, RI, 1997. MR1421568
  24. J.H. Conway, N.J.A. Sloane, Sphere Packings, Lattices and Groups, Springer-Verlag, 1988. MR0920369
  25. T.F. Chan, B. Smith, Domain decomposition and multigrid algorithms for elliptic problems on unstructured meshes, Contemp. Math. (1993) 1–14. MR1312391
  26. P.K. Chan, M. Schlag, J. Zien, Spectral k-way ratio cut partitioning and clustering, in: Symp. on Integrated Systems, 1993.
  27. H.N. Djidjev, J.R. Gilbert, Separators in graphs with negative and multiple vertex weights, Technical Report CS-92–07, Xerox PARC, Palo Alto, 1992.
  28. W.E. Donath, A.J. Hoffman, Algorithms for partitioning of graphs and computer logic based on eigenvectors of connection matrices, IBM Techn. Disclosure Bull. 15 (1972) 938–944.
  29. W.E. Donath, A.J. Hoffman, Lower bounds for the partitioning of graphs, J. Res. Develop. 17 (1973) 420–425. MR0329965
  30. P. Diaconis, D. Strook, Geometric bounds for eigenvalues of Markov chains, Ann. Appl. Probab. 1 (1) (1991) 36–61. MR1097463
  31. H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, NY, 1987. MR0904271
  32. D. Eppstein, G.L. Miller, S.-H. Teng, A deterministic linear time algorithm for geometric separators and its applications, Fund. Inform, 22 (4) (1995) 309–330. MR1360950
  33. M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Math. J. 23 (98) (1973) 298–305. MR0318007
  34. M. Fiedler, Eigenvectors of acyclic matrices, Czechoslovak Math. J. 25 (100) (1975) 607–618. MR0387308
  35. M. Fiedler, A property of eigenvectors of nonnegative symmetric matrices and its applications to graph theory, Czechoslovak Math. J. 25 (100) (1975) 619–633. MR0387321
  36. James Allen Fill, Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process, Ann. Appl. Probab. 1 (1) (1991) 62–87. MR1097464
  37. I. Fried, Condition of finite element matrices generated from nonuniform meshes, AIAA J. 10 (1972) 219–221.
  38. N. Garg, H. Saran, V.V. Vazirani, Finding separator cuts in planar graphs within twice the optimal, SIAM J. Comput. 29 (1) (1999) 159–179. MR1710346
  39. J.R. Gilbert, J.P. Hutchinson, R.E. Tarjan, A separation theorem for graphs of bounded genus, J. Algorith. 5 (1984) 391–407. MR0756165
  40. John Russell Gilbert, Graph Separator theorems and sparse gaussian elimination, Ph.D. thesis, Computer Science Department, Stanford University, 1980.
  41. J.R. Gilbert, N. Kahale, personal communication, 1995.
  42. Stephen Guattery, Gary L. Miller, On the performance of the spectral graph partitioning methods, in: Proceedings of The Second Annual ACM-SIAM Symposium on Discrete Algorithms, ACM-SIAM, 1995, pp. 233–242. MR1321854
  43. L. Greengard, V. Roklin, A fast algorithm for particles simulations, J. Comput. Phys. 73 (1987) 325–348. MR0918448
  44. D. Hilbert, S. Cohn-Vossen, Geometry and the Imagination, Chelsea Publishing Company, New York, 1952. MR0046650
  45. R.W. Hackney, J.W. Eastwood, Computer Simulation Using Particles, McGraw-Hill, 1981.
  46. L. Hagen, A.B. Kahng, New spectral methods for ratio cut partitioning and clustering, IEEE Trans. Computer-Aided Des. 11 (9) (1992) 1074–1085.
  47. K.M. Hall, An r-dimensional quadratic placement algorithm, Manage. Sci. 17 (1970) 219–229.
  48. Bruce Hendrickson, Robert Leland, An improved spectral graph partitioning algorithm for mapping parallel computation, Technical Report SAND92–1460, Sandia National Lab., December 1992.
  49. Bruce Hendrickson, Robert Leland, The Chaco user's guide, Version 1.0, Technical Report SAND93–2339, Sandia National Lab., 1993.
  50. C. Johnson, Numerical Solution of Partial Differential Equations by the Finite Element Method, Cambridge University Press, 1992. MR0925005
  51. J.A. Kelner, Spectral partitioning, eigenvalue Bounds, and circle packings for graphs of bounded genus, in: Proceedings of the 36th Annual ACM Symposium on the Theory of Computing, 2004. MR2121631
  52. Paul Koebe, Kontaktprobleme der konformen Abbildung, Ber. Verh. Sächs. Akademie der Wissenschaften Leipzig, Math.-Phys. Klasse 88 (1936) 141–164.
  53. F.T. Leighton, S. Rao, An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms, in: 29th Annual Symposium on Foundations of Computer Science, 1988, pp. 422–431.
  54. R.J. Lipton, R.E. Tarjan, A separator theorem for planar graphs, SIAM J. Appl Math. 36 (April) (1979) 177–189. MR0524495
  55. M. Mihail, Conductance and convergence of Markov chains—a combinatorial treatment of expanders, in: 30th Annual Symposium on Foundations of Computer Science, IEEE, 1989, pp. 526–531.
  56. B. Mohar, The Laplacian spectrum of graphs, in: Sixth International Conference on the Theory and Applications of Graphs, 1988, pp. 871–898. MR1170831
  57. B. Mohar, Isoperimetric numbers of graphs, J. Combin. Theory, Series B 47 (1989) 274–291. MR1026065
  58. Gary L. Miller, William Thurston, Separators in two and three dimensions, Proceedings of the 22th Annual ACM Symposium on Theory of Computing, Baltimore, May 1990, ACM, pp. 300–309.
  59. G.L. Miller, S.-H. Teng, W. Thurston, S.A. Vavasis, Finite element meshes and geometric separators, SIAM J. Scient. Comput. 19 (2) (1998). MR1618871
  60. G.L. Miller, S.-H. Teng, W. Thurston, S.A. Vavasis, Separators for sphere-packings and nearest neighborhood graphs, J. ACM 44 (1) (1997) 1–29. MR1438463
  61. Gary L. Miller, Dafna Talmor, Shang-Hua Teng, Noel Walkington, A Delaunay based numerical method for three dimensions: generation, formulation, and partition, Proceedings of the 27th Annual ACM Symposium on Theory of Computing, Las Vegas, May 1995, ACM, 1995, pp. 683–692.
  62. G.L. Miller, S.-H. Teng, S.A. Vavasis, An unified geometric approach to graph separators, 32nd Annual Symposium on Foundations of Computer Science, IEEE, 1991, pp. 538–547. MR1177204
  63. Gary L. Miller, Stephen A. Vavasis, Density graphs and separators, in: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 1991, pp. 331–336. MR1095849
  64. R.A. Nicolaides, Direct discretization of planar div-curl problems, SIAM J. Numer. Anal. 29 (1) (1992). MR1149083
  65. S. Plotkin, S. Rao, W.D. Smith, Shallow excluded minors and improved graph decomposition, in: 5th Symp. Discrete Algorithms, SIAM, 1994, pp. 462–470. MR1285188
  66. A. Pothen, H.D. Simon, K.-P. Liou, Partitioning sparse matrices with eigenvectors of graphs, SIAM J. Matrix Anal. Appl. 11 (1990) 430–452. MR1054210
  67. B. Parlett, H. Simon, L. Stringer, Estimating the largest eigenvalues with the lanczos algorithm, Math. Comput. 38 (1982) 153–165. MR0637293
  68. A. Pothen, H.D. Simon, L. Wang, Spectral nested dissection, Technical Report CS-92–01, Pennsylvania State University, Department of Computer Science, 1992.
  69. G. Strang, G.J. Fix, An Analysis of the Finite Element Method, Prentice-Hall, Englewood Cliffs, New Jersey, 1973. MR0443377
  70. H.D. Simon, Partitioning of unstructured problems for parallel processing, Comput. Syst. Eng. 2 (2/3) (1991) 135–148.
  71. A.J. Sinclair, M.R. Jerrum, Conductance and the rapid mixing property for Markov chains: the approximation of the permanent resolved, Proceedings of the 20th Annual ACM Symposium on Theory of Computing, ACM, 1988, pp. 235–244. MR2121652
  72. Alistair Sinclair, Mark Jerrum, Approximative counting, uniform generation and rapidly mixing Markov chains, Inform. Comput. 82 (1) (1989) 93–133. MR1003059
  73. D.A. Spielman, S.-H. Teng, Disk packings and planar separators, in: Proceedings of 12th ACM Symposium on Computational Geometry, May 1996, pp. 358–394.
  74. D.A. Spielman, S.-H. Teng, Spectral partitioning works: planar graphs and finite element meshes, in: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996, pp. 96–106. MR1450607
  75. G. Strang, Linear Algebra and Its Applications, Harcourt Brace Jovanovich, Publishers, San Diego, CA, 1988. MR0384823
  76. S.-H. Teng, Points, spheres, and separators: a unified geometric approach to graph partitioning, Ph.D. thesis, Carnegie-Mellon University, School of Computer Science, 1991, CMU-CS-91–184. MR2687483
  77. Shang-Hua Teng, Provably good partitioning and load balancing algorithms for parallel adaptive n-body simulation, SIAM J. Scient. Comput. 19 (2) (1998) 635–656. MR1618856
  78. Shang-Hua Teng, Combinatorial aspects of geometric graphs, Comput. Geom. 9 (1998) 277–287. MR1609578
  79. W.P. Thurston, The geometry and topology of 3-manifolds, Princeton University Notes, 1988.
  80. J.F. Thompson, Z.U.A. Warsi, C.W. Mastin, Numerical Grid Generation: Foundations and Applications, North Holland, New York, 1985. MR0791004
  81. P. Ungar, A theorem on planar graphs, J. London Math. Soc. 26 (1951) 256–262. MR0044105
  82. R.D. Williams, Performance of dynamic load balancing algorithms for unstructured mesh calculations, Technical Report, California Institute of Technology, 1990.
  83. F. Zhao, An O(n) algorithm for three-dimensional n-body simulation, Technical Report TR AI Memo 995, MIT, AI Lab., October 1987.
This list reflects references listed in the original paper as accurately as possible with no attempt to correct error.
Previous Up Next

© Copyright 2021, American Mathematical Society
Privacy Statement
American Mathematical Society