“Efficient preconditioning of laplacian matrices for computer graphics” by Krishnan, Szeliski and Fattal
Conference:
Type:
Title:
- Efficient preconditioning of laplacian matrices for computer graphics
Session/Category Title: Laplacians, Light Field & Layouts
Presenter(s)/Author(s):
Moderator(s):
Abstract:
We present a new multi-level preconditioning scheme for discrete Poisson equations that arise in various computer graphics applications such as colorization, edge-preserving decomposition for two-dimensional images, and geodesic distances and diffusion on three-dimensional meshes. Our approach interleaves the selection of fine-and coarse-level variables with the removal of weak connections between potential fine-level variables (sparsification) and the compensation for these changes by strengthening nearby connections. By applying these operations before each elimination step and repeating the procedure recursively on the resulting smaller systems, we obtain a highly efficient multi-level preconditioning scheme with linear time and memory requirements. Our experiments demonstrate that our new scheme outperforms or is comparable with other state-of-the-art methods, both in terms of operation count and wall-clock time. This speedup is achieved by the new method’s ability to reduce the condition number of irregular Laplacian matrices as well as homogeneous systems. It can therefore be used for a wide variety of computational photography problems, as well as several 3D mesh processing tasks, without the need to carefully match the algorithm to the problem characteristics.
References:
1. Aksoylu, B., Khodakovsky, A., and Schröder, P. 2005. Multilevel solvers for unstructured surface meshes. SIAM Journal on Scientific Computing 26, 4, 1146–1165. Google ScholarDigital Library
2. Alcouffe, R., Brandt, A., Dendy, Jr, J., and Painter, J. 1981. The multi-grid method for the diffusion equation with strongly discontinuous coefficients. SIAM Journal on Scientific and Statistical Computing 2, 4, 430–454.Google ScholarDigital Library
3. Arbenz, P., Hetmanuik, U., Lehoucq, R., and Tuminaro, R. 2003. A comparison of eigensolvers for large-scale 3D modal analysis using amg-preconditioned iterative methods. Int. Journal for Numerical Methods in Engg. 1.Google Scholar
4. Baker, S., Scharstein, D., Lewis, J. P., Roth, S., Black, M. J., and Szeliski, R. 2011. A database and evaluation methodology for optical flow. Int. J. Comput. Vision 92 (March), 1–31. Google ScholarDigital Library
5. Bhat, P., Zitnick, C. L., Cohen, M., and Curless, B. 2010. Gradientshop: A gradient-domain optimization framework for image and video filtering. ACM Trans. Graph. 29 (April), 10:1–10:14. Google ScholarDigital Library
6. Bolz, J., Farmer, I., Grinspun, E., and Schröoder, P. 2003. Sparse matrix solvers on the GPU: conjugate gradients and multigrid. In ACM SIGGRAPH 2003 Papers, ACM, New York, NY, USA, SIGGRAPH ’03, 917–924. Google ScholarDigital Library
7. Boman, E., G., and Hendrickson, B. 2001. On spanning tree preconditioners. Sandia National Labs.Google Scholar
8. Boman, E., G., and Hendrickson, B. 2003. Support theory for preconditioning. SIAM J. Matrix Anal. Appl., 3, 694–717. Google ScholarDigital Library
9. Bouwmeester, H., Dougherty, A., and Knyazev, A. V. 2012. Nonsymmetric multigrid preconditioning for conjugate gradient methods. arXiv preprint arXiv:1212.6680.Google Scholar
10. Brandt, A., Brannick, J. J., Kahl, K., and Livshits, I. 2011. Bootstrap AMG. SIAM J. Scientific Computing 33, 2, 612–632. Google ScholarDigital Library
11. Brandt, A. 1973. Multi-level adaptive technique (MLAT) for fast numerical solution to boundary value problems. In Proc. Conf. on Numerical Methods in Fluid Mechanics, vol. 18 of Lecture Notes in Physics. Springer Berlin/Heidelberg, 82–89.Google ScholarCross Ref
12. Brandt, A. 1986. Algebraic multigrid theory: The symmetric case. Applied Mathematics and Computation 19, 1-4, 23–56. Google ScholarDigital Library
13. Brandt, A. 2001. Multiscale scientific computation: Review 2001. In Multiscale and Multiresolution Methods, Springer Verlag, 1–96.Google Scholar
14. Crane, K., Weischedel, C., and Wardetzky, M. 2012. Geodesics in heat. ACM Transactions on Graphics (Proc. SIGGRAPH) 31, 4 (July).Google Scholar
15. Davis, T. A. 2006. Direct Methods for Sparse Linear Systems. SIAM. Google ScholarDigital Library
16. Farbman, Z., Fattal, R., Lischinski, D., and Szeliski, R. 2008. Edge-preserving decompositions for multi-scale tone and detail manipulation. ACM Transactions on Graphics (Proc. SIGGRAPH) 27, 3 (August). Google ScholarDigital Library
17. Farbman, Z., Fattal, R., and Lischinski, D. 2011. Convolution pyramids. ACM Trans. Graph. 30 (December), 175:1–175:8. Google ScholarDigital Library
18. Fattal, R., Lischinski, D., and Werman, M. 2002. Gradient domain high dynamic range compression. ACM Transactions on Graphics, 249–256. Google ScholarDigital Library
19. Fattal, R. 2009. Edge-avoiding wavelets and their applications. In ACM SIGGRAPH papers, ACM, New York, NY, USA, 22:1–22:10. Google ScholarDigital Library
20. Fleishman, S., Drori, I., and Cohen-Or, D. 2003. Bilateral mesh denoising. ACM Transactions on Graphics (Proc. SIGGRAPH) 22, 3. Google ScholarDigital Library
21. Golub, G., and Van Loan, C. F. 1996. Matrix computation, third edition. The John Hopkins University Press, Baltimore and London. Google ScholarDigital Library
22. Kazhdan, M., and Hoppe, H. 2008. Streaming multigrid for gradient-domain operations on large images. ACM Trans. Graph. 27, 3, 21:1–21:10. Google ScholarDigital Library
23. Kelner, J. A., Orecchia, L., Sidford, A., and Zhu, Z. A. 2013. A simple, combinatorial algorithm for solving SDD systems in nearly-linear time. arXiv preprint arXiv:1301.6628.Google Scholar
24. Kincaid, D., and Cheney, W. 1991. Numerical analysis: mathematics of scientific computing. Brooks/Cole Publishing Co., Pacific Grove, CA, USA. Google ScholarDigital Library
25. Koutis, I., Miller, G. L., and Peng, R. 2010. Approaching optimality for solving SDD linear systems. Proceedings of FOCS 2010. Google ScholarDigital Library
26. Koutis, I., Miller, G. L., and Tolliver, D. 2011. Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing. Computer Vision and Image Understanding, 1638–1646. Google ScholarDigital Library
27. Koutis, I., Miller, G. L., and Peng, R. 2011. A nearly-m log n time solver for SDD linear systems. In Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, IEEE, 590–598. Google ScholarDigital Library
28. Krishnan, D., and Szeliski, R. 2011. Multigrid and multilevel preconditioners for computational photography. ACM Transactions on Graphics (Proc. SIGGRAPH Asia), 5. Google ScholarDigital Library
29. Kushnir, D., Galun, M., and Brandt, A. 2010. Efficient multilevel eigensolvers with applications to data analysis tasks. Pattern Analysis and Machine Intelligence, IEEE Transactions on 32, 8, 1377–1391. Google ScholarDigital Library
30. Levin, A., Lischinski, D., and Weiss, Y. 2004. Colorization using optimization. ACM Transactions on Graphics, 689–694. Google ScholarDigital Library
31. Levin, A., Rav-Acha, A., and Lischinski, D. 2007. Spectral matting. Proceedings of CVPR.Google Scholar
32. Lipton, R. J., Rose, D. J., and Tarjan, R. E. 1979. Generalized nested dissection. SIAM J. Numer. Anal. 16, 346–358.Google ScholarDigital Library
33. Lischinski, D., Farbman, Z., Uyttendaele, M., and Szeliski, R. 2006. Interactive local adjustment of tonal values. In ACM SIGGRAPH Papers, ACM, New York, NY, USA, 646–653. Google ScholarDigital Library
34. Liu, R., and Zhang, H. 2007. Mesh segmentation via spectral embedding and contour analysis. Eurographics 26, 3.Google ScholarCross Ref
35. Livne, O., and Brandt, A. 2011. Lean algebraic multigrid (LAMG): Fast graph laplacian solver. arXiv:1108.0123v1.Google Scholar
36. Moulton, J. D., Dendy, Jr., J. E., and Hyman, J. M. 1998. The black box multigrid numerical homogenization algorithm. J. Comput. Phys. 142 (May), 80–108. Google ScholarDigital Library
37. Pérez, P., Gangnet, M., and Blake, A. 2003. Poisson image editing. ACM Transactions on Graphics (Proc. SIGGRAPH) 22, 3, 313–318. Google ScholarDigital Library
38. Saad, Y. 2003. Iterative Methods for Sparse Linear Systems, second ed. Society for Industrial and Applied Mathematics. Google ScholarDigital Library
39. Shi, L., Yu, Y., Bell, N., and Feng, W.-W. 2006. A fast multi-grid algorithm for mesh deformation. In ACM SIGGRAPH 2006 Papers, ACM, New York, NY, USA, SIGGRAPH ’06, 1108–1117. Google ScholarDigital Library
40. Spielman, D. A., and Teng, S.-H. 2006. Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. CoRR abs/cs/0607105.Google Scholar
41. Spielman, D., A. 2010. Algorithms, graph theory and linear equations in Laplacian matrices. Proceedings of the International Congress of Mathematicians (ICM).Google Scholar
42. Sun, J., Jia, J., Tang, C.-K., and Shum, H.-Y. 2004. Poisson matting. In ACM SIGGRAPH Papers, ACM, New York, NY, USA, 315–321. Google ScholarDigital Library
43. Szeliski, R. 1990. Fast surface interpolation using hierarchical basis functions. Pattern Analysis and Machine Intelligence, IEEE Transactions on 12, 6 (jun), 513–528. Google ScholarDigital Library
44. Szeliski, R. 2006. Locally adapted hierarchical preconditioning. Proceedings of ACM SIGGRAPH. Google ScholarDigital Library
45. Trottenberg, U., Oosterlee, C., and Schuller, A. 2001. Multigrid. Academic Press. Google ScholarDigital Library
46. Vaidya, P. 1990. Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. Tech. rep., Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL.Google Scholar
47. Vaněk, P., Mandel, J., and Brezina, M. 1996. Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems. Computing 56, 3, 179–196.Google ScholarCross Ref
48. Vaněk, P. 1995. Fast multigrid solver. Applications of Mathematics 40, 1, 1–20.Google ScholarCross Ref
49. Xu, K., Li, Y., Ju, T., Hu, S.-M., and Liu, T.-Q. 2009. Efficient affinity-based edit propagation using K-D tree. In ACM SIGGRAPH Asia papers, ACM, New York, NY, USA, 118:1–118:6. Google ScholarDigital Library
50. Yserentant, H. 1986. On the multi-level splitting of finite element spaces. Numerische Mathematik 49, 379–412. 10.1007/BF01389538. Google ScholarDigital Library
51. Zeeuw, P. D. 1990. Matrix-dependent prolongations and restrictions in a blackbox multigrid solver. Journal of Computational and Applied Mathematics 33, 1, 1–27. Google ScholarDigital Library
52. Zhu, Y., Sifakis, E., Teran, J., and Brandt, A. 2010. An efficient multigrid method for the simulation of high-resolution elastic solids. ACM Trans. Graph. 29 (April), 16:1–16:18. Google ScholarDigital Library
