Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “heuristic”

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 865 records · Page 48

RF-Net 2: fast inference of virus reassortment and hybridization networks

Abstract Motivation A phylogenetic network is a powerful model to represent entangled evolutionary histories with both divergent (speciation) and convergent (e.g. hybridization, reassortment, recombination) evolution. The standard approach to inference of hybridization networks is to (i) reconstruct rooted gene trees and (ii) leverage gene tree discordance for network inference. Recently, we introduced a method called RF-Net for accurate inference of virus reassortment and hybridization networks from input gene trees in the presence of errors commonly found in phylogenetic trees. While RF-Net demonstrated the ability to accurately infer networks with up to four reticulations from erroneous input gene trees, its application was limited by the number of reticulations it could handle in a reasonable amount of time. This limitation is particularly restrictive in the inference of the evolutionary history of segmented RNA viruses such as influenza A virus (IAV), where reassortment is one of the major mechanisms shaping the evolution of these pathogens. Results Here, we expand the functionality of RF-Net that makes it significantly more applicable in practice. Crucially, we introduce a fast extension to RF-Net, called Fast-RF-Net, that can handle large numbers of reticulations without sacrificing accuracy. In addition, we develop automatic stopping criteria to select the appropriate number of reticulations heuristically and implement a feature for RF-Net to output error-corrected input gene trees. We then conduct a comprehensive study of the original method and its novel extensions and confirm their efficacy in practice using extensive simulation and empirical IAV evolutionary analyses. Availability and implementation RF-Net 2 is available at https://github.com/flu-crew/rf-net-2. Supplementary information Supplementary data are available at Bioinformatics online.

Markin, Alexey (ORCID:0000000332809050)↗

Finding diverse ways to improve algebraic connectivity through multi-start optimization

The algebraic connectivity, also known as the Fiedler value, is a spectral measure of network connectivity that can be increased through edge addition. We present an algorithm for producing many diverse ways to add a fixed number of edges to a network to achieve a near optimal Fiedler value. Previous Fielder value optimization algorithms (i.e. the greedy algorithm) output only one solution. Obtaining a single solution is rarely good enough for real-world network redesign problems, as practical constraints (political, physical or financial) may prevent implementation. Our algorithm takes a multi-start optimization approach, adding a random initial edge and then applies a greedy heuristic to improve the Fiedler value. The random choice moves us to a new region of the search space, enabling discovery of diverse solutions. Additionally, we present a Determinantal Point Process framework for quantifying diversity. We then apply a Markov chain Monte Carlo technique to sift through the large number of output solutions and locate a smaller, more manageable collection of highly diverse solutions that can be presented to network redesign engineers. We demonstrate the effectiveness of our algorithm on real-world graphs with varied structures.

97 MATHEMATICS AND COMPUTING↗

Syntgen: a system to generate temporal networks with user-specified topology

Abstract In the last few years, the study of temporal networks has progressed markedly. The evolution of clusters of nodes (or communities) is one of the major focus of these studies. However, the time dimension increases complexity, introducing new constructs and requiring novel and enhanced algorithms. In spite of recent improvements, the relative scarcity of timestamped representations of empiric networks, with known ground truth, hinders algorithm validation. A few approaches have been proposed to generate synthetic temporal networks that conform to static topological specifications while in general adopting an ad hoc approach to temporal evolution. We believe there is still a need for a principled synthetic network generator that conforms to problem domain topological specifications from a static as well as temporal perspective. Here, we present such a system. The unique attributes of our system include accepting arbitrary node degree and cluster size distributions and temporal evolution under user control, while supporting tunable joint distribution and temporal correlation of node degrees. Theoretical contributions include the analysis of conditions for graphic sequences of inter- and intracluster node degrees and cluster sizes and the development of a heuristic to search for the cluster membership of nodes that minimizes the shared information distance between clusterings. Our work shows that this system is capable of generating networks under user controlled topology with up to thousands of nodes and hundreds of clusters with strong topology adherence. Much larger networks are possible with relaxed requirements. The generated networks support algorithm validation as well as problem domain analysis.

Pereira, Luis Ramada↗

CoreCruncher : Fast and Robust Construction of Core Genomes in Large Prokaryotic Data Sets

The core genome represents the set of genes shared by all, or nearly all, strains of a given population or species of prokaryotes. Inferring the core genome is integral to many genomic analyses, however, most methods rely on the comparison of all the pairs of genomes; a step that is becoming increasingly difficult given the massive accumulation of genomic data. Here, we present CoreCruncher; a program that robustly and rapidly constructs core genomes across hundreds or thousands of genomes. CoreCruncher does not compute all pairwise genome comparisons and uses a heuristic based on the distributions of identity scores to classify sequences as orthologs or paralogs/xenologs. Although it is much faster than current methods, our results indicate that our approach is more conservative than other tools and less sensitive to the presence of paralogs and xenologs. CoreCruncher is freely available from: https://github.com/lbobay/CoreCruncher. CoreCruncher is written in Python 3.7 and can also run on Python 2.7 without modification. It requires the python library Numpy and either Usearch or Blast. Certain options require the programs muscle or mafft.

59 BASIC BIOLOGICAL SCIENCES↗

FastTree: Computing Large Minimum Evolution Trees with Profiles instead of a Distance Matrix

Gene families are growing rapidly, but standard methods for inferring phylogenies do not scale to alignments with over 10,000 sequences. We present FastTree, a method for constructing large phylogenies and for estimating their reliability. Instead of storing a distance matrix, FastTree stores sequence profiles of internal nodes in the tree. FastTree uses these profiles to implement Neighbor-Joining and uses heuristics to quickly identify candidate joins. FastTree then uses nearest neighbor interchanges to reduce the length of the tree. For an alignment with N sequences, L sites, and a different characters, a distance matrix requires O(N2) space and O(N2L) time, but FastTree requires just O(NLa+N √N) memory and O(N √N log(N)La) time. To estimate the tree’s reliability, FastTree uses local bootstrapping, which gives another 100-fold speedup over a distance matrix. For example, FastTree computed a tree and support values for 158,022 distinct 16S ribosomal RNAs in 17 h and 2.4 GB of memory. Just computing pairwise Jukes–Cantor distances and storing them, without inferring a tree or bootstrapping, would require 17 h and 50 GB of memory. In simulations, FastTree was slightly more accurate than Neighbor-Joining, BIONJ, or FastME; on genuine alignments, FastTree’s topologies had higher likelihoods. FastTree is available at http://microbesonline.org/fasttree.

59 BASIC BIOLOGICAL SCIENCES↗

Collapsing Cavities and Converging Shocks in Non-Ideal Materials

As modern hydrodynamic codes increase in sophistication, the availability of realistic test problems becomes increasingly important. In gas dynamics, one common unrealistic aspect of most test problems is the ideal gas assumption, which is unsuited to many real applications, especially those involving high pressure and speed metal deformation. In this work, we consider the collapsing cavity and converging shock test problems, showing to what extent the ideal gas assumption can be removed from their specification. It is found that while most materials simply do not admit simple (that is scaling) solutions in this context, there are infinite-dimensional families of materials which do admit such solutions. We characterize such materials, derive the appropriate ordinary differential equations and analyze the associated nonlinear eigenvalue problem. It is shown that there is an inherent tension between boundedness of the solution, boundedness of its derivatives and the entropy condition. The special case of a constant-speed cavity collapse is considered and found to be heuristically possible, contrary to common intuition. Finally, we give an example of a concrete non-ideal collapsing cavity scaling solution based on a recently proposed pseudo-Mie–Gruneisen equation of state.

36 MATERIALS SCIENCE↗

Inferring the shape of data: a probabilistic framework for analysing experiments in the natural sciences

A critical step in data analysis for many different types of experiments is the identification of features with theoretically defined shapes in N -dimensional datasets; examples of this process include finding peaks in multi-dimensional molecular spectra or emitters in fluorescence microscopy images. Identifying such features involves determining if the overall shape of the data is consistent with an expected shape; however, it is generally unclear how to quantitatively make this determination. In practice, many analysis methods employ subjective, heuristic approaches, which complicates the validation of any ensuing results—especially as the amount and dimensionality of the data increase. Here, we present a probabilistic solution to this problem by using Bayes’ rule to calculate the probability that the data have any one of several potential shapes. This probabilistic approach may be used to objectively compare how well different theories describe a dataset, identify changes between datasets and detect features within data using a corollary method called Bayesian Inference-based Template Search; several proof-of-principle examples are provided. Altogether, this mathematical framework serves as an automated ‘engine’ capable of computationally executing analysis decisions currently made by visual inspection across the sciences.

Science & Technology - Other Topics↗

End-to-end protocol for high-quality quantum approximate optimization algorithm parameters with few shots

The quantum approximate optimization algorithm (QAOA) is a quantum heuristic for combinatorial optimization that has been demonstrated to scale better than state-of-the-art classical solvers for some problems. For a given problem instance, QAOA performance depends crucially on the choice of the parameters. While average-case optimal parameters are available in many cases, meaningful performance gains can be obtained by fine-tuning these parameters for a given instance. This task is especially challenging, however, when the number of circuit executions (shots) is limited. In this work, we develop an end-to-end protocol that combines multiple parameter settings and fine-tuning techniques. We use large-scale numerical experiments to optimize the protocol for the shot-limited setting and observe that optimizers with the simplest internal model (linear) perform best. We implement the optimized pipeline on a trapped-ion processor using up to 32 qubits and 5 QAOA layers, and we demonstrate that the pipeline is robust to small amounts of hardware noise. To the best of our knowledge, these are the largest demonstrations of QAOA parameter fine-tuning on a trapped-ion processor in terms of two-qubit gate count.

quantum algorithms & computation↗

Mesoscale variations of the chemical and electronic landscape on the surface of the Weyl semimetal Co 3 ⁢Sn 2⁢ S 2 visualized by ARPES and XPS

The multiple crystalline terminations in magnetic Weyl semimetal Co 3 Sn 2 S 2 display distinct topological and trivial surface states, which have successfully been distinguished experimentally. However, a model of pure terminations is known to be inadequate because these surfaces exhibit a high degree of spatial heterogeneity and point disorder. Here, in this study, we perform a spectromicroscopy study of the surface chemistry and surface electronic structure using photoemission measurements in combination with first-principles calculations of core levels. We identify an intermediate region with properties distinct from both the sulfur and tin terminations, and demonstrate that the spectral features in this region can be associated with a disordered termination with a varying density of surface tin vacancies. This work establishes heuristics for identifying variable surface disorder using photoemission, an important prerequisite to experimentally establishing the behavior of momentum-space topological surface features subject to variable surface disorder on a single cleave.

Sreedhar, Sudheer Anand [Univ. of California, Davi↗

Studying QED 3 with radial quantization on the lattice: Free limit

To investigate the three-dimensional quantum electrodynamics in the radial quantization on the lattice, the lattice action is constructed and the free limit is studied on 𝑆 2 × ℝ. With the overlap fermion, it is numerically verified that the important symmetries of the theory can be realized on the lattice. The analytic correlators are derived and compared to the lattice results, which agree including the overall normalization. The 𝑂⁡(𝑎 2 ) scaling is confirmed toward the analytic value in the continuum limit, and the number of reproduced excited states is estimated heuristically for the first few refinement levels. Our study helps us identify the features of the theory that we can study on the icosahedral lattice without fine-tuning.

Boyle, Peter A. [Brookhaven National Laboratory (B↗

Dual View of the Z 2 -Gauged XY Model in 3D

The 𝑍 2 -gauged XY model is of long-standing interest both in the context of nematic order, and the study of fractionalization and superconductivity. This Letter presents heuristic arguments that no deconfinement of the XY field occurs in this model and presents results of a large-scale Monte Carlo simulations on a cubic lattice that are consistent with this conclusion. Furthermore, the correlation radius determining the confinement is found to be growing rapidly as a function of the parameters in the phase featuring the nematic order. Thus, mesoscopic properties of the system can mimic deconfinement with high accuracy in some part of the phase diagram.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗

Fixed-angle conjectures for the quantum approximate optimization algorithm on regular MaxCut graphs

The quantum approximate optimization algorithm (QAOA) is a near-term combinatorial optimization algorithm suitable for noisy quantum devices. However, little is known about performance guarantees for p > 2. A recent work computing MaxCut performance guarantees for 3-regular graphs conjectures that any d-regular graph evaluated at particular fixed angles has an approximation ratio greater than some worst-case guarantee. In this work, we provide numerical evidence for this fixed angle conjecture for p < 12. We compute and provide these angles via numerical optimization and tensor networks. These fixed angles serve for an optimization-free version of QAOA and have universally good performance on any 3-regular graph. Heuristic evidence is presented for the fixed angle conjecture on graph ensembles, which suggests that these fixed angles are "close" to global optimum. Under the fixed angle conjecture, QAOA has a larger performance guarantee than the Goemans Williamson algorithm on 3-regular graphs for p >= 11.

Wurtz, Jonathan↗

Semiclassical Wigner distribution for a two-mode entangled state generated by an optical parametric oscillator

We derive the steady-state solution of the Fokker-Planck equation that describes the dynamics of the nondegenerate optical parametric oscillator in the truncated Wigner representation of the density operator. We assume that the pump mode is strongly damped, which permits its adiabatic elimination. When the elimination is correctly executed, the resulting stochastic equations contain multiplicative noise terms and do not admit a potential solution. However, we develop a heuristic scheme leading to a satisfactory steady-state solution. This provides a clear view of the intracavity two-mode entangled state valid in all operating regimes of the optical parametric oscillator. A non-Gaussian distribution is obtained for the above threshold solution.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Optimal control landscape for the generation of unitary transformations with constrained dynamics

The reliable and precise generation of quantum unitary transformations is essential for the realization of a number of fundamental objectives, such as quantum control and quantum information processing. Prior work has explored the optimal control problem of generating such unitary transformations as a surface-optimization problem over the quantum control landscape, defined as a metric for realizing a desired unitary transformation as a function of the control variables. It was found that under the assumption of nondissipative and controllable dynamics, the landscape topology is trap free, which implies that any reasonable optimization heuristic should be able to identify globally optimal solutions. The present work is a control landscape analysis, which incorporates specific constraints in the Hamiltonian that correspond to certain dynamical symmetries in the underlying physical system. It is found that the presence of such symmetries does not destroy the trap-free topology. These findings expand the class of quantum dynamical systems on which control problems are intrinsically amenable to a solution by optimal control.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Efficient algorithm for approximating one-dimensional ground states

The density-matrix renormalization-group method is very effective at finding ground states of one-dimensional (1D) quantum systems in practice, but it is a heuristic method, and there is no known proof for when it works. In this article we describe an efficient classical algorithm which provably finds a good approximation of the ground state of 1D systems under well-defined conditions. More precisely, our algorithm finds a matrix product state of bond dimension D whose energy approximates the minimal energy such states can achieve. The running time is exponential in D, and so the algorithm can be considered tractable even for D, which is logarithmic in the size of the chain. The result also implies trivially that the ground state of any local commuting Hamiltonian in 1D can be approximated efficiently; we improve this to an exact algorithm.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Autotuning of Double-Dot Devices In Situ with Machine Learning

The current practice of manually tuning quantum dots (QDs) for qubit operation is a relatively time-consuming procedure that is inherently impractical for scaling up and applications. In this work, we report on the in situ implementation of a recently proposed autotuning protocol that combines machine learning (ML) with an optimization routine to navigate the parameter space. In particular, we show that a ML algorithm trained using exclusively simulated data to quantitatively classify the state of a double-QD device can be used to replace human heuristics in the tuning of gate voltages in real devices. Here, we demonstrate active feedback of a functional double-dot device operated at millikelvin temperatures and discuss success rates as a function of the initial conditions and the device performance. Modifications to the training network, fitness function, and optimizer are discussed as a path toward further improvement in the success rate when starting both near and far detuned from the target double-dot range.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Enhancing Graphene Plasmonic Device Performance via its Dielectric Environment

Graphene plasmons provide a compelling avenue toward chip-scale dynamic tuning of infrared light. Dynamic tunability emerges through controlled alterations in the optical properties of the system defining graphene’s plasmonic dispersion. Typically, electrostatic induced alterations of the carrier concentration in graphene working in conjunction with mobility have been considered the primary factors dictating plasmonic tunability. We find here that the surrounding dielectric environment also plays a primary role, dictating not just the energy of the graphene plasmon but so too the magnitude of its tuning and spectral width. To arrive at this conclusion, poles in the imaginary component of the reflection coefficient are used to efficiently survey the effect of the surrounding dielectric on the tuning of the graphene plasmon. By investigating several common polar materials, optical phonons (i.e., the Reststrahlen band) of the dielectric substrate are shown to appreciably affect not only the plasmon’s spectral location but its tunability, and its resonance shape as well. In particular, tunability is maximized when the resonances are spectrally distant from the Reststrahlen band, whereas sharp resonances (i.e., high-Q) are achievable at the band’s edge. Overall, these observations both underscore the necessity of viewing the dielectric environment in aggregate when considering the plasmonic response derived from two-dimensional materials and provide heuristics to design dynamically tunable graphene-based infrared devices.

36 MATERIALS SCIENCE↗

Short-range magnetic correlations in quasicrystalline i -Tb-Cd

Here, we report on elastic and inelastic neutron scattering from single-grain isotopically enriched samples to elucidate the local magnetic correlations between Tb 3+ moments in quasicrystalline i -Tb-Cd. The inelastic neutron scattering measurements of the crystalline electric field excitations demonstrated that the Tb 3+ moments are directed primarily along the local fivefold axes of the Tsai-type cluster as was found for the TbCd 6 approximant phase. Based on the inelastic measurements, we consider a simple Ising-type model for the moment configurations on a single Tb 3+ icosahedron and enumerate the lowest energy moment configurations. We then calculate the diffuse scattering from these configurations and compare with the experimental magnetic diffuse scattering measurements to identify the most likely single cluster moment configurations and find reasonable agreement between the broad features observed in our scattering simulations. We further use a heuristic glass model as well as large-scale Monte-Carlo simulations of a multicluster model to consider the role of higher-order (longer-range) intercluster correlations for magnetic frustration and the magnetic scattering.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗