Matrix multilevel methods and preconditioning

The Matrix Multilevel approach is based on a purely matrix dependent description of multigrid methods. The formulation of multilevel methods as singular matrix extensions via generating systems leads to the description of the method as a preconditioned iterative scheme, and illuminates the significance of the used prolongation and restriction operator for the related preconditioner. We define the matrix dependent black box restriction C by shifting the original matrix A in the form B = αI - A and picking out every second column to C = B(: 2: 2: n). Here, α has to be chosen as a rough upper estimate of the largest eigenvalue of A. By this mapping the related preconditioner enlarges the small eigenvalues while the maximum eigenvalue remains nearly unchanged. Although we derive our method in an additive setting, we can also use the new prolongations/restrictions in multiplicative algorithms. Our test results are very promising: We give various numerical examples where multigrid with standard prolongation/restriction deteriorates whereas the new method shows optimal behaviour. We also notice that in many cases using B = abs(A) instead of B = αI - A gives equally good results. We mainly consider symmetric positive definite matrices in one and two dimensions, but the results can be generalized to higher dimensional problems.