A multilevel algorithm for solving a boundary integral equation of wave scattering

Abstract

Abstract In the solution of an integral equation using the conjugate gradient (CG) method, the most expensive part is the matrix‐vector multiplication, requiring O(N 2 ) floating‐point operations. The fast multipole method (FMM) reduced the operation to O(N 15 ). In this article we apply a multilevel algorithm to this problem and show that the complexity of a matrix‐vector multiplication is proportional to N (log(N)) 2 . © 1994 John Wiley & Sons, Inc.