2013/08/15 by Huda Ibeid, Rio Yokota, Ibeid, Huda +5 · 2 citations
Computer Science · Engineering · Physics and Astronomy · #65F08 #65F50 #65N30 #65N55 #65N80 #65R20 #65Y05 #65Y20 #D.1.3 #Electromagnetic Scattering and Analysis #Electromagnetic Simulation and Numerical Methods #FOS: Mathematics #G.1.2 #G.1.3 #G.1.8 #G.1.9 #Matrix Theory and Algorithms #Numerical Analysis (math.NA)
paper · pdf · doi:10.48550/arxiv.1308.3339
openalex publication_date 2013/08/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Among optimal hierarchical algorithms for the computational solution of\nelliptic problems, the Fast Multipole Method (FMM) stands out for its\nadaptability to emerging architectures, having high arithmetic intensity,\ntunable accuracy, and relaxable global synchronization requirements. We\ndemonstrate that, beyond its traditional use as a solver in problems for which\nexplicit free-space kernel representations are available, the FMM has\napplicability as a preconditioner in finite domain elliptic boundary value\nproblems, by equipping it with boundary integral capability for satisfying\nconditions at finite boundaries and by wrapping it in a Krylov method for\nextensibility to more general operators. Here, we do not discuss the well\ndeveloped applications of FMM to implement matrix-vector multiplications within\nKrylov solvers of boundary element methods. Instead, we propose using FMM for\nthe volume-to-volume contribution of inhomogeneous Poisson-like problems, where\nthe boundary integral is a small part of the overall computation. Our method\nmay be used to precondition sparse matrices arising from finite\ndifference/element discretizations, and can handle a broader range of\nscientific applications. Compared with multigrid methods, it is capable of\ncomparable algebraic convergence rates down to the truncation error of the\ndiscretized PDE, and it offers potentially superior multicore and distributed\nmemory scalability properties on commodity architecture supercomputers.\nCompared with other methods exploiting the low rank character of off-diagonal\nblocks of the dense resolvent operator, FMM-preconditioned Krylov iteration may\nreduce the amount of communication because it is matrix-free and exploits the\ntree structure of FMM. We describe our tests in reproducible detail with freely\navailable codes and outline directions for further extensibility.\n