WIAS Preprint No. 293, (1996)

An efficient ADI-solver for scattered data problems with global smoothing


  • Arge, Erlend
  • Kunoth, Angela

2010 Mathematics Subject Classification

  • 65D17, 65N06 73N20.


  • Scattered data approximation, fourth order elliptic problems, difference methods, preconditioned conjugate gradient methods, ADI methods


For the approximate representation of large data sets over a parameter domain in ℝ2, many geological and other applications require the construction of surfaces which have minimal energy, i.e., minimal curvature. One way to achieve this is by solving a fourth order elliptic partial differential equation. Its discretization by a difference scheme makes it particularly easy to incorporate (appropriate approximations of) known data points. Because of the solution of the resulting symmetric linear system being the most CPU-demanding step, we investigate first the performance of a preconditioned conjugate gradient method with an SSOR and a RILU preconditioner. However, since the partial differential operator does not contain mixed derivatives, using an alternating-direction-implicit scheme (ADI method) which has been employed successfully in the past for second order problems, together with Cholesky factorization of the corresponding one-dimensional operators provides a fast and effective method for the problem at hand. The computational studies show that an instationary ADI method is superior to the above mentioned preconditioned conjugate gradient solvers both with respect to work load and accuracy of the solution. For the fourth order model problem considered in this paper, the instationary ADI method with Wachspress parameters results in a number of iterations that is essentially independent of the number of variables.

Download Documents