Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “computational 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.

At least 235 records · Page 13
All sourcesNASA NTRSDOE OSTI
NASA NTRS1984

Optical systolic solutions of linear algebraic equations

The philosophy and data encoding possible in systolic array optical processor (SAOP) were reviewed. The multitude of linear algebraic operations achievable on this architecture is examined. These operations include such linear algebraic algorithms as: matrix-decomposition, direct and indirect solutions, implicit and explicit methods for partial differential equations, eigenvalue and eigenvector calculations, and singular value decomposition. This architecture can be utilized to realize general techniques for solving matrix linear and nonlinear algebraic equations, least mean square error solutions, FIR filters, and nested-loop algorithms for control engineering applications. The data flow and pipelining of operations, design of parallel algorithms and flexible architectures, application of these architectures to computationally intensive physical problems, error source modeling of optical processors, and matching of the computational needs of practical engineering problems to the capabilities of optical processors are emphasized.

Neuman, C. P.↗
DOE OSTI2022

Compressed basis GMRES on high-performance graphics processing units

Krylov methods provide a fast and highly parallel numerical tool for the iterative solution of many large-scale sparse linear systems. To a large extent, the performance of practical realizations of these methods is constrained by the communication bandwidth in current computer architectures, motivating the investigation of sophisticated techniques to avoid, reduce, and/or hide the message-passing costs (in distributed platforms) and the memory accesses (in all architectures). This article leverages Ginkgo’s memory accessor in order to integrate a communication-reduction strategy into the (Krylov) GMRES solver that decouples the storage format (i.e., the data representation in memory) of the orthogonal basis from the arithmetic precision that is employed during the operations with that basis. Given that the execution time of the GMRES solver is largely determined by the memory accesses, the cost of the datatype transforms can be mostly hidden, resulting in the acceleration of the iterative step via a decrease in the volume of bits being retrieved from memory. Together with the special properties of the orthonormal basis (whose elements are all bounded by 1), this paves the road toward the aggressive customization of the storage format, which includes some floating-point as well as fixed-point formats with mild impact on the convergence of the iterative process. We develop a high-performance implementation of the “compressed basis GMRES” solver in the Ginkgo sparse linear algebra library using a large set of test problems from the SuiteSparse Matrix Collection. We demonstrate robustness and performance advantages on a modern NVIDIA V100 graphics processing unit (GPU) of up to 50% over the standard GMRES solver that stores all data in IEEE double-precision.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

Randomized Algorithms for Linear Solvers

Recently, randomized algorithms in numerical linear algebra, specifically those centered around random sketching, have gained traction in primarily theoretical research due to their potential to significantly reduce problem dimensionality at the cost of an O(1) multiplicative distortion factor. It has been assumed that this sketching can be done efficiently, but thorough investigation into how precisely to do it has been neglected. Moreover, the theory-based community has argued for sketching’s ability to reduce computational cost via complexity analysis, but has not researched how it affects the stability of the algorithms. At Sandia, efficient linear solvers that scale well on modern HPC architectures while maintaining stability are imperative for practical applications. In this LDRD, we developed a random sketching strategy that is substantially faster than existing ones, and demonstrate its superior performance in practice on a NVIDIA H100 GPU. Moreover, we show how this can be used to significantly outperform existing linear least squares solvers while improving the solver’s stability as well. Additionally, we demonstrate how this sketching strategy can be used to make a fast, stable QR factorization that can subsequently be used in s-step and block Krylov solvers. Finally, we incorporate a sketching-based block orthogonalization scheme into s-step GMRES, which is stable and faster than existing approaches on the Perlmutter supercomputer.

97 MATHEMATICS AND COMPUTING↗
NASA NTRSDate not supplied

Component-Based Development of CFD Software FUN3D

FUN3D, a suite of Computational Fluid Dynamics simulation and design tools developed at the NASA Langley Research Center, has undergone continuous development since the late1980s. It contains a large portion of legacy code. Extending it with new capabilities becomes increasingly difficult. To improve the extensibility and reusability, FUN3D is moving toward component-based development. New features, such as Stabilized Finite Elements, Yoga, and Sparse Linear Algebra Toolkit, are integrated into the system as components. Some existing features such as the Node-Centered Finite Volume Solver, are also being refactored to components. The integration of these components poses new requirements on the development workflow. In this paper, we describe the Continuous Integration of FUN3D to support component-based development, and discuss the tools used, the practices followed, and lessons learned during the transition from the traditional approach.

computational fluid dynamics software↗
NASA NTRS1985

An efficient algorithm for estimating noise covariances in distributed systems

An efficient computational algorithm for estimating the noise covariance matrices of large linear discrete stochatic-dynamic systems is presented. Such systems arise typically by discretizing distributed-parameter systems, and their size renders computational efficiency a major consideration. The proposed adaptive filtering algorithm is based on the ideas of Belanger, and is algebraically equivalent to his algorithm. The earlier algorithm, however, has computational complexity proportional to p to the 6th, where p is the number of observations of the system state, while the new algorithm has complexity proportional to only p-cubed. Further, the formulation of noise covariance estimation as a secondary filter, analogous to state estimation as a primary filter, suggests several generalizations of the earlier algorithm. The performance of the proposed algorithm is demonstrated for a distributed system arising in numerical weather prediction.

Dee, D. P.↗
NASA NTRS1997

Geopotential Error Analysis from Satellite Gradiometer and Global Positioning System Observables on Parallel Architecture

The recovery of a high resolution geopotential from satellite gradiometer observations motivates the examination of high performance computational techniques. The primary subject matter addresses specifically the use of satellite gradiometer and GPS observations to form and invert the normal matrix associated with a large degree and order geopotential solution. Memory resident and out-of-core parallel linear algebra techniques along with data parallel batch algorithms form the foundation of the least squares application structure. A secondary topic includes the adoption of object oriented programming techniques to enhance modularity and reusability of code. Applications implementing the parallel and object oriented methods successfully calculate the degree variance for a degree and order 110 geopotential solution on 32 processors of the Cray T3E. The memory resident gradiometer application exhibits an overall application performance of 5.4 Gflops, and the out-of-core linear solver exhibits an overall performance of 2.4 Gflops. The combination solution derived from a sun synchronous gradiometer orbit produce average geoid height variances of 17 millimeters.

Schutz, Bob E.↗
NASA NTRS1999

Angular-Rate Estimation Using Delayed Quaternion Measurements

This paper presents algorithms for estimating the angular-rate vector of satellites using quaternion measurements. Two approaches are compared one that uses differentiated quaternion measurements to yield coarse rate measurements, which are then fed into two different estimators. In the other approach the raw quaternion measurements themselves are fed directly into the two estimators. The two estimators rely on the ability to decompose the non-linear part of the rotas rotational dynamics equation of a body into a product of an angular-rate dependent matrix and the angular-rate vector itself. This non unique decomposition, enables the treatment of the nonlinear spacecraft (SC) dynamics model as a linear one and, thus, the application of a PseudoLinear Kalman Filter (PSELIKA). It also enables the application of a special Kalman filter which is based on the use of the solution of the State Dependent Algebraic Riccati Equation (SDARE) in order to compute the gain matrix and thus eliminates the need to compute recursively the filter covariance matrix. The replacement of the rotational dynamics by a simple Markov model is also examined. In this paper special consideration is given to the problem of delayed quaternion measurements. Two solutions to this problem are suggested and tested. Real Rossi X-Ray Timing Explorer (RXTE) data is used to test these algorithms, and results are presented.

Azor, R.↗
NASA NTRS1990

On three dimensional object recognition and pose-determination: An abstraction based approach

A method of computing reliable Gaussian and mean curvature sign-map descriptors from the polynomial approximation of surfaces was demonstrated. Such descriptors which are invariant under perspective variation are suitable for hypothesis generation. A means for determining the pose of constructed geometric forms whose algebraic surface descriptors are nonlinear in terms of their orienting parameters was developed. This was done by means of linear functions which are capable of approximating nonlinear forms and determining their parameters. It was shown that biquadratic surfaces are suitable companion linear forms for cylindrical approximation and parameter estimation. The estimates provided the initial parametric approximations necessary for a nonlinear regression stage to fine tune the estimates by fitting the actual nonlinear form to the data. A hypothesis-based split-merge algorithm for extraction and pose determination of cylinders and planes which merge smoothly into other surfaces was developed. It was shown that all split-merge algorithms are hypothesis-based. A finite-state algorithm for the extraction of the boundaries of run-length regions was developed. The computation takes advantage of the run list topology and boundary direction constraints implicit in the run-length encoding.

Quek, Kok How Francis↗
NASA NTRSDate not supplied

Towards Formalization of Advanced Linear Algebra with Applications to Dynamical Systems using PVS

Linear Algebra is essential for numerous aerospace problems of interest. Formal reasoning about hybrid systems that contain variables modeled by differential equations rely on concepts from Linear Algebra such as eigenvalues, matrix decompositions, and matrix valued functions. For example, the long-term dynamics of a system of differential equations depend on the stability/instability of its equilibrium points, which often reduces to an eigenvalue problem. This talk will embark on a quest to formalize theorems and results about eigenvalues and eigenvectors using PVS. We shall start our journey with 2 x 2 complex matrices, where we will apply our PVS code to a simple example of a dynamical system. Since it can be difficult or impossible to give simple expressions of eigenvalues for larger matrices (i.e. 5 x 5 or higher), we then move towards specifying the power method for verified computation of eigenvalue approximations in PVS. This effort requires development of multivariate complex arithmetic. At the end of the day, having such additions to the PVS NASA libraries will help move towards the use of formal methods to verify concepts of control theory and system level verification.

Linear Algebra↗
DOE OSTI2025

A Scalable Interior‐Point Gauss–Newton Method for PDE‐Constrained Optimization With Bound Constraints

Here, we present a scalable approach to solve a class of partial differential equation (PDE)‐constrained optimization problems with bound constraints. This approach utilizes a robust full‐space interior‐point (IP)‐Gauss–Newton optimization method. To cope with the poorly‐conditioned IP‐Gauss–Newton saddle‐point linear systems that need to be solved approximately, once per optimization step, we propose two spectrally related preconditioners. These preconditioners leverage the limited informativeness of data in regularized PDE‐constrained optimization problems. A block Gauss–Seidel preconditioner is proposed for the GMRES‐based solution of the IP‐Gauss–Newton linear systems. It is shown, for a large‐class of PDE‐ and bound‐constrained optimization problems, that the spectrum of the block Gauss–Seidel preconditioned IP‐Gauss–Newton matrix is asymptotically independent of discretization and is not impacted by the ill‐conditioning that notoriously plagues interior‐point methods. We exploit symmetry of the IP‐Gauss–Newton linear systems and propose a regularization and log‐barrier Hessian preconditioner for the preconditioned conjugate gradient (PCG)‐based solution of the equivalent IP‐Gauss–Newton–Schur complement linear systems. The eigenvalues of the block Gauss–Seidel preconditioned IP‐Gauss–Newton matrix, that are not equal to one, are identical to the eigenvalues of the regularization and log‐barrier Hessian preconditioned Schur complement matrix. The scalability of the approach is demonstrated on two example problems. The numerical solution of these optimization problems is shown to require a discretization independent number of IP‐Gauss–Newton linear solves. Furthermore, the linear systems are solved in a discretization and IP ill‐conditioning independent number of preconditioned Krylov subspace iterations. The parallel scalability of the preconditioner, achieved via algebraic multigrid component solvers when applicable, and the aforementioned algorithmic scalability permits a parallel scalable means to compute solutions of a large class of PDE‐ and bound‐constrained problems.

PDE-constrained optimization↗
DOE OSTI2022

Autodifferentiable Spectrum Model for High-dispersion Characterization of Exoplanets and Brown Dwarfs

We present an autodifferentiable spectral modeling of exoplanets and brown dwarfs. This model enables a fully Bayesian inference of the high-dispersion data to fit the ab initio line-by-line spectral computation to the observed spectrum by combining it with the Hamiltonian Monte Carlo in recent probabilistic programming languages. An open-source code, ExoJAX, developed in this study, was written in Python using the GPU/TPU compatible package for automatic differentiation and accelerated linear algebra, JAX. We validated the model by comparing it with existing opacity calculators and a radiative transfer code and found reasonable agreements for the output. As a demonstration, we analyzed the high-dispersion spectrum of a nearby brown dwarf, Luhman 16 A, and found that a model including water, carbon monoxide, and H 2 /He collision-induced absorption was well fitted to the observed spectrum (R = 10 5 and 2.28-2.30 μm). As a result, we found that T0 = 1295$^{-32}_{+35}$ K at 1 bar and C/O = 0.62 ± 0.03, which is slightly higher than the solar value. This work demonstrates the potential of a full Bayesian analysis of brown dwarfs and exoplanets as observed by high-dispersion spectrographs and also directly imaged exoplanets as observed by high-dispersion coronagraphy.

79 ASTRONOMY AND ASTROPHYSICS↗
NASA NTRS1990

SPARSKIT: A basic tool kit for sparse matrix computations

Presented here are the main features of a tool package for manipulating and working with sparse matrices. One of the goals of the package is to provide basic tools to facilitate the exchange of software and data between researchers in sparse matrix computations. The starting point is the Harwell/Boeing collection of matrices for which the authors provide a number of tools. Among other things, the package provides programs for converting data structures, printing simple statistics on a matrix, plotting a matrix profile, and performing linear algebra operations with sparse matrices.

Saad, Youcef↗
NASA NTRS1991

Solution of steady-state, two-dimensional conservation laws by mathematical programming

A truly two-dimensional algorithm is created for solving the steady-state two-dimensional conservation-law problem. An overdetermined system of algebraic equations is obtained through discretization by finite-volume formulas. These equations are perturbed nonsingularly and are solved by an efficient geometrically oriented l(1) procedure. The basic algorithm and the theory for the linear case f(u) = u are presented, and computational results for the nonlinear case f(u) = sq u are also analyzed. It is noted that the l(1) procedure captures boundary shocks as well as oblige and zigzag interior shocks in bands that are one cell wide, and the solution values are accurate up to the edge of the shock.

Lavery, John E.↗
NASA NTRS1992

Analysis and experimental evaluation of a Stewart platform-based force/torque sensor

The kinematic analysis and experimentation of a force/torque sensor whose design is based on the mechanism of the Stewart Platform are discussed. Besides being used for measurement of forces/torques, the sensor also serves as a compliant platform which provides passive compliance during a robotic assembly task. It consists of two platforms, the upper compliant platform (UCP) and the lower compliant platform (LCP), coupled together through six spring-loaded pistons whose length variations are measured by six linear voltage differential transformers (LVDT) mounted along the pistons. Solutions to the forward and inverse kinematics of the force sensor are derived. Based on the known spring constant and the piston length changes, forces/torques applied to the LCP gripper are computed using vector algebra. Results of experiments conducted to evaluate the sensing capability of the force sensor are reported and discussed.

Nguyen, Charles C.↗
NASA NTRS1996

Numerical Modeling of Spray Combustion with an Unstructured-Grid Method

The present unstructured-grid method follows strictly the basic finite volume forms of the conservation laws of the governing equations for the entire flow domain. High-order spatially accurate formulation has been employed for the numerical solutions of the Navier-Stokes equations. A two-equation k-epsilon turbulence model is also incorporated in the unstructured-grid solver. The convergence of the resulted linear algebraic equation is accelerated with preconditioned Conjugate Gradient method. A statistical spray combustion model has been incorporated into the present unstructured-grid solver. In this model, spray is represented by discrete particles, rather than by continuous distributions. A finite number of computational particles are used to predict a sample of total population of particles. Particle trajectories are integrated using their momentum and motion equations and particles exchange mass, momentum and energy with the gas within the computational cell in which they are located. The interaction calculations are performed simultaneously and eliminate global iteration for the two-phase momentum exchange. A transient spray flame in a high pressure combustion chamber is predicted and then the solution of liquid-fuel combusting flow with a rotating cup atomizer is presented and compared with the experimental data. The major conclusion of this investigation is that the unstructured-grid method can be employed to study very complicated flow fields of turbulent spray combustion. Grid adaptation can be easily achieved in any flow domain such as droplet evaporation and combustion zone. Future applications of the present model can be found in the full three-dimensional study of flow fields of gas turbine and liquid propulsion engine combustion chambers with multi-injectors.

Shang, H. M.↗
NASA NTRS2015

Discrete Fourier Transform in a Complex Vector Space

An image-based phase retrieval technique has been developed that can be used on board a space based iterative transformation system. Image-based wavefront sensing is computationally demanding due to the floating-point nature of the process. The discrete Fourier transform (DFT) calculation is presented in "diagonal" form. By diagonal we mean that a transformation of basis is introduced by an application of the similarity transform of linear algebra. The current method exploits the diagonal structure of the DFT in a special way, particularly when parts of the calculation do not have to be repeated at each iteration to converge to an acceptable solution in order to focus an image.

Dean, Bruce H.↗
NASA NTRS1998

Lightning Radio Source Retrieval Using Advanced Lightning Direction Finder (ALDF) Networks

A linear algebraic solution is provided for the problem of retrieving the location and time of occurrence of lightning ground strikes from an Advanced Lightning Direction Finder (ALDF) network. The ALDF network measures field strength, magnetic bearing and arrival time of lightning radio emissions. Solutions for the plane (i.e., no Earth curvature) are provided that implement all of tile measurements mentioned above. Tests of the retrieval method are provided using computer-simulated data sets. We also introduce a quadratic planar solution that is useful when only three arrival time measurements are available. The algebra of the quadratic root results are examined in detail to clarify what portions of the analysis region lead to fundamental ambiguities in source location. Complex root results are shown to be associated with the presence of measurement errors when the lightning source lies near an outer sensor baseline of the ALDF network. In the absence of measurement errors, quadratic root degeneracy (no source location ambiguity) is shown to exist exactly on the outer sensor baselines for arbitrary non-collinear network geometries. The accuracy of the quadratic planar method is tested with computer generated data sets. The results are generally better than those obtained from the three station linear planar method when bearing errors are about 2 deg. We also note some of the advantages and disadvantages of these methods over the nonlinear method of chi(sup 2) minimization employed by the National Lightning Detection Network (NLDN) and discussed in Cummins et al.(1993, 1995, 1998).

Koshak, William J.↗
NASA NTRS2000

Data Retrieval Algorithms for Validating the Optical Transient Detector and the Lightning Imaging Sensor

A linear algebraic solution is provided for the problem of retrieving the location and time of occurrence of lightning ground strikes from an Advanced Lightning Direction Finder (ALDF) network. The ALDF network measures field strength, magnetic bearing, and arrival time of lightning radio emissions. Solutions for the plane (i.e., no earth curvature) are provided that implement all of these measurements. The accuracy of the retrieval method is tested using computer-simulated datasets, and the relative influence of bearing and arrival time data an the outcome of the final solution is formally demonstrated. The algorithm is sufficiently accurate to validate NASA:s Optical Transient Detector and Lightning Imaging Sensor. A quadratic planar solution that is useful when only three arrival time measurements are available is also introduced. The algebra of the quadratic root results are examined in detail to clarify what portions of the analysis region lead to fundamental ambiguities in sc)iirce location, Complex root results are shown to be associated with the presence of measurement errors when the lightning source lies near an outer sensor baseline of the ALDF network. For arbitrary noncollinear network geometries and in the absence of measurement errors, it is shown that the two quadratic roots are equivalent (no source location ambiguity) on the outer sensor baselines. The accuracy of the quadratic planar method is tested with computer-generated datasets, and the results are generally better than those obtained from the three-station linear planar method when bearing errors are about 2 deg.

Koshak, W. J.↗