Extensions to adaptive smooth aggregation (αSA) multigrid: Eigensolver initialization and nonsymmetric problems

2008 2008

Other formats: Order a copy

Abstract (summary)

Many applications of scientific computing require solutions to a system of linear equations Ax=b, where A is a large, real, sparse, nonsingular matrix with a positive real part. Such discrete linear problems are commonly utilized to obtain numerical solutions to steady-state, time-dependent, nonlinear, and optimization problems from Partial Differential Equations (PDE) and other models. For many applications, the computation within the algorithms that solve linear problems dominates the total simulation time and more efficient algorithms will dramatically enhance the usefulness of the simulation.

Multigrid methods are known to provide optimal solvers for a large class of these problems. The favorable convergence properties of these methods stem from combining two complementary error-reduction processes: a local relaxation process, and a coarse-grid correction. It is expected that the relaxation process efficiently attenuates most of the error components. The remaining error is referred to as algebraically smooth error with respect to the given relaxation. The aim is then to construct coarser spaces with much smaller dimension and sparse bases to accurately represent the algebraically smooth error. As a result, an adequate two-grid method is obtained. Recursive application of relaxation and coarse-grid correction results in an efficient multigrid method, provided the sparsity of coarser problems is controlled. Choosing a relaxation with good smoothing properties and constructing coarse subspaces with adequate approximation properties (and the associated multigrid intergrid transfer operators) are the general goals when designing a multigrid method.

Instead of making assumptions regarding the geometric smoothness of algebraically smooth error, the coarsening techniques considered in this thesis focus on constructing coarse spaces within the smoothed aggregation (SA) framework, where interpolation operators are chosen to accurately approximate a certain set of algebraically smooth prototypes. Previously, adaptive smoothed aggregation (αSA) was applied to symmetric applications where a representative set algebraically smooth error vectors is neither obvious nor supplied. In this thesis we present two extensions to the αSA framework: efficient eigensolvers used to develop algebraically smooth error components for SPD problems and design of αSA-based solvers for nonsymmetric problems.

We claim that approximate solutions to certain eigenproblems are obtained with O(n) setup cost have representation of algebraically smooth error that is adequate enough to build an optimal SA solver. Such eigenproblems are available for use within the αSA framework for problems that demand such enhancement. We then discuss the design of a generalized eigensolver based on smoothed aggregation (GES-SA), a sparse iterative eigensolver that uses the same data structures used as the SA framework. We report numerical results for simple problems to assert that GES-SA is one efficient way to build optimal SA multigrid hierarchy.

Additionally, we design a nonsymmetric SA framework, based on the singular value decomposition of A, that reduces to the original SA framework for SPD problems. Within this framework, we provide a nonsymmetric version of the strong approximation property, which is commonly employed for convergence analysis for SPD matrices Preliminary two-level convergence analysis is presented, suggesting more relaxation should be applied at each level within a multigrid solver for highly nonsymmetric problems. Several features new to the SA framework are explored and developed in the design of a nonsymmetric version of αSA, which are also presented. We report numerical results that show our framework successfully creates optimal SA solvers for certain nonsymmetric problems.

Indexing (details)

0346: Mechanics
Identifier / keyword
Applied sciences; Algebraic; Eigensolvers; Multigrids; Nonsymmetric; Smoothed aggregation
Extensions to adaptive smooth aggregation (αSA) multigrid: Eigensolver initialization and nonsymmetric problems
Sanders, Geoffrey D.
Number of pages
Publication year
Degree date
School code
DAI-B 69/12, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
Manteuffel, Tom A.
Committee member
Brezina, Marian; Cai, Xiao-Chuan; McCormick, Steve F.; Ruge, John W.
University of Colorado at Boulder
Applied Mathematics
University location
United States -- Colorado
Source type
Dissertations & Theses
Document type
Dissertation/thesis number
ProQuest document ID
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.