Published |
ABSTRACT:
A Centroidal Voronoi Tessellation (CVT) is a Voronoi tessellation in which the generators are the centroids for each Voronoi region. CVTs have many applications to computer graphics, image processing, data compression, mesh generation, and optimal quantization. Lloyd's method, the most widely method used to generate CVTs, converges very slowly for larger scale problems. Recently quasi-Newton methods using the Hessian of the energy associated as a preconditioner are developed to speed up the rate of convergence. In this work a graph Laplacian preconditioner and a two-grid method are used to speed up quasi-Newton schemes. The proposed graph Laplacian is always symmetric, positive definite and easy to assemble, while the Hessian, in general, may not be positive definite nor easy to assemble. Therefore the graph Laplacian works as a better preconditioner than the Hessian which needs modification to be used a preconditioner. The two-grid method is used to generate a better initial guess to further speed up the convergence. Numerical tests show that our preconditioned optimization methods converges fast and has nearly linear complexity.