More Like this

1. Scalable Adaptive PDE Solvers in Arbitrary Domains

   Kumar, Saurabh; Ishii, Masado; Fernando, Milinda; Gao, Boshun; Tan, Kendrick; Hsu, Ming-Chen; Krishnamurthy, Adarsh; Sundar, Hari; Ganapathysubramanian, Baskar (November 2021, SC21: International Conference for High Performance Computing, Networking, Storage and Analysis)

   Efficiently and accurately simulating partial differential equations (PDEs) in and around arbitrarily defined geometries, especially with high levels of adaptivity, has significant implications for different application domains. A key bottleneck in the above process is the fast construction of a ‘good’ adaptively-refined mesh. In this work, we present an efficient novel octree-based adaptive discretization approach capable of carving out arbitrarily shaped void regions from the parent domain: an essential requirement for fluid simulations around complex objects. Carving out objects produces an incomplete octree. We develop efficient top-down and bottom-up traversal methods to perform finite element computations on incomplete octrees. We validate the framework by (a) showing appropriate convergence analysis and (b) computing the drag coefficient for flow past a sphere for a wide range of Reynolds numbers (0(1-10 6 )) encompassing the drag crisis regime. Finally, we deploy the framework on a realistic geometry on a current project to evaluate COVID-19 transmission risk in classrooms. 

   more » « less
2. Decomposing multitwists

   https://doi.org/10.1007/s11854-023-0301-4  

   Fletcher, Alastair N; Vellis, Vyron (April 2024, Journal d'Analyse Mathématique)

   The Decomposition Problem in the class $$LIP(\S^2)$$ is to decompose any bi-Lipschitz map $$f:\S^2 \to \S^2$$ as a composition of finitely many maps of arbitrarily small isometric distortion. In this paper, we construct a decomposition for certain bi-Lipschitz maps which spiral around every point of a Cantor set $$X$$ of Assouad dimension strictly smaller than one. These maps are constructed by considering a collection of Dehn twists on the Riemann surface $$\S^2 \setminus X$$. The decomposition is then obtained via a bi-Lipschitz path which simultaneously unwinds these Dehn twists. As part of our construction, we also show that $$X \subset \S^2$$ is uniformly disconnected if and only if the Riemann surface $$\S^2 \setminus X$$ has a pants decomposition whose cuffs have hyperbolic length uniformly bounded above, which may be of independent interest. 

   more » « less
3. Induced subgraphs and tree decompositions IX. Grid theorem for perforated graphs

   https://doi.org/10.19086/aic.2025.3  

   Alecu, Bogdan; Chudnovsky, Maria; Spirkl, Sophie (March 2025, Advances in Combinatorics)

   The celebrated Erdős-Pósa Theorem, in one formulation, asserts that for every c ∈ N, graphs with no subgraph (or equivalently, minor) isomorphic to the disjoint union of c cycles have bounded treewidth. What can we say about the treewidth of graphs containing no induced subgraph isomorphic to the disjoint union of c cycles? Let us call these graphs c-perforated. While 1-perforated graphs have treewidth one, complete graphs and complete bipartite graphs are examples of 2-perforated graphs with arbitrarily large treewidth. But there are sparse examples, too: Bonamy, Bonnet, Déprés, Esperet, Geniet, Hilaire, Thomassé and Wesolek constructed 2-perforated graphs with arbitrarily large treewidth and no induced subgraph isomorphic to K3 or K3,3; we call these graphs occultations. Indeed, it turns out that a mild (and inevitable) adjustment of occultations provides examples of 2-perforated graphs with arbitrarily large treewidth and arbitrarily large girth, which we refer to as full occultations. Our main result shows that the converse also holds: for every c ∈ N, a c-perforated graph has large treewidth if and only if it contains, as an induced subgraph, either a large complete graph, or a large complete bipartite graph, or a large full occultation. This distinguishes c-perforated graphs, among graph classes purely defined by forbidden induced subgraphs, as the first to admit a grid-type theorem incorporating obstructions other than subdivided walls and their line graphs. More generally, for all c, o ∈ N, we establish a full characterization of induced subgraph obstructions to bounded treewidth in graphs containing no induced subgraph isomorphic to the disjoint union of c cycles, each of length at least o + 2. 

   more » « less
4. On the connection between mpnn and graph transformer.

   Cai, C; Hy, TS; Yu, R; Wang, Y (July 2023, MLResearch Press)

   Graph Transformer (GT) recently has emerged as a new paradigm of graph learning algorithms, outperforming the previously popular Message Passing Neural Network (MPNN) on multiple benchmarks. Previous work shows that with proper position embedding, GT can approximate MPNN arbitrarily well, implying that GT is at least as powerful as MPNN. In this paper, we study the inverse connection and show that MPNN with virtual node (VN), a commonly used heuristic with little theoretical understanding, is powerful enough to arbitrarily approximate the self-attention layer of GT. In particular, we first show that if we consider one type of linear transformer, the so-called Performer/Linear Transformer, then MPNN+ VN with only depth and width can approximate a self-attention layer in Performer/Linear Transformer. Next, via a connection between MPNN+ VN and DeepSets, we prove the MPNN+ VN with width and depth can approximate the self-attention layer arbitrarily well, where is the input feature dimension. Lastly, under some assumptions, we provide an explicit construction of MPNN+ VN with width and depth approximating the self-attention layer in GT arbitrarily well. On the empirical side, we demonstrate that 1) MPNN+ VN is a surprisingly strong baseline, outperforming GT on the recently proposed Long Range Graph Benchmark (LRGB) dataset, 2) our MPNN+ VN improves over early implementation on a wide range of OGB datasets and 3) MPNN+ VN outperforms Linear Transformer and MPNN on the climate modeling task. 

   more » « less
5. Global-in-time semiclassical regularity for the Hartree–Fock equation

   https://doi.org/10.1063/5.0089741  

   Chong, J_J; Lafleche, L.; Saffirio, C. (August 2022, Journal of Mathematical Physics)

   For arbitrarily large times T > 0, we prove the uniform-in-ℏ propagation of semiclassical regularity for the solutions to the Hartree–Fock equation with singular interactions of the form V(x)=±x−a with a∈(0,12). As a by-product of this result, we extend to arbitrarily long times the derivation of the Hartree–Fock and the Vlasov equations from the many-body dynamics provided in the work of Chong et al. [arXiv:2103.10946 (2021)]. 

   more » « less