Iterative Line Cubic Spline Collocation Methods for Elliptic Partial Differential Equations in Several Dimensions

This paper presents a new class of second- and fourth-order line cubic spline collocation methods (the LCSC methods) for multidimensional linear elliptic partial differential equations with no cross derivative terms. The LCSC methods approximate the differential operator along lines in each dimension independently and then combine the results into one large linear system. Expressed in terms of discretization stencils for the operator, these methods have nonzero entries only in the coordinate directions. The advantage of this approach is that the discretization is much simpler to derive and analyze. Further, iterative methods are easily applied to the resulting linear systems, especially on parallel computers. The disadvantage is that the resulting linear system is k times larger in k dimensions. Using the simplicity of the methods, iterative schemes are analyzed and formulated in order to solve the resulting LCSC linear systems in the case of Helmholtz problems. Block Jacobi, extrapolated Jacobi (EJ), and successive overrelaxation (SOR) iteration methods are analyzed with the rates of convergence and the optimum relaxation parameters determined. The simple structure of the linear system makes these methods particularly suitable for parallel computation. It is shown that the overall efficiency of the method is attractive in spite of involving such a large linear system. Experimental results presented here confirm the convergence results for both the discretization and iterative methods, and indicate that the convergence results hold for problems more general than Helmholtz problems.