Adaptive Multigrid

This page documents developments on the design and implementation of an adaptive multigrid solver that allows for the efficient solution of Poisson-like systems of equations, discretized over an quad/oct-tree.
This material is based upon work supported by the National Science Foundation under Grant No. 1422325:

Goals and Challenges

In numerous fields, ranging from image processing to scientific simulation, solving a large Poisson system is an essential step in integrating locally defined properties into a consistent global solution. Though the linear system is global (with properties at one point in space affecting the solution at points far away), in many cases the details of the solution are only required at particular locations. As a result, computational effort expended on estimating the details of the solution away from these regions of interest is wasted. The proposed research seeks to design, implement, and make publicly available a new solver for addressing this problem - providing a way to adapt traditional hierarchical solvers so that computation is only focused where it is needed.

The motivation for this approach stems from the fact that in solving a Poisson equation, long-distance effects are dominated by lower frequencies, so high-resolution components of the solution need only be computed in regions of interest. Using experiences from prior work in surface reconstruction and large image processing, the PI will explore a modification of traditional multigrid, providing a hierarchical solver even when the function spaces do not nest. To do this the multigrid solver will be modified in two ways. First, to compensate for the fact that the coarser solution cannot be up-sampled to the finer resolutions, the solution of the linear system will be represented as a linear combination of functions at all levels of the hierarchy, not just the finest one. Second, instead of using traditional restriction and prolongation operators to transition between successive levels of the hierarchy, the solver will proceed by iterating through the levels of the hierarchy (fine-to-coarse and then coarse-to-fine as in a typical V- or W-cycle), relaxing the system within each level, and adjusting the constraints at the other levels, accounting for the components of the solution that have already been met. (For example, in the prolongation phase, the coarser solution will be incorporated into the finer levels by adjusting the right-hand-side, rather than updating the current estimate of the solution.) The research will explore both the general design of such a system, as well as domain-specific implementations that facilitate its integration in targeted scientific and entertainment disciplines. Results will be made publicly available in the form C/C++ source code for constructing adapted quadtrees/octrees, formulating the system constraints, and evaluating the computed solution, as well as documentation and application-specific implementations.

Direct Results

Initial research will focus on extending the cascadic solver used in Poisson Surface Reconstruction. This includes:

Indirect Results

In addition to applications in surface reconstruction, we have also begun exploring the use of hierarchical solvers within the broader domain of geometry processing. This has lead to important new results in solving the optical-flow problem over surfaces. This was an important step of the processing that allowed for the computation of motion graphs for unstructued texture meshes.
Contact Info
Michael Kazhdan
Department of Computer Science
Johns Hopkins University
229 Malone Hall
3400 North Charles St.
Baltimore, MD 21218
Fax: (410) 516-6134

Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation
Last updated 08/23/2016