Search NASA⌕ Search

SEARCH · Search NASA

Results for “Laplacian”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 109 records · Page 6
All sourcesNASA NTRSDOE OSTI
DOE OSTI2021

Data-driven Distributed Learning of Multi-agent Systems: A Koopman Operator Approach

Koopman operator theory provides a model-free technique for studying nonlinear dynamical systems purely from data. Since the Koopman operator is infinite-dimensional, researchers have developed several methods that provide a finite-dimensional approximation of the Koopman operator so that it can be applied for practical use cases. One common thing with most of the methods is that their solutions are obtained by solving a centralized minimization problem. In this work, we treat the dynamical system to be a multi-agent system and propose an algorithm to compute the finite-dimensional approximation of the Koopman operator in a distributed manner using the knowledge of the topology of the underlying multi-agent system. The proposed distributed approach is shown to be equivalent to the centralized learning problem and results in a sparse Koopman whose block structure mimics the Laplacian of the multi-agent system. Extensive simulation studies illustrate the proposed framework on the network of oscillators and the IEEE 68 bus system.

Nandanoori, Sai Pushpak↗
DOE OSTI2020

A High-Throughput Solver for Marginalized Graph Kernels on GPU

Here, we present the design and optimization of a solver for efficient and high-throughput computation of the marginalized graph kernel on General Purpose GPUs. The graph kernel is computed using the conjugate gradient method to solve a generalized Laplacian of the tensor product between a pair of graphs. To cope with the large gap between the instruction throughput and the memory bandwidth of the GPUs, our solver forms the graph tensor product on-the-fly without storing it in memory. This is achieved by using threads in a warp cooperatively to stream the adjacency and edge label matrices of individual graphs by small square matrix blocks called tiles, which are then staged in registers and the shared memory for later reuse. Warps across a thread block can further share tiles via the shared memory to increase data reuse. We exploit the sparsity of the graphs hierarchically by storing only non-empty tiles using a coordinate format and nonzero elements within each tile using bitmaps. We propose a new partition-based reordering algorithm for aggregating nonzero elements of the graphs into fewer but denser tiles to further exploit sparsity. We carry out extensive theoretical analyses on the graph tensor product primitives for tiles of various density and evaluate their performance on synthetic and real-world datasets. Our solver delivers three to four orders of magnitude speedup over existing CPU-based solvers such as GraKeL and GraphKernels. The capability of the solver enables kernel-based learning tasks at unprecedented scales.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Online Event Detection in Synchrophasor Data with Graph Signal Processing

Online detection of anomalies is crucial to enhancing the reliability and resiliency of power systems. We propose a novel data-driven online event detection algorithm with synchrophasor data using graph signal processing. In addition to being extremely scalable, our proposed algorithm can accurately capture and leverage the spatio-temporal correlations of the streaming PMU data. This paper also develops a general technique to decouple spatial and temporal correlations in multiple time series. Finally, we develop a unique framework to construct a weighted adjacency matrix and graph Laplacian for product graph. Case studies with real-world, large-scale synchrophasor data demonstrate the scalability and accuracy of our proposed event detection algorithm. Compared to the state-of-the-art benchmark, the proposed method not only achieves higher detection accuracy but also yields higher computational efficiency.

Event detection↗
DOE OSTI2021

Distribution Grid Modeling Using Smart Meter Data

The knowledge of distribution grid models, including topologies and line impedances, is essential for grid monitoring, control and protection. However, such information is often unavailable, incomplete or outdated. The increasing deployment of smart meters (SMs) provides a unique opportunity to tackle this issue. This paper proposes a two-stage framework for distribution grid modeling using SM data. In the first stage, the network topology is identified by reconstructing a weighted Laplacian matrix of distribution networks. In the second stage, a least absolute deviations (LAD) regression model is developed for estimating line impedance of a single branch based on the nonlinear (inverse) power flow model, wherein a conductor library is leveraged to narrow down the solution space. The LAD regression model is originally a mixed-integer nonlinear program whose continuous relaxation is still non-convex. Furthermore, we specially address its convex relaxation and discuss the exactness. The modified regression model is then embedded within a bottom-up sweep algorithm to achieve the identification across the network in a branch-wise manner. Numerical results on the IEEE 13-bus, 37-bus and 69-bus test feeders validate the effectiveness of the proposed methods.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2022

A Laplace-Domain Circuit Model for Fault and Stability Analysis Considering Unbalanced Topology

For systems subject to unbalanced faults, analytical model building for stability assessment is a challenging task. This letter presents a straightforward modeling approach. A generalized dynamic circuit representation is achieved by use of the Laplacian transform variable s . Here, we translate the voltage and current relationship at the fault location into the relationship of three subsystems. The final circuit model is an interconnected sequence network with impedances in the Laplace domain. This circuit can be directly converted from a steady-state sequence network. This modeling procedure is illustrated by an example case of an induction motor served by a grid through a series compensated line. Electromagnetic transient simulation results demonstrate that sub-synchronous oscillations can be mitigated when a single-line to ground fault is applied at the motor terminal. Stability analysis results based on the dynamic circuit corroborate the simulation results. What's more, the derived circuit effortlessly reveals why unbalance can enhance stability.

42 ENGINEERING↗
DOE OSTI2024

Matrix-Free High-Performance Saddle-Point Solvers for High-Order Problems in \(\boldsymbol{H}(\operatorname{\textbf{div}})\)

Here, this work describes the development of matrix-free GPU-accelerated solvers for high-order finite element problems in H(div). The solvers are applicable to grad-div and Darcy problems in saddle-point formulation, and have applications in radiation diffusion and porous media flow problems, among others. Using the interpolation–histopolation basis, efficient matrix-free preconditioners can be constructed for the (1, 1)-block and Schur complement of the block system. With these approximations, block-preconditioned MINRES converges in a number of iterations that is independent of the mesh size and polynomial degree. The approximate Schur complement takes the form of an M-matrix graph Laplacian and therefore can be well-preconditioned by highly scalable algebraic multigrid methods. High-performance GPU-accelerated algorithms for all components of the solution algorithm are developed, discussed, and benchmarked. Numerical results are presented on a number of challenging test cases, including the “crooked pipe” grad-div problem, the SPE10 reservoir modeling benchmark problem, and a nonlinear radiation diffusion test case.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Reducing Operator Complexity of Galerkin Coarse-grid Operators with Machine Learning

Here, we propose a data-driven and machine-learning-based approach to compute non-Galerkin coarse-grid operators in multigrid (MG) methods, addressing the well-known issue of increasing operator complexity. Guided by the MG theory on spectrally equivalent coarse-grid operators, we have developed novel machine learning algorithms that utilize neural networks combined with smooth test vectors from multigrid eigenvalue problems. The proposed method demonstrates promise in reducing the complexity of coarse-grid operators while maintaining overall MG convergence for solving parametric partial differential equation problems. Numerical experiments on anisotropic rotated Laplacian and linear elasticity problems are provided to showcase the performance and comparison with existing methods for computing non-Galerkin coarse-grid operators.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2026

Two-Level Sketching Alternating Anderson Acceleration for Complex Physics Applications

We present a novel two-level sketching extension of the Alternating Anderson–Picard (AAP) method for accelerating fixed-point iterations in challenging single- and multiphysics simulations governed by discretized PDEs. Our approach combines a static, physics-based projection that reduces the least-squares (LS) problem to the most informative field (e.g., via Schur-complement insight) with a dynamic, algebraic sketching stage driven by a backward stability analysis under Lipschitz continuity. We introduce inexpensive estimators for stability thresholds and cache-aware randomized selection strategies to balance computational cost against memory access overhead. The resulting algorithm solves reduced LS systems in place, minimizes memory footprints, and seamlessly alternates between low-cost Picard updates and Anderson mixing. Implemented in Julia, our two-level sketching AAP achieves up to 50% time-to-solution reductions compared to standard Anderson acceleration—without degrading convergence rates—on benchmark problems including Stokes, 𝑝-Laplacian, bidomain, and Navier–Stokes formulations at varying problem sizes. These results demonstrate the method’s robustness, scalability, and potential for integration into high-performance scientific computing frameworks. Our implementation is available open source in the AAP.jl library.

Barnafi, Nicolas [University of Chile, Santiago]↗
DOE OSTI2023

Bound-preserving finite element approximations of the Keller–Segel equations

We report this paper aims to develop numerical approximations of the Keller–Segel equations that mimic at the discrete level the lower bounds and the energy law of the continuous problem. We solve these equations for two unknowns: the organism (or cell) density, which is a positive variable, and the chemoattractant density, which is a non-negative variable. We propose two algorithms, which combine a stabilized finite element method and a semi-implicit time integration. The stabilization consists of a nonlinear artificial diffusion that employs a graph-Laplacian operator and a shock detector that localizes local extrema. As a result, both algorithms turn out to be nonlinear and can generate cell and chemoattractant numerical densities fulfilling lower bounds. However, the first algorithm requires a suitable constraint between the space and time discrete parameters, whereas the second one does not. We design the latter to attain a discrete energy law on acute meshes. We report some numerical experiments to validate the theoretical results on blowup and nonblowup phenomena. In the blowup setting, we identify a locking phenomenon that relates the L ∞ (Ω)-norm to the L 1 (Ω)-norm limiting the growth of the singularity when supported on a macroelement.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

COWALKER:EFFECTIVE TRANSPORT PROPERTIES OF COMPOSITE MATERIALS

SF-23-026 This software computes effective transport properties of composite materials involving fibers and nanoparticles using a random-walk algorithm that efficiently scales to an arbitrary number of processes and cores. Effective transport properties (thermal, electrical) are key to bridge the microstructure of complex materials with its macroscopic behavior. Traditional approaches either use effective medium approximations (closed mathematical expressions that are approximation for certain conditions) or continuum simulation models such as finite element or finite volume, which require the generation of a mesh for each configuration explored. cowalker leverages the equivalence between laplacian or heat equation-based models and random walks to compute the asymptotic transport properties from an ensemble of first sojourn times of a random walker moving through the composite material. This allows us to directly define a composite material as a collection of particles and use algorithms developed for molecular dynamics to quickly compute the intersection of the walker with the different interfaces in the material. cowalker is developed in C++, and it relies on the GNU Scientific Library for random generation. cowalker is currently delivered as source code, so the GSL library is not included in cowalker's distribution. A more userfriendly version, cowalker.jl is currently in development and will be released as part of cowalker.

YANGUAS-GIL, ANGEL↗
DOE OSTI2024

nuclear-score-maximization v1.0

This software library presents efficient and multithreaded implementations of matrix low rank approximation via column selection in C++17 code. The algorithms are described in Fornace, Mark, and Michael Lindsey. "Column and row subset selection using nuclear scores: algorithms and theory for Nystro m approximation, CUR decomposition, and graph Laplacian reduction." arXiv preprint arXiv:2407.01698 (2024). The presented methods are by-and-large ver novel, have provable approximation guarantees, multiple use-cases, and exhibit higher quality approximations on a variety of studied examples.

Fornace, Mark↗
DOE OSTI2021

Decoupled Fréchet kernels based on a fractional viscoacoustic wave equation

We formulate the Fréchet kernel computation using the adjoint-state method based on a fractional viscoacoustic wave equation. We first numerically prove that both the 1/2- and the 3/2-order fractional Laplacian operators are self-adjoint. Using this property, we show that the adjoint wave propagator preserves the dispersion and compensates the amplitude, while the time-reversed adjoint wave propagator behaves identically as the forward propagator with the same dispersion and dissipation characters. Without introducing rheological mechanisms, this formulation adopts an explicit Q parameterization, which avoids the implicit Q in the conventional viscoacoustic/viscoelastic full waveform inversion (Q-FWI). In addition, because of the decoupling of operators in the wave equation, the viscoacoustic Fréchet kernel is separated into three distinct contributions with clear physical meanings: lossless propagation, dispersion, and dissipation. Here, we find that the lossless propagation kernel dominates the velocity kernel, while the dissipation kernel dominates the attenuation kernel over the dispersion kernel.

58 GEOSCIENCES↗
DOE OSTI2025

automesh: Automatic mesh generation in Rust

automesh is an open-source Rust software program that uses a segmentation, typically generated from a 3D image stack, to create a finite element mesh, composed either of hexahedral (volumetric) or triangular (isosurface) elements. automesh converts between segmentation formats (.npy, .spn) and mesh formats (.exo, .inp, .mesh, .stl, .vtk). automesh can defeature voxel domains, apply Laplacian and Taubin smoothing, and output mesh quality metrics. automesh uses an internal octree for fast performance.

Hovey, Chad Brian [Sandia National Laboratories (S↗
DOE OSTI2022

Randomized Cholesky Preconditioning for Graph Partitioning Applications

A graph is a mathematical representation of a network; we say it consists of a set of vertices, which are connected by edges. Graphs have numerous applications in various fields, as they can model all sorts of connections, processes, or relations. For example, graphs can model intricate transit systems or the human nervous system. However, graphs that are large or complicated become difficult to analyze. This is why there is an increased interest in the area of graph partitioning, reducing the size of the graph into multiple partitions. For example, partitions of a graph representing a social network might help identify clusters of friends or colleagues. Graph partitioning is also a widely used approach to load balancing in parallel computing. The partitioning of a graph is extremely useful to decompose the graph into smaller parts and allow for easier analysis. There are different ways to solve graph partitioning problems. For this work, we focus on a spectral partitioning method which forms a partition based upon the eigenvectors of the graph Laplacian (details presented in Acer, et. al.). This method uses the LOBPCG algorithm to compute these eigenvectors. LOBPCG can be accelerated by an operator called a preconditioner. For this internship, we evaluate a randomized Cholesky (rchol) preconditioner for its effectiveness on graph partitioning problems with LOBPCG. We compare it with two standard preconditioners: Jacobi and Incomplete Cholesky (ichol). This research was conducted from August to December 2021 in conjunction with Sandia National Laboratories.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Randomized Cholesky Preconditioning for Graph Partitioning Applications

Graph partitioning has emerged as an area of interest due to its use in various applications in computational research. One way to partition a graph is to solve for the eigenvectors of the corresponding graph Laplacian matrix. This project focuses on the eigensolver LOBPCG and the evaluation of a new preconditioner: Randomized Cholesky Factorization (rchol). This proconditioner was tested for its speed and accuracy against other well-known preconditioners for the method. After experiments were run on several known test matrices, rchol appears to be a better preconditioner for structured matrices. This research was sponsored by National Nuclear Security Administration Minority Serving Institutions Internship Program (NNSA-MSIIP) and completed at host facility Sandia National Laboratories. As such, after discussion of the research project itself, this report contains a brief reflection on experience gained as a result of participating in the NNSA-MSIIP.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

A 6th Order Mehrstellen Finite Volume Discretization of Poisson's Equation in Three Dimensions

We discuss the derivation of a new, sixth-order finite volume scheme for Poisson’s equation on 3D Cartesian equispaced grids. The scheme is based on a discretization of the Laplace operator with a compact (Mehrstellen) 27-point stencil. To achieve sixth order convergence the right hand side of the equation is replaced with a discrete operator that involves the discrete Laplace and Biharmonic operators and the sum of discrete fourth-order cross derivatives applied to the charge function. Numerical tests demonstrate the superiority of the proposed method compared to the well known schemes associated with the 7-point and 19-point discretizations of the Laplacian.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

Theories and Constraints for Massive Higher Spins (Final Technical Report)

The goal of this project was to develop methods for constraining the scattering amplitudes of interacting theories containing massive higher spin particles, and to apply these methods to search for, constrain, and apply theories containing massive high spins. During the 3 year term of the project, 15 papers containing results from the project were published in peer reviewed journals. Highlights of these results include: proofs of the best possible strong coupling scales for theories with massive spin 2 particles, causality constraints on couplings in such theories, the discovery of new effective field theories with extended shift symmetries on curved space, the discovery of a new symmetry of the decoupling limit of massive gravity, a study of the possible shapes of graviton non-gaussianities during inflation, classification results of supersymmetric partially massless fields, and the development of the geometric bootstrap, a novel method to generate new mathematical results about the spectrum of various Laplacian operators on closed Einstein manifolds.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗