The ADI method was introduced by Peaceman and Rachford [6] in 1955, to solve the discretized boundary value problems for elliptic and parabolic PDEs. The finite difference discretization of the model elliptic problem $$ (1) -Delta u = f, Omega = [0, 1] imes [0, 1] $$ $$ u = 0 on delta Omega $$ with 5-point centered finite difference discretization, with n +2 mesh-points in the x - direction and m + 2 points in the y direction, leads to the solution of a linear system of equations of the form $$ (2) Au = b $$ where A is a matrix of dimension $N = n imes m$. Without loss of generality and for the sake of simplicity, we will assume for the remainder of this paper that m = n, so that $N = n^2$.