Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “randomized linear algebra”

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.

67 records · Page 4
All sourcesNASA NTRSDOE OSTI
DOE OSTI2015

Correlation functions from a unified variational principle: Trial Lie groups

Time-dependent expectation values and correlation functions for many-body quantum systems are evaluated by means of a unified variational principle. It optimizes a generating functional depending on sources associated with the observables of interest. It is built by imposing through Lagrange multipliers constraints that account for the initial state (at equilibrium or off equilibrium) and for the backward Heisenberg evolution of the observables. The trial objects are respectively akin to a density operator and to an operator involving the observables of interest and the sources. We work out here the case where trial spaces constitute Lie groups. This choice reduces the original degrees of freedom to those of the underlying Lie algebra, consisting of simple observables; the resulting objects are labeled by the indices of a basis of this algebra. Explicit results are obtained by expanding in powers of the sources. Zeroth and first orders provide thermodynamic quantities and expectation values in the form of mean-field approximations, with dynamical equations having a classical Lie–Poisson structure. At second order, the variational expression for two-time correlation functions separates–as does its exact counterpart–the approximate dynamics of the observables from the approximate correlations in the initial state. Two building blocks are involved: (i) a commutation matrix which stems from the structure constants of the Lie algebra; and (ii) the second-derivative matrix of a free-energy function. The diagonalization of both matrices, required for practical calculations, is worked out, in a way analogous to the standard RPA. The ensuing structure of the variational formulae is the same as for a system of non-interacting bosons (or of harmonic oscillators) plus, at non-zero temperature, classical Gaussian variables. This property is explained by mapping the original Lie algebra onto a simpler Lie algebra. The results, valid for any trial Lie group, fulfill consistency properties and encompass several special cases: linear responses, static and time-dependent fluctuations, zero- and high-temperature limits, static and dynamic stability of small deviations.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2012

Dirac matrices for Chern-Simons gravity

A genuine gauge theory for the Poincare, de Sitter or anti-de Sitter algebras can be constructed in (2n- 1)-dimensional spacetime by means of the Chern-Simons form, yielding a gravitational theory that differs from General Relativity but shares many of its properties, such as second order field equations for the metric. The particular form of the Lagrangian is determined by a rank n, symmetric tensor invariant under the relevant algebra. In practice, the calculation of this invariant tensor can be reduced to the computation of the trace of the symmetrized product of n Dirac Gamma matrices {Gamma}{sub ab} in 2n-dimensional spacetime. While straightforward in principle, this calculation can become extremely cumbersome in practice. For large enough n, existing computer algebra packages take an inordinate long time to produce the answer or plainly fail having used up all available memory. In this talk we show that the general formula for the trace of the symmetrized product of 2n Gamma matrices {Gamma}{sub ab} can be written as a certain sum over the integer partitions s of n, with every term being multiplied by a numerical cofficient {alpha}{sub s}. We then give a general algorithm that computes the {alpha}-coefficients as the solution of a linear system of equations generated by evaluating the general formula for different sets of tensors B{sup ab} with random numerical entries. A recurrence relation between different coefficients is shown to hold and is used in a second, 'minimal' algorithm to greatly speed up the computations. Runtime of the minimal algorithm stays below 1 min on a typical desktop computer for up to n = 25, which easily covers all foreseeable applications of the trace formula.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
DOE OSTI2024

QuTree: A tree tensor network package

Here we present QuTree, a C++ library for tree tensor network approaches. QuTree provides class structures for tensors, tensor trees, and related linear algebra functions that facilitate the fast development of tree tensor network approaches such as the multilayer multiconfigurational time-dependent Hartree approach or the density matrix renormalization group approach and its various extensions. We investigate the efficiency of relevant tensor and tensor network operations and show that the overhead for managing the network structure is negligible, even in cases with a million leaves and small tensors. QuTree focuses on providing simple, high-level routines while retaining easy access to the backend to facilitate novel developments. We demonstrate the capabilities of the package by computing the eigenstates of coupled harmonic oscillator Hamiltonians and performing random circuit simulations on a virtual quantum computer.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2024

Evolution of the SLATE linear algebra library

SLATE (Software for Linear Algebra Targeting Exascale) is a distributed, dense linear algebra library targeting both CPU-only and GPU-accelerated systems, developed over the course of the Exascale Computing Project (ECP). While it began with several documents setting out its initial design, significant design changes occurred throughout its development. In some cases, these were anticipated: an early version used a simple consistency flag that was later replaced with a full-featured consistency protocol. In other cases, performance limitations and software and hardware changes prompted a redesign. Sequential communication tasks were parallelized; host-to-host MPI calls were replaced with GPU device-to-device MPI calls; more advanced algorithms such as Communication Avoiding LU and the Random Butterfly Transform (RBT) were introduced. Early choices that turned out to be cumbersome, error prone, or inflexible have been replaced with simpler, more intuitive, or more flexible designs. Applications have been a driving force, prompting a lighter weight queue class, nonuniform tile sizes, and more flexible MPI process grids. Of paramount importance has been building a portable library that works across several different GPU architectures – AMD, Intel, and NVIDIA – while keeping a clean and maintainable codebase. Here we explore the evolving design choices and their effects, both in terms of performance and software sustainability.

Gates, Mark↗
DOE OSTI2021

Single-Molecule Kinetics of Styrene Hydrogenation on Silica-Supported Vanadium: The Role of Disorder for Single-Atom Catalysts

We report a theoretical approach for the study of supported atom catalysis is developed based on recent advances in the study of single-molecule kinetics. This view is particularly useful in exhibiting the role of disorder in single-atom and single-site catalysts on amorphous supports. The distribution of passage times (or waiting times) through a complex catalytic network originating from a set of coupled active sites is described by a probability distribution function (PDF), f(t), that reflects the local environment of the reaction center. An efficient algorithm is developed based on the linear algebra of the Markov transition matrix that produces f(t) or its moments. The kinetics of the hydrogenation reaction of styrene on an organovanadium(III) catalyst supported on amorphous silica is studied. A kinetic model consisting of three intertwined catalytic cycles emanating from three chemically distinct active sites is proposed to describe the chemistry. Density functional theory (DFT) calculations are employed to determine the free energy barriers of the reactions, which are used to construct the rate coefficient matrix. The disorder induced by the amorphous support material is divided into a low-dimensional short-range component reflecting the covalent structures near the reaction center and a weaker long-range component modeling the bulk randomness. The results are computed and analyzed for a wide range of concentration values and disorder scenarios. The unusual structure in the f(t) PDF is found to occur for certain cases that reveal the contribution of multiple catalytic pathways acting in concert.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2022

Dynamic mode decomposition with core sketch

With the increase in collected data volumes, either from experimental measurements or high fidelity simulations, there is an ever-growing need to develop computationally efficient tools to process, analyze, and interpret these datasets. Modal analysis techniques have gained great interest due to their ability to identify patterns in the data and extract valuable information about the system being considered. Dynamic mode decomposition (DMD) relies on elements of the Koopman approximation theory to compute a set of modes, each associated with a fixed oscillation frequency and a decay/growth rate. Extracting these details from large datasets can be computationally expensive due to the need to implement singular value decomposition of the input data matrix. Sketching algorithms have become popular in numerical linear algebra where statistical theoretic approaches are utilized to reduce the cost of major operations. A sketch of a matrix is another matrix, which is significantly smaller, but still sufficiently approximates the original system. We put forth an efficient DMD framework, SketchyDMD, based on a core sketching algorithm that captures information about the range and corange (their mutual relationship) of input data. The proposed sketching-based framework can accelerate various portions of the DMD routines, compared to classical methods that operate directly on the raw input data. We conduct numerical experiments using the spherical shallow water equations as a prototypical model in the context of geophysical flows. In conclusion, we show that the proposed SketchyDMD is superior to existing randomized DMD methods that are based on capturing only the range of the input data.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
NASA NTRS1983

On obtaining the forward phase functions of Saturn ring features from radio occultation observations

It is noted that the near-forward scattering functions of particles in Saturn ring features are related to 3.6 cm radio occultation power spectra by a Fredholm integral equation of the first kind. The equation reduces to an algebraic system of equation whose solution by usual inversion techniques (that is, least mean squares) is ruled out by the near singularity of the forward transformation matrix. A combination of constrained linear inversion and a filtering algorithm based on eigenvector decomposition of the matrix reduces the instabilities; this yields derived phase functions valid over the range of zero to about 12 mrad. It is noted that these functions represent the collective forward diffraction lobe of particles greater than about 1 m in radius. Since multiple scattering of the signal is a significant effect, the measured phase functions must be adjusted to obtain the singly scattered component. This single-scattering correction is examined for two physical models, namely the monolayer and the classical discrete random slab; in addition, the fraction of opacity in submeter particles for each model for particular ring features is estimated.

Zebker, H. A.↗
DOE OSTI2017

Is the Multigrid Method Fault Tolerant? The Two-Grid Case

The predicted reduced resiliency of next-generation high performance computers means that it will become necessary to take into account the effects of randomly occurring faults on numerical methods. Further, in the event of a hard fault occurring, a decision has to be made as to what remedial action should be taken in order to resume the execution of the algorithm. The action that is chosen can have a dramatic effect on the performance and characteristics of the scheme. Ideally, the resulting algorithm should be subjected to the same kind of mathematical analysis that was applied to the original, deterministic variant. The purpose of this work is to provide the first rigorous analysis of the behavior of the multigrid algorithm in the presence of faults. Specifically, we prove estimates on the behavior of the Two Grid Method similar to the classical asymptotic results. Multigrid is arguably the method of choice for the solution of large-scale linear algebra problems arising from discretization of partial differential equations, and it is of considerable importance to anticipate its behavior on an exascale machine. The analysis of resilience of algorithms is in its infancy, and the current work is perhaps the first to provide a mathematical model for faults and analyze the behavior of a state-of-the-art algorithm under the model. It is shown that the Two Grid Method fails to be resilient to faults. Attention is then turned to identifying the minimal necessary remedial action required to restore the rate of convergence to that enjoyed by the ideal fault-free method.

Mathematics↗
NASA NTRS1996

Bit Error Probability for Maximum Likelihood Decoding of Linear Block Codes

In this paper, the bit error probability P(sub b) for maximum likelihood decoding of binary linear codes is investigated. The contribution of each information bit to P(sub b) is considered. For randomly generated codes, it is shown that the conventional approximation at high SNR P(sub b) is approximately equal to (d(sub H)/N)P(sub s), where P(sub s) represents the block error probability, holds for systematic encoding only. Also systematic encoding provides the minimum P(sub b) when the inverse mapping corresponding to the generator matrix of the code is used to retrieve the information sequence. The bit error performances corresponding to other generator matrix forms are also evaluated. Although derived for codes with a generator matrix randomly generated, these results are shown to provide good approximations for codes used in practice. Finally, for decoding methods which require a generator matrix with a particular structure such as trellis decoding or algebraic-based soft decision decoding, equivalent schemes that reduce the bit error probability are discussed.

Lin, Shu↗
DOE OSTI2025

Developing ML/AI Methods for High-Throughput Characterization of Multiple-Sensor Streams of Tokamak Dynamics for High-Speed Control (Final Report)

This project evaluated and developed new mathematical and algorithmic techniques capable of handling (in real-time) the growing amounts of data generated by modern fusion research. While existing numerical linear algebra (NLA) methods provide the backbone to classical data analysis and algorithms, these methods fundamentally do not port to distributed architectures nor do they allow low-latency data reduction for control. Motivated by the needs for modern fusion reactors, this project explored and implemented new numerical methods to characterize plasma dynamics, respond in real-time to discharge evolution, and to process massive-scale data accurately and rapidly more fully. This project links expertise in multiple-sensor diagnostics of tokamak plasma dynamics from Columbia University’s Plasma Physics Laboratory with expertise in massive-scale data reduction and extreme data control algorithms at Columbia University’s Data Science Institute. This interdisciplinary project (i) applied machine learning methods, (ii) implemented a properly-trained neural-network for very fast processing of high-speed plasma videography, and (ii) developed the applied mathematical methods, based on randomized-NLA (rNLA) routines, for data analysis, reduction, and real-time control. The Columbia University High Beta Tokamak-Extended Pulse (HBT-EP) facility provided data to test new algorithms and partnership with Columbia University's Data Sciences Institute evaluated the broader use of new algorithms for many challenging control applications.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗
DOE OSTI2023

A review on recent machine learning applications for imaging mass spectrometry studies

Imaging mass spectrometry (IMS) is a powerful analytical technique widely used in biology, chemistry, and materials science fields that continue to expand. IMS provides a qualitative compositional analysis and spatial mapping with high chemical specificity. The spatial mapping information can be 2D or 3D depending on the analysis technique employed. Due to the combination of complex mass spectra coupled with spatial information, large high-dimensional datasets (hyperspectral) are often produced. Therefore, the use of automated computational methods for an exploratory analysis is highly beneficial. The fast-paced development of artificial intelligence (AI) and machine learning (ML) tools has received significant attention in recent years. These tools, in principle, can enable the unification of data collection and analysis into a single pipeline to make sampling and analysis decisions on the go. There are various ML approaches that have been applied to IMS data over the last decade. Here, in this review, we discuss recent examples of the common unsupervised (principal component analysis, non-negative matrix factorization, k-means clustering, uniform manifold approximation and projection), supervised (random forest, logistic regression, XGboost, support vector machine), and other methods applied to various IMS datasets in the past five years. The information from this review will be useful for specialists from both IMS and ML fields since it summarizes current and representative studies of computational ML-based exploratory methods for IMS.

47 OTHER INSTRUMENTATION↗
DOE OSTI2023

Binary operations on neuromorphic hardware with application to linear algebraic operations and stochastic equations

Abstract Non-von Neumann computational hardware, based on neuron-inspired, non-linear elements connected via linear, weighted synapses—so-called neuromorphic systems—is a viable computational substrate. Since neuromorphic systems have been shown to use less power than CPUs for many applications, they are of potential use in autonomous systems such as robots, drones, and satellites, for which power resources are at a premium. The power used by neuromorphic systems is approximately proportional to the number of spiking events produced by neurons on-chip. However, typical information encoding on these chips is in the form of firing rates that unarily encode information. That is, the number of spikes generated by a neuron is meant to be proportional to an encoded value used in a computation or algorithm. Unary encoding is less efficient (produces more spikes) than binary encoding. For this reason, here we present neuromorphic computational mechanisms for implementing binary two’s complement operations. We use the mechanisms to construct a neuromorphic, binary matrix multiplication algorithm that may be used as a primitive for linear differential equation integration, deep networks, and other standard calculations. We also construct a random walk circuit and apply it in Brownian motion simulations. We study how both algorithms scale in circuit size and iteration time.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2019

Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing

We present two quantum algorithms based on evolution randomization, a simple variant of adiabatic quantum computing, to prepare a quantum state |x⟩ that is proportional to the solution of the system of linear equations $A\overrightarrow{x} = \overrightarrow{b}$. The time complexities of our algorithms are O(κ 2 log(κ)/ε) and O(κ log(κ)/ε), where κ is the condition number of A and ε is the precision. Both algorithms are constructed using families of Hamiltonians that are linear combinations of products of A, the projector onto the initial state |b⟩, and single-qubit Pauli operators. The algorithms are conceptually simple and easy to implement. They are not obtained from equivalences between the gate model and adiabatic quantum computing. They do not use phase estimation or variable-time amplitude amplification, and do not require large ancillary systems. We discuss a gate-based implementation via Hamiltonian simulation and prove that our second algorithm is almost optimal in terms of κ. Like previous methods, our techniques yield an exponential quantum speed-up under some assumptions. Our results emphasize the role of Hamiltonian-based models of quantum computing for the discovery of important algorithms.

97 MATHEMATICS AND COMPUTING↗