Bibliography

1

S. T. BARNARD AND H. D. SIMON, Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems, Concurrency: Practice and Experience, 6 (1994), pp. 101-117.

2

S. T. BARNARD AND H. D. SIMON, A parallel implementation of multilevel recursive spectral bisection for application to adaptive unstructured meshes, in: SIAM Proceedings Series 195, D.H. Bailey, P. E. Bjorstad, Jr Gilbert, M. V. Mascagni, R. S. Schreiber, H. D. Simon, V. J. Torczon, J. T. Watson, eds., SIAM, Philadelphia, 1995, pp. 627-632.

3

S. T. BARNARD, PMRSB: parallel multilevel recursive spectral bisection, Manuscript, 1996.

4

BERTSEKAS AND TSITSIKLIS, Parallel and Distributed Computation: Numerical Methods, Prentice-Hall, Englewood Cliffs, NJ, 1989.

5

R. BISWAS AND L. OLIKER, Experiments with repartitioning and load balancing adaptive meshes, Technical Report NAS-97-021, NASA Ames Research Center, Moffett Field, CA, 1997.

6

J. E. BOILLAT, Load balancing and Poisson equation in a graph, Concurrency: Practice and Experience, 2 (1990), pp. 289-313.

7

J. E. BOILLAT AND F. BRUGÉ, A dynamic load-balancing algorithm for molecular dynamics simulation on multi-processor systems, Journal of Computational Physics, 96 (1991), pp. 1-14.

8

N. BRIGGS, Algebraic Graph Theory, Cambridge University Press, Cambridge, 1974.

9

W. L. Briggs, A Multigrid Tutorial, SIAM, Philadelphia, 1987.

10

T. N. BUI AND B. R. MOON, Genetic algorithm and graph partitioning, IEEE Transactions on Computers, 45 (1996), pp. 841-855.

11

T. N. BUI, S. CHAUDHURI, F. T. LEIGHTON, M. SIPSER, Graph bisection algorithms with good average case behavior, Combinatorica, 7 (1987), pp. 171-191.

12

U. V. ÇATALYÜREK AND C. AYKANAT, Decomposing Irregularly Sparse Matrices for Parallel Matrix-Vector Multiplication, Lecture Notes in Computer Science, 1117 (1996), pp. 75-86.

13

H.L. DE COUGNY, K. D. DEVINE, J. E. FLAHERTY, R. M. LOY, C. ÖZTURAN AND M. S. SHEPHARD, Load balancing for the parallel adaptive solution of partial differential equations, Applied Numerical Mathematics, 16 (1994), pp. 157-182.

14

G. CYBENKO, Dynamic load balancing for distributed memory multi-processors, Journal of Parallel and Distributed Computing, 7 (1989), pp. 279-301.

15

K. DEVINE, J. FLAHERTY, S. WHEAT AND A. MACCABE, A massively parallel adaptive finite element method with dynamic load balancing, Supercomputing, pp.2-11, 1993.

16

R. DIEKMANN, D. MEYER AND B. MONIEN, Parallel decomposition of unstructured FEM-meshes, Concurrency: Practice and Experience, 10 (1998), pp. 53-72.

17

R. DIEKMANN, S. MUTHUKRISHNAN AND M. V. NAYAKKANKUPPAM, Engineering diffusive load balancing algorithms using experiments Lecture Notes in Computer Science, 1253 (1997), pp. 111-122.

18

P. DINIZ, S. PLIMPTON, B. HENDRICKSON AND R. LELAND, Parallel algorithms for dynamically partitioning unstructured grids, in: SIAM Proceedings Series 195, D.H. Bailey, P. E. Bjorstad, Jr Gilbert, M. V. Mascagni, R. S. Schreiber, H. D. Simon, V. J. Torczon, J. T. Watson, eds., SIAM, Philadelphia, 1995, pp. 627-632.

19

R. VAN DRIESSCHE AND D. ROOSE, Dynamic load balancing with a spectral bisection algorithm for the constrained graph partitioning problem, Lecture Notes in Computer Science, 919 (1995), pp. 392-397.

20

C. FARHAT, A simple and efficient automatic FEM domain decomposer, Computer and Structures, 28 (1988), pp. 579-602.

21

C. FARHAT, S. LANTERI AND H. D. SIMON, TOP/DOMDEC - a software tool for mesh partitioning and parallel-processing, Computing Systems in Engineering, 6 (1995), pp. 13-26.

22

C. FAHAT, N. MAMAN AND G. W. BROWN, Mesh partitioning for implicit computations via iterative domain decomposition - impact and optimization of the subdomain aspect ratio, International Journal for Numerical Methods in Engineering, 38 (1995), pp. 989-1000.

23

D. VANDERSTRAETEN, C. FARHAT, P. S. CHEN, R. KEUNINGS AND O. OZONE, A retrofit based methodology for the fast generation and optimization of large-scale mesh partitions - beyond the minimum interface size criterion, Computer Methods in Applied Mechanics and Engineering, 133 (1996), pp. 25-45.

24

C. M. FIDUCCIA AND R. M. MATTHEYSES, A linear-time heuristic for improving network partitions, ACM Ieee Nineteenth Design Automation Conference Proccedings, vol.1982, ch.126, pp. 175-181, 1982.

25

J. E. FLAHERTY, R. M. LOY, M. S. SHEPARD, B. K. SZYMANSKI, J. D. TERESCO AND L. H. ZIANTZ, Adaptive local refinement with octree load balancing for the parallel solution of three- dimensional conservation laws, Journal of Parallel and Distributed Computing, 47 (1997), pp. 139-152.

26

J. E. FLAHERTY, R. M. LOY, C. ÖZTURAN, M. S. SHEPARD, B. K. SZYMANSKI, J. D. TERESCO AND L. H. ZIANTZ, Parallel structures and dynamic load balancing for adaptive finite element computation, Applied Numerical Mathematics, 26 (1998), pp. 241-263.

27

R. Fletcher, Practical Methods of Optimization, John Wiley and Sons, Chichester, 1987.

28

B. GHOSH AND S. MUTHUKRISHNAN, Dynamic load balancing on parallel and distributed networks by random matchings, in Proceeding of Sixth Annual ACM Symposium om Parallel Algorithms and Architechures, pp. 226-235, 1994.

29

D. H. GOLUB AND C. F. VAN LOAN, Matrix Computations, Johns Hopkins University Press, Baltimore, 1983.

30

C. GREENOUGH AND R. F. FOWLER, Partitioning methods for unstructured finite element meshes, RAL report RAL-94-092, Rutherford Appleton Laboratory, UK, 1994.

31

A. GUPTA, Fast and effective algorithms for graph partitioning and sparse-matrix ordering, IBM Journal of Research and Development, 41 (1996), pp. 171-183.

32

A. GUPTA, WGPP: Watson Graph Partitioning (and Sparse Matrix Ordering) Package: Users' Manual, Technical Report RC-20453 (90427), IBM Thomas J. Watson Research Center, Yorktown Heights, NY, May 6, 1996.

33

A. HEIRICH AND S. TAYLER, A parabolic load balancing method, International Conference on Parallel Processing, 1995

34

B. HENDRICKSON AND R. LELAND, An improved graph partitioning algorithm for mapping parallel computations, Sandia National Laboratories, Albuquerque, NM 87185, 1992.

35

B. HENDRICKSON AND R. LELAND, The Chaco User's Guide, Version 2.0, Technical Report SAND 94-2692, Sandia National Laboratories, Allbuquerque, NM, 1995.

36

B. HENDERSON AND R. LELAND, A multilevel algorithm for partitioning graphs, in Proceeding of Supercomputing '95, ACM, December 1995.

37

B. HENDRICKSON, R. LELAND AND R. VAN DRIESSCHE, Enhancing Data Locality by Using Terminal Propagation, Proc. 29th Hawaii Intl. Conf. System Science, 1996.

38

B. HENDRICKSON, Graph partitioning and parallel solvers: has the emperor no clothes? Lecture Notes in Computer Science, 1457 (1998), pp. 218-225.

39

D. HILBERT, Uber die steitige abbildung einer linie auf ein flachenstuck, Math. Ann., 38, 1891.

40

D. C. HODGSON AND P. K. JIMACK, Efficient parallel generation of partitioned, unstructured meshes, Advances in Engineering Software, 27 (1996), pp. 59-70

41

G. HORTON, A multi-level diffusion method for dynamic load balancing, Parallel Computing, 9 (1993), pp. 209-218.

42

Y .F. Hu AND R. J. Blake, Numerical experiences with partitioning of unstructured meshes, Parallel Computing, 20 (1994), pp. 815-829.

43

Y. F. Hu, R. J. Blake and D. R. Emerson, An optimal migration algorithm for dynamic load balancing , Concurrency: Practice and Experience, 10 (1998), pp. 467-483.

44

Y. F. HU, An Improved Diffusion Algorithm for Dynamic Load Balancing, Parallel Computing, 25 (1999) 417-444.

45

Y. F. HU AND R. J. BLAKE, The optimal property of polynomial based diffusion-like algorithms in dynamic load balancing , in: Computational Dynamics'98, K. D. Papailiou, D. Tsahalis, J. Périaux, D. Knörzer, eds., John Wiley & Son, Chichester, 1998.

46

M. T. JONES AND P. E. PLASSMANN, Parallel algorithms for the adaptive refinement and partitioning of unstructured meshes, in Proceedings of the Scalable High-performance Computing Conference (SHPCC94), 1994, Ch.111, pp. 478-485. Available from http://www-unix.mcs.anl.gov/$\sim$freitag/SC94demo/paper.html

47

G. KARYPIS AND V. KUMAR, A fast and high quality multilevel scheme for partitioning irregular graphs, Technical Report TR 95-035, Department of Computer Science, University of Minnesota, 1995.

48

G. KARYPIS AND V. KUMAR, Parallel multilevel graph partitioning, Technical Report TR 95-036, Department of Computer Science, University of Minnesota, 1995.

49

G. KARYPIS AND V. KUMAR, Parallel Multilevel k-way Partitioning Scheme for Irregular Graphs, Technical Report TR 96-036, Department of Computer Science, University of Minnesota, 1996.

50

G. KARYPIS AND V. KUMAR, A Coarse-Grain Parallel Formulation of a Multilevel k-way Graph Partitioning Algorithm, Eighth SIAM Conference on Parallel Processing for Scientific Computing, 1997.

51

G. KARYPIS AND V. KUMAR, Multilevel algorithms for multi-constraint graph partitioning, Technical Report TR 98-019, Department of Computer Science, University of Minnesota, 1998.

52

G. KARYPIS AND V. KUMAR, Multilevel k-way partitioning scheme for irregular graphs, Journal of Parallel and Distributed Computing, 48 (1998), pp. 96-129.

53

B. W. KERNIGHAN AND S. LIN, An efficient heuristic procedure for partitioning graphs, Bell Systems Tech. J., 49 (1970), pp. 291-308.

54

J. DE KEYSER AND D. ROOSE, Grid partitioning by inertial recursive bisection, Report TW 174, K.U.Leuven, Dept of Computer Science, Belgium, July 1992.

55

G. A. KOHRING, Dynamic load balancing for parallel particular simulation on MIMD computers, Parallel Computing, 21 (1995), pp. 683-693.

56

N. P. KRUYT, A conjugate gradient method for the spectral partitioning of graphs, Parallel Computing, 22 (1997) pp. 1493-1502.

57

M. LUBY, A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, 15 (1986), pp. 1036-1053.

58

J. G. MALONE, Automated mesh decomposition and concurrent finite element analysis for hypercube multiprocessor computers, Computer Methods in Applied Mechanics and Engineering, 70 (1988), pp. 27-58.

59

N. MANSOUR AND G. C. FOX, Allocating data to distributed-memory multiprocessors by genetic algorithms, Concurrency: Practice and Experience, 6 (1994), pp. 485-504.

60

N. MANSOUR, Physical optimization algorithms for mapping data to distributed-memory multiprocessors, Ph. D. thesis, School of Computer Science, Syracuse University, 1992.

=100=200=1000

61

N. MANSOUR, Allocating data the multicomputer nodes by physical optimization algorithms for loosely synchronous computations, Concurrency: Practice and Experience, 4 (1992), pp. 557-574.

62

O. C. MARTIN AND S. W. OTTO, Partitioning of unstructured meshes for load balancing Concurrency: Practice and Experience, 7 (1995), pp. 303-314.

63

B. MOHAR, The Laplacian spectrum of graphs, technical Report, Department of Mathematics, University of Ljubljana, Ljubljana, Yugoslavia, 1988.

64

S. MUTHUKRISHNAN, B. GHOSH AND M. H. SCHULTZ, First- and second-order diffusive methods for rapid, coarse, distributed load balancing, Theory of Computing Systems, 31 (1998), pp. 331-354.

65

L. OLIKER AND R. BISWAS, PLUM: Parallel Load Balancing for Adaptive Unstructured Meshes, Technical Report NAS-97-020, NASA Ames Research Center, Moffett Field, CA, 1997.

66

C. OU, S. RANKA, AND G. FOX, Fast and parallel mapping algorithms for irregular problems, Journal of Supercomputing, 10 (1996), pp. 119-140

67

C.-W. OU AND S. RANKA, Parallel incremental graph partitioning, IEEE Transactions on Parallel and Distributed Systems, 8 (1997), pp. 884-896.

68

A. POTHEN, D. H. SIMON AND K. P. LIOU, Partitioning sparse matrices with eigenvectors of graphs, SIAM Journal of Matrix Analysis and Applications, 11 (1990), pp. 430-452.

69

P. SADAYAPPAN, F.ERCAL AND J. RAMANUJAM, Cluster partitioning approach to mapping parallel programs onto a hypercube, Parallel Computing, 13 (1990), pp. 1-16.

70

K. SCHLOEGEL, G. KARYPIS AND V. KUMAR Multilevel diffusion schemes for repartitioning of adaptive meshes, Journal of Parallel and Distributed Computing, 47 (1997), pp. 109-124

71

K. SCHLOEGEL, G. KARYPIS AND V. KUMAR, Parallel multilevel diffusion algorithms for repartitioning of adaptive meshes, Technical Report TR 97-014, Department of Computer Science, University of Minnesota, 1997.

72

K. SCHLOEGEL, G. KARYPIS, V. KUMAR, R. BISWAS AND L. OLIKER, A performance study of diffusive vs. remapped load-balancing schemes, Technical Report TR 98-018, Department of Computer Science, University of Minnesota, 1998.

73

K. SCHLOEGEL, G. KARYPIS, V. KUMAR, Wavefront diffusion and LMSR: algorithms for dynamic repartitioning of adaptive meshes , Technical Report TR 98-034, Department of Computer Science, University of Minnesota, 1998.

74

M. S. SHEPHARD, J. E. FLAHERTY, H. L. DE COUGNY, C. ÖZTURAN, C. L. BOTTASSO AND M. W. BEALL, Parallel automated adaptive procedures for unstructured meshes, in Parallel Computing in CFD, AGARD-R-807, pp. 6.1-6.49, 1995.

75

H. D. SIMON, Partitioning of unstructured problems for parallel processing, Computer Systems in Engineering, 2 (1991), pp. 135-148.

76

H. D. SIMON AND S. H. TENG, How good is recursive bisection, SIAM Journal on Scientific Computing, 18 (1997), pp. 1436-1445.

77

H. D. SIMON, A. SOHN, AND R. BISWAS, HARP: A Dynamic Spectral Partitioner, Journal of Parallel and Distributed Computing, 50 (1998), pp. 88-103.

78

J. SONG, A partially asynchronous and iterative algorithm for distributed load balancing, Parallel Computing, 20 (1994), pp. 853-868.

79

D. VANDERSTRAETEN AND R. KEUNINGS, Optimized partitioning of unstructured finite-element meshes, International Journal for Numerical Methods in Engineering, 38 (1995), pp. 433-450.

80

C. WALSHAW, M. CROSS, S. JOHNSON AND M. EVERETT, A parallelisable algorithm for partitioning unstructured meshes, in: Proceeding of Irregular '94: Parallel Algorithms for Irregular Problems: State of the Art, A. Ferreira and J. Rolim, eds, Kluwer Academic Publishers, Dordrecht, 1995, pp. 23-44.

81

C. WALSHAW AND M. BERZINS, Dynamic load-balancing for PDE solvers on adaptive unstructured meshes, Concurrency: Practice and Experience, 7 (1995), pp. 17-28.

82

C. WALSHAW, M. CROSS AND M. EVERETT, Dynamic mesh partitioning: a unified optimisation and load-balancing algorithm, Technical Report 95/IM/06, University of Greenwich, London SE18 6PF, UK, 1995.

83

C. WALSHAW, M. CROSS AND M. EVERETT, PARALLEL dynamic load balancing for adaptive unstructured meshes, Journal of Parallel and Distributed Computing, 47 (1997), pp. 102-108.

84

C. WALSHAW, M. CROSS, R. DIEKMANN, AND F. SCHLIMBACH, Multilevel mesh partitioning for aspect ratio, in Proc. VecPar'98, Porto, Portugal, pages 381-394, Universidade do Porto, 1998.

85

C. WALSHAW AND M. CROSS, Parallel optimisation algorithms for multilevel mesh partitioning, Technical Report 99/IM/44, University of Greenwich, London SE18 6PF, UK, 1999.

86

H. G. WELLER, G. TABOR, H. JASAK AND C. FUREBY, A tensorial approach to computational continuum mechanics using object oriented techniques, Thermofluids Section Report TF-98/03, Department of Mechanical Engineering, Imperial College, UK, 1998.

87

R. D. WILLIAMS, Performance of dynamic load balancing algorithms for unstructured mesh calculations, Concurrency: Practice and Experience, 3 (1991), pp. 457-481.

88

C. Z. XU AND F. C. M. LAU, Analysis of the generalized dimension exchange method for dynamic load balancing, Journal of Parallel and Distributed Computing, 16 (1992), pp. 385-393.

89

C. Z. XU AND F. C. M. LAU, The generalized dimension exchange method for load balancing in K-ary ncubes and variants, Journal of Parallel and Distributed Computing, 24 (1995), pp. 72-85.