Iterative methods for Galerkin BEM matrices on anisotropic meshes
This project involves work both on conditioning of Galerkin BEM
matrices in the presence of anisotropic mesh refinement and also on
fast matrix-vector multiplication in such situations.
Conditioning of Galerkin matrices
In this work we obtain upper and lower bounds on the spectrum of the
stiffness matrix arising from a finite element Galerkin approximation
(using
nodal basis functions) of a bounded, symmetric bilinear form which
is elliptic on a Sobolev space of real index~$m\in[-1,1]$.
The key point is that the finite element mesh is required to be
neither quasiuniform nor shape regular, so that our theory
allows anisotropic meshes
often used in practice. (However, we assume that the polynomial degree
of the elements is fixed.) Our bounds indicate the ill-conditioning
which can
arise from anisotropic mesh refinement. In addition we obtain
spectral bounds for the diagonally scaled stiffness matrix, which
indicate the improvement provided by
this simple preconditioning. For the special case of boundary
integral operators on a $2D$~screen in~$\R^3$, numerical
experiments show that our bounds are sharp.
We find that diagonal scaling essentially removes the ill-conditioning
due to mesh degeneracy, leading to the same asymptotic growth in
the condition number
as arises for a quasi-uniform mesh refinement. Our results thus
generalise earlier work by Bank and Scott (1989) and Ainsworth, McLean
and Tran (1999) for the shape-regular case.
The work is written up in the preprint: I.G.
Graham and W. McLean, Anisotropic mesh refinement, the
conditioning of Galerkin boundary element matrices and simple
preconditioners,
submitted to SIAM J. Numerical Analysis, December 2004.
Copy of
final report
for the EPSRC Grant GR/S43399 which funded this work.
Fast matrix-vector multiplication
In this paper we propose and analyse a new enhanced version of the
panel-clustering algorithm for discrete boundary integral equations on
polyhedral surfaces in 3D, which is designed to perform efficiently even
when the meshes contain the highly stretched elements needed for efficient
discretisation when the solution contains edge singularities. The key
features of our algorithm are: (i) the employment of partial analytic
integration in the direction of stretching, yielding a new kernel function
on a one dimensional manifold where the influence of the high aspect ratios
in the stretched elements is removed and (ii) the introduction of a
generalised admissibility condition with respect to the partially integrated
kernel which ensures that certain stretched clusters which are inadmissible
in the classical sense now become admissible. In the context of a model
problem, we prove that our algorithm yields an accurate (up to
discretisation error) matrix-vector multiplication which requires $O(N\log
^{\kappa }N)$ operations, where $N$ is the number of degrees of freedom and $%
\kappa $ is small and independent of the aspect ratio of the elements. We
also show that the classical admissibility condition leads to a sub-optimal
clustering algorithm for these problems. A numerical experiment shows that
the theoretical estimates can be realised in practice. The generalised
admissibility condition can be viewed as a simple addition to the classical
method which may be useful in general when stretched meshes are present.
This work is written up in the preprint:
L. Grasedyck, I.G. Graham, W. Hackbusch and S.A. Sauter,
Optimal Panel-Clustering in the Presence of Anisotropic Mesh
Refinement. Bath Institute for Complex
Systems Preprint number 16/06, University of Bath (2006), submitted
for publication. Details