

FOLLOWUS
1. Department of Computer Science Xiamen University
2. State Key Laboratory of Marine Environmental Science (Xiamen University)
3. Department of Civil and Structural Engineering the Hong Kong Polytechnic University
Online First:10 November 2010,
Published:2010
Scan QR Code
Zhang, Z., Hong, H., Wai, O.W. et al. Parallel hydrodynamic finite element model with an N-Best refining partition scheme., Chin. J. Ocean. Limnol. 28, 1340–1349 (2010). https://doi.org/10.1007/s00343-010-9937-x
We enhance a robust parallel finite element model for coasts and estuaries cases with the use of N-Best refinement algorithms
in multilevel partitioning scheme. Graph partitioning is an important step to construct the parallel model
in which computation speed is a big concern. The partitioning strategy includes the division of the research domain into several semi-equal-sized sub-domains
minimizing the sum weight of edges between different sub-domains. Multilevel schemes for graph partitioning are divided into three phases: coarsening
partitioning
and uncoarsening. In the uncoarsening phase
many refinement algorithms have been proposed previously
such as KL
Greedy
and Boundary refinements. In this study
we propose an N-Best refinement algorithm and show its advantages in our case study of Xiamen Bay. Compared with original partitioning algorithm in previous models
the N-Best algorithm can speed up the computation by 1.9 times
and the simulation results are in a good match with the in-situ data.
Anderson E. 1988. Parallel implementation of preconditioned conjugate gradient methods for solving sparse systems of linear equations. Technical Report 805, Centre for Supercomputing Research and Development, University Illinois, Urbana, IL.
Aykanat C, Özgüner F, Ercal F, Sadayappan P. 1988. Iterative algorithms for solution of large sparse systems of linear equations on hypercubes. IEEE Transactions on Computers, 37(12): 1 554–1 567.
Barnard S T, Simon H D. 1993. A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. In: Sincovec R F, Keyes D E, Leuze M R, Petzold L R, Reed D E eds. Proceedings of the 6th SIAM Conference on Parallel Processing for Scientific Computing. Society for Industrial and Applied Mathematics. Philadelphia, United State. p.711–718.
Baños R, Gil C, Ortega J, Montoya F G. 2004. A parallel multilevel metaheuristic for graph partitioning. Journal of Heuristics, 10(3): 315–336.
Berger M J, Bokhari S H. 1987. A partitioning strategy for nonuniform problems on multiprocessors. IEEE Transactions on Computers, 36(5): 570–580.
Bui T, Jones C. 1993. A heuristic for reducing fill in sparse matrix factorization. Proceedings of the 6th SIAM Conference on Parallel Processing for Scientific Computing. In: Sincovec R F, Keyes D E, Leuze M R, Petzold L R, Reed D E eds. Proceedings of the 6th SIAM Conference on Parallel Processing for Scientific Computing. Society for Industrial and Applied Mathematics. Philadelphia, United State. p. 445–452.
Ciarlet J P, Lamour F. 1996. On the validity of a front-oriented approach to partitioning large sparse graphs with a connectivity constraint. Numerical Algorithms, 12: 193–214.
Cong J, Smith M L. 1993. A parallel bottom-up clustering algorithm with applications to circuit partitioning in VLSI design. In: Dunlop A E (Chairman). Proceedings of the 30th International Conference on Design Automation. Dallas, Texas, United States. p. 755–760.
Farhat C. 1988. A Simple and efficient automatic FEM domain decomposer. Computers and Structures, 28(5): 579–602.
Fiduccia C M, Mattheyses R M. 1982. A linear-time heuristic for improving network partitions. Proceedings of 19th IEEE Design Automation Conference. In: Friendenson R A, Breiland J R, Thompson T J eds. IEEE Press, Piscataway, NJ, USA. p.175–181.
Geohring T, Saad Y. 1994. Heuristic algorithms for automatic graph partitioning. Technical report UMSI-94-29, Department of Computer Science, University of Minnesota, Minneapolis.
George A, Liu J W. 1981. Computer solution of large sparse positive definite systems. Prentice-Hall, Englewood Cliffs, New Jersey.
Hendrickson B, Leland R. 1995a. The Chaco User’s Guide, Version 2.0. Technical Report SAND95-2344, Sandia Natl. Lab., Albuquerque, NM, 87185.
Hendrickson B, Leland R. 1995b. An improved spectral graph partitioning algorithm for mapping parallel computations. SIAM Journal of Scientific Computing, 16(2): 452–469.
Hendrickson B, Leland R. 1995c. A multilevel algorithm for partitioning graphs. Proceedings of Supercomputing. p. 626–657.
Hsieh S H, Paulino G H, Abel J F. 1995. Recursive spectral algorithms for automatic domain partitioning in parallel finite element analysis. Computer Methods in Applied Mechanics and Engineering, 121(1): 137–162.
Jiang Y W, Wai O W H, Li Y S. 2003. 3D parallel estuary model for cohesive sediment transport in large tidal flats. Coastal Sediments’ 03, Fifth International Symposium on Coastal Engineering and Science of Coastal Sediment Processes. Florida. ISTP. ISBN: 981-238-422-7.
Jiang Y W, Wai O W H. 2005. Drying-wetting approach for 3D finite element sigma coordinate model for estuaries with large tidal flats. Advances in Water Resources, 28(8): 779–792.
Jones M T, Plassman P E. 1994. Parallel algorithms for the adaptive refinement and partitioning of unstructured meshes. Proceedings of the Scalable High Performance Computing Conference. p. 478–485.
Kamath C, Sameh A H. 1984. The preconditioned conjugate gradient algorithm on a multiprocessor. In: Vichnevetsky R, Stepleman R S eds. Advances in Computer Methods for Partial Differential Equations, New York, IMACS.
Karypis G, Kumar V. 1995a. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 20(1): 359–392.
Karypis G, Kumar V. 1995b. METIS: Unstructured graph partitioning and sparse matrix ordering system. Technical Report, Department of Computer Science, University of Minnesota.
Karypis G, Kumar V. 1996. Parallel multilevel graph partitioning. Proceedings of the 10th International Parallel Processing Symposium. p. 314–319.
Karypis G, Kumar V. 1998. A parallel algorithm for multilevel graph partitioning and sparse matrix ordering. Journal of Parallel and Distributed Computing, 48(1): 71–95.
Kernighan B W, Lin S. 1970. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 49(2): 291–308.
Kim S K, Chronopoulos A. 1991. A class of Lanczos-like algorithms implemented on parallel computers. Parallel Computing, 17: 763–778.
Lu Q M, Wai O W H. 1998. An efficient operator splitting scheme for three-dimensional hydrodynamic computations. International Journal for Numerical Methods in Fluids, 26(7): 771–789.
Pellegrini F. 1996. SCOTCH 3.1 User’s Guide. Technical Report 1137-96, LaBRI., University Bordeaux, France.
Pothen A, Simon H D, Liou K P. 1990. Partitioning sparse matrices with eigenvectors of graphs. SIAM Journal on Matrix Analysis and Applications, 11(3): 430–452.
Pothen A, Simon H D, Wang L. 1992. Towards a fast implementation of spectral nested dissection. In: Werner Robert ed. Proceedings of the 1992 ACM/IEEE Conference on Supercomputing. Minneapolis, Minnesota, United States. p.42–51.
Preis R, Diekmann R. 1996. The PARTY Partitioning-Library, User Guide-Version 1.1. Technical Report Tr-rsfb-96-024, University of Paderborn, Paderborn, Germany.
Saad Y, Schultz M H. 1985. Parallel implementations of preconditioned conjugate gradient methods. Technical Report, Yale University, Department of Computer Science.
Schloegel K, Karypis G, Kumar V. 2001. Wavefront diffusion and LMSR: algorithms for dynamic repartitioning of adaptive meshes. IEEE Transactions on Parallel and Distributed Systems, 12(5): 451–466.
Wai O W H, Lu Q M. 2000. An efficient parallel model for coastal transport process simulation. Advances in Water Resources, 23(7): 747–764.
Wai O W H, Chen Y, Li Y S. 2004a. A 3-D wave-current driven coastal sediment transport model. Coastal Engineering Journal, 46(4): 385–424.
Wai O W H, Wang C H, Li Y S, Li X D. 2004b. The formation mechanisms of turbidity maximum in the Pearl River estuary, China. Marine Pollution Bulletin, 48(5): 441–448.
Walshaw C, Cross M, Everett M. 1999. Mesh partitioning and load-balancing for distributed memory parallel systems. In: Topping B H V ed. Proceedings Parallel and Distributed Computing for Computational Mechanics: Systems and Tools, Saxe-Coburg Publications, Edinburgh. p. 110–123.
Wang W Q, Zhang Y H, Huang Z Q. 2000. Characteristics of salinity front in Jiulongjiang Estuary Xiamen Harbour. Journal of Oceanography in Taiwan Strait, 19(1): 82–88. (in Chinese with English abstract).
0
Views
0
Downloads
0
CSCD
Publicity Resources
Related Articles
Related Author
Related Institution
京公网安备11010802024621