  This article is devoted to developing a theory for effective kernel
interpolation and approximation in a general setting. For a wide class of
compact, connected $C^\infty$ Riemannian manifolds, including the important
cases of spheres and SO(3), we establish, using techniques involving
differential geometry and Lie groups, that the kernels obtained as fundamental
solutions of certain partial differential operators generate Lagrange functions
that are uniformly bounded and decay away from their center at an algebraic
rate, and in certain cases, an exponential rate. An immediate corollary is that
the corresponding Lebesgue constants for interpolation as well as for $L_2$
minimization are uniformly bounded with a constant whose only dependence on the
set of data sites is reflected in the mesh ratio, which measures the uniformity
of the data. The kernels considered here include the restricted surface splines
on spheres, as well as surface splines for SO(3), both of which have elementary
closed-form representations that are computationally implementable. In addition
to obtaining bounded Lebesgue constants in this setting, we also establish a
"zeros lemma" for domains on compact Riemannian manifolds -- one that holds in
as much generality as the corresponding Euclidean zeros lemma (on Lipschitz
domains satisfying interior cone conditions) with constants that clearly
demonstrate the influence of the geometry of the boundary (via cone parameters)
as well as that of the Riemannian metric.
