  We describe an efficient method for the approximation of functions using
radial basis functions (RBFs), and extend this to a solver for boundary value
problems on irregular domains. The method is based on RBFs with centers on a
regular grid defined on a bounding box, with some of the centers outside the
computational domain. The equation is discretized using collocation with
oversampling, with collocation points inside the domain only, resulting in a
rectangular linear system to be solved in a least squares sense. The goal of
this paper is the efficient solution of that rectangular system. We show that
the least squares problem splits into a regular part, which can be expedited
with the FFT, and a low rank perturbation, which is treated separately with a
direct solver. The rank of the perturbation is influenced by the irregular
shape of the domain and by the weak enforcement of boundary conditions at
points along the boundary. The solver extends the AZ algorithm which was
previously proposed for function approximation involving frames and other
overcomplete sets. The solver has near optimal log-linear complexity for
univariate problems, and loses optimality for higher-dimensional problems but
remains faster than a direct solver.
