We present two efficient numerical methods for susceptibility artifact correction in Echo Planar Imaging (EPI), an ultra fast Magnetic Resonance Imaging (MRI) technique widely used in clinical applications. Our methods address a major practical drawback of EPI, the so-called susceptibility artifacts, which consist of geometrical transformations and intensity modulations. We employ a physical distortion model and the fact that transformations are limited along a known direction that can be controlled by the experimenter. We consider a tailored variational image registration problem aiming at minimizing the distance of two oppositely distorted images. Regularization and constraints are added to the formulation to ensure a smooth and invertible transformation. We follow a discretize- then-optimize approach and present a face-staggered discretization yielding a separable structure in the discretized misfit function and the invertibility constraints. The presence of the smoothness regularizer renders the overall optimization problem non-separable, but we present two optimization schemes that exploit the partial separability. Firstly, we derive a block-Jacobi preconditioner to be used in a Gauss-Newton-PCG method. Secondly, we consider a splitting of the separable and non- separable part and solve the resulting problem using the Alternating Direction Method Of Multipliers (ADMM). Both schemes are of essentially linear complexity and can exploit parallel computing. We test and compare the proposed methods using 2D and 3D real-life data. Our prototype implementation can solve 3D problems with around 2 million degrees of freedom in around 30 seconds on a standard laptop, which corresponds to a 2x speedup factor as compared to established methods.