MULTILEVEL GRADIENT UZAWA ALGORITHMS FOR SYMMETRIC SADDLE POINT PROBLEMS

Abstract. In this paper, we introduce a general multilevel gradient Uzawa algorithm for symmetric saddle point systems. We compare its performance with the performance of the standard Uzawa multilevel al-gorithm. The main idea of the approach is to combine a double inexact Uzawa algorithm at the continuous level with a gradient type algorithm at the discrete level. The algorithm is based on the existence of a priori multilevel sequences of nested approximation pairs of spaces, but the family does not have to be stable. To ensure convergence, the process has to maintain an accurate representation of the residuals at each step of the inexact Uzawa algorithm at the continuous level. The residual representations at each step are approximated by projections or repre-sentation operators. Sufficient conditions for ending the iteration on a current pair of discrete spaces are determined by computing simple in-dicators that involve consecutive iterations. When compared with the standard Uzawa multilevel algorithm, our proposed algorithm has the advantages of automatically selecting the relaxation parameter, lowering the number of iterations on each level, and improving on running time. By carefully choosing the discrete spaces and the projection operators, the error for the second component of the solution can be significantly improved even when comparison is made with the discretization on stan-dard families of stable pairs. 1