Search NASA⌕ Search

SEARCH · Search NASA

Results for “matched bound”

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 37 records · Page 2
All sourcesNASA NTRSDOE OSTI
NASA NTRS1992

Fault-tolerant wait-free shared objects

A concurrent system consists of processes and shared objects. Previous research focused on the problem of tolerating process failure. We study the complementary problem of tolerating failures. We divide object failures into two broad classes: responsive and non-responsive. With responsive failures, a faulty object responds to every invocation, but responses may be incorrect. With non-responsive failures, a faulty object may also 'hang' without responding. For each class, we consider crash, and arbitrary types of failures. For each type of failure, we are seeking a universal implementation for fault-tolerant wait-free shared objects. We present (deterministic) implementations for all types of responsive failures, including arbitrary failures. In contrast, we show that even the most benign type of non-responsive failures requires the use of randomization. Of special interest is the problem of implementing fault-tolerant objects using only objects of the same type. We present such fault-tolerant self-implementations for many common object types. Graceful degradation is a desirable property of fault-tolerant implementations: the implemented object never fails more severely than the base objects it is derived from, even if all the base objects fail. For several failure models, we show whether this property can be achieved, and, if so, how. In addition to the above possibility/impossibility results, we also consider the resources complexity of fault-tolerant implementations. In many cases, we present lower bounds and give matching algorithms.

Jayanti, Prasad↗
DOE OSTI2024

Streaming Matching and Edge Cover in Practice

Graph algorithms with polynomial space and time requirements often become infeasible for massive graphs with billions of edges or more. State-of-the-art approaches therefore employ approximate serial, parallel, and distributed algorithms to tackle these challenges. However, such approaches require storing the entire graph in memory and thus need access to costly computing resources such as clusters and supercomputers. In this paper, we present practical streaming approaches for solving massive graph problems using limited memory for two prototypical graph problems: maximum weighted matching and minimum weighted edge cover. For matching, we conduct a thorough computational study on two of the semi-streaming algorithms including a recent breakthrough result that achieves a $1/(2+\varepsilon)$-approximation of the weight while using $O( n \log W /\epsilon)$ memory (here $n$ is the number of vertices and $W$ is the maximum edge weight), designed by Paz and Schwartzman [SODA, 2017]. Empirically, we show that the semi-streaming algorithms produce matchings whose weight is close to the best $1/2$-approximate offline algorithm while requiring less time and an order-of-magnitude less memory. For minimum weighted edge cover, we develop three novel semi-streaming algorithms. Two of these algorithms require a single pass through the input graph, require $O(n \log n)$ memory, and provide a 2-approximation guarantee on the objective. We also leverage a relationship between approximate maximum weighted matching and approximate minimum weighted edge cover to develop a two-pass $3/2+\epsilon$-approximate algorithm with the memory requirement of Paz and Schwartzman's semi-streaming matching algorithm. These streaming approaches are compared against the state-of-the-art 3/2-approximate offline algorithm. The semi-streaming matching and the novel edge cover algorithms proposed in this paper can process graphs with several billions of edges in under 30 minutes using 6 GB of memory, which is at least an order of magnitude improvement from the offline (non-streaming) algorithms. For the largest graph, the best alternative offline parallel approximation algorithm (GPA+ROMA) could not finish in three hours even while employing hundreds of processors and 1 TB of memory. We also demonstrate an application of the semi-streaming algorithm by computing a matching using linearly bounded memory on item intersection graphs derived from three machine learning datasets, whereas the existing offline algorithms could not complete on one of these datasets since their memory requirements exceeded 1TB.

Ferdous, S M.↗
DOE OSTI2022

Inexact Newton-CG algorithms with complexity guarantees

Abstract We consider variants of a recently developed Newton-CG algorithm for nonconvex problems (Royer, C. W. & Wright, S. J. (2018) Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization. SIAM J. Optim., 28, 1448–1477) in which inexact estimates of the gradient and the Hessian information are used for various steps. Under certain conditions on the inexactness measures, we derive iteration complexity bounds for achieving $\epsilon $-approximate second-order optimality that match best-known lower bounds. Our inexactness condition on the gradient is adaptive, allowing for crude accuracy in regions with large gradients. We describe two variants of our approach, one in which the step size along the computed search direction is chosen adaptively, and another in which the step size is pre-defined. To obtain second-order optimality, our algorithms will make use of a negative curvature direction on some steps. These directions can be obtained, with high probability, using the randomized Lanczos algorithm. In this sense, all of our results hold with high probability over the run of the algorithm. We evaluate the performance of our proposed algorithms empirically on several machine learning models. Our approach is a first attempt to introduce inexact Hessian and/or gradient information into the Newton-CG algorithm of Royer & Wright (2018, Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization. SIAM J. Optim., 28, 1448–1477).

Mathematics↗
NASA NTRS1987

Geophysical constraints on lunar bulk composition and structure - A reassessment

Theoretical lunar mantle seismic velocity and density profiles were calculated for a series of specific bulk composition models, thermal models, and evolutionary models. It was found that most of the calculated seismic profiles are in qualitative agreement with the Nakamura (1983) observational mantle seismic velocity model. With respect to the density modeling results, the most interesting finding is that none of the considered models yield mantle density increases that are sufficient to match the adapted upper bound on the lunar moment-of-inertia factor (0.3928). The results suggest that the moon possesses a dense metallic core with a mass in the range of 1 to 4 percent of the lunar mass and that the alumina-rich models of Morgan et al. (1978) and Taylor (1982) are best able to match the middle mantle velocity increase that characterizes the Nakamura model.

Hood, L. L.↗
NASA NTRS2017

Fracture-Based Mesh Size Requirements for Matrix Cracks in Continuum Damage Mechanics Models

This paper evaluates the ability of progressive damage analysis (PDA) finite element (FE) models to predict transverse matrix cracks in unidirectional composites. The results of the analyses are compared to closed-form linear elastic fracture mechanics (LEFM) solutions. Matrix cracks in fiber-reinforced composite materials subjected to mode I and mode II loading are studied using continuum damage mechanics and zero-thickness cohesive zone modeling approaches. The FE models used in this study are built parametrically so as to investigate several model input variables and the limits associated with matching the upper-bound LEFM solutions. Specifically, the sensitivity of the PDA FE model results to changes in strength and element size are investigated.

Leone, Frank A.↗
DOE OSTI2021

Hotspot Coevolution Is a Key Identifier of Near-Native Protein Complexes

Protein–protein interactions play a key role in mediating numerous biological functions, with more than half the proteins in living organisms existing as either homo- or hetero-oligomeric assemblies. Protein subunits that form oligomers minimize the free energy of the complex, but exhaustive computational search-based docking methods have not comprehensively addressed the challenge of distinguishing a natively bound complex from non-native forms. Current protein docking approaches address this problem by sampling multiple binding modes in proteins and scoring each mode, with the lowest-energy (or highest scoring) binding mode being regarded as a near-native complex. However, high-scoring modes often match poorly with the true bound form, suggesting a need for improvement of the scoring function. Here in this study, we propose a scoring function, KFC-E, that accounts for both conservation and coevolution of putative binding hotspot residues at protein–protein interfaces. We tested KFC-E on four benchmark sets of unbound examples and two benchmark sets of bound examples, with the results demonstrating a clear improvement over scores that examine conservation and coevolution across the entire interface.

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

Near-Efficient and Non-Asymptotic Multiway Inference

We establish non-asymptotic efficiency guarantees for tensor decomposition–based inference in count data models. Under a Poisson framework, we consider two related goals: (i) parametric inference , the estimation of the full distributional parameter tensor, and (ii) multiway analysis , the recovery of its canonical polyadic (CP) decomposition factors. Our main result shows that in the rank-one setting, a rank-constrained maximum-likelihood estimator achieves multiway analysis with variance matching the Cramér–Rao Lower Bound (CRLB) up to absolute constants and logarithmic factors. This provides a general framework for studying “near-efficient” multiway estimators in finite-sample settings. For higher ranks, we illustrate that our multiway estimator may not attain the CRLB; nevertheless, CP-based parametric inference remains nearly minimax optimal, with error bounds that improve on prior work by offering more favorable dependence on the CP rank. Numerical experiments corroborate near-efficiency in the rank-one case and highlight the efficiency gap in higher-rank scenarios.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1987

Solving very large, sparse linear systems on mesh-connected parallel computers

The implementation of Pan and Reif's Parallel Nested Dissection (PND) algorithm on mesh connected parallel computers is described. This is the first known algorithm that allows very large, sparse linear systems of equations to be solved efficiently in polylog time using a small number of processors. How the processor bound of PND can be matched to the number of processors available on a given parallel computer by slowing down the algorithm by constant factors is described. Also, for the important class of problems where G(A) is a grid graph, a unique memory mapping that reduces the inter-processor communication requirements of PND to those that can be executed on mesh connected parallel machines is detailed. A description of an implementation on the Goodyear Massively Parallel Processor (MPP), located at Goddard is given. Also, a detailed discussion of data mappings and performance issues is given.

Opsahl, Torstein↗
DOE OSTI2021

Theory of Trotter Error with Commutator Scaling

The Lie-Trotter formula, together with its higher-order generalizations, provides a simple approach to decomposing the exponential of a sum of operators. Despite significant effort, the error scaling of such product formulas remains poorly understood. We develop a theory of Trotter error that overcomes the limitations of truncating the Baker-Campbell-Hausdorff expansion. Our analysis directly exploits the commutativity of operator summands, producing tighter error bounds for both real- and imaginary-time evolutions. Whereas previous work achieves similar goals for systems with geometric locality or Lie-algebraic structure, our approach holds in general. We give a host of improved algorithms for digital quantum simulation and quantum Monte Carlo methods, nearly matching or even outperforming the best previous results. Our applications include: (i) a simulation of second-quantized plane-wave electronic structure, nearly matching the interaction-picture algorithm of Low and Wiebe; (ii) a simulation of $k$-local Hamiltonians almost with induced one-norm scaling, faster than the qubitization algorithm of Low and Chuang; (iii) a simulation of rapidly decaying power-law interactions, outperforming the Lieb-Robinson-based approach of Tran et al.; (iv) a hybrid simulation of clustered Hamiltonians, dramatically improving the result of Peng, Harrow, Ozols, and Wu; and (v) quantum Monte Carlo simulations of the transverse field Ising model and quantum ferromagnets, tightening previous analyses of Bravyi and Gosset. We obtain further speedups using the fact that product formulas can preserve the locality of the simulated system. Specifically, we show that local observables can be simulated with complexity independent of the system size for power-law interacting systems, which implies a Lieb-Robinson bound nearly matching a recent result of Tran et al. Our analysis reproduces known tight bounds for first- and second-order formulas. We further investigate the tightness of our bounds for higher-order formulas. For quantum simulation of a one-dimensional Heisenberg model with an even-odd ordering of terms, our result overestimates the complexity by only a factor of $5$. Our bound is also close to tight for power-law interactions and other orderings of terms. This suggests that our theory can accurately characterize Trotter error in terms of both the asymptotic scaling and the constant prefactor.

quantum computing, numerical analysis↗
NASA NTRS1984

More than you may want to know about maximum likelihood estimation

A discussion is undertaken concerning the maximum likelihood estimator and the aircraft equations of motion it employs, with attention to the application of the concepts of minimization and estimation to a simple computed aircraft example. Graphic representations are given for the cost functions to help illustrate the minimization process. The basic concepts are then generalized, and estimations obtained from flight data are evaluated. The example considered shows the advantage of low measurement noise, multiple estimates at a given condition, the Cramer-Rao bounds, and the quality of the match between measured and computed data.

Iliff, K. W.↗
NASA NTRS2012

On the Nature and Extent of Optically Thin Marine low Clouds

Macrophysical properties of optically thin marine low clouds over the nonpolar oceans (60 deg S-60 deg N) are measured using 2 years of full-resolution nighttime data from the Cloud-Aerosol Lidar with Orthogonal Polarization (CALIOP). Optically thin clouds, defined as the subset of marine low clouds that do not fully attenuate the lidar signal, comprise almost half of the low clouds over the marine domain. Regionally, the fraction of low clouds that are optically thin (f(sub thin,cld)) exhibits a strong inverse relationship with the low-cloud cover, with maxima in the tropical trades (f(sub thin,cld) greater than 0.8) and minima in regions of persistent marine stratocumulus and in midlatitudes (f(sub thin,cld) less than 0.3). Domain-wide, a power law fit describes the cloud length distribution, with exponent beta = 2.03 +/- 0.06 (+/-95% confidence interval). On average, the fraction of a cloud that is optically thin decreases from approximately 1 for clouds smaller than 2 km to less than 0.3 for clouds larger than 30 km. This relationship is found to be independent of region, so that geographical variations in the cloud length distribution explain three quarters of the variance in f(sub thin,cld). Comparing collocated trade cumulus observations from CALIOP and the airborne High Spectral Resolution Lidar reveals that clouds with lengths smaller than are resolvable with CALIOP contribute approximately half of the low clouds in the region sampled. A bounded cascade model is constructed to match the observations from the trades. The model shows that the observed optically thin cloud behavior is consistent with a power law scaling of cloud optical depth and suggests that most optically thin clouds only partially fill the CALIOP footprint.

Leahy, L. V.↗
NASA NTRS1986

Cramer-Rao bounds for signal-to-noise ratio and combiner weight estimation

Cramer-Rao lower bounds on estimator variance are calculated for arbitrary unbiased estimates of signal-to-noise ratio and combiner weight parameters. Estimates are assumed to be based on a discrete set of observables obtained by matched filtering of a biphase modulated signal. The bounds are developed first for a problem model based on one observable per channel symbol period, and then extended to a more general problem in which subperiod observables are also available.

Dolinar, S. J.↗
NASA NTRS1995

Determination of stability and control derivatives from the NASA F/A-18 HARV from flight data using the maximum likelihood method

This report is a compilation of PID (Proportional Integral Derivative) results for both longitudinal and lateral directional analysis that was completed during Fall 1994. It had earlier established that the maneuvers available for PID containing independent control surface inputs from OBES were not well suited for extracting the cross-coupling static (i.e., C(sub N beta)) or dynamic (i.e., C(sub Npf)) derivatives. This was due to the fact that these maneuvers were designed with the goal of minimizing any lateral directional motion during longitudinal maneuvers and vice-versa. This allows for greater simplification in the aerodynamic model as far as coupling between longitudinal and lateral directions is concerned. As a result, efforts were made to reanalyze this data and extract static and dynamic derivatives for the F/A-18 HARV (High Angle of Attack Research Vehicle) without the inclusion of the cross-coupling terms such that more accurate estimates of classical model terms could be acquired. Four longitudinal flights containing static PID maneuvers were examined. The classical state equations already available in pEst for alphadot, qdot and thetadot were used. Three lateral directional flights of PID static maneuvers were also examined. The classical state equations already available in pEst for betadot, p dot, rdot and phi dot were used. Enclosed with this document are the full set of longitudinal and lateral directional parameter estimate plots showing coefficient estimates along with Cramer-Rao bounds. In addition, a representative time history match for each type of meneuver tested at each angle of attack is also enclosed.

Napolitano, Marcello R.↗
DOE OSTI2026

Exact and Fixed-Point Grover Search with Qudits

Grover's algorithm provides a quadratic speedup for searching unstructured databases and is traditionally implemented with qubits in Hilbert spaces whose dimensions are powers of two. With the advent of quantum platforms utilizing qudits---quantum systems with more than two levels---there is a need to generalize Grover search to these architectures, including heterogeneous systems with qudits of varying dimensions. Here, we present a unified framework for qudit-based Grover search, detailing the construction of oracles and diffusion operators with and without ancilla qubits and generalizing deterministic and fixed-point search variants that ensure exact or bounded success probabilities. We analyze phase-matching techniques and provide explicit circuit decompositions suitable for diverse hardware platforms. We also compare the corresponding trajectories on the Bloch sphere to provide an intuitive visualization of how the different phase choices amplify the target state. These results facilitate flexible, hardware-oriented protocols for implementing Grover search on qudit processors, potentially reducing circuit depth and enhancing success probabilities, thereby offering a practical toolkit for quantum computation and sensing applications leveraging multilevel quantum systems.

Roy, Tanay [Fermilab] (ORCID:000000019442862X)↗
NASA NTRS1979

Theoretical modelling and experimental data matching for active and passive microwave remote sensing of Earth terrain

Two theoretical models were developed to characterize terrain media: a random medium with a variance, a horizontal correlation length; and a homogeneous dielectric containing discrete scatterers. The earth terrain is modelled as layers of such scattering media bounded by air above and half-space below. Matching the theoretical results with experimental data collected from vegetation and snow-ice fields shows that: (1) for observation angles near nadir, rough surface effects are important; (2) for snow-ice field the horizontal correlation length is greater than the vertical correlation length whereas for vegetation field their relative sizes depend on the types of vegetation; (3) the vertically polarized backscattering cross-section is always larger than the horizontally polarized backscattering cross-section for half-space scattering media; (4) for snow field displaying diurnal change, a three-layer model including a thin top layer caused by sunlight illumination must be used; and (5) for a random medium with equal horizontal and vertical correlation lengths, the measured data can also be matched with a corresponding discrete scatterer model.

Kong, J. A.↗
NASA NTRS1997

Efficient algorithms for robust feature matching

One of the basic building blocks in any point-based registration scheme involves matching feature points that are extracted from the sensed image to their counterparts in the reference image. This leads to the fundamental problem of point matching: given two sets of points, find the affine transformation that transforms one point set so that its distance from the other point set is minimized. Because of measurement errors and the presence of outlying data points, it is important that the distance measure between two point sets be robust to these effects. We measure distances using the generalized Hausdorff distance. Point matching can be a computationally intensive task, and there have been a number of algorithms and approaches proposed for solving this problem both theoretical and applied. We present two approaches to the point matching problem, in an attempt to reduce the computational complexity of the problem, while still providing guarantees on the quality of the final match. Our first method is an approximation algorithm, which is loosely based on a branch-and-bound approach due to Huttenlocher and Rucklidge. We show that by varying the approximation error bounds, it is possible to achieve a tradeoff between the quality of the match and the running time of the algorithm. Our second method involves a Monte Carlo method for accelerating the search process used in the first algorithm. With high probability this method succeeds in finding an approximately optimal match. We establish the efficiency of our approaches empirically.

Mount, David M.↗
DOE OSTI2025

Selective deuteration of an RNA:RNA complex for structural analysis using small-angle scattering

The structures of RNA:RNA complexes regulate many biological processes. Despite their importance, protein-free RNA:RNA complexes represent a tiny fraction of experimentally determined structures. Here, we describe a joint small-angle X-ray and neutron scattering (SAXS/SANS) approach to structurally interrogate conformational changes in a model RNA:RNA complex. Using SAXS, we measured the solution structures of the individual RNAs and of the overall RNA:RNA complex. With SANS, we demonstrate, as a proof of principle, that isotope labeling and contrast matching (CM) can be combined to probe the bound state structure of an RNA within a selectively deuterated RNA:RNA complex. Furthermore, we show that experimental scattering data can validate and improve predicted AlphaFold 3 RNA:RNA complex structures to reflect its solution structure. In conclusion, our work demonstrates that in silico modeling, SAXS, and CM-SANS can be used in concert to directly analyze conformational changes within RNAs when in complex, enhancing our understanding of RNA structure in functional assemblies.

HIV-1 dimerization initiation site↗
NASA NTRS1992

Robust stabilization, robust performance, and disturbance attenuation for uncertain linear systems

This paper presents a linear quadratic regulator approach to the robust stabilization, robust performance, and disturbance attenuation of uncertain linear systems. The state-feedback designed systems provide both the robust stability with optimal performance and the disturbance attenuation with H-infinity-norm bounds. The proposed approach can be applied to matched and/or mismatched uncertain linear systems. For a matched uncertain linear system, it is shown that the disturbance attenuation robust-stabilizing controllers with or without optimal performance always exist and can be easily determined without searching; whereas, for a mismatched uncertain linear system, the introduced tuning parameters greatly enhance the flexibility of finding the disturbance-attenuation robust-stabilizing controllers.

Wang, Yeih J.↗