A Preconditioned Conjugate Gradient Method for Non-Selfadjoint or Indefinite Orthogonal Spline Collocation Problems
by
Bernard Bialecki
Department of Mathematical and Computer Sciences, Colorado School of Mines, Golden, Colorado 80401, U.S.A.
Coauthors: Rakhim Aitbayev, Department of Mathematical and Computer Sciences, Colorado School of Mines, Golden, Colorado 80401, U.S.A.

We consider, on the unit square, a boundary value problem with the zero Dirichlet boundary condition and a nonselfadjoint or an indefinite partial differential operator of the form

Lu= 2 å i, j  aij(x)uxixj+ 2 å i=1  bi(x) uxi+c(x)u.

The orthogonal spline collocation solution of this problem is a piecewise Hermite bicubic function that vanishes on the boundary of the square and satisfies the partial differential equation at the nodes of the composite two-point Gauss quadrature. We study the solution of the resulting linear system by the preconditioned conjugate gradient method applied to the system of normal equations. The preconditioner is the matrix arising from the orthogonal spline collocation discretization of the corresponding boundary value problem with a separable partial differential operator. Using H²-norm analysis of the orthogonal spline collocation, we show that the convergence rate of the proposed preconditioned conjugate gradient method is independent of the partition step size. We solve a linear system with the preconditioner using an efficient direct matrix decomposition algorithm that involves the use of FFTs. On a uniform N×N partition, the cost of the algorithm for computing the collocation solution within the tolerance \epsilon is O(N²lnN |ln\epsilon|). We present results of numerical tests and compare our algorithm to similar methods for solving finite difference and finite element problems.

Date received: January 11, 2001