Publications 2010-
Abstract:
We present a numerical method for the variable coefficient Poisson equation in three dimensional irregular domains and with interfacial discontinuities. The discretization embeds the domain and interface into a uniform Cartesian grid augmented with virtual degrees of freedom to provide accurate treatment of jump and boundary conditions. The matrix associated with the discretization is symmetric positive definite and equal to the standard 7-point finite divergence stencil away from embedded interfaces and boundaries. Numerical evidence suggests second order accuracy in the L1-norm. Our approach improves the treatment of Dirichlet and jump constraints in the recent work of Bedrossian et al. and provides novel aspects necessary for problems in three dimensions. Specifically, we construct new constraint-based Lagrange multiplier spaces that significantly improve the conditioning of the associated linear system of equations; we provide a method for sub-cell polyhedral approximation to the zero isocontour surface of a level set needed for three dimensional embedding; and we show that the new Lagrange multiplier spaces naturally lead to a class of easy-to-implement multigrid methods that achieve near-optimal efficiency, as shown by numerical examples. For the specific case of a continuous Poisson coefficient in interface problems, we provide an expansive treatment of the construction of a particular solution that satisfies the value jump and flux jump constraints. As in Bedrossian et al., this is used in a discontinuity removal technique that yields the standard 7-point Poisson stencil across the interface and only requires a modification to the right-hand side of the linear system.
Abstract:
We present a highly efficient numerical solver for the Poisson equation on irregular voxelized domains supporting an arbitrary mix of Neumann and Dirichlet boundary conditions. Our approach employs a multigrid cycle as a preconditioner for the conjugate gradient method, which enables the use of a lightweight, purely geometric multigrid scheme while drastically improving convergence and robustness on irregular domains. Our method is designed for parallel execution on shared-memory platforms and poses modest requirements in terms of bandwidth and memory footprint. Our solver will accommodate as many as 768X1152 voxels with a memory footprint less than 16GB, while a full smoke simulation at this resolution fits in 32GB of RAM. Our preconditioned conjugate gradient solver typically reduces the residual by one order of magnitude every 2 iterations, while each PCG iteration requires approximately 6.1 sec on a 16-core SMP at 768^3 resolution. We demonstrate the efficacy of our method on animations of smoke flow past solid objects and free surface water animations using Poisson pressure projection at unprecedented resolutions.
Abstract:
We present a method for simulating quasistatic crack propagation in 2-D which combines the extended finite element method (XFEM) with a general algorithm for cutting triangulated domains, and introduce a simple yet general and flexible quadrature rule based on the same geometric algorithm. The combination of these methods gives several advantages. First, the cutting algorithm provides a flexible and systematic way of determining material connectivity, which is required by the XFEM enrichment functions. Also, our integration scheme is straightfoward to implement and accurate, without requiring a triangulation that incorporates the new crack edges or the addition of new degrees of freedom to the system.
Abstract:
We present a second order accurate, geometrically flexible and easy to implement method for solving the variable coefficient Poisson equation with interfacial discontinuities on an irregular domain. We discretize the equations using an embedded approach on a uniform Cartesian grid employing virtual nodes at interfaces and boundaries. A variational method is used to define numerical stencils near these special virtual nodes and a Lagrange multiplier approach is used to enforce jump conditions and Dirichlet boundary conditions. Our combination of these two aspects yields a symmetric positive definite discretization. In the general case, we obtain the standard 5-point stencil away from the interface. For the specific case of interface problems with continuous coefficients, we present a discontinuity removal technique that admits use of the standard 5-point finite difference stencil everywhere in the domain. Numerical experiments indicate second order accuracy in Linf.
Abstract:
We present a multigrid framework for the simulation of high resolution elastic deformable models, designed to facilitate scalability on shared memory multiprocessors. We incorporate several state-of-the-art techniques from multigrid theory, while adapting them to the specific requirements of graph- ics and animation applications, such as the ability to handle elaborate geometry and complex boundary conditions. Our method supports simulation of linear elasticity and co-rotational linear elasticity. The efficiency of our solver is practically independent of material parameters, even for near- incompressible materials. We achieve simulation rates as high as 6 frames per second for test models with 256K vertices on an 8-core SMP, and 1.6 frames per second for a 2M vertex object on a 16-core SMP.
Abstract:
Micro-organisms often navigate through complex environments such as biofilms and mucosal tissues and tracts. To understand the effect of a complex media upon micro-organismal locomotion, we investigate numerically the effect of fluid viscoelasticity on the dynamics of a undulating swimming sheet. First, we recover recent small-amplitude results for bi-infinite sheets that suggests that viscoelasticity impedes locomotion. We find the opposite result when simulating free swimmers with large tail undulations, with both velocity and mechanical efficiency peaking for Deborah numbers near one. We associate this with regions of highly stressed fluid aft of the undulating tail.