Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “algorithmic efficiency”

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 271 records · Page 15

Calculation of permanent magnet arrangements for stellarators: a linear least-squares method

A problem arising in several engineering areas is to design magnets outside a volume that produce a desired magnetic field inside it. One instance of this problem is stellarator design, where it has recently been shown that permanent magnets can provide the required shaping of the magnetic field. Here we demonstrate a robust and efficient algorithm REGCOIL_PM to calculate the spatial distribution of these permanent magnets. The procedure involves a small number of fixed-point iterations, with a linear least-squares problem solved at each step. Furthermore, the method exploits the Biot–Savart Law's exact linearity in magnetization density and approximate linearity in magnet size, for magnets far from the target region. No constraint is placed on the direction of magnetization, so Halbach solutions are found naturally, and the magnitude of the magnetization can be made uniformly equal to a target value.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

Implementation of Maxwell's equations in the reconstruction of the magnetic field in the g -2 storage ring

We present a method for implementing the constraints that are implied by Maxwell's equations in fits to measurements of the magnetic field in the muon storage ring of the $g - 2$ experiment. The method that we use makes use of toroidal-harmonic solutions of Laplace's equation. We point out that the fitting problem can be approximated well as a linear-algebra problem. We have devised an efficient algorithm for the linear-algebra problem that makes it possible to find a solution for 10 5 data points and 10 4 harmonics in less than an hour on a present-day desktop computer. We illustrate our method by applying it to some preliminary measurements of the magnetic field in the $g - 2$ storage ring.

43 PARTICLE ACCELERATORS↗

A variant selection framework for genome graphs

Abstract Motivation Variation graph representations are projected to either replace or supplement conventional single genome references due to their ability to capture population genetic diversity and reduce reference bias. Vast catalogues of genetic variants for many species now exist, and it is natural to ask which among these are crucial to circumvent reference bias during read mapping. Results In this work, we propose a novel mathematical framework for variant selection, by casting it in terms of minimizing variation graph size subject to preserving paths of length α with at most δ differences. This framework leads to a rich set of problems based on the types of variants [e.g. single nucleotide polymorphisms (SNPs), indels or structural variants (SVs)], and whether the goal is to minimize the number of positions at which variants are listed or to minimize the total number of variants listed. We classify the computational complexity of these problems and provide efficient algorithms along with their software implementation when feasible. We empirically evaluate the magnitude of graph reduction achieved in human chromosome variation graphs using multiple α and δ parameter values corresponding to short and long-read resequencing characteristics. When our algorithm is run with parameter settings amenable to long-read mapping (α = 10 kbp, δ = 1000), 99.99% SNPs and 73% SVs can be safely excluded from human chromosome 1 variation graph. The graph size reduction can benefit downstream pan-genome analysis. Availability and implementation https://github.com/AT-CG/VF. Supplementary information Supplementary data are available at Bioinformatics online.

59 BASIC BIOLOGICAL SCIENCES↗

FluxRETAP: a REaction TArget Prioritization genome-scale modeling technique for selecting genetic targets

MOTIVATION: Metabolic engineering is rapidly evolving as a result of new advances in synthetic biology tools and automation platforms that enable high throughput strain construction, as well as the development of machine learning tools (ML) for biology. However, selecting genetic engineering targets that effectively guide the metabolic engineering process is still challenging. ML can provide predictive power for synthetic biology, but current technical limitations prevent the independent use of ML approaches without previous biological knowledge. RESULTS: Here, we present FluxRETAP, a simple and computationally inexpensive method that leverages the prior mechanistic knowledge embedded in genome-scale models for suggesting targets for genetic overexpression, downregulation or deletion, with the final goal of increasing the production of a desired metabolite. This method can provide a list of desirable engineering targets that can be combined with current ML pipelines. FluxRETAP captured 100% of reaction targets experimentally verified to improve Escherichia coli isoprenol production, 50% of targets that experimentally improved taxadiene production in E. coli and ∼60% of genetic targets from a verified minimal constrained cut-set in Pseudomonas putida, while providing additional high priority targets that could be tested. Overall, FluxRETAP is an efficient algorithm for identifying a prioritized list of testable genetic and reaction targets. AVAILABILITY AND IMPLEMENTATION: FluxRETAP is implemented in python and released under the creative commons license. The implementation and code are freely available at: https://github.com/JBEI/FluxRETAP.

Czajka, Jeffrey J↗

Automatic detection of low surface brightness galaxies from Sloan Digital Sky Survey images

ABSTRACT Low surface brightness (LSB) galaxies are galaxies with central surface brightness fainter than the night sky. Due to the faint nature of LSB galaxies and the comparable sky background, it is difficult to search LSB galaxies automatically and efficiently from large sky survey. In this study, we established the low surface brightness galaxies autodetect (LSBG-AD) model, which is a data-driven model for end-to-end detection of LSB galaxies from Sloan Digital Sky Survey (SDSS) images. Object-detection techniques based on deep learning are applied to the SDSS field images to identify LSB galaxies and estimate their coordinates at the same time. Applying LSBG-AD to 1120 SDSS images, we detected 1197 LSB galaxy candidates, of which 1081 samples are already known and 116 samples are newly found candidates. The B-band central surface brightness of the candidates searched by the model ranges from 22 to 24 mag arcsec−2, quite consistent with the surface brightness distribution of the standard sample. A total of 96.46 per cent of LSB galaxy candidates have an axial ratio (b/a) greater than 0.3, and 92.04 per cent of them have $fracDev\_r$ < 0.4, which is also consistent with the standard sample. The results show that the LSBG-AD model learns the features of LSB galaxies of the training samples well, and can be used to search LSB galaxies without using photometric parameters. Next, this method will be used to develop efficient algorithms to detect LSB galaxies from massive images of the next-generation observatories.

79 ASTRONOMY AND ASTROPHYSICS↗

Using galaxy pairs to investigate the three-point correlation function in the squeezed limit

We investigate the three-point correlation function (3PCF) in the squeezed limit by considering galaxy pairs as discrete objects and cross-correlating them with the galaxy field. We develop an efficient algorithm using fast Fourier transforms to compute such cross-correlations and their associated pair-galaxy bias bp, g and the squeezed 3PCF coefficient Qeff. We implement our method using N-body cosmological simulations and a fiducial halo occupation distribution (HOD) and present the results in both the real space and redshift space. In real space, we observe a peak in b p, g and Q eff at pair separation of ~2 Mpc, attributed to the fact that galaxy pairs at 2 Mpc separation trace the most massive dark matter haloes. We also see strong anisotropy in the b p, g and Qeff signals that track the large-scale filamentary structure. In redshift space, both the 2 Mpc peak and the anisotropy are significantly smeared out along the line of sight due to finger-of-God effect. In both the real space and redshift space, the squeezed 3PCF shows a factor of 2 variation, contradicting the hierarchical ansatz, but offering rich information on the galaxy-halo connection. Thus, we explore the possibility of using the squeezed 3PCF to constrain the HOD. When we compare two simple HOD models that are closely matched in their projected two-point correlation function (2PCF), we do not yet see a strong variation in the 3PCF that is clearly disentangled from variations in the projected 2PCF. Nevertheless, we propose that more complicated HOD models, e.g. those incorporating assembly bias, can break degeneracies in the 2PCF and show a distinguishable squeezed 3PCF signal.

79 ASTRONOMY AND ASTROPHYSICS↗

Time evolution of projected entangled pair states in the single-layer picture

We propose an efficient algorithm for simulating quantum many-body systems in two spatial dimensions using projected entangled pair states. This is done by approximating the environment, arising in the context of updating tensors in the process of time evolution, using a single-layered tensor network structure. This significantly reduces the computational costs and allows simulations in a larger submanifold of the Hilbert space as bounded by the bond dimension of the tensor network. We present numerical evidence for stability of the method on an antiferromagnetic isotropic Heisenberg model where good agreement is found with the available accurate results.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Exactly solvable model for nonlinear light-matter interaction in an arbitrary time-dependent field

Exact analytic expressions are derived for the dipole moment and nonlinear current of a one-dimensional quantum particle subject to a short-range attractive potential and an arbitrary time-dependent electric field. An efficient algorithm for the current evaluation is described and a robust implementation suitable for numerical simulations is demonstrated.

74 ATOMIC AND MOLECULAR PHYSICS↗

Efficient numerical method for evaluating normal and anomalous time-domain equilibrium Green's functions in inhomogeneous systems

In this work we develop EPOCH (equilibrium propagator by orthogonal polynomial chain), a computationally efficient method to calculate the time-dependent equilibrium Green's functions, including the anomalous Green's functions of superconductors, to capture the time evolution in large inhomogeneous systems. The EPOCH method generalizes the Chebyshev wave-packet propagation method from quantum chemistry and efficiently incorporates the Fermi-Dirac statistics that is needed for equilibrium quantum condensed matter systems. The computational cost of EPOCH scales only linearly in the system degrees of freedom, generating an extremely efficient algorithm also for very large systems. We demonstrate the power of the EPOCH method by calculating the time evolution of an excitation near a superconductor–normal metal interface in two and three dimensions, capturing transmission as well as normal and Andreev reflections.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗

Precisely computing phonons via irreducible derivatives

Computing phonons from first principles is typically considered a solved problem, yet inadequacies in existing techniques continue to yield deficient results in systems with sensitive phonons. Here, in this study, we circumvent this issue using the lone irreducible derivative (LID) and bundled irreducible derivative (BID) approaches to computing phonons via finite displacements, where the former optimizes precision via energy derivatives and the latter provides the most efficient algorithm using force derivatives. A condition number optimized basis for BID is derived which guarantees the minimum amplification of error. Additionally, a hybrid LID-BID approach is formulated, in which select irreducible derivatives computed using LID replace BID results. We illustrate our approach on two prototypical systems with sensitive phonons: the shape memory alloy AuZn and metallic lithium. Comparing our resulting phonons in the aforementioned crystals to calculations in the literature reveals nontrivial inaccuracies. Our approaches can be fully automated, making them well suited for both niche systems of interest and high-throughput approaches.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗

Many-body localization as a large family of localized ground states

Many-body localization (MBL) addresses the absence of thermalization in interacting quantum systems, with nonergodic high-energy eigenstates behaving as ground states, only area-law entangled. However, computing highly excited many-body eigenstates using exact methods is very challenging. Instead, we show that one can address high-energy MBL physics using ground-state methods, which are much more amenable to many efficient algorithms. Here, we find that a localized many-body ground state of a given interacting disordered Hamiltonian H 0 is a very good approximation for a high-energy eigenstate of a parent Hamiltonian, close to H 0 but more disordered. Lastly, this construction relies on computing the covariance matrix, easily achieved using density-matrix renormalization group for disordered Heisenberg chains up to L=256 sites.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Efficient neutrino oscillation parameter inference using Gaussian processes

The unified approach of Feldman and Cousins allows for exact statistical inference of small signals that commonly arise in high energy physics. It has gained widespread use, for instance, in measurements of neutrino oscillation parameters in long-baseline experiments. However, the approach relies on the Neyman construction of the classical confidence interval and is computationally intensive as it is typically done in a grid-based fashion over the entire parameter space. In this article, we propose an efficient algorithm for the Feldman-Cousins approach using Gaussian processes to construct confidence intervals iteratively. Further, we show that in the neutrino oscillation context, one can obtain confidence intervals fives times faster in one dimension and ten times faster in two dimensions, while maintaining an accuracy above 99.5%.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

Constraints on a phenomenologically parametrized neutron-star equation of state

We introduce a parametrized high-density equation of state (EOS) in order to systematize the study of constraints placed by astrophysical observations on the nature of neutron-star matter. To obtain useful constraints, the number of parameters must be smaller than the number of EOS-related neutron-star properties measured, but large enough to accurately approximate the large set of candidate EOSs. We find that a parametrized EOS based on piecewise polytropes with 3 free parameters matches, to about 4% rms error, an extensive set of candidate EOSs at densities below the central density of 1.4M{sub {center_dot}} stars. Adding observations of more massive stars constrains the higher-density part of the EOS and requires an additional parameter. We obtain constraints on the allowed parameter space set by causality and by present and near-future astronomical observations with the least model dependence. Stringent constraints on the EOS parameter space are associated with the future measurement of the moment of inertia of PSR J0737-3039A combined with the maximum known neutron-star mass. We also present in an appendix a more efficient algorithm than has previously been used for finding points of marginal stability and the maximum angular velocity of stable stars.

79 ASTRONOMY AND ASTROPHYSICS↗

Universal energy-speed-accuracy trade-offs in driven nonequilibrium systems

The connection between measure theoretic optimal transport and dissipative nonequilibrium dynamics provides a language for quantifying nonequilibrium control costs, leading to a collection of thermodynamic speed limits, which rely on the assumption that the target probability distribution is perfectly realized. This is almost never the case in experiments or numerical simulations, so here we address the situation in which the external controller is imperfect. We obtain a lower bound for the dissipated work in generic nonequilibrium control problems that (1) is asymptotically tight and (2) matches the thermodynamic speed limit in the case of optimal driving. Along with analytically solvable examples, we refine this imperfect driving notion to systems in which the controlled degrees of freedom are slow relative to the nonequilibrium relaxation rate, and identify independent energy contributions from fast and slow degrees of freedom. Furthermore, we develop a strategy for optimizing minimally dissipative protocols based on optimal transport flow matching, a generative machine learning technique. Furthermore, this latter approach ensures the scalability of both the theoretical and computational framework we put forth. Crucially, we demonstrate that we can compute the terms in our bound numerically using efficient algorithms from the computational optimal transport literature and that the protocols we learn saturate the bound.

59 BASIC BIOLOGICAL SCIENCES↗

Topological Quantum Hashing with the Icosahedral Group

We study an efficient algorithm to hash any single-qubit gate into a braid of Fibonacci anyons represented by a product of icosahedral group elements. By representing the group elements by braid segments of different lengths, we introduce a series of pseudogroups. Joining these braid segments in a renormalization group fashion, we obtain a Gaussian unitary ensemble of random-matrix representations of braids. With braids of length O(log{sup 2}(1/{epsilon})), we can approximate all SU(2) matrices to an average error {epsilon} with a cost of O(log(1/{epsilon})) in time. The algorithm is applicable to generic quantum compiling.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Predicting Adaptively Chosen Observables in Quantum Systems

Recent advances have demonstrated that 𝒪⁡(log 𝑀) measurements suffice to predict 𝑀 properties of arbitrarily large quantum many-body systems. However, these remarkable findings assume that the properties to be predicted are chosen independently of the data. This assumption can be violated in practice, where scientists adaptively select properties after looking at previous predictions. This work investigates the adaptive setting for three classes of observables: local, Pauli, and bounded-Frobenius-norm observables. We prove that Ω⁡(√𝑀) samples of an arbitrarily large unknown quantum state are necessary to predict expectation values of 𝑀 adaptively chosen local and Pauli observables, where the system size scales exponentially and polynomially in 𝑀, respectively. We also present computationally efficient algorithms that achieve this information-theoretic lower bound. In contrast, for bounded-Frobenius-norm observables, we devise an algorithm requiring only 𝒪⁡(log 𝑀) samples, independent of system size. These results highlight the potential pitfalls of adaptivity in analyzing data from quantum experiments and provide algorithmic tools to safeguard against erroneous predictions in quantum experiments.

Machine learning↗

Triangulation Made Easy

We describe a simple and efficient algorithm for two-view triangulation of 3D points from approximate 2D matches based on minimizing the L2 reprojection error. Our iterative algorithm improves on the one by Kanatani et al. by ensuring that in each iteration the epipolar constraint is satisfied. In the case where the two cameras are pointed in the same direction, the method provably converges to an optimal solution in exactly two iterations. For more general camera poses, two iterations are sufficient to achieve convergence to machine precision, which we exploit to devise a fast, non-iterative method. The resulting algorithm amounts to little more than solving a quadratic equation, and involves a fixed, small number of simple matrixvector operations and no conditional branches. We demonstrate that the method computes solutions that agree to very high precision with those of Hartley and Sturm's original polynomial method, though achieves higher numerical stability and 1-4 orders of magnitude greater speed.

99 GENERAL AND MISCELLANEOUS↗

Scalable Static and Dynamic Community Detection Using Grappolo

Graph clustering, popularly known as community detection, is a fundamental kernel for several applications of relevance to the Defense Advanced Research Projects Agency’s (DARPA) Hierarchical Identify Verify Exploit (HIVE) Pro- gram. Clusters or communities represent natural divisions within a network that are densely connected within a cluster and sparsely connected to the rest of the network. The need to compute clustering on large scale data necessitates the development of efficient algorithms that can exploit modern architectures that are fundamentally parallel in nature. How- ever, due to their irregular and inherently sequential nature, many of the current algorithms for community detection are challenging to parallelize. In response to the HIVE Graph Challenge, we present several parallelization heuristics for fast community detection using the Louvain method as the serial template. We implement all the heuristics in a software library called Grappolo. Using the inputs from the HIVE Challenge, we demonstrate superior performance and high quality solutions based on four parallelization heuristics. We use Grappolo on static graphs as the first step towards community detection on streaming graphs.

Community Detection↗