Algebraic multigrid (AMG) techniques offer optimal performance as solvers or preconditioners for many of the large-scale linear systems that arise in modern applications. Many of these applications, however, exhibit strongly heterogeneous characteristics that preclude analysis using classical techniques such as Fourier analysis. In this talk, we introduce AMG and discuss the challenges of deriving good theoretical bounds on its performance. In particular, we consider challenges in making practical choices in the algorithmic components based on theoretical analysis.
Theoretical bounds on AMG performance come with many different conditions and assumptions, reflecting AMG's many variants and options. For the practitioner, however, it is desirable to have a simple sharp bound that accurately reflects the choices made in constructing the AMG grid and operator hierarchies. The questions of sharpness and computability of existing bounds on AMG convergence are, thus, considered. The role in which recent advances in adaptive AMG and compatible relaxation can play in these bounds is also discussed. Despite these and other advances, the challenge of deriving useful bounds for complex applications subject to limitations of computer architectures remains distant; our viewpoint suggests possibilities for research to achieve this goal.