“Localized solutions of sparse linear systems for geometry processing”
Conference:
Type(s):
Title:
- Localized solutions of sparse linear systems for geometry processing
Session/Category Title: Geometry and Shape
Presenter(s)/Author(s):
Abstract:
Computing solutions to linear systems is a fundamental building block of many geometry processing algorithms. In many cases the Cholesky factorization of the system matrix is computed to subsequently solve the system, possibly for many right-hand sides, using forward and back substitution. We demonstrate how to exploit sparsity in both the right-hand side and the set of desired solution values to obtain significant speedups. The method is easy to implement and potentially useful in any scenarios where linear problems have to be solved locally. We show that this technique is useful for geometry processing operations, in particular we consider the solution of diffusion problems. All problems profit significantly from sparse computations in terms of runtime, which we demonstrate by providing timings for a set of numerical experiments.
References:
1. Marc Alexa and Max Wardetzky. 2011. Discrete Laplacians on General Polygonal Meshes. In ACM SIGGRAPH 2011 Papers (SIGGRAPH ’11). ACM, New York, NY, USA, Article 102, 10 pages.
2. Mario Botsch and Olga Sorkine. 2008. On Linear Variational Surface Deformation Methods. IEEE Transactions on Visualization and Computer Graphics 14, 1 (Jan 2008), 213–230.
3. Sofien Bouaziz, Mario Deuss, Yuliy Schwartzburg, Thibaut Weise, and Mark Pauly. 2012. Shape-Up: Shaping Discrete Geometry with Projections. Computer Graphics Forum 31, 5 (2012), 1657–1667.
4. Isaac Chao, Ulrich Pinkall, Patrick Sanan, and Peter Schröder. 2010. A Simple Geometric Model for Elastic Deformations. ACM Trans. Graph. 29, 4, Article 38 (July 2010), 6 pages.
5. Keenan Crane, Clarisse Weischedel, and Max Wardetzky. 2013. Geodesics in Heat: A New Approach to Computing Distance Based on Heat Flow. ACM Trans. Graph. 32, 5, Article 152 (Oct. 2013), 11 pages.
6. T. A. Davis. 2006. Direct Methods for Sparse Linear Systems. SIAM, Philadelphia, PA.
7. Timothy A Davis, Sivasankaran Rajamanickam, and Wissam M Sid-Lakhdar. 2016. A survey of direct methods for sparse linear systems. Acta Numerica 25 (2016), 383–566. Cross Ref
8. Mathieu Desbrun, Mark Meyer, and Pierre Alliez. 2002. Intrinsic Parameterizations of Surface Meshes. Computer Graphics Forum 21, 3 (2002), 209–218. Cross Ref
9. Mathieu Desbrun, Mark Meyer, Peter Schröder, and Alan H. Barr. 1999. Implicit Fairing of Irregular Meshes Using Diffusion and Curvature Flow. In Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’99). ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 317–324.
10. Matthias Eck, Tony DeRose, Tom Duchamp, Hugues Hoppe, Michael Lounsbery, and Werner Stuetzle. 1995. Multiresolution Analysis of Arbitrary Meshes. In Proceedings of the 22Nd Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’95). ACM, New York, NY, USA, 173–182.
11. Sharif Elcott and Peter Schröder. 2006. Building Your Own DEC at Home. In ACM SIGGRAPH 2006 Courses (SIGGRAPH ’06). ACM, New York, NY, USA, 55–59.
12. K Gebal, Jakob Andreas Bærentzen, Henrik Aanæs, and Rasmus Larsen. 2009. Shape analysis using the auto diffusion function. In Computer Graphics Forum, Vol. 28. Wiley Online Library, 1405–1413.
13. Alan George. 1973. Nested Dissection of a Regular Finite Element Mesh. SIAM J. Numer. Anal. 10, 2 (1973), 345–363.
14. A. George and J. W. H. Liu. 1978. An Automatic Nested Dissection Algorithm for Irregular Finite Element Problems. SIAM J. Numer. Anal. 15, 5 (1978), 1053–1069.
15. J. R. Gilbert and T. Peierls. 1988. Sparse Partial Pivoting in Time Proportional to Arithmetic Operations. SISC 9, 5 (1988), 862–874.
16. G.H. Golub and C.F. Van Loan. 2013. Matrix Computations. Johns Hopkins University Press.
17. Philipp Herholz, Felix Haase, and Marc Alexa. 2017. Diffusion Diagrams: Voronoi Cells and Centroids from Diffusion. Computer Graphics Forum 36, 2 (2017), 163–175.
18. Ilse C. F. Ipsen. 1997. Computing an Eigenvector with Inverse Iteration. SIAM Rev. 39, 2 (1997), 254–291.
19. George Karypis and Vipin Kumar. 1998. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on scientific Computing 20, 1 (1998), 359–392.
20. Bruno Lévy, Sylvain Petitjean, Nicolas Ray, and Jérome Maillot. 2002. Least Squares Conformal Maps for Automatic Texture Atlas Generation. ACM Trans. Graph. 21, 3 (July 2002), 362–371.
21. Joseph W.H. Liu. 1990. The Role of Elimination Trees in Sparse Factorization. SIAM J. Matrix Anal. Appl. 11, 1 (1990), 134–172.
22. Ligang Liu, Lei Zhang, Yin Xu, Craig Gotsman, and Steven J. Gortler. 2008. A Local/Global Approach to Mesh Parameterization. Computer Graphics Forum 27, 5 (2008), 1495–1504.
23. Mark Meyer, Mathieu Desbrun, Peter Schröder, and Alan H. Barr. 2003. Discrete Differential-Geometry Operators for Triangulated 2-Manifolds. Springer Berlin Heidelberg, Berlin, Heidelberg, 35–57.
24. Patrick Mullen, Yiying Tong, Pierre Alliez, and Mathieu Desbrun. 2008. Spectral Conformal Parameterization. In Proceedings of the Symposium on Geometry Processing (SGP ’08). Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 1487–1494. http://dl.acm.org/citation.cfm?id=1731309.1731335
25. Daniele Panozzo, Ilya Baran, Olga Diamanti, and Olga Sorkine-Hornung. 2013. Weighted Averages on Surfaces. ACM Trans. Graph. 32, 4, Article 60 (July 2013), 12 pages.
26. Ulrich Pinkall and Konrad Polthier. 1993. Computing discrete minimal surfaces and their conjugates. Experim. Math. 2 (1993), 15–36. Cross Ref
27. Olga Sorkine and Marc Alexa. 2007. As-rigid-as-possible Surface Modeling. In Proceedings of the Fifth Eurographics Symposium on Geometry Processing (SGP ’07). Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 109–116.
28. Jian Sun, Maks Ovsjanikov, and Leonidas Guibas. 2009. A Concise and Provably Informative Multi-Scale Signature Based on Heat Diffusion. Computer Graphics Forum 28, 5 (2009), 1383–1392. Cross Ref
