A log-barrier method for mesh quality improvement and untangling

详细信息    查看全文

• 作者：Shankar P. Sastry (1)
  Suzanne M. Shontz (2)
  Stephen A. Vavasis (3)
  
• 关键词：Mesh quality improvement ; Mesh optimization ; Mesh untangling ; Interior point method ; Log ; barrier
• 刊名：Engineering with Computers
• 出版年：2014
• 出版时间：July 2014
• 年：2014
• 卷：30
• 期：3
• 页码：315-329
• 全文大小：
• 参考文献：1. Fried E (1972) Condition of finite element matrices generated from nonuniform meshes. AIAA J 10:219鈥?21 CrossRef
  2. Babuska I, Suri M (1994) The p and h-p versions of the finite element method, basic principles, and properties. SIAM Rev 35:579鈥?32
  3. Berzins M (1997) Solution-based mesh quality for triangular and tetrahedral meshes. In: Proceedings of the 6th international meshing roundtable, pp 427鈥?36
  4. Berzins M (1998) Mesh quality鈥攇eometry, error estimates, or both? In: Proceedings of the 7th international meshing roundtable, pp 229鈥?37
  5. Knupp P (1999) Matrix norms and the condition number: a general framework to improve mesh quality via node-movement. In: Proceedings of the 8th international meshing roundtable, pp 13鈥?2
  6. Knupp P, Freitag L (2002) Tetrahedral mesh improvement via optimization of the element condition number. Int J Numer Methods Eng 53:1377鈥?391 CrossRef
  7. Amenta N, Bern M, Eppstein D (1997) Optimal point placement for mesh smoothing. In: Proceedings of the 8th ACM-SIAM symposium on discrete algorithms, pp 528鈥?37
  8. Munson T (2007) Mesh shape-quality optimization using the inverse mean-ratio metric. Math Program 110:561鈥?90 CrossRef
  9. Plaza A, Su谩rez J, Padr贸n M, Falc贸n S, Amieiro D (2004) Mesh quality improvement and other properties in the four-triangles longest-edge partition. Comput Aided Geom Des 21(4):353鈥?69 CrossRef
  10. Shewchuk J (2002) What is a good linear element? Interpolation, conditioning, and quality measures. In: Proceedings of the 11th international meshing roundtable, pp 115鈥?26
  11. Nocedal J, Wright S (2006) Numerical optimization, 2nd edn. Springer, New York
  12. Tang T (2004) Moving mesh methods for computational fluid dynamics. In: Proceedings of the international conference on recent advances in adaptive computation, vol 383, contemporary mathematics
  13. Shontz S, Vavasis S (2010) Analysis of and workarounds for element reversal for a finite element-based algorithm for warping triangular and tetrahedral meshes. BIT Numer Math 50:863鈥?84 CrossRef
  14. Shontz S, Vavasis S (2012) A robust solution procedure for hyperelastic solids with large boundary deformation. Eng Comput 28(2):135鈥?47 CrossRef
  15. Knupp P (2007) Updating meshes on deforming domains: an application of the target-matrix paradigm. Commun Num Method Eng 24:467鈥?76 CrossRef
  16. Kim J, Sastry S, Shontz S (2010) Efficient solution of elliptic partial differential equations via effective combination of mesh quality metrics, preconditioners, and sparse linear solvers. In: Proceedings of the 19th international meshing roundtable, pp 103鈥?20
  17. Bank R, Smith R (1997) Mesh smoothing using a posterior error estimates. SIAM J Numer Anal 34:979鈥?97 CrossRef
  18. Freitag L, Plassmann P (2000) Local optimization-based simplicial mesh untangling and improvement. Int J Numer Methods Eng 49:109鈥?25 CrossRef
  19. Park J, Shontz S (2010) Two derivative-free optimization algorithms for mesh quality improvement. In: Proceedings of the 2010 international conference on computational science, vol 1, pp 387鈥?96
  20. Escobar J, Rodriguez E, Montenegro R, Montero G, Gonzalez-Yuste J (2003) Simultaneous untangling and smoothing of tetrahedral meshes. Comput Method Appl Mech Eng 192:2775鈥?787 CrossRef
  21. Sastry S, Shontz S, Vavasis S (2011) A log-barrier method for mesh quality improvement. In Proceedings of the 20th international meshing roundtable, pp 329鈥?46
  22. Parthasarathy V, Graichen C, Hathaway A (1994) A comparison of tetrahedron quality measures. Finite Elem Anal Des 15:255鈥?61 CrossRef
  23. Brewer M, Frietag-Diachin L, Knupp P, Laurent T, Melander D (2003) The mesquite mesh quality improvement toolkit. In: Procedings of the 12th international meshing roundtable, pp 239鈥?50
  24. CUBIT generation and mesh generation toolkit. http://cubit.sandia.gov/
  25. Si H, TetGen: A quality tetrahedral mesh generator and three-dimensional delaunay triangulator. http://tetgen.berlios.de/
  26. Knupp P (2003) Sandia National Laboratories, personal communication
  27. Mehrotra S (1992) On the implementation of a primal-dual interior point method. SIAM J Optim 2(4):575鈥?01 CrossRef
  
• 作者单位：Shankar P. Sastry (1)
  Suzanne M. Shontz (2)
  Stephen A. Vavasis (3)
  
  1. The Pennsylvania State University, University Park, PA, 16802, USA
  2. Mississippi State University, Mississippi State, MS, 39762, USA
  3. University of Waterloo, Waterloo, ON, N2L-3G1, Canada
  
• ISSN：1435-5663

文摘

The presence of a few inverted or poor-quality mesh elements can negatively affect the stability, convergence and efficiency of a finite element solver and the accuracy of the associated partial differential equation solution. We propose a mesh quality improvement and untangling method that untangles a mesh with inverted elements and improves its quality. Worst element mesh quality improvement and untangling can be formulated as a nonsmooth unconstrained optimization problem, which can be reformulated as a smooth constrained optimization problem. Our technique solves the latter problem using a log-barrier interior point method and uses the gradient of the objective function to efficiently converge to a stationary point. The method uses a logarithmic barrier function and performs global mesh quality improvement. We have also developed a smooth quality metric that takes both signed area and the shape of an element into account. This quality metric assigns a negative value to an inverted element. It is used with our algorithm to untangle a mesh by improving the quality of an inverted element to a positive value. Our method usually yields better quality meshes than existing methods for improvement of the worst quality elements, such as the active set, pattern search, and multidirectional search mesh quality improvement methods. Our method is faster and more robust than existing methods for mesh untangling, such as the iterative stiffening method.