Algebraic multigrid (AMG) is an optimal algorithm for solving large-scale sparse linear systems. However, its complexity makes it challenging to achieve ideal parallel scalability and identify parallel scalability bottlenecks. In this paper, we analyze the performance skeletons and communication patterns of the AMG algorithm to identify three categories of scalability bottlenecks. Additionally, we introduce the concept of the sparse matrix communication domain to characterize the influence of sparse patterns on parallel communication performance. We examine six typical examples with varying sparse pattern features in practical applications such as radiation fluid dynamics, structural mechanics, and aero-engines. Through our analysis, we identify and analyze multi-granularity parallel scalability bottlenecks and provide insights into future directions for improving AMG parallel performance.

In this paper, we study in detail the specific convergence property of the physical-variable-based coarsening two-level iterative method (PCTL) algorithm based on the theory of algebraic multigrid method (AMG), and give a reasonable upper bound on the convergence factor, which provides a theoretical guarantee for the PCTL algorithm. Moreover, we also analyze the algebraic features that affect the convergence of the PCTL algorithm, such as diagonal dominance and coupling strength, hoping to provide theoretical guidance for the applications and algorithm optimization of the PCTL algorithm.