摘要
We present a fast algorithm based on polynomial interpolation to approximate matrices arising from the discretization of second-kind integral equations where the kernel function is either smooth, non-oscillatory and possessing only a finite number of singularities or a product of such function with a highly oscillatory coefficient function. Contrast to wavelet-like approximations, ourapproximation matrix is not sparse. However, the approximation can be construced in O(n) operations and requires O(n) storage, where n is the number of quadrature points used in the discretization. Moreover, the matrix-vector multiplication cost is of order O(nlogn). Thus our scheme is well suitable for conjugate gradient type methods. Our numerical results indicate that the algorithm is very accurate and stable for high degree polynomial interpolation.
We present a fast algorithm based on polynomial interpolation to approximate matrices arising from the discretization of second-kind integral equations where the kernel function is either smooth, non-oscillatory and possessing only a finite number of singularities or a product of such function with a highly oscillatory coefficient function. Contrast to wavelet-like approximations, our approximation matrix is not sparse. However, the approximation can be construced in O(n) operations and requires O(n) storage, where n is the number of quadrature points used in the discretization. Moreover, the matrix-vector multiplication cost is of order O(nlogn). Thus our scheme is well suitable for conjugate gradient type methods. Our numerical results indicate that the algorithm is very accurate and stable for high degree polynomial interpolation.
基金
Research supported in part by Hong Kong Research Grant Council grats no.CUHK178/83E
