[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A least-squares preconditioner for radial basis functions collocation methods

  • Published:
Advances in Computational Mathematics Aims and scope Submit manuscript

Abstract

Although meshless radial basis function (RBF) methods applied to partial differential equations (PDEs) are not only simple to implement and enjoy exponential convergence rates as compared to standard mesh-based schemes, the system of equations required to find the expansion coefficients are typically badly conditioned and expensive using the global Gaussian elimination (G-GE) method requiring \(\mathcal{O}(N^{3})\) flops. We present a simple preconditioning scheme that is based upon constructing least-squares approximate cardinal basis functions (ACBFs) from linear combinations of the RBF-PDE matrix elements. The ACBFs transforms a badly conditioned linear system into one that is very well conditioned, allowing us to solve for the expansion coefficients iteratively so we can reconstruct the unknown solution everywhere on the domain. Our preconditioner requires \(\mathcal{O}(mN^{2})\) flops to set up, and \(\mathcal{O}(mN)\) storage locations where m is a user define parameter of order of 10. For the 2D MQ-RBF with the shape parameter \(c\sim1/\sqrt{N}\) , the number of iterations required for convergence is of order of 10 for large values of N, making this a very attractive approach computationally. As the shape parameter increases, our preconditioner will eventually be affected by the ill conditioning and round-off errors, and thus becomes less effective. We tested our preconditioners on increasingly larger c and N. A more stable construction scheme is available with a higher set up cost.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. B. Baxter, The asymptotic cardinal function of the multiquadratic φ(r)=(r2+c2)1/2 as c→∞, Comput. Math. Appl. 24(12) (1992) 1–6.

    Google Scholar 

  2. R.K. Beatson, J.B. Cherrie and C.T. Mouat, Fast fitting of radial basis functions: Methods based on preconditioned GMRES iteration, Adv. Comput. Math. 11 (1999) 253–270.

    Google Scholar 

  3. R.K. Beatson, J.B. Cherrie and G.N. Newsam, Fast evaluation of radial basis functions: Methods for generalized multiquadrics in Rn, SIAM J. Sci. Comput. 23(5) (2002) 1549–1571.

    Article  MathSciNet  MATH  Google Scholar 

  4. R.K. Beatson and W.A. Light, Fast evaluation of radial basis function: Methods for two-dimensional polyharmonic splines, IMA J. Numer. Anal. 17 (1997) 343–372.

    MathSciNet  MATH  Google Scholar 

  5. R.K. Beatson, W.A. Light and S. Billings, Fast solution of the radial basis function interpolation methods: Domain decomposition methods, SIAM J. Sci. Comput. 22(5) (2000) 1717–1740.

    Google Scholar 

  6. R.K. Beatson and G.N. Newsam, Fast evaluation of radial basis functions I, Comput. Math. Appl. 24(12) (1992) 7–19.

    Google Scholar 

  7. M. Bozzini, L. Lenarduzzi and R. Schaback, Kernel B-splines and adaptive interpolation, Manuscript (2002)

  8. P.N. Brown and H.F. Walker, GMRES on (nearly) singular systems, SIAM J. Matrix. Anal. Appl. 18 (1997) 37–51.

    Google Scholar 

  9. M.D. Buhmann, Multivariate interpolation in odd-dimensional Euclidean spaces using multiquadrics, Constr. Approx. 6(1) (1990) 21–34.

    Google Scholar 

  10. M.D. Buhmann, Multivariate cardinal interpolation with radial-basis functions, Constr. Approx. 6(3) (1990) 225–255.

    Google Scholar 

  11. M.D. Buhmann and C.A. Micchelli, Multiquadric interpolation improved, Comput. Math. Appl. 24(12) (1992) 21–25.

    Google Scholar 

  12. A.H.D. Cheng, M.A. Golberg, E.J. Kansa and T. Zammito, Exponential convergence and h-c multiquadric collocation method for partial differential equations, Numer. Methods Partial Differential Equations (to appear)

  13. G.E. Fasshauer, On the numerical solution of differential equations with radial basis functions, in: Boundary Element Technology, Vol. XIII, eds. C.S. Chen, C.A. Brebbia and D.W. Pepper (WIT Press, 1999) pp. 291–300.

  14. A.C. Faul, Iterative techniques for radial basis function interpolation, Ph.D. thesis, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Cambridge, England (2001).

  15. A.C. Faul and M.J.D. Powell, Krylov subspace methods for radial basis function interpolation, in: Numerical Analysis 1999, Dundee, Research Notes in Mathematics, Vol. 420 (Chapman & Hall/CRC, Boca Raton, FL, 2000) pp. 115–141.

    Google Scholar 

  16. A.I. Fedoseyev, M.J. Friedman and E.J. Kansa, Improved multiquadric method for elliptic partial differential equations via PDE collocation on the boundary, Comput. Math. Appl. 43(3–5) (2002) 439–455.

    Google Scholar 

  17. B. Fornberg, T.A. Driscoll, G. Wright and R. Charles, Observations on the behavior of radial basis functions near boundaries, Comput. Math. Appl. 43 (2002) 473–490.

    Google Scholar 

  18. B. Fornberg and G. Wright, Stable computation of multiquadric interpolants for all values of the shape parameter, BIT (to appear)

  19. G.H. Golub and C.F. Van Loan, Matrix Computations, 3rd ed. (Johns Hopkins Univ. Press, Baltimore/London, 1996).

    Google Scholar 

  20. R.L. Hardy, Theory and applications of the multiquadric-biharmonic method. 20 years of discovery 1968–1988, Comput. Math. Appl. 10(8/9) (1990) 163–208.

    Google Scholar 

  21. Y.C. Hon and Z. Wu, Additive Schwarz domain decomposition with radial basis approximation, Internat. J. Appl. Math. 4 (2002) 81–98.

    Google Scholar 

  22. E.J. Kansa, Multiquadrics – a scattered data approximation scheme with applications to computational fluid-dynamics. I. Surface approximations and partial derivative estimates, Comput. Math. Appl. 19(8/9) (1990) 127–145.

    Google Scholar 

  23. E.J. Kansa, Multiquadrics – a scattered data approximation scheme with applications to computational fluid-dynamics. II. Solutions to parabolic, hyperbolic and elliptic partial differential equations, Comput. Math. Appl. 19(8/9) (1990) 147–161.

    Google Scholar 

  24. E.J. Kansa and Y.C. Hon, Circumventing the ill-conditioning problem with multiquadric radial basis functions: Applications to elliptic partial differential equations, Comput. Math. Appl. 39(7/8) (2000) 123–137.

    Google Scholar 

  25. E.J. Kansa, H. Power, G.E. Fasshauer and L. Ling, A volumetric integral radial basis function method for time dependent partial differential equations I. Formulation, Engrg. Anal. Bound. Elem. (in review).

  26. E. Larsson and B. Fornberg, A numerical study of radial basis functions based solution methods for elliptic PDEs, Comput. Math. Appl. (in press).

  27. C.L. Lawson and R.J. Hanson, Solving Least Squares Problems (Prentice-Hall, Englewood Cliffs, NJ, 1974).

    Google Scholar 

  28. J. Li and Y.C. Hon, Domain decomposition for radial basis meshless methods, Numer. Methods Partial Differential Equations (in review)

  29. W.R. Madych, Miscellaneous error bounds for multiquadric and related interpolatiors, Comput. Math. Appl. 24 (1992) 121–138.

    Google Scholar 

  30. C.T. Mouat, Fast algorithms and preconditioning techniques for fitting radial basis functions. Ph.D. thesis, Mathematics Department, University of Canterbury, Christchurch, New Zealand (2001)

  31. R. Sibson and G. Stone, Computation of thin-plate splines, SIAM J. Sci. Statist. Comput. 12 (1991) 1304–1313.

    Google Scholar 

  32. B.F. Smith, P.E. Bjørstad and W.D. Gropp, Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations (Cambridge Univ. Press, Cambridge, UK, 1996).

    Google Scholar 

  33. L.N. Trefethen and D. Bau III, Numerical Linear Algebra (SIAM, Philadelphia, PA, 1997).

    Google Scholar 

  34. X. Zhou, Y.C. Hon and J. Li, Overlapping domain decomposition method by radial basis functions, Appl. Numer. Math. (in press)

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Simon Fraser University, 8888 University Drive, Burnaby, BC, Canada, V5A 1S6

    Leevan Ling

  2. Embry-Riddle Aeronautical University, Oakland Center, 7700 Edgewater Dr., Oakland, CA, 94621, USA

    Edward J. Kansa

Authors
  1. Leevan Ling
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Edward J. Kansa
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by Z. Wu and B.Y.C. Hon

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ling, L., Kansa, E.J. A least-squares preconditioner for radial basis functions collocation methods. Adv Comput Math 23, 31–54 (2005). https://doi.org/10.1007/s10444-004-1809-5

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10444-004-1809-5

Keywords

Search

Navigation