# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
An adaptive fast direct solver for boundary integral equations in two dimensions. (English) Zbl 1227.65118
Summary: 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 r\left(s\right)-r\left(t\right)\parallel$ between two points on the boundary is related to their corresponding distance $|s-t|$ in the parameter space. The algorithm has an asymptotic complexity of $O\left(N{log}^{2}N\right)$, where $N$ is the number of nodes in the discretization. The performance of the algorithm is illustrated with several numerical examples.
##### MSC:
 65N38 Boundary element methods (BVP of PDE) 35J05 Laplacian operator, reduced wave equation (Helmholtz equation), Poisson equation 65Y20 Complexity and performance of numerical algorithms
##### References:
 [1] Björck, å.: Numerical methods for least squares problems, (1996) · Zbl 0847.65023 [2] Carrier, J.; Greengard, L.; Rokhlin, V.: A fast adaptive multipole algorithm for particle simulations, SIAM J. Sci. stat. Comput. 9, No. 4, 669-686 (1988) · Zbl 0656.65004 · doi:10.1137/0909044 [3] Chandler, G.: Galkerin’s method for boundary integral equations on polygonal domains, J. aust. Math. soc., ser. B 26, 1-13 (1984) · Zbl 0559.65083 · doi:10.1017/S033427000000429X [4] Chandrasekaran, S.; Gu, M.; Pals, T.: A fast ULV decomposition solver for hierarchically semi-separable representations, SIAM J. Matrix anal. Appl. 28, No. 3, 603-622 (August 2006) · Zbl 1120.65031 · doi:10.1137/S0895479803436652 [5] Chen, Y.: A fast direct algorithm for the Lippmann-Schwinger integral equation in two dimensions, Adv. comput. Math. 16, No. 2-3, 175-190 (2002) · Zbl 0993.65137 · doi:10.1023/A:1014450116300 [6] Chew, W. C.: An n2 algorithm for the multiple scattering solution of n scatterers, Micro. optical tech. Lett. 2, 380-383 (1989) [7] Coifman, R.; Meyer, Y.: Wavelets: Calderón-Zygmund and multilinear operators, (1997) [8] Folland, G.: Introduction to partial differential equations, (1976) [9] Gines, D.; Beylkin, G.; Dunn, J.: Lu factorization of non-standard forms and direct multiresolution solvers, Appl. comput. Harmon. anal. 5, No. 2, 156-201 (1998) · Zbl 0914.65017 · doi:10.1006/acha.1997.0227 [10] Golub, G.; Loan, C. V.: Matrix computations, (1989) [11] Greengard, L.; Rokhlin, V.: A fast algorithm for particle simulations, J. comput. Phys. 73, 325-348 (1987) · Zbl 0629.65005 · doi:10.1016/0021-9991(87)90140-9 [12] Gu, Ming; Eisenstat, Stanley C.: Efficient algorithms for computing a strong rank-revealing QR factorization, SIAM J. Sci. comput. 17, No. 4, 848-869 (1996) · Zbl 0858.65044 · doi:10.1137/0917055 [13] Hackbusch, W.: A sparse matrix arithmetic based on H-matrices. I. introduction to H-matrices, Computing 62, No. 2, 89-108 (1999) · Zbl 0927.65063 · doi:10.1007/s006070050015 [14] Hackbusch, W.; Börm, S.: Data-sparse approximation by H2-matrices, Computing 69, No. 1, 1-35 (2002) · Zbl 1012.65023 · doi:10.1007/s00607-002-1450-4 [15] Helsing, J.; Ojala, R.: Corner singularities for elliptic problems: integral equations, graded meshes, quadrature, and compressed inverse preconditioning, J. comput. Phys. 227 (2008) · Zbl 1152.65114 · doi:10.1016/j.jcp.2008.06.022 [16] Hrycak, T.; Rokhlin, V.: An improved fast multipole algorithm for potential fields, SIAM J. Sci. comput. 19, No. 6, 1804-1826 (1998) · Zbl 0915.65116 · doi:10.1137/S106482759630989X [17] Kellog, O.: Foundations of potential theory, (1953) [18] Kenig, C.: Elliptic boundary value problems on Lipschitz domains, Ann. of math. Stud. 112, 131-183 (1986) · Zbl 0624.35029 [19] Kress, R.: A Nyström method for boundary integral equations in domains with corners, Numer. math. 58, 145-161 (1990) · Zbl 0707.65078 · doi:10.1007/BF01385616 [20] Kress, R.: Integral equations, (1999) [21] Martinsson, P. G.; Rokhlin, V.: A fast direct solver for boundary integral equations in two dimensions, J. comput. Phys. 205, 1-23 (2005) · Zbl 1078.65112 · doi:10.1016/j.jcp.2004.10.033 [22] Mikhlin, S.: Integral equations, (1957) [23] Rokhlin, V.: Rapid solution of integral equations of classical potential theory, J. comput. Phys. 60, 187-207 (1983) · Zbl 0629.65122 · doi:10.1016/0021-9991(85)90002-6 [24] Starr, P.; Rokhlin, V.: On the numerical solution of two-point boundary value problems II, Comm. pure appl. Math. 47, 1117-1159 (1994) · Zbl 0805.65080 · doi:10.1002/cpa.3160470806 [25] Stoer, J.; Bulirsch, R.: Introduction to numerical analysis, (1993) · Zbl 0771.65002 [26] Verchota, G.: Layer potentials and boundary value problems for Laplace’s equation in Lipschitz domains, J. funct. Anal. 59, 572-611 (1984) · Zbl 0589.31005 · doi:10.1016/0022-1236(84)90066-1 [27] Woolfe, F.; Liberty, E.; Rokhlin, V.; Tygert, M.: A fast randomized algorithm for the approximation of matrices, Appl. comput. Harmon. anal. 25, 335-366 (2008) · Zbl 1155.65035 · doi:10.1016/j.acha.2007.12.002