SEARCH · Engineering Papers

Results for “Graph algorithms”

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.

SourceResearch connectionFrom yearThrough year

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

At least 523 records · Page 29

All sources NASA NTRS DOE OSTI

DOE OSTI2025

Classical eikonal from Magnus expansion

In a classical scattering problem, the classical eikonal is defined as the generator of the canonical transformation that maps in-states to out-states. It can be regarded as the classical limit of the log of the quantum S-matrix. In a classical analog of the Born approximation in quantum mechanics, the classical eikonal admits an expansion in oriented tree graphs, where oriented edges denote retarded/advanced worldline propagators. The Magnus expansion, which takes the log of a time-ordered exponential integral, offers an efficient method to compute the coefficients of the tree graphs to all orders. We exploit a Hopf algebra structure behind the Magnus expansion to develop a fast algorithm which can compute the tree coefficients up to the 12th order (over half a million trees) in less than an hour. In a relativistic setting, our methods can be applied to the post-Minkowskian (PM) expansion for gravitational binaries in the worldline formalism. We demonstrate the methods by computing the 3PM eikonal and find agreement with previous results based on amplitude methods. Importantly, the Magnus expansion yields a finite eikonal, while the naïve eikonal based on the time-symmetric propagator is infrared-divergent from 3PM on.

Black Holes↗

DOE OSTI2025

Dirac traces and the Tutte polynomial

Perturbative calculations involving fermion loops in quantum field theories require tracing over Dirac matrices. A simple way to regulate the divergences that generically appear in these calculations is dimensional regularisation, which has the consequence of replacing 4-dimensional Dirac matrices with d-dimensional counterparts for arbitrary complex values of d. In this work, a connection between traces of d-dimensional Dirac matrices and computations of the Tutte polynomial of associated graphs is proven. The time complexity of computing Dirac traces is analysed by this connection, and improvements to algorithms for computing Dirac traces are proposed.

Renormalization and Regularization↗

DOE OSTI2021

A Confidence-Guided Technique for Tracking Time-Varying Features

Application scientists often employ feature tracking algorithms to capture the temporal evolution of various features in their simulation data. However, as the complexity of the scientific features is increasing with the advanced simulation modeling techniques, quantification of reliability of the feature tracking algorithms is becoming important. One of the desired requirements for any robust feature tracking algorithm is to estimate its confidence during each tracking step so that the results obtained can be interpreted without any ambiguity. To address this, we develop a confidence-guided feature tracking algorithm that allows reliable tracking of user-selected features and presents the tracking dynamics using a graph-based visualization along with the spatial visualization of the tracked feature. Here, the efficacy of the proposed method is demonstrated by applying it to two scientific datasets containing different types of time-varying features.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2026

EvoDiffMol: evolutionary diffusion framework for 3D molecular design with optimized properties

Designing molecules with specific target properties remains a fundamental challenge in computational chemistry. While existing approaches show promise, most rely on simplified representations like SMILES strings or 2D graphs that lack essential three-dimensional geometric information. We present EvoDiffMol, a computational framework that integrates evolutionary algorithms with three-dimensional diffusion models for property-driven molecular generation. The method operates through adaptive evolutionary optimization, where population-based selection guides the generation process toward desired property landscapes. EvoDiffMol supports both unconstrained molecular design and scaffold-constrained generation that preserves fixed substructures while optimizing complementary regions. Comprehensive evaluation demonstrates exceptional performance, achieving the highest drug-likeness score (0.94) among all compared state-of-the-art methods while maintaining excellent validity, uniqueness, and novelty. Beyond single property optimization, the framework demonstrates flexible multi-property optimization capabilities, simultaneously controlling multiple molecular descriptors including synthetic accessibility, lipophilicity, topological polar surface area, and clinically relevant ADMET properties such as cardiotoxicity (hERG) and intestinal permeability (Caco-2). This adaptability spans from simple descriptors to practical pharmaceutical endpoints without requiring complete model retraining. The framework achieves precise control over target property values, generating molecules with properties closely matching specified targets for both single and multiple descriptors. Scaffold-constrained experiments preserve fixed molecular cores while maintaining effective property optimization. The three-dimensional representation offers advantages in maintaining structural validity during iterative optimization, with potential for geometry-aware applications in materials science and drug discovery.

3D molecular generation↗

DOE OSTI2021

Machine-learning-aided cognitive reconfiguration for flexible-bandwidth HPC and data center networks [Invited]

This paper proposes a machine-learning (ML)-aided cognitive approach for effective bandwidth reconfiguration in optically interconnected datacenter/high-performance computing (HPC) systems. The proposed approach relies on a Hyper-X-like architecture augmented with flexible-bandwidth photonic interconnections at large scales using a hierarchical intra/inter-POD photonic switching layout. We first formulate the problem of the connectivity graph and routing scheme optimization as a mixed-integer linear programming model. A two-phase heuristic algorithm and a joint optimization approach are devised to solve the problem with low time complexity. Then, we propose an ML-based end-to-end performance estimator design to assist the network control plane with intelligent decision making for bandwidth reconfiguration. Numerical simulations using traffic distribution profiles extracted from HPC applications traces as well as random traffic matrices verify the accuracy performance of the ML design estimator ( < <#comment/> 9 % <#comment/> error) and demonstrate up to 5 × <#comment/> throughput gain from the proposed approach compared with the baseline Hyper-X network using fixed all-to-all intra/inter-portable data center interconnects.

Chen, Xiaoliang (ORCID:0000000278056237)↗

DOE OSTI2023

ARENA: Adversary-Resistant Evolving Neural Architectures

Neural networks are becoming the cornerstone for national security prediction tasks. However, designing them requires significant research and trial/error, as they have many hyperparameters, including their computation graph (“architecture”). Neural architecture search (NAS) employs secondary optimizers to search for architectures maximizing objectives like accuracy. Evolutionary algorithms (EAs) are the most used class of optimizer for NAS. However, existing Python libraries for writing EAs limit the complexity of experiments a user can design. In this project, we built ARENA, a Python framework that encodes complex, hyper-realistic EAs. ARENA collects detailed information as it runs and is flexible enough to encode non-EA search algorithms. We tested ARENA on 4 toy optimization problems by encoding 3 search algorithms for each—random search, an EA, and simulated annealing. We also designed an EA that performs NAS on the MNIST dataset. Our experiments suggest the potential for immediate mission impact through solving lab-wide optimization problems.

97 MATHEMATICS AND COMPUTING↗

NASA NTRS1972

Computer generation of symbolic network functions - A new theory and implementation.

A new method is presented for obtaining network functions in which some, none, or all of the network elements are represented by symbolic parameters (i.e., symbolic network functions). Unlike the topological tree enumeration or signal flow graph methods generally used to derive symbolic network functions, the proposed procedure employs fast, efficient, numerical-type algorithms to determine the contribution of those network branches that are not represented by symbolic parameters. A computer program called NAPPE (for Network Analysis Program using Parameter Extractions) and incorporating all of the concepts discussed has been written. Several examples illustrating the usefulness and efficiency of NAPPE are presented.

Alderson, G. E.↗

NASA NTRS1985

Integrated risk/cost planning models for the US Air Traffic system

A prototype network planning model for the U.S. Air Traffic control system is described. The model encompasses the dual objectives of managing collision risks and transportation costs where traffic flows can be related to these objectives. The underlying structure is a network graph with nonseparable convex costs; the model is solved efficiently by capitalizing on its intrinsic characteristics. Two specialized algorithms for solving the resulting problems are described: (1) truncated Newton, and (2) simplicial decomposition. The feasibility of the approach is demonstrated using data collected from a control center in the Midwest. Computational results with different computer systems are presented, including a vector supercomputer (CRAY-XMP). The risk/cost model has two primary uses: (1) as a strategic planning tool using aggregate flight information, and (2) as an integrated operational system for forecasting congestion and monitoring (controlling) flow throughout the U.S. In the latter case, access to a supercomputer is required due to the model's enormous size.

Mulvey, J. M.↗

NASA NTRS1989

Power flow for spacecraft power systems

A method for constructing the generalized system-level admittance matrix for use with a Newton-Raphson power flow is presented. The network modeling technique presented does not use the standard pi-equivalent models, which assume a lossless return path, for the transmission line and transformer. If the return path cannot be assumed lossless, then the standard algorithms for constructing the system admittance matrix cannot be used. The method presented here uses concepts from linear graph theory to combine network modules to form the system-level admittance matrix. The modeling technique is presented, and the resulting matrix is used with a standard Newton-Raphson power flow to calculate all system voltages and current (power) flows.

Halpin, S. M.↗

NASA NTRS2010

NASA Tech Briefs, May 2010

Topics covered include: Instrument for Analysis of Greenland's Glacier Mills Cryogenic Moisture Apparatus; A Transportable Gravity Gradiometer Based on Atom Interferometry; Three Methods of Detection of Hydrazines; Crossed, Small-Deflection Energy Analyzer for Wind/Temperature Spectrometer; Wavefront Correction for Large, Flexible Antenna Reflector; Novel Micro Strip-to-Waveguide Feed Employing a Double-Y Junction; Thin-Film Ferro Electric-Coupled Microstripline Phase Shifters With Reduced Device Hysteresis; Two-Stage, 90-GHz, Low-Noise Amplifier; A 311-GHz Fundamental Oscillator Using InP HBT Technology; FPGA Coprocessor Design for an Onboard Multi-Angle Spectro-Polarimetric Imager; Serrating Nozzle Surfaces for Complete Transfer of Droplets; Turbomolecular Pumps for Holding Gases in Open Containers; Triaxial Swirl Injector Element for Liquid-Fueled Engines; Integrated Budget Office Toolbox; PLOT3D Export Tool for Tecplot; Math Description Engine Software Development Kit; Astronaut Office Scheduling System Software; ISS Solar Array Management; Probabilistic Structural Analysis Program; SPOT Program; Integrated Hybrid System Architecture for Risk Analysis; System for Packaging Planetary Samples for Return to Earth; Offset Compound Gear Drive; Low-Dead-Volume Inlet for Vacuum Chamber; Simple Check Valves for Microfluidic Devices; A Capillary-Based Static Phase Separator for Highly Variable Wetting Conditions; Gimballing Spacecraft Thruster; Finned Carbon-Carbon Heat Pipe with Potassium Working Fluid; Lightweight Heat Pipes Made from Magnesium; Ceramic Rail-Race Ball Bearings; Improved OTEC System for a Submarine Robot; Reflector Surface Error Compensation in Dual-Reflector Antennas; Enriched Storable Oxidizers for Rocket Engines; Planar Submillimeter-Wave Mixer Technology with Integrated Antenna; Widely Tunable Mode-Hop-Free External-Cavity Quantum Cascade Laser; Non-Geiger-Mode Single-Photon Avalanche Detector with Low Excess Noise; Using Whispering-Gallery-Mode Resonators for Refractometry; RF Device for Acquiring Images of the Human Body; Reactive Collision Avoidance Algorithm; Fast Solution in Sparse LDA for Binary Classification; Modeling Common-Sense Decisions in Artificial Intelligence; Graph-Based Path-Planning for Titan Balloons; Nanolaminate Membranes as Cylindrical Telescope Reflectors; Air-Sea Spray Airborne Radar Profiler Characterizes Energy Fluxes in Hurricanes; Large Telescope Segmented Primary Mirror Alignment; and Simplified Night Sky Display System.

Source record↗

NASA NTRS2014

Recent Advances in Registration, Integration and Fusion of Remotely Sensed Data: Redundant Representations and Frames

In recent years, sophisticated mathematical techniques have been successfully applied to the field of remote sensing to produce significant advances in applications such as registration, integration and fusion of remotely sensed data. Registration, integration and fusion of multiple source imagery are the most important issues when dealing with Earth Science remote sensing data where information from multiple sensors, exhibiting various resolutions, must be integrated. Issues ranging from different sensor geometries, different spectral responses, differing illumination conditions, different seasons, and various amounts of noise need to be dealt with when designing an image registration, integration or fusion method. This tutorial will first define the problems and challenges associated with these applications and then will review some mathematical techniques that have been successfully utilized to solve them. In particular, we will cover topics on geometric multiscale representations, redundant representations and fusion frames, graph operators, diffusion wavelets, as well as spatial-spectral and operator-based data fusion. All the algorithms will be illustrated using remotely sensed data, with an emphasis on current and operational instruments.

Fusion↗

DOE OSTI2023

Faster approximate subgraph counts with privacy

One of the most common problems studied in the context of differential privacy for graph data is counting the number of non-induced embeddings of a subgraph in a given graph. These counts have very high global sensitivity. Therefore, adding noise based on powerful alternative techniques, such as smooth sensitivity and higher-order local sensitivity have been shown to give significantly better accuracy. However, all these alternatives to global sensitivity become computationally very expensive, and to date efficient polynomial time algorithms are known only for few selected subgraphs, such as triangles, k-triangles, and k-stars. In this paper, we show that good approximations to these sensitivity metrics can be still used to get private algorithms. Using this approach, we much faster algorithms for privately counting the number of triangles in real-world social networks, which can be easily parallelized. We also give a private polynomial time algorithm for counting any constant size subgraph using less noise than the global sensitivity; we show this can be improved significantly for counting paths in special classes of graphs

Nguyen, Dung↗

DOE OSTI2020

Compiler and Runtime Approaches to Enable Large-Scale Irregular Programs. Final report, July 2013 - July 2019

While regular algorithms, characterized by operations on dense matrices and arrays, have long been the mainstay of scientific, high-performance computing, irregular algorithms, which feature unpredictable accesses to pointer-based data structures, are becoming increasingly common in high performance computing, arising in graph analysis, data mining and visualization, among other domains. Unfortunately, the defining characteristics of irregular applications, their dynamic, unpredictable, data-dependent access patterns and data layouts, make achieving high performance on large scale systems difficult. Scaling applications to peta- and exa-scale requires carefully controlling communication and data movement and placement, an inherently difficult task when access patterns and data layouts are unpredictable! Most irregular applications that attain high performance must be painstakingly hand-written and hand-tuned, with few common principles or paradigms uniting various implementations and easing future development. Despite the increasing importance of irregular applications, there is little programmer knowledge, and even less compiler ability, devoted to optimizing them. This project aims to solve these problems. By allowing programmers to write irregular applications in high level forms, with at most a few annotations highlighting key structural properties, programmers can focus on developing their algorithms and methods. The compiler and run-time system can take on the tedious task of optimizing the application for execution at large scales, and can automatically provide efficient implementations. This will provide portability and ease maintenance for existing irregular applications, but, more importantly, open up whole new domains of computational science to large-scale, high-performance simulation codes.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2025

Knowledge graph-aided Bayesian active learning for top- K genetic interaction discovery

In silico methods for predicting the effects of multi-gene perturbations hold great promise for advancing functional genomics, computational drug discovery, and disease modeling. However, the development of these predictive algorithms for mammalian systems has been hampered by limited datasets and high experimental costs. In this study, we present a Bayesian active learning framework designed to discover pairwise host gene knockdowns that effectively inhibit viral proliferation in an in vitro HIV-1 infection model. Our method leverages a biological knowledge graph as side information and employs a computationally efficient batch diversification approach. We evaluated this framework using a dataset of viral load measurements obtained from multi-day dual-gene depletion experiments, encompassing all possible pairwise knockdowns of over 350 host genes associated with HIV infection. We demonstrate that our framework rapidly identifies the most effective gene knockdown pairs for reducing viral load. Furthermore, we show that incorporating side information enhances performance during the early stages of active learning (low data regime), while our batch diversification strategy significantly boosts performance in later stages (high data regime). This framework is general and can be adapted to explore gene interactions in other contexts, such as synthetic lethality prediction and mapping epistatic effects across quantitative trait loci.

Computational biology and bioinformatics↗

NASA NTRS1991

A scheduling algorithm for parallelizable dependent tasks

Scheduling a collection of tasks on a multiprocessor consisting of p processors, that minimizes the maximum completion time has attracted a lot of attention in the literature. This paper introduces a new problem of scheduling a task graph on a multiprocessor, called the parallelizable dependent task scheduling problem. Associated with each task, the paper shows the time it takes to run on a uniprocessor, and the speedup that can be obtained by running it on i processors, with i between 1 and p. Also presented are an algorithm for the problem and an analysis of the performance.

Belkhale, Krishna P.↗

NASA NTRS2000

A Parallel Genetic Algorithm for Automated Electronic Circuit Design

Parallelized versions of genetic algorithms (GAs) are popular primarily for three reasons: the GA is an inherently parallel algorithm, typical GA applications are very compute intensive, and powerful computing platforms, especially Beowulf-style computing clusters, are becoming more affordable and easier to implement. In addition, the low communication bandwidth required allows the use of inexpensive networking hardware such as standard office ethernet. In this paper we describe a parallel GA and its use in automated high-level circuit design. Genetic algorithms are a type of trial-and-error search technique that are guided by principles of Darwinian evolution. Just as the genetic material of two living organisms can intermix to produce offspring that are better adapted to their environment, GAs expose genetic material, frequently strings of 1s and Os, to the forces of artificial evolution: selection, mutation, recombination, etc. GAs start with a pool of randomly-generated candidate solutions which are then tested and scored with respect to their utility. Solutions are then bred by probabilistically selecting high quality parents and recombining their genetic representations to produce offspring solutions. Offspring are typically subjected to a small amount of random mutation. After a pool of offspring is produced, this process iterates until a satisfactory solution is found or an iteration limit is reached. Genetic algorithms have been applied to a wide variety of problems in many fields, including chemistry, biology, and many engineering disciplines. There are many styles of parallelism used in implementing parallel GAs. One such method is called the master-slave or processor farm approach. In this technique, slave nodes are used solely to compute fitness evaluations (the most time consuming part). The master processor collects fitness scores from the nodes and performs the genetic operators (selection, reproduction, variation, etc.). Because of dependency issues in the GA, it is possible to have idle processors. However, as long as the load at each processing node is similar, the processors are kept busy nearly all of the time. In applying GAs to circuit design, a suitable genetic representation 'is that of a circuit-construction program. We discuss one such circuit-construction programming language and show how evolution can generate useful analog circuit designs. This language has the desirable property that virtually all sets of combinations of primitives result in valid circuit graphs. Our system allows circuit size (number of devices), circuit topology, and device values to be evolved. Using a parallel genetic algorithm and circuit simulation software, we present experimental results as applied to three analog filter and two amplifier design tasks. For example, a figure shows an 85 dB amplifier design evolved by our system, and another figure shows the performance of that circuit (gain and frequency response). In all tasks, our system is able to generate circuits that achieve the target specifications.

Long, Jason D.↗

DOE OSTI2024

Multilevel well modeling in aggregation-based nonlinear multigrid for multiphase flow in porous media

A full approximation scheme (FAS) nonlinear multigrid solver for two-phase flow and transport problems driven by wells with multiple perforations is developed here. It is an extension to our previous work on FAS solvers for diffusion and transport problems. The solver is applicable to discrete problems defined on unstructured grids as the coarsening algorithm is aggregation-based and algebraic. To construct coarse basis that can better capture the radial flow near wells, coarse grids in which perforated well cells are not near the coarse-element interface are desired. This is achieved by an aggregation algorithm proposed in this paper that makes use of the location of well cells in the cell-connectivity graph. Numerical examples in which the FAS solver is compared against Newton's method on benchmark problems are given. In particular, for a refined version of the SAIGUP model, the FAS solver is at least 35% faster than Newton's method for time steps with a CFL number greater than 10.

58 GEOSCIENCES↗

DOE OSTI2021

Searching for metastable particles using graph computing

The reconstruction of charged particle trajectories at the Large Hadron Collider and future colliders relies on energy depositions in sensors placed at distances ranging from a centimeter to a meter from the colliding beams. We propose a method of detecting charged particles that decay invisibly after traversing a short distance of about 25 cm inside the experimental apparatus. One of the decay products may constitute the dark matter known to be 84% of all matter at galactic and cosmological distance scales. Our method uses graph computing to cluster spacepoints recorded by two-dimensional silicon pixel sensors into mathematically-defined patterns. The algorithm may be implemented on silicon-based integrated circuits using field-programmable gate array technology to augment or replace traditional computing platforms.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗