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.
Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.
Computational Complexity of Neuromorphic Algorithms
Neuromorphic computing has several characteristics that make it an extremely compelling computing paradigm for post Moore computation. Some of these characteristics include intrinsic parallelism, inherent scalability, collocated processing and memory, and event-driven computation. While these characteristics impart energy efficiency to neuromorphic systems, they do come with their own set of challenges. One of the biggest challenges in neuromorphic computing is to establish the theoretical underpinnings of the computational complexity of neuromorphic algorithms. In this paper, we take the first steps towards defining the space and time complexity of neuromorphic algorithms. Specifically, we describe a model of neuromorphic computation and state the assumptions that govern the computational complexity of neuromorphic algorithms. Next, we present a theoretical framework to define the computational complexity of a neuromorphic algorithm. We explicitly define what space and time complexities mean in the context of neuromorphic algorithms based on our model of neuromorphic computation. Finally, we leverage our approach and define the computational complexities of six neuromorphic algorithms: constant function, successor function, predecessor function, projection function, neuromorphic sorting algorithm and neighborhood subgraph extraction algorithm.
Computational complexity of the landscape II—Cosmological considerations
We propose a new approach for multiverse analysis based on computational complexity, which leads to a new family of “computational” measure factors. By defining a cosmology as a space–time containing a vacuum with specified properties (for example small cosmological constant) together with rules for how time evolution will produce the vacuum, we can associate global time in a multiverse with clock time on a supercomputer which simulates it. We argue for a principle of “limited computational complexity” governing early universe dynamics as simulated by this supercomputer, which translates to a global measure for regulating the infinities of eternal inflation. The rules for time evolution can be thought of as a search algorithm, whose details should be constrained by a stronger principle of “minimal computational complexity”. Unlike previously studied global measures, ours avoids standard equilibrium considerations and the well-known problems of Boltzmann Brains and the youngness paradox. We also give various definitions of the computational complexity of a cosmology, and argue that there are only a few natural complexity classes.
The Computational Complexity of Multidimensional Persistence
We present findings on the computational complexity of computing multidimensional persistent homology. We first show that the worst-case computational complexity of multidimensional persistence is exponential. We then present an algorithm for computing multidimensional persistence which extends the algorithm given by Zomorodian and Carlsson for computing one-dimensional persistence. The computational complexity of our algorithm is polynomial in the size of the persistence module and exponential in the persistence dimension.
Analyzing the Effects of Water Output Rates on the Strategic Computing Complex
At the Los Alamos National Laboratory, the Strategic Computing Complex (SCC) requires chilled water to properly allow its supercomputers and other systems to properly function. In order to do so, the SCC heavily relies on the use of treated water from the Sanitary Waste Water System (SWWS) and the Sanitary Effluent Reclamation Facility (SERF). Industrial water that can be reused, such as from toilets and sinks, as well as rain and well water, arrives at the SWWS where it is aerated and processed. From there, a portion of the water can evaporate, while some of it is removed in the form of sludge or discharged into the nearby canyon. However, a majority of this reuse water is transported to SERF, where it is further processed and treated. Here is the location where this water becomes “usable” once again. From there, is transported to cooling towers where the water becomes chilled and can properly cool the supercomputers at the SCC. In fact, nearly all of the reuse water utilized by the SCC is treated and processed at SERF. This analysis specifically examines the water that leaves SWWS for SERF.
Computational Spectroscopy of the Cr–Cr Bond in Coordination Complexes
In this work, we report the accurate computational vibrational analysis of the Cr–Cr bond in dichromium complexes using second-order multireference complete active space methods (CASPT2), allowing direct comparison with experimental spectroscopic data both to facilitate interpreting the low-energy region of the spectra and to provide insights into the nature of the bonds themselves. Recent technological development by the authors has realized such computation for the first time. Accurate simulation of the vibrational structure of these compounds has been hampered by their notorious multiconfigurational electronic structure that yields bond distances that do not correlate with bond order. Some measured Cr–Cr vibrational stretching modes, ν(Cr 2 ), have suggested weaker bonding, even for so-called ultrashort Cr–Cr bonds, while others are in line with the bond distance. Here, we optimize geometries and compute ν(Cr 2 ) with CASPT2 for three well-characterized complexes, Cr 2 (O 2 CCH 3 ) 4 (H 2 O) 2 , Cr 2 (mhp) 4 , and Cr 2 (dmp) 4 . We obtain CASPT2 harmonic ν(Cr 2 ) modes in good agreement with experiment at 282 cm –1 for Cr 2 (mhp) 4 and 353 cm –1 for Cr 2 (dmp) 4 , compute 50 Cr and 54 Cr isotope shifts, and demonstrate that the use of the so-called IPEA shift leads to improved Cr–Cr distances. Additionally, normal mode sampling was used to estimate anharmonicity along ν(Cr 2 ), leading to an anharmonic mode of 272 cm –1 for Cr 2 (mhp) 4 and 333 cm –1 for Cr 2 (dmp) 4 .
Charge-Transfer Luminescence in a Molecular Donor–Acceptor Complex: Computational Insights
Donor–acceptor molecular complexes are a popular class of materials utilizing charge-transfer states for practical applications. A recent class of donor–acceptor dyads based on the fluorescent BODIPY functionalized with triphenylamine (TPA) shows the peculiar property of dual fluorescence. It is hypothesized that instead of the sensitized charge-transfer state being optically dark, it provides an additional bright radiative pathway. In this study, we use time-dependent density functional theory to characterize the energetic alignment of excitonic and charge-transfer states in a BODIPY-TPA molecular complex. We observe that using a long-range exchange corrected functional in combination with state-specific solvation scheme gives a qualitatively correct alignment of the exciton and charge-transfer states and an enhancement in oscillator strength for the equilibrium solvated charge-transfer state, in agreement with experiment. Furthermore, this work provides rationalization of charge-transfer state emission and provides a foundation to explore charge-transfer using ab initio excited-state nonadiabatic dynamics.
Efficient electronic structure theory via hierarchical scale-adaptive coupled-cluster formalism: I. Theory and computational complexity analysis
In this work, a novel reduced-scaling, general-order coupled-cluster approach is formulated by exploiting hierarchical representations of many-body tensors, combined with the recently suggested formalism of scale-adaptive tensor algebra. Inspired by the hierarchical techniques from the renormalization group approach, H/H 2 -matrix algebra and fast multipole method, the computational scaling reduction in our formalism is achieved via coarsening of quantum many-body interactions at larger interaction scales, thus imposing a hierarchical structure on many-body tensors of coupled-cluster theory. In our approach, the interaction scale can be defined on any appropriate Euclidean domain (spatial domain, momentum-space domain, energy domain, etc.). Additionally, we show that the hierarchically resolved many-body tensors reduce the storage requirements to O(N), where N is the number of simulated quantum particles. Subsequently, we prove that any connected many-body diagram with arbitrary-order tensors, e.g., an arbitrary coupled-cluster diagram, can be evaluated in O(NlogN) floating-point operations. On top of that, we elaborate an additional approximation to further reduce the computational complexity of higher-order coupled-cluster equations, i.e., equations involving higher than double excitations, which otherwise would introduce a large prefactor into formal O(NlogN) scaling.
Quantum magic and computational complexity in the neutrino sector
We consider the quantum magic in systems of dense neutrinos undergoing coherent flavor transformations, relevant for supernova and neutron-star binary mergers. Mapping the three-flavor-neutrino system to qutrits, the evolution of quantum magic is explored in the single scattering angle limit for a selection of initial tensor-product pure states for 𝑁 𝜈 ≤ 8 neutrinos. For |𝜈𝑒⟩ ⊗𝑁𝜈 initial states, the magic, as measured by the 𝛼 = 2 stabilizer Renyi entropy ℳ 2 , is found to decrease with radial distance from the neutrino sphere, reaching a value that lies below the maximum for tensor-product qutrit states. Further, the asymptotic magic per neutrino, ℳ 2 /𝑁 𝜈 , decreases with increasing 𝑁 𝜈 . In contrast, the magic evolving from states containing all three flavors reaches values only possible with entanglement, with the asymptotic ℳ 2 /𝑁 𝜈 increasing with 𝑁 𝜈 . These results highlight the connection between the complexity in simulating quantum physical systems and the parameters of the Standard Model.
Glassy Word Problems: Ultraslow Relaxation, Hilbert Space Jamming, and Computational Complexity
We introduce a family of local models of dynamics based on “word problems” from computer science and group theory, for which we can place rigorous lower bounds on relaxation timescales. These models can be regarded either as random circuit or local Hamiltonian dynamics and include many familiar examples of constrained dynamics as special cases. The configuration space of these models splits into dynamically disconnected sectors, and for initial states to relax, they must “work out” the other states in the sector to which they belong. When this problem has a high time complexity, relaxation is slow. In some of the cases we study, this problem also has high space complexity. When the space complexity is larger than the system size, an unconventional type of jamming transition can occur, whereby a system of a fixed size is not ergodic but can be made ergodic by appending a large reservoir of sites in a trivial product state. This finding manifests itself in a new type of Hilbert space fragmentation that we call fragile fragmentation. We present explicit examples where slow relaxation and jamming strongly modify the hydrodynamics of conserved densities. In one example, density modulations of wave vector q exhibit almost no relaxation until times O ( exp ( 1 / q ) ) , at which point they abruptly collapse. We also comment on extensions of our results to higher dimensions. Published by the American Physical Society 2024
Reducing COmputational Complexity in Moment of Fluid Interface Reconstruction
Abstract not provided
Quantum Magic and Computational Complexity in the Neutrino Sector
Explore the source record for details and available documents.
Entanglement entropy and computational complexity of the periodically driven Anderson impurity model
We study the growth of entanglement entropy and bond dimension with time in density matrix renormalization group simulations of the periodically driven single-impurity Anderson model. The growth of entanglement entropy is found to be related to the ordering of the bath orbitals and to the relation of the driving period T to the convergence radius of the Floquet-Magnus expansion. Furthermore, ordering the bath orbitals by their Floquet quasienergy is found to reduce the exponential growth rate of the computation time at intermediate driving periods, suggesting new ways to optimize matrix product state calculations of driven systems.
Quantum sampling algorithms, phase transitions, and computational complexity
Not Available
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.