An adaptive fast direct solver for boundary integral equations in two dimensions

We describe an algorithm for the rapid direct solution of linear algebraic systems arising from the discretization of boundary integral equations of potential theory in two dimensions. The algorithm is combined with a scheme that adaptively rearranges the parameterization of the boundary in order to minimize the ranks of the off-diagonal blocks in the discretized operator, thus obviating the need for the user to supply a parameterization r of the boundary for which the distance parallel to r(s) - r(t)parallel to between two points on the boundary is related to their corresponding distance vertical bar s - t vertical bar in the parameter space. The algorithm has an asymptotic complexity of O(N log(2) N), where N is the number of nodes in the discretization. The performance of the algorithm is illustrated with several numerical examples. (C) 2011 Elsevier Inc. All rights reserved.