Parallel hydrodynamic finite element model with an N-Best refining partition scheme

Zhenchang Zhang; Huasheng Hong; Onyx Winghong Wai; Yuwu Jiang; Changle Zhou

doi:10.1007/s00343-010-9937-x

Your Location：

Home >

Browse articles >

Parallel hydrodynamic finite element model with an N-Best refining partition scheme

OriginalPaper | Updated：2023-05-16

- Parallel hydrodynamic finite element model with an N-Best refining partition scheme
- Parallel hydrodynamic finite element model with an N-Best refining partition scheme
- 海洋湖沼学报（英文） 2010年28卷第6期页码：1340-1349
- Affiliations：
  
  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
- Author bio：
- Funds：
  
  Supported by the National Natural Science Foundation of China (Nos. 40406005, 41076001, 40440420596)
- DOI：10.1007/s00343-010-9937-x
  中图分类号：
- 网络首发：2010-11-10，
  
  纸质出版：2010
- Accepted：
Scan QR Code
Parallel hydrodynamic finite element model with an N-Best refining partition scheme[J]. 海洋湖沼学报（英文）, 2010,28(6):1340-1349.

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
Parallel hydrodynamic finite element model with an N-Best refining partition scheme[J]. 海洋湖沼学报（英文）, 2010,28(6):1340-1349. DOI： 10.1007/s00343-010-9937-x.

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 DOI：

摘要

Abstract

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.

关键词

Keywords

references

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).

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

暂无数据