Fast evaluation of radial basis functions: I

✍ Scribed by R.K. Beatson; G.N. Newsam

• Publisher: Elsevier Science
• Year: 1992
• Tongue: English
• Weight: 987 KB
• Volume: 24
• Category: Article
• ISSN: 0898-1221
• DOI: 10.1016/0898-1221(92)90167-g

✦ Synopsis

This paper describes some new tedmiques for the rapid evaluation and fitting of radial balfis functions. The techniques are based on the hierarchical and multipole expmmions recently introduced by several authors for the calculation of ma~-body potentials. Cmmider in paxticnlar the N term thin-plate spline, a(z) ---E~,ffil djqb(x -zj), where

The direct evaluation of s at a single extra point requires an extra O(N) operations. This paper shows that, with judicious use of series expaxmious, the incre~nental cost of evaluating a(x) to within precltdon e, can be cut to O(1 + IlogeD operations. In particular, if A is the interpolation matrix, ai,j = qb(=i -xj), the technique allows computation of the matrix-vector product Ad in O(N), rather than the previously required O(N 2) operations, and using only O(N) storage. Fast, storage-efficlent, computation of this matrix-vector product makes pre-conditioned conjugate~gradie~t methods very attractive as solvers of the interpolation equations, Ad --y, when N is large.