Search NASA⌕ Search

SEARCH · Search NASA

Results for “Vectorized 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 847 records · Page 47

A Virtual Space Vector Model Predictive Control for a Seven-Level Hybrid Multilevel Converter

This paper proposes a virtual space vector (VSV) model predictive control (MPC) for a three-phase seven-level (7L) hybrid multilevel converter (HMC), where each phase consists of an active-neutral-point-clamped converter with a floating H-bridge. To achieve the best current tracking, which is the primary goal of the proposed algorithm, a novel geometrical positioning approach is proposed to select the optimal voltage vector among all the realspace vectors and VSVs. Then, all the possible switching sequences that belong to the optimal voltage vector are evaluated to realize the dc capacitor voltage balancing and common-mode voltage reduction. Through an external modulator, the optimal voltage vector can be synthesized by using either one-, three-, or seven-segment switching sequence. Compared with the conventional MPC, the proposed VSV-MPC can reduce not only the computational burden but also the current THD. Both simulation and experimental results obtained on silicon carbide based 7L-HMC prototype are presented to validate the feasibility and effectiveness of the proposed VSVMPC strategy.

42 ENGINEERING↗

Analytical modeling of elastic-plastic wave behavior near grain boundaries in crystalline materials

It is well known that changes in material properties across an interface will produce differences in the behavior of reflected and transmitted waves. This is seen frequently in planar impact experiments, and to a lesser extent, oblique impacts. In anisotropic elastic materials, wave behavior as a function of direction is usually accomplished with the aid of velocity surfaces, a graphical method for predicting wave scattering configurations. They have expanded this method to account for inelastic deformation due to crystal plasticity. The set of derived equations could not be put into a characteristic form, but instead led to an implicit problem. to overcome this difficulty an algorithm was developed to search the parameters space defined by a wave normal vector, particle velocity vector, and a wave speed. A solution was said to exist when a set from this parameter space satisfied the governing vector equation. Using this technique they can predict the anisotropic elastic-plastic velocity surfaces and grain boundary scattering configuration for crystalline materials undergoing deformation by slip. Specifically, they have calculated the configuration of scattered elastic-plastic waves in anisotropic NiAl for an incident compressional wave propagating along a <111> direction and contacting a 45 degree inclined grain boundary and found that large amplitude transmitted waves exist owing to the fact that the wave surface geometry forces it to propagate near the zero Schmid factor direction <100>.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Semi-Analytic Reconstruction of Flux in Finite Volume Formulations

Semi-analytic reconstruction uses the analytic solution to a second-order, steady, ordinary differential equation (ODE) to simultaneously evaluate the convective and diffusive flux at all interfaces of a finite volume formulation. The second-order ODE is itself a linearized approximation to the governing first- and second- order partial differential equation conservation laws. Thus, semi-analytic reconstruction defines a family of formulations for finite volume interface fluxes using analytic solutions to approximating equations. Limiters are not applied in a conventional sense; rather, diffusivity is adjusted in the vicinity of changes in sign of eigenvalues in order to achieve a sufficiently small cell Reynolds number in the analytic formulation across critical points. Several approaches for application of semi-analytic reconstruction for the solution of one-dimensional scalar equations are introduced. Results are compared with exact analytic solutions to Burger s Equation as well as a conventional, upwind discretization using Roe s method. One approach, the end-point wave speed (EPWS) approximation, is further developed for more complex applications. One-dimensional vector equations are tested on a quasi one-dimensional nozzle application. The EPWS algorithm has a more compact difference stencil than Roe s algorithm but reconstruction time is approximately a factor of four larger than for Roe. Though both are second-order accurate schemes, Roe s method approaches a grid converged solution with fewer grid points. Reconstruction of flux in the context of multi-dimensional, vector conservation laws including effects of thermochemical nonequilibrium in the Navier-Stokes equations is developed.

Gnoffo, Peter A.↗

On the Design, Development, and Analysis of Optimized Matrix-Vector Multiplication Routines for Coprocessors

The manycore paradigm shift, and the resulting change in modern computer architectures, has made the development of optimal numerical routines extremely challenging. In this work, we target the development of numerical algorithms and implementations for Xeon Phi coprocessor architecture designs. In particular, we examine and optimize the general and symmetric matrix-vector multiplication routines (gemv/symv), which are some of the most heavily used linear algebra kernels in many important engineering and physics applications. We describe a successful approach on how to address the challenges for this problem, starting with our algorithm design, performance analysis and programing model and moving to kernel optimization. Our goal, by targeting low-level and easy to understand fundamental kernels, is to develop new optimization strategies that can be effective elsewhere for use on manycore coprocessors, and to show significant performance improvements compared to existing state-of-the-art implementations. Therefore, in addition to the new optimization strategies, analysis, and optimal performance results, we finally present the significance of using these routines/strategies to accelerate higher-level numerical algorithms for the eigenvalue problem (EVP) and the singular value decomposition (SVD) that by themselves are foundational for many important applications.

Kabir, Khairul↗

A Newton algorithm for complex curve fitting

The problem of synthesizing transfer functions from frequency response measurements is considered. Given a complex vector representing the measured frequency response of a physical system, a transfer function of specified order is determined that minimizes the sum of the magnitude-squared of the frequency response errors. This nonlinear least squares minimization problem is solved by an iterative global descent algorithm of the Newton type which converges quadratically near the minimum. The unknown transfer function is expressed as a sum of second order rational polynomials, a parameterization that facilitates a numerically robust computer implementation. The algorithm is developed for single-input, single-output, causal, stable transfer functions.

Spanos, J. T.↗

Three-dimensional multigrid algorithms for the flux-split Euler equations

The Full Approximation Scheme (FAS) multigrid method is applied to several implicit flux-split algorithms for solving the three-dimensional Euler equations in a body fitted coordinate system. Each of the splitting algorithms uses a variation of approximate factorization and is implemented in a finite volume formulation. The algorithms are all vectorizable with little or no scalar computation required. The flux vectors are split into upwind components using both the splittings of Steger-Warming and Van Leer. The stability and smoothing rate of each of the schemes are examined using a Fourier analysis of the complete system of equations. Results are presented for three-dimensional subsonic, transonic, and supersonic flows which demonstrate substantially improved convergence rates with the multigrid algorithm. The influence of using both a V-cycle and a W-cycle on the convergence is examined.

Anderson, W. Kyle↗

Autonomous frequency domain identification: Theory and experiment

The analysis, design, and on-orbit tuning of robust controllers require more information about the plant than simply a nominal estimate of the plant transfer function. Information is also required concerning the uncertainty in the nominal estimate, or more generally, the identification of a model set within which the true plant is known to lie. The identification methodology that was developed and experimentally demonstrated makes use of a simple but useful characterization of the model uncertainty based on the output error. This is a characterization of the additive uncertainty in the plant model, which has found considerable use in many robust control analysis and synthesis techniques. The identification process is initiated by a stochastic input u which is applied to the plant p giving rise to the output. Spectral estimation (h = P sub uy/P sub uu) is used as an estimate of p and the model order is estimated using the produce moment matrix (PMM) method. A parametric model unit direction vector p is then determined by curve fitting the spectral estimate to a rational transfer function. The additive uncertainty delta sub m = p - unit direction vector p is then estimated by the cross spectral estimate delta = P sub ue/P sub uu where e = y - unit direction vectory y is the output error, and unit direction vector y = unit direction vector pu is the computed output of the parametric model subjected to the actual input u. The experimental results demonstrate the curve fitting algorithm produces the reduced-order plant model which minimizes the additive uncertainty. The nominal transfer function estimate unit direction vector p and the estimate delta of the additive uncertainty delta sub m are subsequently available to be used for optimization of robust controller performance and stability.

Yam, Yeung↗

On the impact of communication complexity on the design of parallel numerical algorithms

This paper describes two models of the cost of data movement in parallel numerical alorithms. One model is a generalization of an approach due to Hockney, and is suitable for shared memory multiprocessors where each processor has vector capabilities. The other model is applicable to highly parallel nonshared memory MIMD systems. In this second model, algorithm performance is characterized in terms of the communication network design. Techniques used in VLSI complexity theory are also brought in, and algorithm-independent upper bounds on system performance are derived for several problems that are important to scientific computation.

Gannon, D. B.↗

Integrating Natural Language Processing and Machine Learning Algorithms to Categorize Oncologic Response in Radiology Reports

A significant volume of medical data remains unstructured. Natural language processing (NLP) and machine learning (ML) techniques have shown to successfully extract insights from radiology reports. However, the codependent effects of NLP and ML in this context have not been well-studied. Between April 1, 2015 and November 1, 2016, 9418 cross-sectional abdomen/pelvis CT and MR examinations containing our internal structured reporting element for cancer were separated into four categories: Progression, Stable Disease, Improvement, or No Cancer. We combined each of three NLP techniques with five ML algorithms to predict the assigned label using the unstructured report text and compared the performance of each combination. The three NLP algorithms included term frequency-inverse document frequency (TF-IDF), term frequency weighting (TF), and 16-bit feature hashing. The ML algorithms included logistic regression (LR), random decision forest (RDF), one-vs-all support vector machine (SVM), one-vs-all Bayes point machine (BPM), and fully connected neural network (NN). The best-performing NLP model consisted of tokenized unigrams and bigrams with TF-IDF. Increasing N-gram length yielded little to no added benefit for most ML algorithms. With all parameters optimized, SVM had the best performance on the test dataset, with 90.6 average accuracy and F score of 0.813. The interplay between ML and NLP algorithms and their effect on interpretation accuracy is complex. The best accuracy is achieved when both algorithms are optimized concurrently.

62 RADIOLOGY AND NUCLEAR MEDICINE↗

Implementing Scientific Simulation Codes Highly Tailored for Vector Architectures Using Custom Configurable Computing Machines

The motivation for this work comes from an observation that amidst the push for Massively Parallel (MP) solutions to high-end computing problems such as numerical physical simulations, large amounts of legacy code exist that are highly optimized for vector supercomputers. Because re-hosting legacy code often requires a complete re-write of the original code, which can be a very long and expensive effort, this work examines the potential to exploit reconfigurable computing machines in place of a vector supercomputer to implement an essentially unmodified legacy source code. Custom and reconfigurable computing resources could be used to emulate an original application's target platform to the extent required to achieve high performance. To arrive at an architecture that delivers the desired performance subject to limited resources involves solving a multi-variable optimization problem with constraints. Prior research in the area of reconfigurable computing has demonstrated that designing an optimum hardware implementation of a given application under hardware resource constraints is an NP-complete problem. The premise of the approach is that the general issue of applying reconfigurable computing resources to the implementation of an application, maximizing the performance of the computation subject to physical resource constraints, can be made a tractable problem by assuming a computational paradigm, such as vector processing. This research contributes a formulation of the problem and a methodology to design a reconfigurable vector processing implementation of a given application that satisfies a performance metric. A generic, parametric, architectural framework for vector processing implemented in reconfigurable logic is developed as a target for a scheduling/mapping algorithm that maps an input computation to a given instance of the architecture. This algorithm is integrated with an optimization framework to arrive at a specification of the architecture parameters that attempts to minimize execution time, while staying within resource constraints. The flexibility of using a custom reconfigurable implementation is exploited in a unique manner to leverage the lessons learned in vector supercomputer development. The vector processing framework is tailored to the application, with variable parameters that are fixed in traditional vector processing. Benchmark data that demonstrates the functionality and utility of the approach is presented. The benchmark data includes an identified bottleneck in a real case study example vector code, the NASA Langley Terminal Area Simulation System (TASS) application.

Rutishauser, David↗

Encoding of linear kinetic plasma problems in quantum circuits via data compression

We propose an algorithm for encoding linear kinetic plasma problems in quantum circuits. The focus is on modelling electrostatic linear waves in a one-dimensional Maxwellian electron plasma. The waves are described by the linearized Vlasov–Ampère system with a spatially localized external current that drives plasma oscillations. This system is formulated as a boundary-value problem and cast in the form of a linear vector equation Aψ = b to be solved by using the quantum signal processing algorithm. The latter requires encoding of matrix A in a quantum circuit as a sub-block of a unitary matrix. We propose how to encode A in a circuit in a compressed form and discuss how the resulting circuit scales with the problem size and the desired precision.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

AveBoost2: Boosting for Noisy Data

AdaBoost is a well-known ensemble learning algorithm that constructs its constituent or base models in sequence. A key step in AdaBoost is constructing a distribution over the training examples to create each base model. This distribution, represented as a vector, is constructed to be orthogonal to the vector of mistakes made by the pre- vious base model in the sequence. The idea is to make the next base model's errors uncorrelated with those of the previous model. In previous work, we developed an algorithm, AveBoost, that constructed distributions orthogonal to the mistake vectors of all the previous models, and then averaged them to create the next base model s distribution. Our experiments demonstrated the superior accuracy of our approach. In this paper, we slightly revise our algorithm to allow us to obtain non-trivial theoretical results: bounds on the training error and generalization error (difference between training and test error). Our averaging process has a regularizing effect which, as expected, leads us to a worse training error bound for our algorithm than for AdaBoost but a superior generalization error bound. For this paper, we experimented with the data that we used in both as originally supplied and with added label noise-a small fraction of the data has its original label changed. Noisy data are notoriously difficult for AdaBoost to learn. Our algorithm's performance improvement over AdaBoost is even greater on the noisy data than the original data.

Oza, Nikunj C.↗

Time-explicit Darwin PIC algorithm

A new approach to Darwin particle-in-cell plasma simulation is described. Using a finite-element approach, the vector potential is assured to be exactly solenoidal. This allows writing the system of multi-species particles as an action-at-a-distance Hamiltonian system. Applying recently-developed explicit symplectic methods to this gives a time-explicit algorithm with all desired properties. Elliptic systems for the electrostatic and magneto-static portions of the problem are inverted efficiently by an algebraic multi-grid algorithm. The algorithm is implemented in a two-dimensional Cartesian-geometry code and tested by application to Weibel instability and to Alfvén wave dynamics. Results show the effectiveness of this approach. Extensions to arbitrary meshes and to a partially time-implicit scheme are briefly discussed.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

Iterative quantum optimization of spin glass problems with rapidly oscillating transverse fields

In this work, we introduce a new iterative quantum algorithm, called Iterative Symphonic Tunneling for Satisfiability problems (IST-SAT), which solves quantum spin glass optimization problems using high-frequency oscillating transverse fields. IST-SAT operates as a sequence of iterations, in which bitstrings returned from one iteration are used to set spin-dependent phases in oscillating transverse fields in the next iteration. Over several iterations, the novel mechanism of the algorithm steers the system toward the problem ground state. We benchmark IST-SAT on sets of hard MAX-3-XORSAT problem instances with exact state vector simulation, and report polynomial speedups over Trotterized adiabatic quantum computation and the best known semi-greedy classical algorithm. When IST-SAT is seeded with a sufficiently good initial approximation, the algorithm converges to exact solution(s) in a polynomial number of iterations. Our numerical results identify a critical Hamming radius, or quality of initial approximation, where the time-to-solution crosses from exponential to polynomial scaling in problem size. This work proposes IST-SAT a new quantum algorithm, which improves upon solutions obtained from initial classical or quantum optimization algorithms. The steering mechanism we introduce through IST-SAT presents a new path toward achieving quantum advantage in optimization.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Sweep-tracing algorithm: in silico slip crystallography and tension-compression asymmetry in BCC metals

Abstract Direct Molecular Dynamics (MD) simulations are being increasingly employed to model dislocation-mediated crystal plasticity with atomic resolution. Thanks to the dislocation extraction algorithm (DXA), dislocation lines can be now accurately detected and positioned in space and their Burgers vector unambiguously identified in silico, while the simulation is being performed. However, DXA extracts static snapshots of dislocation configurations that by themselves present no information on dislocation motion. Referred to as a sweep-tracing algorithm (STA), here we introduce a practical computational method to observe dislocation motion and to accurately quantify its important characteristics such as preferential slip planes (slip crystallography). STA reconnects pairs of successive snapshots extracted by DXA and computes elementary slip facets thus precisely tracing the motion of dislocation segments from one snapshot to the next. As a testbed for our new method, we apply STA to the analysis of dislocation motion in large-scale MD simulations of single crystal plasticity in BCC metals. We observe that, when the crystal is subjected to uniaxial deformation along its [001] axis, dislocation slip predominantly occurs on the {112} maximum resolved shear stress plane under tension, while in compression slip is non-crystallographic (pencil) resulting in asymmetric mechanical response. The marked contrast in the observed slip crystallography is attributed to the twinning/anti-twinning asymmetry of shears in the {112} planes relatively favoring dislocation motion in the twinning sense while hindering dislocations from moving in the anti-twinning directions.

36 MATERIALS SCIENCE↗

Reliable and Efficient Parallel Processing Algorithms and Architectures for Modern Signal Processing

Least-squares (LS) estimations and spectral decomposition algorithms constitute the heart of modern signal processing and communication problems. Implementations of recursive LS and spectral decomposition algorithms onto parallel processing architectures such as systolic arrays with efficient fault-tolerant schemes are the major concerns of this dissertation. There are four major results in this dissertation. First, we propose the systolic block Householder transformation with application to the recursive least-squares minimization. It is successfully implemented on a systolic array with a two-level pipelined implementation at the vector level as well as at the word level. Second, a real-time algorithm-based concurrent error detection scheme based on the residual method is proposed for the QRD RLS systolic array. The fault diagnosis, order degraded reconfiguration, and performance analysis are also considered. Third, the dynamic range, stability, error detection capability under finite-precision implementation, order degraded performance, and residual estimation under faulty situations for the QRD RLS systolic array are studied in details. Finally, we propose the use of multi-phase systolic algorithms for spectral decomposition based on the QR algorithm. Two systolic architectures, one based on triangular array and another based on rectangular array, are presented for the multiphase operations with fault-tolerant considerations. Eigenvectors and singular vectors can be easily obtained by using the multi-pase operations. Performance issues are also considered.

Liu, Kuojuey Ray↗

A comparison of machine learning methods to classify radioactive elements using prompt-gamma-ray neutron activation data

The detection of illicit radiological materials is critical to establishing a robust second line of defence in nuclear security. Neutron-capture prompt-gamma activation analysis (PGAA) can be used to detect multiple radioactive materials across the entire Periodic Table. However, long detection times and a high rate of false positives pose a significant hindrance in the deployment of PGAA-based systems to identify the presence of illicit substances in nuclear forensics. In the present work, six different machine-learning algorithms were developed to classify radioactive elements based on the PGAA energy spectra. The model performance was evaluated using standard classification metrics and trend curves with an emphasis on comparing the effectiveness of algorithms that are best suited for classifying imbalanced datasets. We analyse the classification performance based on Precision, Recall, F1-score, Specificity, Confusion matrix, ROC-AUC curves, and Geometric Mean Score (GMS) measures. The tree-based algorithms (Decision Trees, Random Forest and AdaBoost) have consistently outperformed Support Vector Machine and K-Nearest Neighbours. Based on the results presented, AdaBoost is the preferred classifier to analyse data containing PGAA spectral information due to the high recall and minimal false negatives reported in the minority class.

97 MATHEMATICS AND COMPUTING↗

Application of small-angle neutron scattering to the study of forces between magnetically chained monodisperse ferrofluid emulsion droplets

The optical magnetic chaining technique (MCT) developed by Leal-Calderon, Bibette and co-workers in the 1990 s allows precise measurements of force profiles between droplets in monodisperse ferrofluid emulsions. However, the method lacks an in-situ determination of droplet size and therefore requires the combination of separately acquired measurements of droplet chain periodicity versus an applied magnetic field from optical Bragg scattering and droplet diameter inferred from dynamic light scattering (DLS) to recover surface force-distance profiles between the colloidal particles. Compound refractive lens (CRL) focussed small-angle scattering (SANS) MCT should result in more consistent measurements of droplet size (form factor measurements in the absence of field) and droplet chaining period (from structure factor peaks when the magnetic field is applied); and, with access to shorter length scales, extend force measurements to closer approaches than possible by optical measurements. We report on CRL-SANS measurements of monodisperse ferrofluid emulsion droplets aligned in straight chains by an applied field perpendicular to the incident beam direction. Analysis of the scattering from the closely spaced droplets required algorithms that carefully treated resolution and its effect on mean scattering vector magnitudes in order to determine droplet size and chain periods to sufficient accuracy. At lower applied fields scattering patterns indicate structural correlations transverse to the magnetic field direction due to the formation of intermediate structures in early chain growth.

Colloid↗