Globally Convergent Multigrid Methods for Porous Medium Type Equations

. We consider the fast solution of large, piecewise smooth minimization problems as typically arising from the nite element discretization of porous media ow. For lack of smoothness, usual Newton multigrid methods cannot be applied. We propose a new approach based on a combination of convex minization with constrained Newton linearization. No regularization is involved. We show global convergence of the resulting monotone multigrid methods and give logarithmic upper bounds for the asymptotic convergence rates. EÆciency and robustness is illustrated by numerical experiments. 1. Introduction Let be a polyhedral domain in the Euclidean space R d . We consider the minimization problem u 2 H : J (u) + (u) J (v) + (v) 8v 2 H (1.1) on a closed subspace H H 1( 2 For simplicity, we concentrate on H = H 1 0 and d = 2. Other boundary conditions of Neumann or mixed type and the case of three space dimensions can be treated in a similar way [6, 7]. The quadratic functional J , J (..