“Updated Sparse Cholesky Factors for Corotational Elastodynamics” by Hecht, Lee, Shewchuk and O’Brien

  • ©Florian Hecht, Yeon Jin Lee, Jonathan R. Shewchuk, and James F. O'Brien




    Updated Sparse Cholesky Factors for Corotational Elastodynamics



    We present warp-canceling corotation, a nonlinear finite element formulation for elastodynamic simulation that achieves fast performance by making only partial or delayed changes to the simulation’s linearized system matrices. Coupled with an algorithm for incremental updates to a sparse Cholesky factorization, the method realizes the stability and scalability of a sparse direct method without the need for expensive refactorization at each time step. This finite element formulation combines the widely used corotational method with stiffness warping so that changes in the per-element rotations are initially approximated by inexpensive per-node rotations. When the errors of this approximation grow too large, the per-element rotations are selectively corrected by updating parts of the matrix chosen according to locally measured errors. These changes to the system matrix are propagated to its Cholesky factor by incremental updates that are much faster than refactoring the matrix from scratch. A nested dissection ordering of the system matrix gives rise to a hierarchical factorization in which changes to the system matrix cause limited, well-structured changes to the Cholesky factor. We show examples of simulations that demonstrate that the proposed formulation produces results that are visually comparable to those produced by a standard corotational formulation. Because our method requires computing only partial updates of the Cholesky factor, it is substantially faster than full refactorization and outperforms widely used iterative methods such as preconditioned conjugate gradients. Our method supports a controlled trade-off between accuracy and speed, and unlike most iterative methods its performance does not slow for stiffer materials but rather it actually improves.


    Barrett, R., Berry, M., Chan, T., Demmel, J., Donato, J., Dongarra, J., Eijkhout, V., Pozo, R., Romine, C., and van der Vorst, H. 1993. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. SIAM, Pennsylvania, PA.Google Scholar
    Belytschko, T. and Hsieh, B. 1979. Application of higher order corotational stretch theories to nonlinear finite element analysis. Comput. Struct. 11, 175–182.Google ScholarCross Ref
    Bergou, M., Wardetzky, M., Robinson, S., Audoly, B., and Grinspun, E. 2008. Discrete elastic rods. ACM Trans. Graph. 27, 3, 63:1–63:12. Google ScholarDigital Library
    Botsch, M., Bommes, D., and Kobbelt, L. 2005. Efficient linear system solvers for mesh processing. In Proceedings of the IMA Conference on the Mathematics of Surfaces. Springer, 62–83. Google ScholarDigital Library
    Bridson, R., Fedkiw, R., and Muller-Fischer, M. 2006. Fluid simulation: SIGGRAPH course notes. In ACM SIGGRAPH Courses. 1–87. Google ScholarDigital Library
    Bridson, R., Marino, S., and Fedkiw, R. 2003. Simulation of clothing with folds and wrinkles. In Proceedings of the Symposium on Computer Animation. 28–36. Google ScholarDigital Library
    Chen, Y., Davis, T. A., Hager, W. W., and Rajamanickam, S. 2008. Algorithm 887: CHOLMOD, supernodal sparse Cholesky factorization and update/downdate. ACM Trans. Math. Softw. 35, 22:1–22:14. Google ScholarDigital Library
    Chentanez, N., Alterovitz, R., Ritchie, D., Cho, L., Hauser, K. K., Goldberg, K., Shewchuk, J. R., and O’Brien, J. F. 2009. Interactive simulation of surgical needle insertion and steering. ACM Trans. Graph. 28, 3, 88.1–88.10. Google ScholarDigital Library
    Choi, M. G. and Ko, H.-S. 2005. Modal warping: Real-Time simulation of large rotational deformation and manipulation. IEEE Trans. Vis. Comput. Graph. 11, 1, 91–101. Google ScholarDigital Library
    Cholesky, A.-L. 1910. Sur la résolution numérique des systèmes d’équations linéaires. Manuscript. Subsequently published in Bull. de la Sabix 39, 81–95, 2005.Google Scholar
    Courtecuisse, H., Allard, J., Duriez, C., and Cotin, S. 2010. Asynchronous preconditioners for efficient solving of non-linear deformations. In Proceedings of the 7th Workshop on Virtual Reality Interaction and Physical Simulation. 59–68.Google Scholar
    Davis, T. A. 2006. Direct Methods for Sparse Linear Systems. Fundamentals of Algorithms, vol. 2, SIAM. Google ScholarDigital Library
    Davis, T. A. and Hager, W. W. 1999. Modifying a sparse Cholesky factorization. SIAM J. Matrix Anal. Appl. 20, 3, 606–627. Google ScholarDigital Library
    Davis, T. A. and Hager, W. W. 2009. Dynamic supernodes in sparse Cholesky update/downdate and triangular solves. ACM Trans. Math. Softw. 35, 4. Google ScholarDigital Library
    Etzmuss, O., Keckeisen, M., and Strasser, W. 2003. A fast finite element solution for cloth modelling. In Proceedings of the 11th Pacific Conference on Computer Graphics and Applications. 244–251. Google ScholarDigital Library
    Felippa, C. 2007. Introduction to finite element methods. http://www.colorado.edu/engineering/cas/courses.d/NFEM.d.Google Scholar
    George, A. 1973. Nested dissection of a regular finite element mesh. SIAM J. Numer. Anal. 10, 2, 345–363.Google ScholarDigital Library
    Gibson, S. F. F. and Mirtich, B. 1997. A survey of deformable modeling in computer graphics. Tech. rep. TR97-19, Mitsubishi Electric Research Laboratory. November.Google Scholar
    Gill, P. E., Golub, G. H., Murray, W., and Saunders, M. A. 1974. Methods for modifying matrix factorizations. Math. Comput. 28, 126, 505–535.Google Scholar
    Golub, G. H. and Van Loan, C. F. 1996. Matrix Computations, 3rd Ed. The Johns Hopkins University Press. Google ScholarDigital Library
    Gould, N. I. M., Scott, J. A., and Hu, Y. 2007. A numerical evaluation of sparse direct solvers for the solution of large sparse symmetric linear systems of equations. ACM Trans. Math. Softw. 33, 2, 1–32. Google ScholarDigital Library
    Grcar, J. F. 2011. John von Neumann’s analysis of Gaussian elimination and the origins of modern numerical analysis. SIAM Rev. 53, 4, 607–682. Google ScholarDigital Library
    Grinspun, E., Hirani, A. N., Desbrun, M., and Schröder, P. 2003. Discrete shells. In Proceedings of the Symposium on Computer Animation. 62–67. Google ScholarDigital Library
    Hestenes, M. R. and Stiefel, E. 1952. Methods of conjugate gradients for solving linear systems. J. Res. Nat. Bureau Standards 49, 409–436.Google ScholarCross Ref
    Horn, B. K. P. 1987. Closed-Form solution of absolute orientation using unit quaternions. J. Opt. Soc. A 4, 4, 629–642.Google ScholarCross Ref
    Irving, G., Teran, J., and Fedkiw, R. 2004. Invertible finite elements for robust simulation of large deformation. In Proceedings of the Symposium on Computer Animation. 131–140. Google ScholarDigital Library
    Karypis, G. and Kumar, V. 1995. A fast and high quality multilevel scheme for partitioning irregular graphs. In Proceedings of the International Conference on Parallel Processing. 113–122.Google Scholar
    Li, X. S. and Demmel, J. W. 1999. A scalable sparse direct solver using static pivoting. In Proceedings of the 9th SIAM Conference on Parallel Processing for Scientic Computing. 1–10.Google Scholar
    Lipton, R. J., Rose, D. J., and Tarjan, R. E. 1979. Generalized nested dissection. SIAM J. Numer. Anal. 16, 2, 346–358.Google ScholarDigital Library
    Martin, S., Kaufmann, P., Botsch, M., Grinspun, E., and Gross, M. 2010. Unified simulation of elastic rods, shells, and solids. ACM Trans. Graph. 29, 4, 39:1–39:10. Google ScholarDigital Library
    Müller, M., Dorsey, J., McMillan, L., Jagnow, R., and Cutler, B. 2002. Stable real-time deformations. In Proceedings of the Symposium on Computer Animation. 49–54. Google ScholarDigital Library
    Müller, M. and Gross, M. 2004. Interactive virtual materials. In Proceedings of Graphics Interface Conference. 239–246. Google ScholarDigital Library
    Müller, M., Heidelberger, B., Teschner, M., and Gross, M. 2005. Meshless deformations based on shape matching. ACM Trans. Graph. 24, 3, 471–478. Google ScholarDigital Library
    Nealen, A., Müller, M., Keiser, R., Boxerman, E., and Carlson, M. 2006. Physically based deformable models in computer graphics. Comput. Graph. Forum 25, 4, 809–836.Google ScholarCross Ref
    Nour-Omid, B. and Rankin, C. C. 1991. Finite rotation analysis and consistent linearization using projectors. Comput. Meth. Appl. Mechan. Engin. 93, 353–384.Google ScholarCross Ref
    Parker, E. G. and O’Brien, J. F. 2009. Real-Time deformation and fracture in a game environment. In Proceedings of the Symposium on Computer Animation. 156–166. Google ScholarDigital Library
    Press, W. H., Teukolsky, S. A., Vetterling, W. T., and Flannery, B. P. 2002. Numerical Recipes in C++: The Art of Scientific Computing. Cambridge University Press. Google ScholarDigital Library
    Shewchuk, J. R. 1994. An introduction to the conjugate gradient method without the agonizing pain. Tech. rep. CMU-CS-94-125, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA. Google ScholarDigital Library
    Sorkine, O., Cohen-Or, D., Irony, D., and Toledo, S. 2005. Geometry-Aware bases for shape approximation. IEEE Trans. Vis. Comput. Graph. 11, 2, 1–11. Google ScholarDigital Library
    Terzopoulos, D., Platt, J., Barr, A., and Fleischer, K. 1987. Elastically deformable models. In Proceedings of SIGGRAPH Conference. 205–214. Google ScholarDigital Library
    Toledo, S. 2003. TAUCS: A library of sparse linear solvers. http://www.tau.ac.il/~stoledo/taucs.Google Scholar
    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, 2, 16:1–16:18. Google ScholarDigital Library

ACM Digital Library Publication: