{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,27]],"date-time":"2026-10-27T22:43:47Z","timestamp":1793141027912,"version":"4.5.0"},"reference-count":49,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"crossref","award":["W911NF-115-2-0121"],"award-info":[{"award-number":["W911NF-115-2-0121"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000070","name":"National Institute of Biomedical Imaging and Bioengineering","doi-asserted-by":"crossref","award":["10042242"],"award-info":[{"award-number":["10042242"]}],"id":[{"id":"10.13039\/100000070","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"crossref","award":["1337393"],"award-info":[{"award-number":["1337393"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-12-10484"],"award-info":[{"award-number":["FA9550-12-10484"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006132","name":"Office of Science","doi-asserted-by":"publisher","award":["SC0010518"],"award-info":[{"award-number":["SC0010518"]}],"id":[{"id":"10.13039\/100006132","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006132","name":"Office of Science","doi-asserted-by":"publisher","award":["SC0009286"],"award-info":[{"award-number":["SC0009286"]}],"id":[{"id":"10.13039\/100006132","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2016,1]]},"abstract":"<jats:p>From molecular dynamics and quantum chemistry, to plasma physics and computational astrophysics, Poisson solvers in the unit cube are used in many applications in computational science and engineering. In this work, we benchmark and discuss the performance of the scalable methods for the Poisson problem which are used widely in practice: the fast Fourier transform (FFT), the fast multipole method (FMM), the geometric multigrid (GMG), and algebraic multigrid (AMG). Our focus is on solvers supporting high-order, highly nonuniform discretizations. To allow comparisons with standard libraries we also compare adaptive solvers with solvers specialized for problems on regular grids, that is, FFT and regular-stencil multigrid, since both are very popular algorithms for several practical applications. For the multigrid, we use the finite element variant of a high-performance geometric multigrid (HPGMG) benchmark. In total we compare five different codes, three of which are developed in our group. Our FFT, GMG, and FMM are parallel solvers that use high-order approximation schemes for Poisson problems with continuous forcing functions (the source or right-hand side). Our FFT code is based on the FFTW for single node parallelism. The AMG code is from the Trilinos library from the Sandia National Laboratory. Our GMG and FMM support octree based mesh refinement and variable coefficients and enable highly nonuniform discretizations. The GMG actually also supports complex (noncubic) geometries using a forest of octrees. We examine and report results for weak scaling, strong scaling, and time to solution for uniform and highly refined grids. We present results on the Stampede system at the Texas Advanced Computing Center and on the Titan system at the Oak Ridge National Laboratory. In our largest test case, we solved a problem with 600 billion unknowns on 229,379 cores of Titan. Overall, all methods scale quite well to these problem sizes. We have tested all of the methods with different source functions (the right-hand side in the Poisson problem). Our results indicate that FFT is the method of choice for smooth source functions that require uniform resolution. However, FFT loses its performance advantage when the source function has highly localized features like internal sharp layers. FMM and GMG considerably outperform FFT for those cases. The distinction between FMM and GMG is less pronounced and is sensitive to the quality (from a performance point of view) of the underlying implementations. The high-order accurate versions of GMG and FMM significantly outperform their low-order accurate counterparts.<\/jats:p>","DOI":"10.1137\/15m1010798","type":"journal-article","created":{"date-parts":[[2016,6,29]],"date-time":"2016-06-29T16:33:14Z","timestamp":1467217994000},"page":"C280-C306","source":"Crossref","is-referenced-by-count":79,"title":["FFT, FMM, or Multigrid? A comparative Study of State-Of-the-Art Poisson Solvers for Uniform and Nonuniform Grids in the Unit Cube"],"prefix":"10.1137","volume":"38","author":[{"given":"Amir","family":"Gholami","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dhairya","family":"Malhotra","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hari","family":"Sundar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"George","family":"Biros","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2016,6,29]]},"reference":[{"key":"atypb1","volume-title":"High-performance geometric multigrid, https:\/\/hpgmg.org","author":"Adams M.","year":"2014"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.88.063308"},{"key":"atypb3","volume-title":"PETSc Web page, \\burlhttp:\/\/www.mcs.anl.gov\/petsc","author":"Balay S.","year":"2014"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1145\/1268776.1268779"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2011.18"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1977-0431719-X"},{"key":"atypb7","volume-title":"SC10: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, ACM\/IEEE, IEEE Computer Society","author":"Burstedde C.","year":"2010"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/100791634"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/0909044"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.1999.6355"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1145\/2304576.2304604"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546792"},{"key":"atypb13","first-page":"1","volume-title":"Proceedings of the 2010 ACM\/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis, IEEE Computer Society","author":"Dror R. O.","year":"2010"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827500369967"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60902-4_23"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827594266891"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2004.840301"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1145\/1995896.1995924"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2010.5470417"},{"key":"atypb20","unstructured":"M. W. Gee, C. M. Siefert, J. J. Hu, R. S. Tuminaro, and M. G. Sala,\n                      ML $5.0$ smoothed aggregation user's guide\n                      , Tech. Report SAND2006-2649, Sandia National Laboratories, Albuquerque, NM and Livermore, CA, 2006."},{"key":"atypb21","series-title":"SIAM J. Sci. Comput., submitted","volume-title":"AccFFT: A library for distributed-memory 3-D FFT on CPU and GPU architectures","author":"Gholami A."},{"key":"atypb22","volume-title":"An Introduction to Parallel Computing: Design and Analysis of Algorithms","author":"Grama A.","year":"2003","edition":"2"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02427-0"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1145\/1089014.1089021"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2012.47"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.2140\/camcos.2011.6.79"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1145\/2160718.2160740"},{"key":"atypb28","first-page":"1","volume-title":"Cray User Group 2010 Conference","author":"Li N.","year":"2010"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1145\/779359.779361"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-004-4787-3"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.2140\/camcos.2007.2.57"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2012.100"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1137\/11082748X"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2002.10019"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1109\/43.662670"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1137\/120885887"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1137\/090747774"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2005.11.017"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2012.91"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1137\/070681727"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1002\/nla.1979"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(87)90018-4"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(05)80100-0"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1109\/SUPERC.1994.344279"},{"key":"atypb46","volume-title":"Multigrid","author":"Trottenberg U.","year":"2000"},{"key":"atypb47","volume-title":"NM","author":"Tuminaro R. S.","year":"2013"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-06486-4_7"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2003.11.021"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1177\/1094342011429952"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/15M1010798","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:35:23Z","timestamp":1787333723000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/15M1010798"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1]]},"references-count":49,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["10.1137\/15M1010798"],"URL":"https:\/\/doi.org\/10.1137\/15m1010798","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1]]}}}