ON THE ITERATIVE SOLUTION OF HERMITE COLLOCATION EQUATIONS

Collocation methods based on bicubic Hermite piecewise polynomials hav e been proven to be effective techniques for solving general second or der linear elliptic partial differential equations (PDEs) with mixed b oundary conditions [ACM Trans. Math. Software, 11 (1985), pp. 379-412] . The corresponding system of discrete collocation equations is genera lly nonsymmetric and nondiagonally dominant. Methods for their iterati ve solution are not known and are currently solved using Gauss elimina tion with scaling and partial pivoting. Point iterative methods like t hose in ITPACK [Tech. Report CNA-216, Center for Numerical Analysis, U niv. of Texas at Austin, April 1988] do not converge even for the coll ocation equations obtained from the discretization of model PDE proble ms. The development of efficient iterative solvers for these collocati on equations is necessary for the case of three-dimensional PDE proble ms and their parallel solution, since direct solvers tend to be space bound and their parallelization is difficult. In this paper block iter ative methods are developed and analysed for the collocation equations corresponding to elliptic PDEs defined on a rectangle and subject to uncoupled mixed boundary conditions. For these types of PDE problems c ertain boundary degrees of freedom of the collocation approximation ca n be predetermined symbolically [Houstis, Mitchell, and Rice]. The rem aining equations are called ''interior'' collocation equations. The sy stem of all discrete equations is referred to as ''general'' collocati on equations. Papatheodorou [Math. Comp., 41 (1983), pp. 511-525] was first to determine the exact parameters of accelerated overrelaxation (AOR)-type iterative methods for the case of ''interior'' collocation equations associated with a model problem. This paper generalizes the results of Papatheodorou for the ''interior'' collocation equations an d presents new results for a particular class of ''general'' collocati on equations. Specifically, in the case of a model elliptic PDE proble m with uncoupled mixed boundary conditions, analytic expressions are d erived for the eigenvalues of the block Jacobi iteration matrix based on a new partitioning of the interior collocation matrix, and the opti mal overrelaxation factors are determined for the block successive ove rrelaxation (SOR) iterative method. A number of numerical results are presented to verify the theoretical analysis of the block SOR method a nd to compare its convergence behavior with those of the block Jacobi, Gauss-Seidel and the optimal AOR of Papatheodorou. Furthermore, the a uthors compare the time and memory complexity of the block SOR, LINPAC K Band GE, and generalized minimal residual (GMRES) mathematical softw are for solving the Hermite collocation equations obtained from the di scretization of several PDE problems. The numerical results indicate t hat the block SOR is an efficient method for solving these equations.