“Efficient preconditioning of laplacian matrices for computer graphics” by Krishnan, Szeliski and Fattal

  • ©Dilip Krishnan, Richard Szeliski, and Raanan Fattal



Session Title:

    Laplacians, Light Field & Layouts


    Efficient preconditioning of laplacian matrices for computer graphics




    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.


    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

ACM Digital Library Publication: