Search NASA⌕ Search

SEARCH · Search NASA

Results for “Numerical algorithm”

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 1,675 records · Page 93

Parallel reduction to hessenberg form with algorithm-based fault tolerance

This paper studies the resilience of a two-sided factorization and presents a generic algorithm-based approach capable of making two-sided factorizations resilient. We establish the theoretical proof of the correctness and the numerical stability of the approach in the context of a Hessenberg Reduction (HR) and present the scalability and performance results of a practical implementation. Our method is a hybrid algorithm combining an Algorithm Based Fault Tolerance (ABFT) technique with diskless checkpointing to fully protect the data. We protect the trailing and the initial part of the matrix with checksums, and protect finished panels in the panel scope with diskless checkpoints. Compared with the original HR (the ScaLAPACK PDGEHRD routine) our fault-tolerant algorithm introduces very little overhead, and maintains the same level of scalability. We prove that the overhead shows a decreasing trend as the size of the matrix or the size of the process grid increases.

Computer Science↗

Noise Robustness and Experimental Demonstration of a Quantum Generative Adversarial Network for Continuous Distributions

Abstract The potential advantage of machine learning in quantum computers is a topic of intense discussion in the literature. Theoretical, numerical, and experimental explorations will most likely be required to understand its power. There have been different algorithms proposed to exploit the probabilistic nature of variational quantum circuits for generative modeling. In this paper, a hybrid architecture for quantum generative adversarial networks (QGANs) is employed and their robustness in the presence of noise is studied. A simple way of adding different types of noise to the quantum generator circuit is devised, and the noisy hybrid QGANs (HQGANs) are simulated numerically to learn continuous probability distributions, and to show that the performance of HQGANs remains unaffected. The effect of different parameters on the training time is also investigated to reduce the computational scaling of the algorithm and simplify its deployment on a quantum computer. The training on Rigetti's Aspen‐4‐2Q‐A quantum processing unit is then performed, and the results from the training are presented. The authors' results pave the way for experimental exploration of different quantum machine learning algorithms on noisy intermediate‐scale quantum devices.

Anand, Abhinav↗

Numerical Method for Fractional Advection-Diffusion Equation with Heredity

We propose a method of construction of difference schemes for fractional partial differential equations with delay in time. For the fractional equation with two-sided diffusion, fractional transfer in time, and a functional aftereffect, we construct an implicit difference scheme. We use the shifted Grünwald–Letnikov formulas for the approximation of fractional derivatives with respect to spatial variables and the L1-algorithm for the approximation of fractional derivatives in time. Also we use piecewise constant interpolation and extrapolation by extending the discrete prehistory of the model in time. The algorithm is a fractional analog of a purely implicit method; on each time step, it is reduced to the solution of linear algebraic systems. We prove the stability of the method and find its order of convergence.

97 MATHEMATICS AND COMPUTING↗

Fast, Dynamic, and Scalable Algorithms for Large-Scale Constrained Optimization

Scientists and engineers constantly aim to optimize an objective subject to physical, environmental, and/or resource constraints. The technique of using mathematical models to formulate and find real solutions of such problems is known as mathematical optimization, a process that has become invaluable for design and discovery in numerous scientific fields. This project has focused on the design, analysis, and implementation of high-performance computing algorithms for solving cutting-edge optimization problems. These include problems that involve (1) data uncertainties, such as those in the future supply, demand, and capacity of a given power system, (2) extreme numbers of alternatives, such as in the design of electrical power grids to avoid network vulnerabilities, and (3) real-time decisions, such as in the control of chemical reactors. The key features of the new algorithms are that they are fast, dynamic, and scalable to meet the computational requirements of scientists and researchers working to optimize large-scale, complex systems. The algorithms that have been designed, analyzed, and tested as part of the project can be characterized based on the types of optimization problems they have been designed to solve. Much of the work has focused on algorithms for solving large-scale constrained optimization problems. Contributions have also been made in the design of algorithms for unconstrained optimization, with some specialized methods for solving problems that have inherent nonsmoothness. Contributions have also been made in areas that have grown to prominence in the field over the five-year award period. These include the design of algorithms for solving large-scale stochastic optimization problems, such as those that arise in large-scale machine learning, and in complexity analyses for solving nonconvex problems, which has been a focal point of much recent work in continuous optimization. Overall, the project has supported work that has led to almost 30 articles that have been published or accepted to top journals in the field of mathematical optimization.

97 MATHEMATICS AND COMPUTING↗

Quantum Davidson algorithm for excited states

Abstract Excited state properties play a pivotal role in various chemical and physical phenomena, such as charge separation and light emission. However, the primary focus of most existing quantum algorithms has been the ground state, as seen in quantum phase estimation and the variational quantum eigensolver (VQE). Although VQE-type methods have been extended to explore excited states, these methods grapple with optimization challenges. In contrast, the quantum Krylov subspace (QKS) method has been introduced to address both ground and excited states, positioning itself as a cost-effective alternative to quantum phase estimation. However, conventional QKS methodologies depend on a pre-generated subspace through real or imaginary-time evolutions. This subspace is inherently expansive and can be plagued with issues like slow convergence or numerical instabilities, often leading to relatively deep circuits. Our research presents an economic QKS algorithm, which we term the quantum Davidson (QDavidson) algorithm. This innovation hinges on the iterative expansion of the Krylov subspace and the incorporation of a pre-conditioner within the Davidson framework. By using the residues of eigenstates to expand the Krylov subspace, we manage to formulate a compact subspace that aligns closely with the exact solutions. This iterative subspace expansion paves the way for a more rapid convergence in comparison to other QKS techniques, such as the quantum Lanczos. Using quantum simulators, we employ the novel QDavidson algorithm to delve into the excited state properties of various systems, spanning from the Heisenberg spin model to real molecules. Compared to the existing QKS methods, the QDavidson algorithm not only converges swiftly but also demands a significantly shallower circuit. This efficiency establishes the QDavidson method as a pragmatic tool for elucidating both ground and excited state properties on quantum computing platforms.

97 MATHEMATICS AND COMPUTING↗

Field Dynamics of Coherent Synchrotron Radiation Using a Direct Numerical Solution of Maxwell's Equations

We present and discuss the properties of the coherent electromagnetic fields of a very short, ultrarelativistic bunch in a rectangular vacuum chamber inside a bending magnet. The analysis is based on the results of a direct numerical solution of Maxwell's equations together with Newton's equations. We use a new dispersion-free time-domain algorithm which employs a more efficient use of finite element mesh techniques and, hence, produces self-consistent and stable solutions for very short bunches. We investigate the fine structure of the coherent synchrotron radiation fields. We also discuss coherent edge radiation. We present a clear picture of the field using the electric field lines constructed from the numerical solutions. This method should be useful in the study of existing and future concepts of particle accelerators and ultrafast coherent light sources, where high peak currents and very short bunches are envisioned.

43 PARTICLE ACCELERATORS↗

Distributed Link Removal Using Local Estimation of Network Topology

In this paper, we consider the problem of network structure manipulation in the absence of information on the global network topology. In particular, the problem of removing some of links is investigated in order to slow or stop the spread of disease in a network while preserving its connectivity. Existing methods solve this combinatorial problem in a centralized manner and they require the global information of network structure. In this paper, we propose a distributed design algorithm to compute a suboptimal solution to this problem efficiently by mimicking gradient based method, namely by iteratively removing one or multiple links at a time from the network. Specifically, using matrix perturbation analysis we formulate an optimization problem involving the eigenvector associated with the largest eigenvalue of the adjacency matrix and whose solution is equal to a suboptimal solution to the original problem. This strategy also enables us to overcome the combinatorial issue of the problem. Distributed algorithms to estimate the eigenvector and to verify network’s connectivity are then proposed which facilitate us to solve the new optimization problem. In addition, topological insights into the proposed algorithm and optimality of its solution are also discussed. Lastly, the proposed distributed design method is demonstrated and evaluated via several numerical examples.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Radiation dose reduction in medical x-ray CT via Fourier-based iterative reconstruction

Purpose: A Fourier-based iterative reconstruction technique, termed Equally Sloped Tomography (EST), is developed in conjunction with advanced mathematical regularization to investigate radiation dose reduction in x-ray CT. The method is experimentally implemented on fan-beam CT and evaluated as a function of imaging dose on a series of image quality phantoms and anonymous pediatric patient data sets. Numerical simulation experiments are also performed to explore the extension of EST to helical cone-beam geometry. Methods: EST is a Fourier based iterative algorithm, which iterates back and forth between real and Fourier space utilizing the algebraically exact pseudopolar fast Fourier transform (PPFFT). In each iteration, physical constraints and mathematical regularization are applied in real space, while the measured data are enforced in Fourier space. The algorithm is automatically terminated when a proposed termination criterion is met. Experimentally, fan-beam projections were acquired by the Siemens z-flying focal spot technology, and subsequently interleaved and rebinned to a pseudopolar grid. Image quality phantoms were scanned at systematically varied mAs settings, reconstructed by EST and conventional reconstruction methods such as filtered back projection (FBP), and quantified using metrics including resolution, signal-to-noise ratios (SNRs), and contrast-to-noise ratios (CNRs). Pediatric data sets were reconstructed at their original acquisition settings and additionally simulated to lower dose settings for comparison and evaluation of the potential for radiation dose reduction. Numerical experiments were conducted to quantify EST and other iterative methods in terms of image quality and computation time. The extension of EST to helical cone-beam CT was implemented by using the advanced single-slice rebinning (ASSR) method. Results: Based on the phantom and pediatric patient fan-beam CT data, it is demonstrated that EST reconstructions with the lowest scanner flux setting of 39 mAs produce comparable image quality, resolution, and contrast relative to FBP with the 140 mAs flux setting. Compared to the algebraic reconstruction technique and the expectation maximization statistical reconstruction algorithm, a significant reduction in computation time is achieved with EST. Finally, numerical experiments on helical cone-beam CT data suggest that the combination of EST and ASSR produces reconstructions with higher image quality and lower noise than the Feldkamp Davis and Kress (FDK) method and the conventional ASSR approach. Conclusions: A Fourier-based iterative method has been applied to the reconstruction of fan-bean CT data with reduced x-ray fluence. This method incorporates advantageous features in both real and Fourier space iterative schemes: using a fast and algebraically exact method to calculate forward projection, enforcing the measured data in Fourier space, and applying physical constraints and flexible regularization in real space. Our results suggest that EST can be utilized for radiation dose reduction in x-ray CT via the readily implementable technique of lowering mAs settings. Numerical experiments further indicate that EST requires less computation time than several other iterative algorithms and can, in principle, be extended to helical cone-beam geometry in combination with the ASSR method.

60 APPLIED LIFE SCIENCES↗

An algorithm for continuum modeling of rocks with multiple embedded nonlinearly-compliant joints [Continuum modeling of elasto-plastic media with multiple embedded nonlinearly-compliant joints]

Here, we present a numerical method for modeling the mechanical effects of nonlinearly-compliant joints in elasto-plastic media. The method uses a series of strain-rate and stress update algorithms to determine joint closure, slip, and solid stress within computational cells containing multiple “embedded” joints. This work facilitates efficient modeling of nonlinear wave propagation in large spatial domains containing a large number of joints that affect bulk mechanical properties. We implement the method within the massively parallel Lagrangian code GEODYN-L and provide verification and examples. We highlight the ability of our algorithms to capture joint interactions and multiple weakness planes within individual computational cells, as well as its computational efficiency. We also discuss the motivation for developing the proposed technique: to simulate large-scale wave propagation during the Source Physics Experiments (SPE), a series of underground explosions conducted at the Nevada National Security Site (NNSS).

42 ENGINEERING↗

A Three-level BDDC algorithm for saddle point problems

BDDC algorithms have previously been extended to the saddle point problems arising from mixed formulations of elliptic and incompressible Stokes problems. In these two-level BDDC algorithms, all iterates are required to be in a benign space, a subspace in which the preconditioned operators are positive definite. This requirement can lead to large coarse problems, which have to be generated and factored by a direct solver at the beginning of the computation and they can ultimately become a bottleneck. An additional level is introduced in this paper to solve the coarse problem approximately and to remove this difficulty. This three-level BDDC algorithm keeps all iterates in the benign space and the conjugate gradient methods can therefore be used to accelerate the convergence. This work is an extension of the three-level BDDC methods for standard finite element discretization of elliptic problems and the same rate of convergence is obtained for the mixed formulation of the same problems. Estimate of the condition number for this three-level BDDC methods is provided and numerical experiments are discussed.

97 MATHEMATICS AND COMPUTING↗

Quantum computing without quantum computers: Database search and data processing using classical wave superposition

Quantum computers are proven to be more efficient at solving a specific class of problems compared to traditional digital computers. Superposition of states and quantum entanglement are the two key ingredients that make quantum computing so powerful. However, not all quantum algorithms require quantum entanglement (e.g., search through an unsorted database). Is it possible to utilize classical wave superposition to speed up database searching as much as by using quantum computers? There were several attempts to mimic quantum computers using classical waves. It was concluded that the use of classical wave superposition comes with the cost of an exponential increase in resources. In this work, we consider the feasibility of building classical wave-based devices able to provide fundamental speedup over digital counterparts without the exponential overhead. We present experimental data on database searching through a magnetic database using spin wave superposition. The results demonstrate the same speedup as expected for quantum computers. Also, we present examples of numerical modeling demonstrating classical wave interference for period finding. This approach may not compete with quantum computers with efficiency but outperform classical digital computers. We argue that classical wave-based devices can perform some of the quantum algorithms with the same efficiency as quantum computers as long as quantum entanglement is not required.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

A Multifidelity Ensemble Kalman Filter with Reduced Order Control Variates

This work develops a new multi delity ensemble Kalman lter (MFEnKF) algorithm based on linear control variate framework. The approach allows for rigorous multi delity extensions of the EnKF, where the uncertainty in coarser delities in the hierarchy of models represent control variates for the uncertainty in ner delities. Small ensembles of high delity model runs are com- plemented by larger ensembles of cheaper, lower delity runs, to obtain much improved analyses at only small additional computational costs. We investigate the use of reduced order models as coarse delity control variates in the MFEnKF, and provide analyses to quantify the improvements over the traditional ensemble Kalman lters. We apply these ideas to perform data assimilation with a quasi-geostrophic test problem, using direct numerical simulation and a corresponding POD-Galerkin reduced order model. Numerical results show that the two- delity MFEnKF provides better analyses than existing EnKF algorithms at comparable or reduced computational costs.

97 MATHEMATICS AND COMPUTING↗

MATBOX, an Open-Source Microstructure Analysis Toolbox for Meshing, Generation, Segmentation, and Characterization of 3D Heterogenous Volumes

Battery performance is strongly correlated with electrode microstructural properties. To account for its impact, lithium-ion battery (LIB) models either abstract the microstructural heterogeneity of composite electrodes using effective macroscopic properties (macro- or meso- scale models) or directly solve the system of equations on the microstructure geometry or mesh (microstructure-scale models). Therefore, to be adequate, both families of models require information from the microstructure geometry, which can be provided by the numerical tool presented in this work. MATBOX is a MATLAB open-source application [1] developed by NREL for performing various microstructure-related tasks including microstructure numerical generation, image filtering and microstructure segmentation, microstructure characterization and correlation, visualization, and microstructure meshing. MATBOX was originally developed for the analysis of LIB electrode microstructures; however, the algorithms provided by the toolbox are widely applicable to other heterogeneous materials. The toolbox provides a user-friendly experience thanks to a Graphical-User Interface, requires no coding by the user, and is well documented. This presentation will illustrate various MATBOX features for the characterization of a LIB electrode, including a fully automated Representative Volume Element (RVE) analysis, the numerical generation of complex 'virtual' microstructure, including dual-layer electrodes and carbon-binder additive phase, and the meshing of a complex NMC/graphite full cell microstructure suitable for 3D finite-element modeling. Other modules (segmentation, visualization, and correlation) will be briefly presented. Thanks to its modular, open-source approach, MATBOX can easily incorporate third-party algorithms to eventually build a standard in the field that will benefit the whole scientific community. Effective diffusion coefficient [2], additive phase numerical generation [3], and meshing [4] third-party algorithms have been already integrated in the toolbox with more to come.

DIRECT ENERGY CONVERSION,MATHEMATICS AND COMPUTING↗

Cyber Physical Grid-Interactive Distributed Energy Resources Control for VPP Dispatch and Regulation: Preprint

This paper presents a cyber-physical algorithm for grid interactive DER control to enable two features of Virtual Power Plants (VPPs) dispatch and grid voltage regulation, considering the communication and security impacts. We first formulate the DER dispatch problem as a real-time, iterative, and grid-interactive DER control problem. Thereafter, we consider a probabilistic traffic model to characterize packet delays and loss in a communication network, and study how the delays enter the process of information exchange among the grid measurement units, local DER controllers and the grid control center that coordinately execute this dispatch algorithm. Finally, we propose a cyber-physical grid-interactive DER control algorithm using the previous message strategy. The tracking and regulation capabilities of this proposed algorithm can be made immune to the asynchrony resulting from the communications network traffic. We carry out simulations to show possible numerical instabilities and sensitivities of the tracking and regulation capabilities on the proposed strategy. Our results exhibit that the uncertainties of the underlying communications infrastructure must be considered in the control algorithm for the VPP tracking and regulation capabilities of any DER in a generic Cyber-Physical System (CPS).

co-simulation↗

Computational physics and applied mathematics capability review June 8-10, 2010 (Advance materials to committee members)

Los Alamos National Laboratory will review its Computational Physics and Applied Mathematics (CPAM) capabilities in 2010. The goals of capability reviews are to assess the quality of science, technology, and engineering (STE) performed by the capability, evaluate the integration of this capability across the Laboratory and within the scientific community, examine the relevance of this capability to the Laboratory's programs, and provide advice on the current and future directions of this capability. This is the first such review for CPAM, which has a long and unique history at the laboratory, starting from the inception of the Laboratory in 1943. The CPAM capability covers an extremely broad technical area at Los Alamos, encompassing a wide array of disciplines, research topics, and organizations. A vast array of technical disciplines and activities are included in this capability, from general numerical modeling, to coupled mUlti-physics simulations, to detailed domain science activities in mathematics, methods, and algorithms. The CPAM capability involves over 12 different technical divisions and a majority of our programmatic and scientific activities. To make this large scope tractable, the CPAM capability is broken into the following six technical 'themes.' These themes represent technical slices through the CP AM capability and collect critical core competencies of the Laboratory, each of which contributes to the capability (and each of which is divided into multiple additional elements in the detailed descriptions of the themes in subsequent sections): (1) Computational Fluid Dynamics - This theme speaks to the vast array of scientific capabilities for the simulation of fluids under shocks, low-speed flow, and turbulent conditions - which are key, historical, and fundamental strengths of the laboratory; (2) Partial Differential Equations - The technical scope of this theme is the applied mathematics and numerical solution of partial differential equations (broadly defined) in a variety of settings, including particle transport, solvers, and plasma physics; (3) Monte Carlo - Monte Carlo was invented at Los Alamos, and this theme discusses these vitally important methods and their application in everything from particle transport, to condensed matter theory, to biology; (4) Molecular Dynamics - This theme describes the widespread use of molecular dynamics for a variety of important applications, including nuclear energy, materials science, and biological modeling; (5) Discrete Event Simulation - The technical scope of this theme represents a class of complex system evolutions governed by the action of discrete events. Examples include network, communication, vehicle traffic, and epidemiology modeling; and (6) Integrated Codes - This theme discusses integrated applications (comprised of all of the supporting science represented in Themes 1-5) that are of strategic importance to the Laboratory and the nation. The laboratory has in approximately 10 million source lines of code in over 100 different such strategically important applications. Of these themes, four of them will be reviewed during the 2010 review cycle: Themes 1, 2, 3, and 6. Because these capability reviews occur every three years, Themes 4 and 5 will be reviewed in 2013, along with Theme 6 (which will be reviewed during each review, owing to this theme's role as an integrator of the supporting science represented by the other 5 themes). Yearly written status reports will be provided to the Capability Review Committee Chair during off-cycle years.

99 GENERAL AND MISCELLANEOUS↗

Algorithmically scalable block preconditioner for fully implicit shallow-water equations in CAM-SE

Performing accurate and efficient numerical simulation of global atmospheric climate models is challenging due to the disparate length and time scales over which physical processes interact. Implicit solvers enable the physical system to be integrated with a time step commensurate with processes being studied. The dominant cost of an implicit time step is the ancillary linear system solves, so we have developed a preconditioner aimed at improving the efficiency of these linear system solves. Our preconditioner is based on an approximate block factorization of the linearized shallow-water equations and has been implemented within the spectral element dynamical core within the Community Atmospheric Model (CAM-SE). Furthermore, in this paper we discuss the development and scalability of the preconditioner for a suite of test cases with the implicit shallow-water solver within CAM-SE.

97 MATHEMATICS AND COMPUTING↗

Effects of refractive index mismatch in optical CT imaging of polymer gel dosimeters

Purpose: Proposing an image reconstruction technique, algebraic reconstruction technique-refraction correction (ART-rc). The proposed method takes care of refractive index mismatches present in gel dosimeter scanner at the boundary, and also corrects for the interior ray refraction. Polymer gel dosimeters with high dose regions have higher refractive index and optical density compared to the background medium, these changes in refractive index at high dose results in interior ray bending. Methods: The inclusion of the effects of refraction is an important step in reconstruction of optical density in gel dosimeters. The proposed ray tracing algorithm models the interior multiple refraction at the inhomogeneities. Jacob’s ray tracing algorithm has been modified to calculate the pathlengths of the ray that traverses through the higher dose regions. The algorithm computes the length of the ray in each pixel along its path and is used as the weight matrix. Algebraic reconstruction technique and pixel based reconstruction algorithms are used for solving the reconstruction problem. The proposed method is tested with numerical phantoms for various noise levels. The experimental dosimetric results are also presented. Results: The results show that the proposed scheme ART-rc is able to reconstruct optical density inside the dosimeter better than the results obtained using filtered backprojection and conventional algebraic reconstruction approaches. The quantitative improvement using ART-rc is evaluated using gamma-index. The refraction errors due to regions of different refractive indices are discussed. The effects of modeling of interior refraction in the dose region are presented. Conclusions: The errors propagated due to multiple refraction effects have been modeled and the improvements in reconstruction using proposed model is presented. The refractive index of the dosimeter has a mismatch with the surrounding medium (for dry air or water scanning). The algorithm reconstructs the dose profiles by estimating refractive indices of multiple inhomogeneities having different refractive indices and optical densities embedded in the dosimeter. This is achieved by tracking the path of the ray that traverses through the dosimeter. Extensive simulation studies have been carried out and results are found to be matching that of experimental results.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

Implicit, manifold-preserving numerical representations and solvers for multiscale kinetic simulations of plasmas

Presentation Conclusions: We have derived manifold-preserving algorithms for kinetic plasma simulation; Collisionless (PIC): we have solved the 40-year-old algorithmic challenge of developing accurate implicit PIC algorithms; Collisional (VFP): we have demonstrated a truly multiscale algorithm that has enabled routine simulation of ICF spherical capsule implosions with a few hundred cores for a couple of days.; In both cases: Strict conservation properties have been shown to be critical for long-term accuracy.; Significant algorithmic acceleration has been achieved by using nested asymptotic models.; We have seen similar benefits in other applications

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗