Summary: Two different algorithms are applied to a model of brittle damage including the gradient of the damage variable. Both algorithms are based on a modified Newton method. In the first algorithm the Newton method is applied directly to the whole system of equations, while in the second algorithm, the equilibrium equations and the damage evolution problem are solved uncoupled from each other in a Gauss-Seidel scheme. The algorithms are applied to two different formulations of the problem. In the first formulation the thermodynamic force, work conjugate to the damage variable is kept as an auxiliary variable, while in the second formulation this variable is eliminated. It turns out that the formulation using the extra variable is more robust in the sense that the algorithms converge even for very large load increments. On the other hand, the formulation where the extra variable is eliminated is more efficient for small time steps since a smaller system of equations is solved for each increment. Furthermore, it is found that the direct approach is more efficient than the decoupled approach for this problem.