An official website of the United States government
Summation-by-parts (SBP) finite difference methods are widely used in scientific applications alongside a special treatment of boundary conditions through the simultaneous-approximate-term (SAT) technique which enables the valuable proof of numerical stability. Our work is motivated by multi-scale earthquake cycle simulations described by partial differential equations (PDEs) whose discretizations lead to huge systems of equations and often rely on iterative schemes and parallel implementations to make the nu- merical solutions tractable. In this study, we consider 2D, variable coefficient elliptic PDEs in complex geometries discretized with the SBP-SAT method. The multigrid method is a well-known, efficient solver or preconditioner for traditional numerical discretizations, but they have not been well-developed for SBP-SAT methods on HPC platforms. We propose a custom geometric-multigrid pre- conditioned conjugate-gradient (MGCG) method that applies SBP- preserving interpolations. We then present novel, matrix-free GPU kernels designed specifically for SBP operators whose differences from traditional methods make this task nontrivial but that perform 3× faster than SpMV while requiring only a fraction of memory. The matrix-free GPU implementation of our MGCG method per- forms 5× faster than the SpMV counterpart for the largest problems considered (67 million degrees of freedom). When compared to off- the-shelf solvers in the state-of-the-art libraries PETSc and AmgX, our implementation achieves superior performance in both itera- tions and overall runtime. The method presented in this work offers an attractive solver for simulations using the SBP-SAT method.
more »
« less
A multigrid method for kernel functions acting on interacting structures with applications to biofluids
Simulating the dynamics of discretized interacting structures whose relationship is dictated by a kernel function gives rise to a large dense matrix. We propose a multigrid solver for such a matrix that exploits not only its data-sparsity resulting from the decay of the kernel function but also the regularity of the geometry of the structures and the quantities of interest distributed on them. Like the well-known multigrid method for large sparse matrices arising from boundary-value problems, our method requires a smoother for removing high-frequency terms in solution errors, a strategy for coarsening a grid, and a pair of transfer operators for exchanging information between two grids. We develop new techniques for these processes that are tailored to a kernel function acting on discretized interacting structures. They are matrix-free in the sense that there is no need to construct the large dense matrix. Numerical experiments on a variety of bio-inspired microswimmers immersed in a Stokes flow demonstrate the effectiveness and efficiency of the proposed multigrid solver. In the case of free swimmers that must maintain force and torque balance, additional sparse rows and columns need to be appended to the dense matrix above. We develop a matrix-free fast solver for this bordered matrix as well, in which the multigrid method is a key component.
more »
« less
- Award ID(s):
- 2408964
- PAR ID:
- 10534621
- Publisher / Repository:
- Elsevier Inc.
- Date Published:
- Journal Name:
- Journal of computational physics
- Volume:
- 494
- ISSN:
- 0021-9991
- Page Range / eLocation ID:
- 112506
- Subject(s) / Keyword(s):
- Multigrid Kernel function Block Gauss-Seidel Method of regularized Stokeslets Fluid-structure interaction
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Kernel methods for solving partial differential equations work coordinate-free on the surface and yield high approximation rates for smooth solutions. Localized Lagrange bases have proven to alleviate the computational complexity of usual kernel methods for data fitting problems, but the efficient numerical solution of the ill-conditioned linear systems of equations arising from kernel- based Galerkin solutions to PDEs is a challenging problem which has not been addressed in the literature so far. In this article we apply the framework of the geometric multigrid method with a τ ≥ 2-cycle to scattered, quasi-uniform point clouds on the surface. We show that the resulting solver can be accelerated by using the Lagrange function decay and obtain satisfying convergence rates by a rigorous analysis. In particular, we show that the computational cost of the linear solver scales log-linear in the degrees of freedom.more » « less
-
null (Ed.)Recent spectral graph sparsification techniques have shown promising performance in accelerating many numerical and graph algorithms, such as iterative methods for solving large sparse matrices, spectral partitioning of undirected graphs, vectorless verification of power/thermal grids, representation learning of large graphs, etc. However, prior spectral graph sparsification methods rely on fast Laplacian matrix solvers that are usually challenging to implement in practice. This work, for the first time, introduces a solver-free approach (SF-GRASS) for spectral graph sparsification by leveraging emerging spectral graph coarsening and graph signal processing (GSP) techniques. We introduce a local spectral embedding scheme for efficiently identifying spectrally-critical edges that are key to preserving graph spectral properties, such as the first few Laplacian eigenvalues and eigenvectors. Since the key kernel functions in SF-GRASS can be efficiently implemented using sparse-matrix-vector-multiplications (SpMVs), the proposed spectral approach is simple to implement and inherently parallel friendly. Our extensive experimental results show that the proposed method can produce a hierarchy of high-quality spectral sparsifiers in nearly-linear time for a variety of real-world, large-scale graphs and circuit networks when compared with prior state-of-the-art spectral methods.more » « less
-
Abstract Discretization of flow in fractured porous media commonly lead to large systems of linear equations that require dedicated solvers. In this work, we develop an efficient linear solver and its practical implementation for mixed‐dimensional scalar elliptic problems. We design an effective preconditioner based on approximate block factorization and algebraic multigrid techniques. Numerical results on benchmarks with complex fracture structures demonstrate the effectiveness of the proposed linear solver and its robustness with respect to different physical and discretization parameters.more » « less
-
This work studies three multigrid variants for matrix-free finite-element computations on locally refined meshes: geometric local smoothing, geometric global coarsening (both h -multigrid), and polynomial global coarsening (a variant of p -multigrid). We have integrated the algorithms into the same framework—the open source finite-element library deal.II —, which allows us to make fair comparisons regarding their implementation complexity, computational efficiency, and parallel scalability as well as to compare the measurements with theoretically derived performance metrics. Serial simulations and parallel weak and strong scaling on up to 147,456 CPU cores on 3,072 compute nodes are presented. The results obtained indicate that global-coarsening algorithms show a better parallel behavior for comparable smoothers due to the better load balance, particularly on the expensive fine levels. In the serial case, the costs of applying hanging-node constraints might be significant, leading to advantages of local smoothing, even though the number of solver iterations needed is slightly higher. When using p - and h -multigrid in sequence ( hp -multigrid), the results indicate that it makes sense to decrease the degree of the elements first from a performance point of view due to the cheaper transfer.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1016/j.jcp.2023.112506
