Truncated Newton-Based Multigrid Algorithm for Centroidal Voronoi Diagram Calculation

作     者：Zichao Di Maria Emelianenko Stephen Nash 

作者机构：Department of Mathematical SciencesGeorge Mason UniversityFairfaxVA 22030USA. Systems Engineering and Operations Research DepartmentGeorge Mason UniversityFairfaxVA 22030USA 

出 版 物：《Numerical Mathematics(Theory,Methods and Applications)》 (高等学校计算数学学报（英文版）)

年 卷 期：2012年第5卷第2期

页      面：242-259页

核心收录：

学科分类：0820[工学-石油与天然气工程] 07[理学] 070102[理学-计算数学] 0714[理学-统计学（可授理学、经济学学位）] 0701[理学-数学] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：supported by the U.S.Department of Energy under Award DE-SC-0001691 support from the ORAU Ralph E.Powe Junior Faculty Enhancement Award and from the National Science Foundation under the grants DMS-1056821 and DMS-0915013. 

主　　题：Centroidal Voronoi tessellation optimal quantization truncated Newton method Lloyd’s algorithm multilevel method uniform convergence 

摘      要：In a variety of modern applications there arises a need to tessellate the domain into representative regions,called Voronoi cells.A particular type of such tessellations,called centroidal Voronoi tessellations or CVTs,are in big demand due to their optimality properties important for many applications.The availability of fast and reliable algorithms for their construction is crucial for their successful use in practical settings.This paper introduces a new multigrid algorithm for constructing CVTs that is based on the MG/Opt algorithm that was originally designed to solve large nonlinear optimization problems.Uniform convergence of the new method and its speedup comparing to existing techniques are demonstrated for linear and nonlinear densities for several 1d and 2d problems,and O(k)complexity estimation is provided for a problem with k generators.