New Algebraic Fast Algorithms for $N$-body Problems in Two and Three Dimensions

[2309.14085] New Algebraic Fast Algorithms for $N$-body Problems in Two and Three Dimensions Skip to main content Search Submit Donate Log in Search arXiv Press Enter to search · Advanced search Mathematics > Numerical Analysis arXiv:2309.14085 (math) [Submitted on 25 Sep 2023 ( v1 ), last revised 29 Nov 2024 (this version, v3)] Title: New Algebraic Fast Algorithms for $N$-body Problems in Two and Three Dimensions Authors: Ritesh Khan , Sivaram Ambikasaran View a PDF of the paper titled New Algebraic Fast Algorithms for $N$-body Problems in Two and Three Dimensions, by Ritesh Khan and 1 other authors View PDF HTML (experimental) Abstract: We present two new algebraic multilevel hierarchical matrix algorithms to perform fast matrix-vector product (MVP) for $N$-body problems in $d$ dimensions, namely efficient $\mathcal{H}^2_{*}$ (fully nested algorithm, i.e., $\mathcal{H}^2$ matrix-like algorithm) and $(\mathcal{H}^2 + \mathcal{H})_{*}$ (semi-nested algorithm, i.e., cross of $\mathcal{H}^2$ and $\mathcal{H}$ matrix-like algorithms). The efficient $\mathcal{H}^2_{*}$ and $(\mathcal{H}^2 + \mathcal{H})_{*}$ hierarchical representations are based on our recently introduced weak admissibility condition in higher dimensions, where the admissible clusters are the far-field and the vertex-sharing clusters. Due to the use of nested form of the bases, the proposed hierarchical matrix algorithms are more efficient than the non-nested algorithms ($\mathcal{H}$ matrix algorithms). We rely on purely algebraic low-rank approximation techniques (e.g., ACA and NCA) and develop both algorithms in a black-box fashion. Another noteworthy contribution of this article is that we perform a comparative study of the proposed algorithms with different algebraic (NCA or ACA-based compression) fast MVP algorithms in $2$D and $3$D. The fast algorithms are tested on various kernel matrices and applied to get fast iterative solutions of a dense linear system arising from the discretized integral equations and radial basis function interpolation. Notably, all the algorithms are developed in a similar fashion in $\texttt{C++}$ and tested within the same environment, allowing for meaningful comparisons. The numerical results demonstrate that the proposed algorithms are competitive to the NCA-based standard $\mathcal{H}^2$ matrix algorithm with respect to the memory and time. The C++ implementation of the proposed algorithms is available at this https URL . Comments: 44 pages Subjects: Numerical Analysis (math.NA) ; Mathematical Physics (math-ph) MSC classes: 65F55, 65D12, 65R20, 65D05, 65R10 Cite as: arXiv:2309.14085 [math.NA] (or arXiv:2309.14085v3 [math.NA] for this version) https://doi.org/10.48550/arXiv.2309.14085 Focus to learn more arXiv-issued DOI via DataCite Journal reference: Communications in Computational Physics, Volume 37(4), 2025 Related DOI : https://doi.org/10.4208/cicp.OA-2024-0100 Focus to learn more DOI(s) linking to related resources Submission history From: Ritesh Khan [ view email ] [v1] Mon, 25 Sep 2023 12:29:23 UTC (5,868 KB) [v2] Sat, 27 Apr 2024 11:40:28 UTC (4,326 KB) [v3] Fri, 29 Nov 2024 15:59:18 UTC (6,250 KB) Full-text links: Access Paper: View a PDF of the paper titled New Algebraic Fast Algorithms for $N$-body Problems in Two and Three Dimensions, by Ritesh Khan and 1 other authors View PDF HTML (experimental) TeX Source view license Current browse context: math.NA < prev | next > new | recent | 2023-09 Change to browse by: cs cs.NA math math-ph math.MP References & Citations NASA ADS Google Scholar Semantic Scholar export BibTeX citation Loading... BibTeX formatted citation × loading... Data provided by: Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer ( What is the Explorer? ) Connected Papers Toggle Connected Papers ( What is Connected Papers? ) Litmaps Toggle Litmaps ( What is Litmaps? ) scite.ai Toggle scite Smart Citations ( What are Smart Citations? ) Code, Data, Media Code, Data and Media Associated with this Article alphaXiv Toggle alphaXiv ( What is alphaXiv? ) Links to Code Toggle CatalyzeX Code Finder for Papers ( What is CatalyzeX? ) DagsHub Toggle DagsHub ( What is DagsHub? ) GotitPub Toggle Gotit.pub ( What is GotitPub? ) Huggingface Toggle Hugging Face ( What is Huggingface? ) ScienceCast Toggle ScienceCast ( What is ScienceCast? ) Demos Demos Replicate Toggle Replicate ( What is Replicate? ) Spaces Toggle Hugging Face Spaces ( What is Spaces? ) Spaces Toggle TXYZ.AI ( What is TXYZ.AI? ) Related Papers Recommenders and Search Tools Link to Influence Flower Influence Flower ( What are Influence Flowers? ) Core recommender toggle CORE Recommender ( What is CORE? ) Author Venue Institution Topic About arXivLabs arXivLabs: experimental projects with community collaborators arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website. Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them. Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs . Which authors of this paper are endorsers? | Disable MathJax ( What is MathJax? ) We gratefully acknowledge support from our major funders , member institutions , , and all contributors. About · Help · Contact · Subscribe · Copyright · Privacy · Accessibility · Operational Status (opens in new tab) Major funding support from

Related documents

• No infinite spin in the $n$-body problem in all dimensions#1117962
• Isogeometric multi-patch preconditioner for time-dependent electromagnetic problems#1130290
• Nonsymmetric sign-changing solutions for the partially overdetermined eigenvalue problem on a hollow cylinder#612707
• Nonsymmetric sign-changing solutions for the partially overdetermined eigenvalue problem on a hollow cylinder#611230
• Twisted and intermediate eigenvalue problems in shape optimisation#208691