Finite Difference Preconditioning for Solving Orthogonal Collocation Equations for Boundary Value Problems.
A technique to construct a low-order finite difference preconditioner for solving orthogonal collocation equations for boundary value problems is presented.  It is shown numerically and theoretically that the spectral condition numbers of the preconditioned collocation matrices are bounded by constants independent of the number of mesh nodes when certain exact low-order finite difference preconditionings are used. Preconditioners based on incomplete LU factorization are also discussed. Numerical experiments show the efficiency and robustness of the preconditioning.
Introduction
. In this paper, we shall consider orthogonal collocation methods
for solving elliptic differential equations. These methods have been extensively
investigated in the last twenty years due to their ease of implementationand high-order
accuracy (see [RS72], [DS73] and [PR76]). An apparent disadvantage of orthogonal
collocation lies in the fact that a collocation matrix is generally nonsymmetric, even
for a Poisson equation with a uniform mesh. Gauss elimination often has been used
for solving the collocation equations, and its cost has restricted the applicability of
the methods.
In recent years, some efforts in solving the collocation equations by alternative
methods have been made. A so-called alternating direction collocation (ADC) or
generalized ADI method was introduced by Hayes [Hay80] and Hayes, Pinder and
Celia [HPC81] for solving a parabolic problem. A full theory for convergence of
ADC on a uniform mesh is given for the model problem in a rectangular
domain by Dyksen [Dyk87]. Significantly, a closed form for the eigenvalues and their
associated eigenfunctions is also given. Cooper and Prenter [CP91] give a complete
theory for convergence of ADC applied to a large class of linear separable elliptic
partial differential equations on a rectangular domain. Bialecki [Bia91] considers
the problem of determining optimal acceleration parameters for ADC by using the
Jordan acceleration technique. Besides ADC, a fast direct methods (FFT) has been
developed for solving on a uniform mesh in [SZ89] and [BFB92]. In [Sun(a)],
a class of block stationary (standard) methods are applied to second-order separable
elliptic partial differential equations and their convergence is proven. However, all of
above methods are only applicable for linear separable and self-adjoint elliptic partial
differential equations.
It has been well demonstrated that when solving partial differential equations
(PDEs) a significant improvement in convergence of conventional iterative methods
y This work is supported in part by the Natural Science and Engineering Research Council of
Canada (NSERC) Grant A8781.
z Department of Mathematics & Statistics, Simon Fraser University Burnaby, B. C. V5A 1S6,
Canada (wsun@cs.sfu.ca).
x Department of Mathematics & Statistics, Simon Fraser University Burnaby, B. C. V5A 1S6,
Canada. Current address: Department of Mathematics, University of Kansas, Lawrence, KS 66045,
U.S.A. (whuang@math.ukans.edu).
- Department of Mathematics & Statistics, Simon Fraser University Burnaby, B. C. V5A 1S6,
Canada (rdr@cs.sfu.ca).
W. SUN, W. HUANG AND R.D. RUSSELL
can be gained by using preconditioning techniques. They have been investigated extensively
for finite difference, finite element and spectral methods, e.g., see [Ors80],
[Eva83], [Won87] [CE88], and [CHQZ88]. For spectral methods, a low-order finite
difference approximation or its incomplete-LU factorization can often be proven to be
an efficient preconditioning [Ors80]. Recently, for finite element and finite difference
methods, some theoretical analysis applicable for a large class of elliptic partial differential
equations has been carried out in [MP90] and [JMPW92]. However, to our
knowledge preconditioning has not been applied in the orthogonal collocation con-
text. The objective of this paper is to present a technique to construct such a finite
difference preconditioning. A major difficulty lies in the fact that the unknowns in
the Hermite collocation approximation involve both the variable u and its derivatives,
while those in the standard finite difference approximation contain only the variable
u.
An outline of the paper is as follows. In Section 2, we introduce some notation
and give a brief description of the orthogonal Hermite cubic collocation method. In
Section 3, a technique to construct a finite difference preconditioning is presented for
one and two dimensional model problems. Several versions of the preconditioning are
discussed. In Section 4, we show that for the model problems with periodic boundary
conditions and uniform mesh, the condition number of a preconditioned system is
bounded by a constant independent of the number of mesh nodes. Numerical results
supporting this theory and showing the efficacy of the preconditioning methods are
presented in Section 5. Section 6 contains conclusions and additional comments.
2. Orthogonal Collocation Methods. Consider the problem
with the Dirichlet boundary conditions or the periodic boundary
conditions Given a partition \Pi
i=0 on [0,1]
such that
the Hermite cubic collocation approximation v is defined as follows:
on each element [x
and
denote approximations to u(x i ) and u 0 respectively, and  1 are
the so-called shape functions for one dimensional Hermite cubic interpolation defined
by
Denoting the collocation points by \Pi COL := fx
x
x
x
x
PRECONDITIONING FOR COLLOCATION SYSTEMS 3
with oe := 1
Gaussian points on (0,1)), the orthogonal Hermite
cubic collocation approximation v(x) of (2.1) is defined by the collocation equations
2i+l
and boundary conditions v(x 0 This can be rewritten in the matrix
where
The matrices AC and BC can be regarded as collocation approximations to the second
derivative and identity operators, respectively, and are neither symmetric nor diagonally
dominant. This is why that although some iterative and fast-FFT-like methods
have been developed recently for solving many PDE systems, Gauss elimination has
predominated in the general collocation matrix context.
3. Finite Difference Preconditioning. In this section, we present a technique
to construct a finite difference preconditioning for the orthogonal collocation system.
For simplicity, the technique is illustrated for orthogonal Hermite cubic collocation
applied to Dirichlet and periodic problems for one and two dimensional Poisson equa-
tions. However, as will be evident, the technique may be applied for more general
collocation methods and boundary value problems.
3.1 One-dimensional case. We consider the one dimensional Dirichlet model
problem (2.1) but ignore the zeroth-order term here. The collocation approximation
contains and we consider a finite difference approximation
which involves the same number of unknowns. A natural way to construct
such an approximation is to use centred differences based on the collocation points
fx
1g. That is, use
x
x
supplemented with the boundary conditions w denotes the
finite difference approximation of u(x
In matrix form this is
where f is defined by (2.6) and
Since w and v approximate different quantities, AF cannot be expected to be a suitable
preconditioner for ACOL . However, a relation between these two sets of unknowns is
easily found using (2.2), viz., we have
4 W. SUN, W. HUANG AND R.D. RUSSELL
Both v(x
are approximations to u(x
replaced by w j we
obtain
Substituting (3.5) into (2.5) with
Now, (3.6) has the same unknowns as (3.2), which motivates using AF as our preconditioner
C . The periodic problem can be considered similarly.
The accuracy of this preconditioner has been examined for several examples.
Throughout, the numerical experiments are performed on a Sun SPARC+1 in double
precision, using standard IMSL routines for solving the linear systems and eigenvalue
problems.
In

Table

1, the condition numbers of ACOL and T 1
boundary conditions with boundary conditions with are
listed. The condition number used here is defined as
and the meshes are the following:
ffl 1D-Mesh 2: x
ffl 1D-Mesh 3: x
ffl 1D-Mesh 4: a uniform mesh consisting of N \Gamma 3 nodes, with four additional
local uniform nodes close to Figure 1). The ratio of these two
spacings is denoted by fi.
The two quantities
the so-called local mesh ratio and global mesh ratio, are used to measure the smoothness
of a given mesh. In Figures 2-3, we plot the distributions of eigenvalues of ACOL
and T 1 for 1D-Meshes 1 and 3 and
conditions. Several observations can be made.
Many of the eigenvalues of ACOL are complex. ACOL is indefinite, as its eigen-values
have both positive and negative real parts. This illustrates why conventional
iterative methods, such as Jacobi, Gauss-Seidel and SOR, are divergent when they
are applied to the collocation equations (2.5). The condition number of ACOL is quite
sensitive to the smoothness of the mesh used.
Since both ACOLB \Gamma1
C and AF are symmetric for 1D-Mesh 1 [Bia91], the eigen-values
of T 1 are real and positive. In the case of Dirichlet boundary conditions, the
condition numbers of T 1 are less sensitive than ACOL to the smoothness of the mesh.
For a smooth or a moderately non-smooth mesh (h
1 is not large and the spacing
does not have a steep change, such as 1D-Meshes 1, 2, 3 and 4 with
is small. Even for a fairly nonsmooth mesh (such as 1D-Mesh 4 with
1000, whose spacing has a steep jump near much smaller than
meshes, the norms of the eigenvalues of the preconditioned matrix

Table
Condition numbers of the collocation and preconditioned matrices for the 1-D model problem.
uniform
are bounded below by one and above by a constant which is independent of N . For
example, the upper bound is about 3.17 for 1D-Mesh 1, 3.16 for 1D-Mesh 2 and 3.86
for 1D-Mesh 3 with Dirichlet boundary conditions. A similar observation can be made
for the periodic boundary value problem except for Mesh 2 and Mesh 3 which are not
suitable to this case.
Thus AF is a good preconditioner for ACOLB \Gamma1
C . The preconditioned matrix has
a desirable distribution of eigenvalues for smooth and moderately non-smooth meshes.
Some of these numerical observations will be confirmed theoretically in Section 4. In
Section 5 it is demonstrated that fast convergence can be gained when a conventional
iterative method, such as Richardson and conjugate gradient iteration, is applied to
the preconditioned system.
3.2 Two dimensional case. Now we illustrate the preconditioning technique
for the more interesting case of a two dimensional Helmholtz equation
with Dirichlet or periodic boundary conditions on
1). Four
meshes are used,
On \Pi COL \Theta \Pi COL , the orthogonal Hermite bicubic collocation and five-point centred
finite difference approximations to (3.8) are obtained in the same way as in the one
dimensional case. They are also denoted (using the natural ordering) by ACOL
and AF relation between the collocation and finite difference approximations
can be obtained and expressed by
(BC\Omega
where BC is defined in (3.4)
and\Omega denotes the Kronecker tensor product. Using AF
as a preconditioner, the resulting preconditioned collocation system is
6 W. SUN, W. HUANG AND R.D. RUSSELL

Table
Condition numbers of the collocation and preconditioned matrices for the 2-D model problems.
uniform 8 0.583E3 3.128 0.399E3 2.196 1.0 1.0
where
F
ACOL
The condition numbers of ACOL and T 2 are shown in Table 2 for both Dirichlet
boundary conditions with boundary conditions with ff = 1. These
results confirm the observations made in the one dimensional case. It is interesting to
notice that for Mesh 4 the condition number again increases linearly with the measure
fi of its smoothness for both Dirichlet and periodic boundary conditions.
3.3 Incomplete-LU factorization preconditioning. For one dimensional
problems, finite difference preconditioning is a quite inexpensive part of the iterative
scheme. In higher dimensions, however, inversion of these finite difference matrices
can become relatively expensive and/or complicated. Obviously, this disadvantage is
overcome by using a multigrid method or an incomplete LU factorization technique.
Here, for simplicity we restrict our attention to the latter and the approach for a
Dirichlet problem.
If a five-point finite difference approximation to a two dimensional second-order
elliptic differential equations is given by
then a five-diagonal incomplete-LU factorization can be expressed by
where
(see [CHQZ88] and [Won87]). The choice gives the standard incomplete-LU
factorization HLU5 (ILU) and the row-sum-equivalence version HRS5
(MILU [CE88]). Using these preconditionings for the AF factor, we have the two new
preconditioned matrices T 3
RS5 ACOL
(BC\Omega
Note that the LU factorizations of BC and
BC\Omega are inexpensive because
of their sparse and banded structure.

Table

3 summarizes how the extreme eigenvalues of T 3 and T 4 depend on N and
the smoothness of the mesh. There are some differences from using an exact factorization
of the original finite difference matrix. Roughly speaking, the incomplete-LU case
is somewhat better for the high frequency components and the row-sum-equivalence
alternative is more accurate for the low frequency components, as can be seen from

Table

3. In fact, the minimal eigenvalue of T 3 is nearly one, which implies that HRS5
and ACOL
low frequency components. On the other hand,
the maximal eigenvalue of T 4 is bounded above by a constant independent of N , and
HLU5 and ACOL
components. Unlike the
exact finite difference preconditioning, the condition numbers of both T 3 and T 4 can
increase slowly with N . Since convergence rates for most conventional iterative methods
are strongly related to the condition number, the row-sum-equivalence version on
this basis appears to be more suitable as a preconditioning. Other important indicators
for the convergence of iterative methods are ratios of real parts and imaginary
parts of eigenvalues, which are listed in the table. It is obvious that the maximal ratio
is strongly dependent upon the smoothness of meshes.
A more accurate factorization can be achieved by including one extra nonzero
diagonal in each of L and U . The seven-diagonal LU factorization is given by
where the coefficients can be calculated from
~
~
Now gives the HLU7 version and the HRS7 version. Table 4 shows the
extreme eigenvalues of T 5 := HRS7ACOL
Results are consistent with the observation concerning T 3 and T 4 , but the condition
numbers are smaller.
4. Condition Number Estimates. The numerical results in the previous sections
illustrate that the eigenvalues of the preconditioned collocation systems are
bounded below by 1 and above by a constant which is independent of the number
of mesh points, except in the case of Mesh 2 and Mesh 3 with periodic boundary
conditions. Here, we shall present a theoretical analysis of the preconditioned system.
The discussion is restricted to the simple model problem (2.1) with periodic boundary
conditions and a uniform collocation mesh (Mesh 1).
8 W. SUN, W. HUANG AND R.D. RUSSELL

Table
Extreme eigenvalues of the HRS5 and HLU5 preconditioned matrices for the two dimensional
Laplacian operator with Dirichlet boundary conditions and

Table
Extreme eigenvalues of the HRS7 and HLU7 preconditioned matrices for the two dimensional
Laplacian operator with Dirichlet boundary conditions and
For a uniform collocation mesh fx i g 2N
i=0 a corresponding finite difference approximation
for (2.1) with periodic boundary conditions is produced on the mesh fx
defined in (2.3). Arranging the variables and equations to correspond to the node ordering
fx
4N+1 g and using the periodic boundary conditions
u(x
1 ), the global finite difference matrix is given by
\GammaC
where I is the 2N \Theta 2N identity matrix,
a cC C C A
is a circulant matrix,
a =h 2
PRECONDITIONING FOR COLLOCATION SYSTEMS 9
and h is the collocation mesh stepsize. The corresponding Hermite cubic collocation
system is given by
or
where
u. The objective of this section is to establish bounds on condition
numbers of the matrix
Our approach is an algebraic one.
4.1 Eigensystem of collocation matrix. The eigenvalues and eigenvectors
for the finite difference matrix are well-known, and the corresponding eigensystem for
the Hermite collocation matrix has been analyzed by Dyksen [Dyk87]. He considers
the generalized eigenvalue problem \Gamma
and the corresponding matrix eigenvalue
problem
with Dirichlet boundary conditions and gives an analytic expression of the eigenvalues.
The problem with periodic boundary conditions also has been analyzed in [Sun(b)],
and these results can be summarized as follows:
Lemma 4.1. Let (AC ; BC ) denote a Hermite cubic collocation discretization for (2.1)
with periodic boundary conditions. The eigenvalue problem ACB \Gamma1
has a complete set of eigenvectors for which the eigenvalues are nonnegative and given
by
and
where
and
collocation points; The corresponding eigen-vectors
are given by
sink
sink
e
\Gammae
and v \GammaN =2
e
where
z l =h
I 2N and d l is a constant.
It is not difficult to obtain from Lemma 4.1 that
l h 2
and 12
\Gammal
The following Lemma is a result of the fact ACB \Gamma1
C is symmetric when Gaussian
points are chosen as the collocation points [Ben91].
Lemma 4.2. The eigenvectors fv l g \Sigma(2N \Gamma1)
l=\Sigma0 defined in (4.10)-(4.12) form an orthogonal
set under the inner product
I
Close scrutiny reveals a natural bound for the ratios of eigenvalues of ACB \Gamma1
and
the five-point finite difference matrix.
Lemma 4.3. The eigenvalues  c
defined in
(4.8) and (4.9) satisfy
l
sin
Proof. It follows from Lemma 4.1 that for 1  l
l
sin
Letting
PRECONDITIONING FOR COLLOCATION SYSTEMS 11
Thus,
l
sin
and
min
l
sin
From the above proof, we can see that the bounds in (4.15) are asymptotically
optimal. Let
l :=
l := (cosk' l
be 2N-dimensional vectors. If A is a circulant matrix defined by
a 0 a 1 a p
a p a 0 a 1 a
a 1 a 2 a p a 0C C A
then it is well-known [Dav79] that its eigenvalues are given by
where
Furthermore, A can be decomposed into
where
Lemma 4.4. a) If the 2N \Theta 2N circulant matrix A is symmetric then
b) If A is skew-symmetric then
where
Proof. (a) is a straightforward calculation, noting the fact that
where F j is the j-th column vector of F . By (4.19)
l
l
Since each eigenvalue of a skew-symmetric circulant matrix is imaginary,
so (4.21) follows.
Let
l'
N+l
l
and
e
It follows directly that the eigenvectors of ACB \Gamma1
C defined in (4.10)-(4.12) can be
expressed by
(v l ; v \Gammal
where
~
I =2
I \GammaI
I I
' \Gammaz l d l \Gammaz \Gammal d \Gammal
2hd l 2hd \Gammal
with
r \Gammaz \Gammal
r z l
Lemma 4.5. Each D l , is an orthogonal matrix.
Proof. It is obvious that D 0 D T
. For
N , by (4.24) we obtain
D l D T
l d 2
l
\Gammal d 2
\Gammal d l d \Gammal (z l z \Gammal
d l d \Gammal (z l z \Gammal
l
\Gammal
It follows from (4.8) and (4.13) that
z l z \Gammal =
so
z l z \Gammal
Using (4.26) and (4.27), we obtain
l d 2
l
\Gammal d 2
l
\Gammal
Thus,
D l D T
4.2. Bounds for condition numbers of preconditioned systems. Before
showing the uniform boundedness of condition numbers of the preconditioned matrices
T in (4.6), we show that ACB \Gamma1
C and the preconditioner AF share two-dimensional
invariant subspaces.
Theorem 4.1. Let (AC ; BC ) define a Hermite cubic collocation discretization of (2.1)
and (2.3) and fv l g \Sigma(2N \Gamma1)
l=\Sigma0 , defined in (4.10)-(4.12), be the eigenvectors of ACB \Gamma1
C .
Then each is an invariant subspace of AF .
Proof. By (4.1) and (4.24), we have
~
I T AF ~
where
2c a a
a 2c a
a a 2cC C A ;
\Gammaa a
a 0 \Gammaa
\Gammaa a 0C C A :
Thus,
I
It follows from Lemma 4.4 that
and therefore,
D l
Letting
D l :=
\Gammaasin' l (b
and using Lemma 4.5 and equation (4.23), (4.30) can be rewritten as
l
D l D l :
Thus, S l , are invariant subspaces of AF .
Thus, we only need to estimate the spectrum in each subspace S l . The main
theorem is presented below and its proof can be found in [SHR93].
14 W. SUN, W. HUANG AND R.D. RUSSELL
Theorem 4.2 Given (AC ; BC ) and AF as in Theorem 4.1 with ff ? 0, there exist
positive constants C 1 and C 2 independent of h such that T defined in (4.6) satisfies
Let  2 (T ) denote the condition number of T for the L 2 norm, i.e.,
The following two corollaries follow immediately.
Corollary 4.1. There exists a constant C
1 independent of h such that
Corollary 4.2. There exist constants C
3 and C
4 independent of h such that
and
Remarks:
(i). From the proof of Theorem 4.2, each eigenvalue of
a continuous function of ff in (0; 1) with
lim
Thus, C 1 and C 2 can be assumed to be independent of ff.
(ii). Theorem 4.2, while showing that the eigenvalues of the preconditioned matrix
are bounded by constants, does not give an explicit bound. Numerical observation
has shown that each  i increases as ff increases,
with Furthermore, for a given ff ? 0, both the
maximum and minimum eigenvalues of T occur for
are the maximum and minimum eigenvalues of T , respectively. It follows from (4.52)
that 1= 1
We can examine the bounds for  i explicitly for
Letting
fi 1l and
fi 2l can be expressed as
Let
It is easy to show that, for
dx
dx
0:
Thus,
which agrees with the numerical tests in Section 2. Similar relationships hold for the
(iii). One can use central differences with a uniform mesh on [0; 1] instead of the
non-uniform mesh fx
in (2.5) and obtain a matrix having the same form as (4.5)
with
and
The above arguments hold with minor modification, and the boundness of the eigen-values
of T and T T T is still valid.
(iv). It is easy to find examples of some discretizations of partial differential
equations for which the spectral condition numbers are bounded but the condition
numbers in the L 2 -norm sense are not. Nevertheless, some iterative methods can still
be very effective and converges quickly when applied to such preconditioned systems
if the eigenvalues are properly distributed.
It should be noted that the collocation system preconditioned by a simple finite
difference scheme is a very special case. Since AF and ACB \Gamma1
C have 2N common
invariant subspaces for a uniform mesh and periodic boundary conditions, in this case
both spectral condition numbers and condition numbers in the L 2 -norm are bounded
by constants independent of h. Our numerical results indicate that in the case of
a non-uniform mesh and/or Dirichlet boundary conditions, the spectral conditions
are bounded although we have as yet been unable to provide a theoretical proof and
however, the corresponding condition numbers in the L 2 -norm are unbounded.
(v). Although the discussion is based on a one-dimensional model problem, the
results for the corresponding two-dimensional model problem are straightforward to
generalize.
5. Numerical Solution of PDEs. The collocation matrices AC and BC are
generally nonsymmetric, as are the resulting preconditioned matrices using the pre-
conditionings. A number of iterative methods have been developed in recent years
for the solution of nonsymmetric preconditioned systems. They would be expected
to be efficient in our context because of the relatively small condition numbers and
the close concentration of eigenvalues for the preconditioned matrices. To illustrate
that this is indeed the case, we consider two examples of two dimensional second-order
elliptic partial differential equations defined
boundary conditions. The orthogonal Hermite bicubic collocation method is used for
the discretization of the PDEs. In order to avoid the effect of discretization errors
W. SUN, W. HUANG AND R.D. RUSSELL

Table
Example 5.1 Iteration numbers of (HRS5 ) preconditioned GCR and (non-preconditioned) BGS,
methods.
28
in our tests, the right-hand sides and boundary conditions in the two examples are
chosen such that
is both the PDE solution and the collocation solution. The five-diagonal row-sum-
equivalence incomplete-LU factorization (HRS5 ) is a preconditioner and a generalized
conjugate residual method (GCR) [EES83] is employed to solve the preconditioned
collocation equations. The error is measured by
denotes the exact solution and its first and mixed derivative values at mesh
points, and u (k)
ij denotes the corresponding numerical solution at the kth iteration. For
both examples, the initial guess is taken as zero. The iterative procedure is stopped
when e (k) is smaller than a prescribed tolerance ffi .
Example 5.1. Poisson Equation
In

Table

5, we list the number of iterations required for preconditioned GCR
(PGCR) with four tolerances and using the 2D-Meshes 1-3. Since this example is
separable, other iterative methods such as block Gauss-Seidel (BGS), block SOR
(BSOR) [Sun(a)] and ADC [Dyk87], are also applicable when a uniform mesh is used.
The results with BGS and BSOR are also given in Table 5. ADC is not considered
since it is actually a direct method for this simple problem [Dyk87]. Although the
number of iterations for PGCR to achieve a prescribed tolerance increases with N ,
the growth rate is acceptable and is smaller than that of BGS or BSOR. For given
nearly the same number of iterations for 2D-Mesh 2 and 3 as for
a uniform mesh.
Example 5.2. A Nonseparable Elliptic PDE (Problem
@x
@y
None of other iterative methods are applicable for this non-separable problem.
Numbers of iterations for PGCR using various meshes and tolerances are summarized
in

Table

6. The same basic conclusions about PGCR can be made as in the previous
example.
PRECONDITIONING FOR COLLOCATION SYSTEMS 17

Table
Example 5.2 Iteration numbers of (HRS5 ) preconditioned GCR method.
MESH NO. N
6. Conclusions and Comments. A technique has been presented to construct
a finite difference preconditioning for orthogonal collocation matrices. Only cubic
Hermite basis functions have been considered, although the preconditioning principles
are straightforward to generalize for higher order collocation methods. It is shown
numerically that the norms of eigenvalues of the preconditioned collocation matrices
can be bounded below by one and above by a constant independent of the number of
mesh nodes using the exact low-order finite difference preconditioner. For both smooth
and moderately nonsmooth meshes, the preconditioned matrix has a small spectral
condition number, with its eigenvalues located in a narrow interval on the positive
real axis. As a consequence, conventional iterative methods such as Richardson and
conjugate gradient iterations give fast convergence for the preconditioned collocation
equations.
We have also investigated much cheaper alternatives involving incomplete-LU
factorizations based on a low-order finite difference approximation. The row-sum-
equivalence version is particularly efficient although condition numbers may grow
slowly with the number of mesh points. Moreover, the generalized conjugate residual
method with this preconditioning has been seen to converge fast for both separable
and non-separable problems with uniform or non-uniform meshes.
While only limited experiments and comparisons have been performed, the results
are quite encouraging. It is our intention to perform a theoretical analysis of these
preconditioning schemes (possibly developing a general theoretical framework for the
collocation methods analogous to that is done in [MP90] for the finite element method)
and do a more careful comparison with the currently popular direct schemes for solving
the collocation linear systems.

Acknowledgement

The authors are indebted to Tom Manteuffel for his constructive
suggestions.



--R

Numerical Solution of Boundary Value Problems for Ordinary Differential Equations
Parallel collocation methods for boundary value problems
Fast direct solvers for piecewise Hermite bicubic orthogonal spline collocation equations
An alternating direction implicit method for orthogonal spline collocation linear systems
Fourier analysis of iterative methods for elliptic problems
Spectral Methods in Fluid Dynamics
Alternating direction collocation for separable elliptic partial differential equations
New York
Collocation at Gaussian points
Tensor product generalized ADI method for separable elliptic problems
Variational iterative method for nonsymmetric systems of linear equations
Preconditioning Methods: Analysis and Applications
An alternating direction collocation method for finite element approximations on rectangles
Alternating direction collocation for rectangular regions
Preconditioning second-order elliptic operators: experiment and theory
Preconditioning and boundary conditions
Spectral methods for problems in complex geometries
Orthogonal collocation for elliptic partial differential equa- tions
Solving Elliptic Problem Using Ellpack
A collocation method for boundary value problems
Finite difference preconditioning for solving orthogonal collocation equations for boundary value problems
Iterative algorithms for solving Hermite bicubic collocation equations
A high order direct method for solving Poisson's equation on a disc
A fast algorithm for solving the tensor product collocation equa- tions
Preconditioned gradient type methods applied to nonsymmetric linear systems
--TR
collocation;boundary value problem;preconditioning