Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “algorithms scalability”

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 91 records · Page 5

Acceleration of k-Eigenvalue / Criticality Calculations using the Jacobian-Free Newton-Krylov Method

We present a new approach for the $k$--eigenvalue problem using a combination of classical power iteration and the Jacobian--free Newton--Krylov method (JFNK). The method poses the $k$--eigenvalue problem as a fully coupled nonlinear system, which is solved by JFNK with an effective block preconditioning consisting of the power iteration and algebraic multigrid. We demonstrate effectiveness and algorithmic scalability of the method on a 1-D, one group problem and two 2-D two group problems and provide comparison to other efforts using silmilar algorithmic approaches.

97 MATHEMATICS AND COMPUTING↗

Real time operation of high-capacity electric vehicle ridesharing fleets

We study the feasibility of using electric vehicles in online, high-capacity ridepooling systems. Prior work has shown that online algorithms perform well for centrally-controlled, high-capacity ridepool systems. First, we propose a mixed integer linear program to expand past algorithms on ridepooling to electric vehicle fleets with the objective of scheduling vehicle charging to maintain sufficient fleet sizes at various times of day. Then we show a faster, scalable algorithm with similar performance that is practical for full-scale systems. Furthermore, our contributions reinforce the importance of having knowledge and estimates of future demand even when operating in the online setting.

33 ADVANCED PROPULSION SYSTEMS↗

Randomized Algorithms for Symmetric Nonnegative Matrix Factorization

Symmetric Nonnegative Matrix Factorization (SymNMF) is a technique in data analysis and machine learning that approximates a matrix with a product of a nonnegative, low-rank matrix and it transpose. To design faster and more scalable algorithms for SymNMF we develop two randomized algorithms for its computation. The first method uses randomized matrix sketching to compute an initial low-rank approximation to the input matrix and proceeds to uses this as a low-rank input to rapidly compute a SymNMF. The second methods uses randomized leverage score sampling to approximately solve constrained least squares problems. Many successful methods for SymNMF rely on (approximately) solving sequences of constrained least squares problems. Here, we prove theoretically that leverage score sampling can approximately solve constrained least squares problems to e-accuracy. Finally we demonstrate both methods work in practice by applying them to graph clustering tasks on large real world data sets. These experiments show that our methods approximately maintain solution quality and achieve significant speed ups for both large dense and large sparse problems.

97 MATHEMATICS AND COMPUTING↗

Multilevel Convergence Analysis of Multigrid-Reduction-in-Time

This study presents a multilevel convergence framework for multigrid-reduction-in-time (MGRIT) as a generalization of previous two-grid estimates. The framework provides a priori upper bounds on the convergence of MGRIT V- and F-cycles, with different relaxation schemes, by deriving the respective residual and error propagation operators. The residual and error operators are functions of the time-stepping operator, analyzed directly and bounded in the norm, both numerically and analytically. We present various upper bounds of different computational cost and varying sharpness. These upper bounds are complemented by proposing analytic formulae for the approximate convergence factor of V-cycle algorithms that take the number of fine grid time points, the temporal coarsening factors, and the eigenvalues of the time-stepping operator as parameters. The paper concludes with supporting numerical investigations of parabolic (anisotropic diffusion) and hyperbolic (wave equation) model problems. We assess the sharpness of the bounds and the quality of the approximate convergence factors. Observations from these numerical investigations demonstrate the value of the proposed multilevel convergence framework for estimating MGRIT convergence a priori and for the design of a convergent algorithm. We further highlight that observations in the literature are captured by the theory, including that two-level Parareal and multilevel MGRIT with F-relaxation do not yield scalable algorithms and the benefit of a stronger relaxation scheme. An important observation is that with increasing numbers of levels MGRIT convergence deteriorates for the hyperbolic model problem, while constant convergence factors can be achieved for the diffusion equation. The theory also indicates that L-stable Runge--Kutta schemes are more amendable to multilevel parallel-in-time integration with MGRIT than A-stable Runge--Kutta schemes.

97 MATHEMATICS AND COMPUTING↗

A Scalable O(N) Algorithm for Large-Scale Parallel First-Principles Molecular Dynamics Simulations

Traditional algorithms for first-principles molecular dynamics (FPMD) simulations only gain a modest capability increase from current petascale computers, due to their O(N 3 ) complexity and their heavy use of global communications. To address this issue, we are developing a truly scalable O(N) complexity FPMD algorithm, based on density functional theory (DFT), which avoids global communications. The computational model uses a general nonorthogonal orbital formulation for the DFT energy functional, which requires knowledge of selected elements of the inverse of the associated overlap matrix. We present a scalable algorithm for approximately computing selected entries of the inverse of the overlap matrix, based on an approximate inverse technique, by inverting local blocks corresponding to principal submatrices of the global overlap matrix. The new FPMD algorithm exploits sparsity and uses nearest neighbor communication to provide a computational scheme capable of extreme scalability. Accuracy is controlled by the mesh spacing of the finite difference discretization, the size of the localization regions in which the electronic orbitals are confined, and a cutoff beyond which the entries of the overlap matrix can be omitted when computing selected entries of its inverse. We demonstrate the algorithm's excellent parallel scaling for up to O(100K) atoms on O(100K) processors, with a wall-clock time of O(1) minute per molecular dynamics time step.

36 MATERIALS SCIENCE↗

Decentralized Low-Rank State Estimation for Power Distribution Systems

This article considers the low-observability state estimation problem in power distribution networks and develops a decentralized state estimation algorithm leveraging the matrix completion methodology. Matrix completion has been shown to be an effective technique in state estimation that exploits the low dimensionality of the power system measurements to recover missing information. This technique can utilize an approximate (linear) load flow model, or it can be used with no physical models in a network where no information about the topology or line admittance is available. The direct application of matrix completion algorithms requires solving a semi-definite programming (SDP) problem, which becomes computationally challenging for large networks. We therefore develop a decentralized algorithm that capitalizes on the popular proximal alternating direction method of multipliers (proximal ADMM). The method allows us to distribute the computation among different areas of the network, leading to a scalable algorithm. By doing all computations at individual control areas and only communicating with neighboring areas, the algorithm eliminates the need for data to be sent to a central processing unit and thus increases efficiency and contributes to the goal of autonomous control of distribution networks. We illustrate the advantages of the proposed algorithm numerically using standard IEEE test cases.

41 EE - Solar Energy Technologies Office (EE-4S)↗

CAST: Contraction Algorithm for Symmetric Tensors

Tensor contractions represent the most compute-intensive core kernels in ab initio computational quantum chemistry and nuclear physics. Symmetries in these tensor contractions makes them difficult to load balance and scale to large distributed systems. In this paper, we develop an efficient and scalable algorithm to contract symmetric tensors. We introduce a novel approach that avoids data redistribution in contracting symmetric tensors while also avoiding redundant storage and maintaining load balance. We present experimental results on two parallel supercomputers for several symmetric contractions that appear in the CCSD quantum chemistry method. We also present a novel approach to tensor redistribution that can take advantage of parallel hyperplanes when the initial distribution has replicated dimensions, and use collective broadcast when the final distribution has replicated dimensions, making the algorithm very efficient.

distributed memory↗

On the Preconditioning of a Newton-Krylov Solver for a High-Order reconstructed Discontinuous Galerkin Discretization of All-Speed Compressible Flow with Phase Change for Application in Laser-Based Additive Manufacturing

This dissertation focuses on the development of a fully-implicit, high-order compressible ow solver with phase change. The work is motivated by laser-induced phase change applications, particularly by the need to develop large-scale multi-physics simulations of the selective laser melting (SLM) process in metal additive manufacturing (3D printing). Simulations of the SLM process require precise tracking of multi-material solid-liquid-gas interfaces, due to laser-induced melting/ solidi cation and evaporation/condensation of metal powder in an ambient gas. These rapid density variations and phase change processes tightly couple the governing equations, requiring a fully compressible framework to robustly capture the rapid density variations of the ambient gas and the melting/evaporation of the metal powder. For non-isothermal phase change, the velocity is gradually suppressed through the mushy region by a variable viscosity and Darcy source term model. The governing equations are discretized up to 4th-order accuracy with our reconstructed Discontinuous Galerkin spatial discretization scheme and up to 5th-order accuracy with L-stable fully implicit time discretization schemes (BDF2 and ESDIRK3-5). The resulting set of non-linear equations is solved using a robust Newton-Krylov method, with the Jacobian-free version of the GMRES solver for linear iterations. Due to the sti nes associated with the acoustic waves and thermal and viscous/material strength e ects, preconditioning the GMRES solver is essential. A robust and scalable approximate block factorization preconditioner was developed, which utilizes the velocity-pressure (vP) and velocity-temperature (vT) Schur complement systems. This multigrid block reduction preconditioning technique converges for high CFL/Fourier numbers and exhibits excellent parallel and algorithmic scalability on classic benchmark problems in uid dynamics (lid-driven cavity ow and natural convection heat transfer) as well as for laser-induced phase change problems in 2D and 3D.

42 ENGINEERING↗

Next-Generation Optimization under Uncertainty: Structure-Oriented Algorithms

With the advent of the smart grid, renewable technologies, and carbon emission programs, a key concern is the coordination of national infrastructures such as the electricity, natural gas, and water supply network systems. Anticipating and mitigating uncertainty of weather, demands, and contingencies in a more integrated environment is necessary to maximize resource efficiency and prevent cascading failures that can ultimately lead to catastrophic shortages of supplies. This project developed scalable algorithms for stochastic optimization capable of addressing extreme-scale problems (motivated by challenges in the design and operation of national infrastructures). Specifically, the project developed a new family of algorithms to solve continuous stochastic problems to local and global optimality as well as algorithms to solve mixed-integer convex and nonconvex stochastic programs. We developed supporting local and global convergence theory for these algorithms and implemented the algorithms in open-source software packages that can leverage high-performance computing architectures.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Quantitative Parameter Estimation, Model Selection, and Variable Selection in Battery Science

Numerical physics-based models are useful in understanding battery performance and devel- oping optimal battery design architectures. Data science developments have enabled software algorithms to perform data analysis and decision making that traditionally could only be per- formed by technical experts. Traditional workflows of model development - manual parameter estimation through visual comparison of simulations to experimental observations, and model discrimination through expert intuition - are time-consuming, and difficult to justify. This paper compares the conclusions derived from computationally scalable algorithms to conclu- sions developed by expert researchers. This paper illustrates how data science techniques, such as cross-validation and lasso regression, can be used to augment physics-based simulations to perform data analysis such as parameter estimation, model selection, variable selection, and model-guided design of experiment. The validation of these algorithms is that they produce results similar to those of the expert modeler. The algorithms outlined are well-established and the approaches are general, so can be applied to a variety of battery chemistries and architectures. The conclusions reached using these approaches are in agreement with expert analysis (literature results), were reached with minimal human intervention, and provide quantitative justification. By minimizing the amount of expert time, and providing rigorous quantitative justifications, these methods may accelerate battery development.

25 ENERGY STORAGE↗

GPU Accelerated Event Detection Algorithm

Smart grid external require new algorithmic approaches as well as parallel formulations. One of the critical components is the prediction of changes and detection of anomalies within the power grid. The state-of-the-art algorithms are not suited to handle the demands of streaming data analysis. (i) need for events detection algorithms that can scale with the size of data, (ii) need for algorithms that can not only handle multi dimensional nature of the data, but also model both spatial and temporal dependencies in the data, which, for the most part, are highly nonlinear, (iii) need for algorithms that can operate in an online fashion with streaming data. The GAEDA code is a new online anomaly detection techniques that take into account spatial, temporal, multi-dimensional aspects of the data set. The basic idea behind the proposed approach is to (a) to convert a multi-dimensional sequence into a univariate time series that captures the changes between successive windows extracted from the original sequence using singular value decomposition (SVD), and then (b) to apply known anomaly detection techniques for univariate time series. A key challenge for the proposed approach is to make the algorithm scalable to huge datasets by adopting techniques from perturbation theory, incremental SVD analysis. We used recent advances in tensor decomposition techniques which reduce computational complexity to monitor the change between successive windows and detect anomalies in the same manner as described above. Therefore we propose to develop the parallel solutions on many core systems such as GPUs, because these algorithms involve lot of numerical operations and are highly data-parallelizable.

Source record↗

Privacy-Preserving Federated Learning for Science: Challenges and Research Directions

This paper discusses the key challenges and future research directions for privacy-preserving federated learning (PPFL), with a focus on its application to large-scale scientific AI models, in particular, foundation models~(FMs). PPFL enables collaborative model training across distributed datasets while preserving privacy-- an important collaborative approach for science. We discuss the need for efficient and scalable algorithms to address the increasing complexity of FMs, particularly when dealing with heterogeneous clients. In addition, we underscore the need for developing advance privacy-preserving techniques, such as differential privacy, to balance privacy and utility in large FMs emphasizing fairness and incentive mechanisms to ensure equitable participation among heterogeneous clients. Finally, we emphasize the need for a robust software stack supporting scalable and secure PPFL deployments across multiple high-performance computing facilities. We envision that PPFL would play a crucial role to advance scientific discovery and enable large-scale, privacy-aware collaborations across science domains.

Kim, Kibaek [Argonne National Laboratory (ANL)]↗

Exploring temporal community evolution: algorithmic approaches and parallel optimization for dynamic community detection

Abstract Dynamic (temporal) graphs are a convenient mathematical abstraction for many practical complex systems including social contacts, business transactions, and computer communications. Community discovery is an extensively used graph analysis kernel with rich literature for static graphs. However, community discovery in a dynamic setting is challenging for two specific reasons. Firstly, the notion of temporal community lacks a widely accepted formalization, and only limited work exists on understanding how communities emerge over time. Secondly, the added temporal dimension along with the sheer size of modern graph data necessitates new scalable algorithms. In this paper, we investigate how communities evolve over time based on several graph metrics under a temporal formalization. We compare six different algorithmic approaches for dynamic community detection for their quality and runtime. We identify that a vertex-centric (local) optimization method works as efficiently as the classical modularity-based methods. To its advantage, such local computation allows for the efficient design of parallel algorithms without incurring a significant parallel overhead. Based on this insight, we design a shared-memory parallel algorithm DyComPar , which demonstrates between 4 and 18 fold speed-up on a multi-core machine with 20 threads, for several real-world and synthetic graphs from different domains.

97 MATHEMATICS AND COMPUTING↗

Detecting Extreme Events in Gridded Climate Data

Detecting and tracking extreme events in gridded climatological data is a challenging problem on several fronts: algorithms, scalability, and I/O. Successful detection of these events will give climate scientists an alternate view of the behavior of different climatological variables, leading to enhanced scientific understanding of the impacts of events such as heat and cold waves, and on a larger scale, the El Nin o Southern Oscillation. Recent advances in computing power and research in data sciences enabled us to look at this problem with a different perspective from what was previously possible. In this paper we present our computationally efficient algorithms for anomalous cluster detection on climate change big data. We provide results on detection and tracking of surface temperature and geopotential height anomalies, a trend analysis, and a study of relationships between the variables. We also identify the limitations of our approaches, future directions for research and alternate approaches.

climate extremes temperature anomalies reanalysis↗

Parallel Algorithms for the Exascale Era

New parallel algorithms are needed to reach the Exascale level of parallelism with millions of cores. We look at some of the research developed by students in projects at LANL. The research blends ideas from the early days of computing while weaving in the fresh approach brought by students new to the field of high performance computing. We look at reproducibility of global sums and why it is important to parallel computing. Next we look at how the concept of hashing has led to the development of more scalable algorithms suitable for next-generation parallel computers. Nearly all of this work has been done by undergraduates and published in leading scientific journals.

97 MATHEMATICS AND COMPUTING↗

Scalable Implicit Solvers with Dynamic Mesh Adaptation for a Relativistic Drift-Kinetic Fokker–Planck–Boltzmann Model

In this work we consider a relativistic drift-kinetic model for runaway electrons along with a Fokker–Planck operator for small-angle Coulomb collisions, a radiation damping operator, and a secondary knock-on (Boltzmann) collision source. Here, we develop a new scalable fully implicit solver utilizing finite volume and conservative finite difference schemes and dynamic mesh adaptivity. A new data management framework in the PETSc library based on the p4est library is developed to enable simulations with dynamic adaptive mesh refinement (AMR), distributed memory parallelization, and dynamic load balancing of computational work. This framework and the runaway electron solver building on the framework are able to dynamically capture both bulk Maxwellian at the low-energy region and a runaway tail at the high-energy region. To effectively capture features via the AMR algorithm, a new AMR indicator prediction strategy is proposed that is performed alongside the implicit time evolution of the solution. This strategy is complemented by the introduction of computationally cheap feature-based AMR indicators that are analyzed theoretically. Numerical results quantify the advantages of the prediction strategy in better capturing features compared with nonpredictive strategies; and we demonstrate trade-offs regarding computational costs. The robustness with respect to model parameters, algorithmic scalability, and parallel scalability are demonstrated through several benchmark problems including manufactured solutions and solutions of different physics models. We focus on demonstrating the advantages of using implicit time stepping and AMR for runaway electron simulations.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

Scalable Techniques for Stochastic Power Flow Problems (Final Report)

The proposed research focuses on developing scalable algorithms for two-stage security-constrained OPF problems with AC power flow constraints, a class of problems complicated by (i) scale arising from a scenario representation; and (ii) the presence of nonlinearity, nonconvexity, and possibly second-stage discreteness or complementarity. Unfortunately, most existing solvers cannot contend with both challenges simultaneously; accordingly, the proposed research focuses on developing solution techniques that can both scale with the number of scenarios and contend with nonconvexity and second-stage complementarity. We consider three avenues for addressing such problems: (i) Variable sample-size SQP (VS-SQP) methods that combine sparse Quasi-Newton updates with a scalable variance-reduced stochastic gradient scheme for stochastic QP subproblems, allowing for contending with second-stage complementarity via regularization; (ii) Variable sample-size stochastic Interior-point (VS-sIP) schemes that propose a sampling-based regularized (to allow for contending with complementarity) interior-point schemes in which a Schur-complement technique is employed for decomposing the Newton direction computation step; (iii) Variable sample-size tractable ADMM (VS-tADMM) schemes combine variable sample-sizes with carefully designed techniques for resolving each of the nonconvex updates (by leveraging the QCQP structures). We intend to compare the three schemes using performance profiles in terms of solution quality, scalability, etc. and then select one scheme which will then be developed and further refined in Python for purposes of the GO competition.

42 ENGINEERING↗

ASC-ATDM Performance Portability Requirements for 2015-2019

This report outlines the research, development, and support requirements for the Advanced Simulation and Computing (ASC ) Advanced Technology, Development, and Mitigation (ATDM) Performance Portability (a.k.a., Kokkos) project for 2015 - 2019 . The research and development (R&D) goal for Kokkos (v2) has been to create and demonstrate a thread - parallel programming model a nd standard C++ library - based implementation that enables performance portability across diverse manycore architectures such as multicore CPU, Intel Xeon Phi, and NVIDIA Kepler GPU. This R&D goal has been achieved for algorithms that use data parallel pat terns including parallel - for, parallel - reduce, and parallel - scan. Current R&D is focusing on hierarchical parallel patterns such as a directed acyclic graph (DAG) of asynchronous tasks where each task contain s nested data parallel algorithms. This five y ear plan includes R&D required to f ully and performance portably exploit thread parallelism across current and anticipated next generation platforms (NGP). The Kokkos library is being evaluated by many projects exploring algorithm s and code design for NGP. Some production libraries and applications such as Trilinos and LAMMPS have already committed to Kokkos as their foundation for manycore parallelism an d performance portability. These five year requirements includes support required for current and antic ipated ASC projects to be effective and productive in their use of Kokkos on NGP. The greatest risk to the success of Kokkos and ASC projects relying upon Kokkos is a lack of staffing resources to support Kokkos to the degree needed by these ASC projects. This support includes up - to - date tutorials, documentation, multi - platform (hardware and software stack) testing, minor feature enhancements, thread - scalable algorithm consulting, and managing collaborative R&D.

97 MATHEMATICS AND COMPUTING↗