In this paper we describe an aggregation-based algebraic multigrid method for the solution of discrete k-form Laplacians. Our work generalizes Reitzinger and Schoberl's algorithm to higher dimensional discrete forms. We provide conditions on the tentative prolongators under which the commutativity of the coarse and fine de Rham complexes is maintained. Further, a practical algorithm that satisfies these conditions is outlined and smoothed prolongation operators and the associated finite element spaces are highlighted. Numerical evidence of the efficiency and generality of the proposed method is presented in the context of discrete Hodge decompositions.

In this paper, we present a multigrid technique for efficiently deforming large surface and volume meshes. We show that a previous least-squares formulation for distortion minimization reduces to a Laplacian system on a general graph structure for which we derive an analytic expression. We then describe an efficient multigrid algorithm for solving the relevant equations. Here we develop novel prolongation and restriction operators used in the multigrid cycles. Combined with a simple but effective graph coarsening strategy, our multigrid algorithm outperforms other direct and multigrid solvers in both time and memory cost. While direct factorization methods have frequently been applied to related problems, it is demonstrated that even for modestly sized meshes, our multigrid solver surpasses the most sophisticated factorization codes. Moreover, since our multigrid solver does not rely on extensive precomputation, it is particularly well suited for integration with a general mesh editing environment where unpredictable combinations of different operations will invalidate the results of any such precomputation. Experimental evidence of these advantages is provided on a number of meshes with a wide range of size.

Granular materials, such as sand and grains, are ubiquitous. Simulating the 3D dynamic motion of such materials represents a challenging problem in graphics because of their unique physical properties. In this paper we present a simple and effective method for granular material simulation. By incorporating techniques from physical models, our approach describes granular phenomena more faithfully than previous methods. Granular material is represented by a large collection of non-spherical particles which may be in persistent contact. The particles represent discrete elements of the simulated material. One major advantage of using discrete elements is that the topology of particle interaction can evolve freely. As a result, highly dynamic phenomena, such as splashing and avalanches, can be conveniently generated by this meshless approach without sacrificing physical accuracy. We generalize this discrete model to rigid bodies by distributing particles over their surfaces. In this way, two-way coupling between granular materials and rigid bodies is achieved.

We describe a method for coarsening chain complexes arising from discrete differential forms. The coarse complexes are shown to retain essential properties of the original complex while being smaller in size. A hierarchy of coarse complexes provides piecewise-constant interpolation operators which can be used in a Smoothed Aggregation multigrid method for efficient solution of discrete Laplacians.