skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


This content will become publicly available on February 1, 2026

Title: Kernel multigrid on manifolds
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
Award ID(s):
2010051
PAR ID:
10549880
Author(s) / Creator(s):
;
Publisher / Repository:
Journal of Complexity
Date Published:
Journal Name:
Journal of Complexity
Volume:
86
Issue:
C
ISSN:
0885-064X
Page Range / eLocation ID:
101900
Subject(s) / Keyword(s):
Geometric multigrid Partial differential equations on manifold Kernel-based Galerkin methods Localized Lagrange basis
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ACES (Ed.)
    We present a family of numerical methods for the solution of Maxwell’s equations, with application to simulation, optimization, and design. In particular, a novel rectangular-polar integral equation solver is mentioned which can produce solutions to the time harmonic Maxwell’s equations, with high order accuracy, for general 2D and 3D structures, with an extension to time domain problems on the basis of a time re-centering synthesis technique. An effective integral equation acceleration method, the IFGF method (Interpolated Factored Green Function), is used, which evaluates the action of Green function-based integral operators for an 𝑁𝑁-point surface discretization at a computational cost of 𝑂(𝑁log𝑁) operations without recourse to the FFT—thus, lending itself to effective distributed memory parallelization. Computational illustrations include applications to photonic optimization and design. 
    more » « less
  2. In this paper, we present efficient numerical schemes based on the Lagrange multiplier approach for the Navier-Stokes equations. By introducing a dynamic equation (involving the kinetic energy, the Lagrange multiplier, and a regularization parameter), we form a new system which incorporates the energy evolution process but is still equivalent to the original equations. Such nonlinear system is then discretized in time based on the backward differentiation formulas, resulting in a dynamically regularized Lagrange multiplier (DRLM) method. First- and second-order DRLM schemes are derived and shown to be unconditionally energy stable with respect to the original variables. The proposed schemes require only the solutions of two linear Stokes systems and a scalar quadratic equation at each time step. Moreover, with the introduction of the regularization parameter, the Lagrange multiplier can be uniquely determined from the quadratic equation, even with large time step sizes, without affecting accuracy and stability of the numerical solutions. Fully discrete energy stability is also proved with the Marker-and-Cell (MAC) discretization in space. Various numerical experiments in two and three dimensions verify the convergence and energy dissipation as well as demonstrate the accuracy and robustness of the proposed DRLM schemes. 
    more » « less
  3. ppohBEM is an open-source software package im- plementing the boundary element method. One of its main software tasks is the solution of the dense linear system of equations, for which, ppohBEM relies on another software package called HACApK. To reduce the cost of solving the linear system, HACApK hierarchically compresses the coefficient matrix using adaptive cross approximation. This hierarchical compression greatly reduces the storage and time complexities of the solver and enables the solution of large-scale boundary value problems. To extend the capability of ppohBEM, in this paper, we carefully port the HACApK’s linear solver onto GPU clusters. Though the potential of the GPUs has been widely accepted in high-performance computing, it is still a challenge to utilize the GPUs for a solver, like HACApK’s, that requires fine-grained computation and global communication. First, to utilize the GPUs, we integrate the batched GPU kernel that was recently released in the MAGMA software package. We discuss several techniques to improve the performance of the batched kernel. We then study various techniques to address the inter-GPU communication and study their effects on state-of- the-art GPU clusters. We believe that the techniques studied in this paper are of interest to a wide range of software packages running on GPUs, especially with the increasingly complex node architectures and the growing costs of the communication. We also hope that our efforts to integrate the GPU kernel or to setup the inter-GPU communication will influence the design of the future-generation batched kernels or the communication layer within a software stack. 
    more » « less
  4. In this paper, we consider minimizers for nonlocal energy functionals generalizing elastic energies that are connected with the theory of peridynamics [19] or nonlocal diffusion models [1]. We derive nonlocal versions of the Euler-Lagrange equations under two sets of growth assumptions for the integrand. Existence of minimizers is shown for integrands with joint convexity (in the function and nonlocal gradient components). By using the convolution structure, we show regularity of solutions for certain Euler-Lagrange equations. No growth assumptions are needed for the existence and regularity of minimizers results, in contrast with the classical theory. 
    more » « less
  5. Abstract Chemotaxis phenomena govern the directed movement of microorganisms in response to chemical stimuli. In this paper, we investigate two Keller–Segel systems of reaction–advection–diffusion equations modeling chemotaxis on thin networks. The distinction between two systems is driven by the rate of diffusion of the chemo-attractant. The intermediate rate of diffusion is modeled by a coupled pair of parabolic equations, while the rapid rate is described by a parabolic equation coupled with an elliptic one. Assuming the polynomial rate of growth of the chemotaxis sensitivity coefficient, we prove local well-posedness of both systems on compact metric graphs, and, in particular, prove existence of unique classical solutions. This is achieved by constructing sufficiently regular mild solutions via analytic semigroup methods and combinatorial description of the heat kernel on metric graphs. The regularity of mild solutions is shown by applying abstract semigroup results to semi-linear parabolic equations on compact graphs. In addition, for logistic-type Keller–Segel systems we prove global well-posedness and, in some special cases, global uniform boundedness of solutions. 
    more » « less