Date of Award

Spring 1-1-2011

Document Type


Degree Name

Master of Science (MS)


Applied Mathematics

First Advisor

Marian Brezina

Second Advisor

Thomas Manteuffel

Third Advisor

Stephen McCormick


The application of multilevel methods to solving large algebraic systems obtained by discretization of PDEs has seen great success. However, these methods often perform sub-optimally when treating problems with anisotropies. For problems posed over unstructured meshes, optimal automatic multigrid coarsening is not a fully solved problem for the smoothed aggregation multigrid.

The focus of this thesis is on enhancing robustness of the coarsening in the Smoothed Aggregation (SA) multigrid. We focus on improving the standard detection of coupling, on which the coarsening decisions in SA are based. Our approach takes the form of a two-pass test which allows for a more robust local control over the coupling detection, as well as added exibility permitting utilization of new coupling detection measures in a more systematic way.

For isotropic problems, smoothed aggregation coarsening is known to offer very favorable operator complexity, but achieving similar behavior in the presence of anisotropy is more challenging. Special attention is paid to addressing the issue of controlling the complexity of the method. We discuss several existing approaches to curbing coarse-level operator fill-in, and offer generalizations and improvements.

Numerical experiments are provided to demonstrate the performance of the improved coarsening on model examples of anisotropic problems featuring both cases where anisotropies are aligned with the grid, as well as cases where they are not.