Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “approximation algorithm”

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 1,081 records · Page 60
All sourcesNASA NTRSDOE OSTI
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 OSTI2025

Fragme∩t: An Open‐Source Framework for Multiscale Quantum Chemistry Based on Fragmentation

Fragment-based quantum chemistry offers a means to circumvent the nonlinear computational scaling of conventional electronic structure calculations, by partitioning a large calculation into smaller subsystems then considering the many-body interactions between them. Variants of this approach have been used to parameterize classical force fields and machine learning potentials, applications that benefit from interoperability between quantum chemistry codes. However, there is a dearth of software that provides interoperability yet is purpose-built to handle the combinatorial complexity of fragment-based calculations. To fill this void we introduce “Fragme∩t”, an open-source software application that provides a tool for community validation of fragment-based methods, a platform for developing new approximations, and a framework for analyzing many-body interactions. Fragme∩t includes algorithms for automatic fragment generation and structure modification, and for distance- and energy-based screening of the requisite subsystems. Checkpointing, database management, and parallelization are handled internally and results are archived in a portable database. Interfaces to various quantum chemistry engines are easy to write and exist already for Q-Chem, PySCF, xTB, Orca, CP2K, MRCC, Psi4, NWChem, GAMESS, and MOPAC. Applications reported here demonstrate parallel efficiencies around 96% on more than 1000 processors but also showcase that the code can handle large-scale protein fragmentation using only workstation hardware, all with a codebase that is designed to be usable by non-experts. Fragme∩t conforms to modern software engineering best practices and is built upon well established technologies including Python, SQLite, and Ray. The source code is available under the Apache 2.0 license.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2022

Comparison of multiobjective optimization methods for the $\mathrm{LCLS-II}$ photoinjector

Particle accelerators are among some of the largest science experiments in the world and can consist of thousands of components with a wide variety of input ranges. These systems can easily become unwieldy optimization problems during design and operations studies. Starting in the early 2000s, searching for better beam dynamics configurations became synonymous with heuristic optimization methods in the accelerator physics community. Genetic algorithms and particle swarm optimization are currently the most widely used. These algorithms can take thousands of simulation evaluations to find optimal solutions for one machine prototype. For large facilities such as the Linac Coherent Light Source (LCLS) and others, this equates to a limited exploration of many possible design configurations. In this paper, the LCLS-II photoinjector is optimized with three optimization algorithms. All optimizations were started from both a uniform random and Latin hypercube sample. In all cases, the optimizations started from Latin hypercube samples outperformed optimizations started from uniform samples. All three algorithms were able to optimize the photoinjector, with the model-based methods approximating the Pareto front in fewer simulation evaluations. This work, in combination with previous optimization observations, indicates objective penalties have a strong impact on the efficiency of such methods. In general, we recommend heuristic methods for initial optimizations and model-based methods when information about the objective space is available.

43 PARTICLE ACCELERATORS↗
DOE OSTI2020

Optimal Network Topology for Node-Breaker Representations With AC Power Flow Constraints

It has been demonstrated that network topology optimization (NTO) may change the topology of power system networks, and consequently, provide additional flexibility to reduce network congestion and violations. Most NTO problems are formulated based on the bus-branch model in which it is challenging to represent a realistic picture of all substation configurations. In this paper, we explore advantages of substation reconfiguration modeling based on node-breaker representations for NTO problem with full nonlinear alternating current power flow. It also proposes a tailored solution algorithm to solve this nonconvex mixed-integer nonlinear programming through the outer approximation method. The proposed solution approach iterates between a mixed-integer linear programming and a nonlinear subproblem. Additional enhancements to further accelerate the iteration process are illustrated. Numerical case studies demonstrate the relative economic and operational impact of optimal network topology with node-breaker representations.

42 ENGINEERING↗
DOE OSTI2020

eFESTA: Ensemble Feature Exploration with Surface Density Estimates

We propose surface density estimate (SDE) to model the spatial distribution of surface features-isosurfaces, ridge surfaces, and streamsurfaces-in 3D ensemble simulation data. The inputs of SDE computation are surface features represented as polygon meshes, and no field datasets are required (e.g., scalar fields or vector fields). The SDE is defined as the kernel density estimate of the infinite set of points on the input surfaces and is approximated by accumulating the surface densities of triangular patches. We also propose an algorithm to guide the selection of a proper kernel bandwidth for SDE computation. An ensemble Feature Exploration method based on Surface densiTy EstimAtes (eFESTA) is then proposed to extract and visualize the major trends of ensemble surface features. For an ensemble of surface features, each surface is first transformed into a density field based on its contribution to the SDE, and the resulting density fields are organized into a hierarchical representation based on the pairwise distances between them. The hierarchical representation is then used to guide visual exploration of the density fields as well as the underlying surface features. We demonstrate the application of our method using isosurface in ensemble scalar fields, Lagrangian coherent structures in uncertain unsteady flows, and streamsurfaces in ensemble fluid flows.

Computational modeling↗
DOE OSTI2022

An MILP-Based Distributed Energy Management for Coordination of Networked Microgrids

An MILP-based distributed energy management for the coordination of networked microgrids is proposed in this paper. Multiple microgrids and the utility grid are coordinated through iteratively adjusted price signals. Based on the price signals received, the microgrid controllers (MCs) and distribution management system (DMS) update their schedules separately. Then, the price signals are updated according to the generation–load mismatch and distributed to MCs and DMS for the next iteration. The iteration continues until the generation–load mismatch is small enough, i.e., the generation and load are balanced under agreed price signals. Through the proposed distributed energy management, various microgrids and the utility grid with different economic, resilient, emission and socio-economic objectives are coordinated with generation–load balance guaranteed and the microgrid customers’ privacy preserved. In particular, a piecewise linearization technique is employed to approximate the augmented Lagrange term in the alternating direction method of multipliers (ADMM) algorithm. Thus, the subproblems are transformed into mixed integer linear programming (MILP) problems and efficiently solved by open-source MILP solvers, which would accelerate the adoption and deployment of microgrids and promote clean energy. The proposed MILP-based distributed energy management is demonstrated through various case studies on a networked microgrids test system with three microgrids.

24 POWER TRANSMISSION AND DISTRIBUTION↗
NASA NTRS1975

Compression of ephemerides

An algorithm is proposed for generating sequences of Chebyshev series which are the best approximations of an astronomical ephemeris in the sense of Chebyshev over large intervals of time. The criterion for a polynomial approximation of a function to be the best polynomial approximation of the function is that the error function present certain rippling characteristics as described by Remez (1957). General features of the program in PL/1 are described.

Deprit, A.↗
NASA NTRS1980

System design for a million channel digital spectrum analyzer /MCSA/

The system design of a wideband (8 MHz) million-channel digital spectrum analyzer for use with a SETI receiver is presented. The analyzer makes use of a digital bandpass filter bank for transforming the wideband input signal into a specified number (120) of uniform narrowband output channels by the use of a Fourier transform digital processor combined with a prototype digital weighting network (finite impulse response filter). The output is then processed separately by 120 microprocessor-based discrete Fourier transform computers, each producing 8190 output channels of approximately 8 Hz bandwidth by the use of an 8190-point prime factor algorithm.

Peterson, A.↗
NASA NTRS1981

Theory, computation, and application of exponential splines

A generalization of the semiclassical cubic spline known in the literature as the exponential spline is discussed. In actuality, the exponential spline represents a continuum of interpolants ranging from the cubic spline to the linear spline. A particular member of this family is uniquely specified by the choice of certain tension parameters. The theoretical underpinnings of the exponential spline are outlined. This development roughly parallels the existing theory for cubic splines. The primary extension lies in the ability of the exponential spline to preserve convexity and monotonicity present in the data. Next, the numerical computation of the exponential spline is discussed. A variety of numerical devices are employed to produce a stable and robust algorithm. An algorithm for the selection of tension parameters that will produce a shape preserving approximant is developed. A sequence of selected curve-fitting examples are presented which clearly demonstrate the advantages of exponential splines over cubic splines.

Mccartin, B. J.↗
NASA NTRS1984

Numerical simulation of the transonic flowfield for wing/nacelle configurations

An efficient grid-interfacing zonal algorithm has been developed for computing the three-dimensional transonic flow field about wing/nacelle multicomponent configurations. The algorithm uses the full-potential formulation and the AF2 fully-implicit approximate factorization scheme. The flow field position is computed using a component-adaptive grid approach in which separate grids are employed for the individual components in the multicomponent configuration, where each component grid is optimized for a particular geometry such as the wing or nacelle. The wing and nacelle component grids are allowed to overlap, and flow field information is transmitted from one grid to another through the overlap region using trivariate interpolation. This paper presents a discussion of the computational methods used to generate both the wing and nacelle component grids, the technique used to interface the component grids, and the method used to obtain the inviscid multicomponent flow field solution. Computed results and correlations with experiment are presented to illustrate application of the analysis.

Atta, E. H.↗
NASA NTRS1988

Closed-form Grammians and model reduction for flexible space structures

Analytical expression are derived for the Grammians of a model in modal coordinates for the dynamics of a flexible space structure (FSS). These exact results provide insight into the dynamics of such systems and reduce the known approximate expressions in the case of lightly damped, widely separated modes. A novel algorithm is outlined that uses these to compute a dominant reduced-order model for such a system in an efficient manner.

Williams, Trevor↗
NASA NTRS1989

Numerical simulation of flow over a hypersonic aircraft using an explicit upwind PNS solver

A hypersonic flow field over a generic airplane configuration is simulated by solving the Parabolized Navier-Stokes (PNS) equations. The finite difference solution of the PNS equations is calculated using a noniterative space marching, explicit, upwind scheme recently developed by the authors. Special gridding techniques are used which allowed the sharp changes in surface geometry of the airplane configuration to be modelled without smoothing of corners. Comparisons of the PNS results to a solution of the Navier-Stokes equations demonstrates a good agreement of the numerical results in approximately 1/6 of the cpu time. This paper demonstrates that the explicit upwind algorithm for solving the PNS equations is an efficient method for simulating hypersonic flow fields about complete airplane configurations and should be considered as an alternative to solving the Navier-Stokes equations for flow fields where the PNS equations are valid.

Korte, John J.↗
NASA NTRS1990

Dual-shaped offset reflector antenna designs from solutions of the geometrical optics first-order partial differential equations

In obtaining solutions to the first-order nonlinear partial differential equations (PDEs) for synthesizing offset dual-shaped reflectors, it is found that previously observed computational problems can be avoided if the integration of the PDEs is started from an inner projected perimeter and integrated outward rather than starting from an outer projected perimeter and integrating inward. This procedure, however, introduces a new parameter, the main reflector inner perimeter radius p(o), when given a subreflector inner angle 0(o). Furthermore, a desired outer projected perimeter (e.g., a circle) is no longer guaranteed. Stability of the integration is maintained if some of the initial parameters are determined first from an approximate solution to the PDEs. A one-, two-, or three-parameter optimization algorithm can then be used to obtain a best set of parameters yielding a close fit to the desired projected outer rim. Good low cross-polarization mapping functions are also obtained. These methods are illustrated by synthesis of a high-gain offset-shaped Cassegrainian antenna and a low-noise offset-shaped Gregorian antenna.

Galindo-Israel, V.↗
NASA NTRS1991

Optimal control study for the Space Station Solar Dynamic power module

The authors present the design of an optimal control system for the Space Station Freedom's Solar Dynamic Fine Pointing and Tracking (SDFPT) module. A very large state model of six rigid body modes and 272 flexible modes is used in conjunction with classical LQG optimal control to produce a full-order controller which satisfies the requirements. The results obtained are compared with those of a classically designed PID (proportional plus integral plus derivative) controller that was implemented for a six-rigid-body-mode forty-flexible-mode model. A major difficulty with designing LQG controllers for large models is solving the Riccati equation that arises from the optimal formulation. A Riccati solver based on a Pade approximation to the matrix sign function is used. A symmetric version of this algorithm is derived for the special class of Hamiltonion matrices, thereby yielding, for large problems, a nearly twofold speed increase over a previous algorithm.

Papadopoulos, P. M.↗
NASA NTRS1992

An explicit canopy BRDF model and inversion

Based on a rigorous canopy radiative transfer equation, the multiple scattering radiance is approximated by the asymptotic theory, and the single scattering radiance calculation, which requires an numerical intergration due to considering the hotspot effect, is simplified. A new formulation is presented to obtain more exact angular dependence of the sky radiance distribution. The unscattered solar radiance and single scattering radiance are calculated exactly, and the multiple scattering is approximated by the delta two-stream atmospheric radiative transfer model. The numerical algorithms prove that the parametric canopy model is very accurate, especially when the viewing angles are smaller than 55 deg. The Powell algorithm is used to retrieve biospheric parameters from the ground measured multiangle observations.

Liang, Shunlin↗
NASA NTRS1993

The Coherent Launchsite Wind Sounder (CLAWS)

This talk will provide a description of the Coherent Launchsite Wind Sounder (CLAWS) program for the development of a near real-time launchsite wind measurement system. The CLAWS program was motivated by the need to have wind measurements for spacecraft launch systems that are more timely than those from balloons. and that measure the winds along the booster's flight path. This program went from conceptual development to the testing of a breadboard system at KSC in concert with the launch of STS-48 in September of 1991. The system demonstrated the capability to measure the wind field, that a launch vehicle will traverse, from ground level to an altitude of 26 Km in approximately six minutes. The presentation will cover the concept, the hardware and the algorithms required, the test program and some results from the CLAWS system.

Price, Douglas B.↗
NASA NTRS1996

Effect of Dust Coagulation Dynamics on the Geometry of Aggregates

Master equation gives a more fundamental description of stochastic coagulation processes rather than popular Smoluchowski's equation. In order to examine the effect of the dynamics on the geometry of resulting aggregates, we study Master equation with a rigorous Monte Carlo algorithm. It is found that Cluster-Cluster aggregation model is a good approximation of orderly growth and the aggregates have fluffy structures with a fractal dimension approx. 2. A scaling analysis of Smoluchowski's equation also supports this conclusion.

Nakamura, R.↗