Algebraic construction of edge matrices with application to AMG

Priv.-Doz. Dr. Johannes Kraus

Dec. 6, 2004, 12:30 p.m. HF 136

In the first part of this talk we consider the problem of splitting a symmetric positive definite (SPD) stiffness matrix A arising from finite element discretization into a sum of edge matrices thereby assuming that A is given as a sum of symmetric positive semidefinite (SPSD) element matrices. We give necessary and sufficient conditions for the existence of a decomposition into SPSD edge matrices and provide a feasible algorithm for the computation of edge matrices in case of general SPSD element matrices. In the second part of the talk, we focus on a new approach in algebraic multigrid (AMG): Based on the knowledge of edge matrices, we discuss how to alter the concept of 'strong' and 'weak' connections, as it is used for coarse-grid selection in classical AMG. We further derive interpolation from a local energy minimization rule: the 'computational molecules' involved in this process are assembled from edge matrices. Numerical tests show the robustness of the new method, which we refer to as AMGm (Algebraic MultiGrid based on computational molecules).

This is a joint talk by Josef Schicho and Johannes Kraus.