SEARCH · Engineering Papers

Results for “Computational Complexity”

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 55 records · Page 3

All sources NASA NTRS DOE OSTI

DOE OSTI2016

Characterization of bandwidth requirements of algorithms for extreme scale science

Technology trends have resulted in widely different rates of improvement in computational throughput as compared to data movement rates in computer systems. With future systems, the cost of data movement through the memory hierarchy is expected to become even more dominant relative to the cost of performing arithmetic operations, both in terms of time and energy. Therefore, optimizing data access costs will become ever more critical in the coming years. However, unlike the well understood model of computational complexity in terms of the number of elementary operations to execute an algorithm, the inherent data-movement complexity of computations is unknown for most algorithms. Given the crucial importance of optimizing data access costs in scalable parallel systems, it is of great interest to develop techniques for understanding the inherent data movement complexity of an algorithm. In this project, we focus on this fundamental and significant problem.

97 MATHEMATICS AND COMPUTING↗

NASA NTRS2004

Iterative Demodulation and Decoding of Non-Square QAM

It has been shown that a non-square (NS) 2(sup 2n+1)-ary (where n is a positive integer) quadrature amplitude modulation [(NS)2(sup 2n+1)-QAM] has inherent memory that can be exploited to obtain coding gains. Moreover, it should not be necessary to build new hardware to realize these gains. The present scheme is a product of theoretical calculations directed toward reducing the computational complexity of decoding coded 2(sup 2n+1)-QAM. In the general case of 2(sup 2n+1)-QAM, the signal constellation is not square and it is impossible to have independent in-phase (I) and quadrature-phase (Q) mapping and demapping. However, independent I and Q mapping and demapping are desirable for reducing the complexity of computing the log likelihood ratio (LLR) between a bit and a received symbol (such computations are essential operations in iterative decoding). This is because in modulation schemes that include independent I and Q mapping and demapping, each bit of a signal point is involved in only one-dimensional mapping and demapping. As a result, the computation of the LLR is equivalent to that of a one-dimensional pulse amplitude modulation (PAM) system. Therefore, it is desirable to find a signal constellation that enables independent I and Q mapping and demapping for 2(sup 2n+1)-QAM.

Li, Lifang↗

NASA NTRSDate not supplied

Assessment of Quantum ML Applicability for Climate Actions: Comparison of the Variational Quantum Classifier and the Quantum Support Vector Classifier with Classical ML Models

Climate change refers to significant and long-term alterations in the Earth’s climate patterns, typically resulting from human activities that increase greenhouse gas emissions. Addressing climate change is not merely an option but a necessity, demanding creative solutions and efforts from individuals, researchers, communities, and governments. Despite the capabilities of machine learning (ML) with data-driven solutions promising to combat climate change-related problems, they face challenges stemming from traditional computational methods and prolonged training times, impeding their practical utility. Recent strides in quantum computing have permeated diverse domains, spanning from manufacturing engineering and pharmaceutical discovery to the latest frontier of detecting climate anomalies. With the potential to substantially reduce time and computational complexity, quantum computing shows promise in addressing climate change impacts. Its distinctive features will enable the concurrent exploration of expansive solution spaces, making it well-suited for analyzing extensive climate datasets, simulating intricate climate models, optimizing resource allocation, and discerning patterns in climate data for mitigation and adaptation endeavors. This study explores the potential of using Quantum machine learning (QML) techniques on climate and weather data obtained from NASA Giovannis. We used two QML algorithms, the Quantum Support Vector Classifier (QSVC) and the Variational Quantum Classifier (VQC) models, using the IBM Qiskit ML 0.7.2 ecosystem. We used an actual 127-Qubit IBM Quantum Computer (IBM 127-qubit Eagle) in this study. The methodology and results sections describe the experiences gained from applying and evaluating quantum ML results on climate and weather data obtained from NASA satellites as a novel practical application of quantum computing.

Earth Observational Data↗

DOE OSTI2021

Scalable Approaches to Selecting Key Entities in Large Networked Infrastructure Systems

This work aims at bringing advances in discrete optimization algorithms to solving practical engineering problems at scale. Often times, in many engineering design problems, there is a need to select a small set of influential or representative elements from a large ground set of entities in an optimal fashion. Submodular optimization provides for a formal way to solve such problems. Common examples with infrastructure systems involve sensor placement and identification of key entities with certain objectives. However, scaling these approaches to large infrastructure systems can be challenging because of the high computational complexity of the overall framework that include the optimization algorithms as well as high-complexity compute-oracles that provide the necessary objective function values. In this work, we explore a well-studied and widely-applicable paradigm, namely leader-selection in a multi-agent networked setting in the context of scalable methodologies. We demonstrate novel frameworks that utilize variations of accelerated submodular optimization algorithms along with linear-algebraic methods that can help accelerate the oracle computations. We further explore this combination in conjunction with graph partitioning paradigms to take advantage of the accelerated algorithms in a distributed setting. Finally we demonstrate the key findings on a practical problem in an operational setting. For this, we leverage an example road network with approximately 18k nodes and 27k edges in a traffic control application, where we seek a limited number of k=200 key intersections. This problem can be solved in a serial setting in just under 5 hours providing more than 2 orders of magnitude speed-up over methods that do not consider acceleration techniques.

Visweswara Sathanur, Arun↗

NASA NTRS1989

Thermodynamic cost of computation, algorithmic complexity and the information metric

Algorithmic complexity is discussed as a computational counterpart to the second law of thermodynamics. It is shown that algorithmic complexity, which is a measure of randomness, sets limits on the thermodynamic cost of computations and casts a new light on the limitations of Maxwell's demon. Algorithmic complexity can also be used to define distance between binary strings.

Zurek, W. H.↗

DOE OSTI2023

Computing the Relative Affinity of Chlorophylls a and b to Light-Harvesting Complex II

In plants and algae, the primary antenna protein bound to photosystem II is light-harvesting complex II (LHCII), a pigment–protein complex that binds eight chlorophyll (Chl) a molecules and six Chl b molecules. Chl a and Chl b differ only in that Chl a has a methyl group (–CH 3 ) on one of its pyrrole rings, while Chl b has a formyl group (–CHO) at that position. This blue-shifts the Chl b absorbance relative to Chl a . It is not known how the protein selectively binds the right Chl type at each site. Knowing the selection criteria would allow the design of light-harvesting complexes that bind different Chl types, modifying an organism to utilize the light of different wavelengths. The difference in the binding affinity of Chl a and Chl b in pea and spinach LHCII was calculated using multiconformation continuum electrostatics and free energy perturbation. Both methods have identified some Chl sites where the bound Chl type ( a or b ) has a significantly higher affinity, especially when the protein provides a hydrogen bond for the Chl b formyl group. However, the Chl a sites often have little calculated preference for one Chl type, so they are predicted to bind a mixture of Chl a and b . The electron density of the spinach LHCII was reanalyzed, which, however, confirmed that there is negligible Chl b in the Chl a -binding sites. Finally, it is suggested that the protein chooses the correct Chl type during folding, segregating the preferred Chl to the correct binding site.

chemical calculations↗

DOE OSTI2017

Cloud Computing for Complex Performance Codes.

This report describes the use of cloud computing services for running complex public domain performance assessment problems. The work consisted of two phases: Phase 1 was to demonstrate complex codes, on several differently configured servers, could run and compute trivial small scale problems in a commercial cloud infrastructure. Phase 2 focused on proving non-trivial large scale problems could be computed in the commercial cloud environment. The cloud computing effort was successfully applied using codes of interest to the geohydrology and nuclear waste disposal modeling community.

12 MANAGEMENT OF RADIOACTIVE AND NON-RADIOACTIVE W↗

DOE OSTI2017

Systems and methods for rapid processing and storage of data

Systems and methods of building massively parallel computing systems using low power computing complexes in accordance with embodiments of the invention are disclosed. A massively parallel computing system in accordance with one embodiment of the invention includes at least one Solid State Blade configured to communicate via a high performance network fabric. In addition, each Solid State Blade includes a processor configured to communicate with a plurality of low power computing complexes interconnected by a router, and each low power computing complex includes at least one general processing core, an accelerator, an I/O interface, and cache memory and is configured to communicate with non-volatile solid state memory.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2019

Systems and methods for rapid processing and storage of data

Stalzer, Mark A.↗

DOE OSTI2021

Systems and methods for rapid processing and storage of data

Stalzer, Mark A.↗

DOE OSTI2025

Sign Problem in Tensor-Network Contraction

We investigate how the computational difficulty of contracting tensor networks depends on the sign structure of the tensor entries. Using results from computational complexity, we observe that the approximate contraction of tensor networks with only positive entries has lower computational complexity as compared to tensor networks with general real or complex entries. This raises the question of how this transition in computational complexity manifests itself in the hardness of different tensor-network-contraction schemes. We pursue this question by studying random tensor networks with varying bias toward positive entries. First, we consider contraction via Monte Carlo sampling and find that the transition from hard to easy occurs when the tensor entries become predominantly positive; this can be understood as a tensor-network manifestation of the well-known negative-sign problem in quantum Monte Carlo. Second, we analyze the commonly used contraction based on boundary tensor networks. The performance of this scheme is governed by the number of correlations in contiguous parts of the tensor network (which by analogy can be thought of as entanglement). Remarkably, we find that the transition from hard to easy—i.e., from a volume-law to a boundary-law scaling of entanglement—already occurs for a slight bias of the tensor entries toward a positive mean, scaling inversely with the bond dimension D , and thus the problem becomes easy the earlier the larger D occurs. This is in contrast both to expectations and to the behavior found in Monte Carlo contraction, where the hardness at fixed bias increases with the bond dimension. To provide insight into this early breakdown of computational hardness and the accompanying entanglement transition, we construct an effective classical statistical-mechanical model that predicts a transition at a bias of the tensor entries of 1 / D , confirming our observations. We conclude by investigating the computational difficulty of computing expectation values of tensor-network wave functions (projected entangled-pair states, PEPSs) and find that in this setting, the complexity of entanglement-based contraction always remains low. We explain this by providing a local transformation that maps PEPS expectation values to a positive-valued tensor network. This not only provides insight into the origin of the observed boundary-law entanglement scaling but also suggests new approaches toward PEPS contraction based on positive decompositions. Published by the American Physical Society 2025

Chen, Jielun (ORCID:0000000178411545)↗

DOE OSTI2018

On Bellman’s and Knuth’s Problems and their Generalizations

Various generalizations of the classical problem of the fastest raising to a power (or the so-called problem on addition chains) are studied in the asymptotic sense. Under weak restrictions, we demonstrate asymptotically tight solutions of the two best known generalizations, namely, Bellman’s problem on the computational complexity (on the minimal number of multiplication operations) of a normed monomial of several variables and Knuth’s problem on the computational complexity of a power system of one variable. We also briefly review some results on the computational complexity for three problems, namely, the computation of p-element systems of normed monomials in q variables, additive computations for systems of p integer linear forms over q variables, and the computation of p-element systems of the free Abelian group with q generators.

97 MATHEMATICS AND COMPUTING↗

NASA NTRS1969

Efficient computation of the complex error function

Computation of complex error function

Gautschi, W.↗

DOE OSTI2023

The Tiny Triplet Finder as a Versatile Track Segment Seeding Engine for Trigger Systems

In high energy physics experiment trigger systems, track segment seeding is a resource consuming function and the primary reason is the computing complexity of the segment finding process. As the Moore's Law is reaching its physical limit, reducing computing complexity should be carefully considered, rather than keep piling up silicon resources. The Tiny Triplet Finder is a scheme that reduces the computing complexity of the segment seeding. As a proof of concept, a 3D track segment seeding engine core based on the Tiny Triplet Finder has been implemented and tested in a low-cost FPGA device. The seeding engine is designed to preselect and group hits (stubs) from detector layers to feed subsequent track fitting stage. The seeding engine consists of a Hough transform space for r-z view and a Tiny Triplet Finder for r-phi view to implement 3D constraints. The seeding engine is organized as a pipeline so that each hit is processed in a single clock cycle. Taking advantage of the register-like storage block scheme which enables effectively resetting of a block RAM within a single clock cycle, clearing or refreshing the seeding engine takes only one clock cycles between two events. The Tiny Triplet Finder is also a generic coincidence finding scheme that can be used for many tasks. As a versatility demonstration, track segment finding performances for two distinctive detector geometries are tested in our seeding engine. In a collider barrel-layer geometry, the fake segment rates are studied for 3D (i.e., both r-phi and r-z views) and 2D (i.e., r-phi or r-z view only) configurations for high hit multiplicity events (>4000 hits/layer in the barrel region). Another detector geometry contains strip plane layers with timing information. The numbers of coincidences, both real or fake, with or without timing ("3D" or "2D") information at various hit multiplicities are studied.

43 PARTICLE ACCELERATORS↗

DOE OSTI2023

Efficient and Robust Jet Tagging at the LHC with Knowledge Distillation

The challenging environment of real-time data processing systems at the Large Hadron Collider (LHC) strictly limits the computational complexity of algorithms that can be deployed. For deep learning models, this implies that only models with low computational complexity that have weak inductive bias are feasible. To address this issue, we utilize knowledge distillation to leverage both the performance of large models and the reduced computational complexity of small ones. In this paper, we present an implementation of knowledge distillation, demonstrating an overall boost in the student models' performance for the task of classifying jets at the LHC. Furthermore, by using a teacher model with a strong inductive bias of Lorentz symmetry, we show that we can induce the same inductive bias in the student model which leads to better robustness against arbitrary Lorentz boost.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

DOE OSTI2022

Trajectory prediction dimensionality reduction for low-cost connected automated vehicle systems

Here, to facilitate low-cost connected automated vehicle (CAV) system development, this study proposes two interpretable dimensionality reduction techniques in vehicle trajectory prediction, i.e., the piecewise Taylor series approximation (PTA) and the piecewise Fourier series approximation (PFA), to lower computation complexity, reduce device investment, and decrease computation energy consumption. Two benchmarks are developed, the long short-term memory (LSTM)-based model without dimensionality reduction and the LSTM-based model with encoder-decoder (a widely used dimensionality reduction technique). Results show that the four predictions have similar accuracy, and the training time (proportional to computation energy consumption) of models with dimensionality reduction techniques is greatly reduced. The reduction is even more significant when PTA/PFA is used. Sensitivity analysis advises PFA/PTA parameter selections to reduce computation complexity without significant loss of prediction accuracy. Further, the robustness of the LSTM PTA/PFA is proven by the investigation of data noises.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

NASA NTRS1985

Where are the parallel algorithms?

Four paradigms that can be useful in developing parallel algorithms are discussed. These include computational complexity analysis, changing the order of computation, asynchronous computation, and divide and conquer. Each is illustrated with an example from scientific computation, and it is shown that computational complexity must be used with great care or an inefficient algorithm may be selected.

Voigt, R. G.↗

NASA NTRS1989

A unifying framework for rigid multibody dynamics and serial and parallel computational issues

A unifying framework for various formulations of the dynamics of open-chain rigid multibody systems is discussed. Their suitability for serial and parallel processing is assessed. The framework is based on the derivation of intrinsic, i.e., coordinate-free, equations of the algorithms which provides a suitable abstraction and permits a distinction to be made between the computational redundancy in the intrinsic and extrinsic equations. A set of spatial notation is used which allows the derivation of the various algorithms in a common setting and thus clarifies the relationships among them. The three classes of algorithms viz., O(n), O(n exp 2) and O(n exp 3) or the solution of the dynamics problem are investigated. Researchers begin with the derivation of O(n exp 3) algorithms based on the explicit computation of the mass matrix and it provides insight into the underlying basis of the O(n) algorithms. From a computational perspective, the optimal choice of a coordinate frame for the projection of the intrinsic equations is discussed and the serial computational complexity of the different algorithms is evaluated. The three classes of algorithms are also analyzed for suitability for parallel processing. It is shown that the problem belongs to the class of N C and the time and processor bounds are of O(log2/2(n)) and O(n exp 4), respectively. However, the algorithm that achieves the above bounds is not stable. Researchers show that the fastest stable parallel algorithm achieves a computational complexity of O(n) with O(n exp 4), respectively. However, the algorithm that achieves the above bounds is not stable. Researchers show that the fastest stable parallel algorithm achieves a computational complexity of O(n) with O(n exp 2) processors, and results from the parallelization of the O(n exp 3) serial algorithm.

Fijany, Amir↗