Search NASA⌕ Search

SEARCH · Search NASA

Results for “Sparse solver”

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 271 records · Page 15

Bayesian differential programming for robust systems identification under uncertainty

This paper presents a machine learning framework for Bayesian systems identification from noisy, sparse and irregular observations of nonlinear dynamical systems. The proposed method takes advantage of recent developments in differentiable programming to propagate gradient information through ordinary differential equation solvers and perform Bayesian inference with respect to unknown model parameters using Hamiltonian Monte Carlo sampling. This allows an efficient inference of the posterior distributions over plausible models with quantified uncertainty, while the use of sparsity-promoting priors enables the discovery of interpretable and parsimonious representations for the underlying latent dynamics. A series of numerical studies is presented to demonstrate the effectiveness of the proposed methods, including nonlinear oscillators, predator–prey systems and examples from systems biology. Taken together, our findings put forth a flexible and robust workflow for data-driven model discovery under uncertainty. All codes and data accompanying this article are available at https://bit.ly/34FOJMj .

Science & Technology - Other Topics↗

Parameter Sensitivity Analysis of the SparTen High Performance Sparse Tensor Decomposition Software (Extended Analysis)

Tensor decomposition models play an increasingly important role in modern data science applications. One problem of particular interest is fitting a low-rank Canonical Polyadic (CP) tensor decomposition model when the tensor has sparse structure and the tensor elements are nonnegative count data. SparTen is a high-performance C++ library which computes a low-rank decomposition using different solvers: a first-order quasi-Newton or a second-order damped Newton method, along with the appropriate choice of runtime parameters. Since default parameters in SparTen are tuned to experimental results in prior published work on a single real-world dataset conducted using MATLAB implementations of these methods, it remains unclear if the parameter defaults in SparTen are appropriate for general tensor data. Furthermore, it is unknown how sensitive algorithm convergence is to changes in the input parameter values. This report addresses these unresolved issues with large-scale experimentation on three benchmark tensor data sets. Experiments were conducted on several different CPU architectures and replicated with many initial states to establish generalized profiles of algorithm convergence behavior.

97 MATHEMATICS AND COMPUTING↗

Efficient convolutional sparse coding

Computationally efficient algorithms may be applied for fast dictionary learning solving the convolutional sparse coding problem in the Fourier domain. More specifically, efficient convolutional sparse coding may be derived within an alternating direction method of multipliers (ADMM) framework that utilizes fast Fourier transforms (FFT) to solve the main linear system in the frequency domain. Such algorithms may enable a significant reduction in computational cost over conventional approaches by implementing a linear solver for the most critical and computationally expensive component of the conventional iterative algorithm. The theoretical computational cost of the algorithm may be reduced from O(M.sup.3N) to O(MN log N), where N is the dimensionality of the data and M is the number of elements in the dictionary. This significant improvement in efficiency may greatly increase the range of problems that can practically be addressed via convolutional sparse representations.

97 MATHEMATICS AND COMPUTING↗

MueMat Multicrid Toolbox

MueMat is intended for the research and development of multigrid algorithms used in the solution of sparse linear systems arising from systems of partial differential equations. The software can generate example linear systems and provides short programs to demonstrate the various interfaces for creating, accessing, and applying the solvers. MueMat currently includes two types of algebraic multigrid methods and many commonly used smoothers. However, the software is intended to be extensible, and new methods can be incorporated easily. MueMat also allows for advanced usage, such as combining multiple methods and segregated solves. The library supports point and block access to matrix data. MueMat has been designed for use within the programming environment of the Mathworks program MATLAB®. All algorithms and methods in MueMat have been or will be published in the open scientific literature.

Boman, ErikG.↗

MueLu Multigrid Preconditioning Package

MueLu is intended for the research and development of multigrid algorithms used in the solution of sparse linear systems arising from systems of partial differential equations. The software provides multigrid source code, test programs, and short example programs to demonstrate the various interfaces for creating, accessing, and applying the solvers. MueLu currently provides an implementation of smoothed aggregation algebraic multigrid method and interfaces to many commonly used smoothers. However, the software is intended to be extensible, and new methods can be incorporated easily. MueLu also allows for advanced usage, such as combining multiple methods and segregated solves. The library supports point and block access to matrix data. All algorithms and methods in MueLu have been or will be published in the open scientific literature.

Tuminaro, Raymond↗

MueLu Multigrid Preconditioning Package

MueLu is intended for the research and development of multigrid algorithms used in the solution of sparse linear systems arising from systems of partial differential equations. The software provides multigrid source code, test programs, and short example programs to demonstrate the various interfaces for creating, accessing, and applying the solvers. MueLu currently provides an implementation of smoothed aggregation algebraic multigrid method and interfaces to many commonly used smoothers. However, the software is intended to be extensible, and new methods can be incorporated easily. MueLu also allows for advanced usage, such as combining multiple methods and segregated solves. The library supports point and block access to matrix data. All algorithms and methods in MueLu have been or will be published in the open scientific literature.

Source record↗

Scalable implicit incompressible resistive MHD with stabilized FE and fully-coupled Newton–Krylov-AMG

Here, we discuss that the computational solution of the governing balance equations for mass, momentum, heat transfer and magnetic induction for resistive magnetohydrodynamics (MHD) systems can be extremely challenging. These difficulties arise from both the strong nonlinear, nonsymmetric coupling of fluid and electromagnetic phenomena, as well as the significant range of time- and length-scales that the interactions of these physical mechanisms produce. This paper explores the development of a scalable, fully-implicit stabilized unstructured finite element (FE) capability for 3D incompressible resistive MHD. The discussion considers the development of a stabilized FE formulation in context of the variational multiscale (VMS) method, and describes the scalable implicit time integration and direct-to-steady-state solution capability. The nonlinear solver strategy employs Newton–Krylov methods, which are preconditioned using fully-coupled algebraic multilevel preconditioners. These preconditioners are shown to enable a robust, scalable and efficient solution approach for the large-scale sparse linear systems generated by the Newton linearization. Verification results demonstrate the expected order-of-accuracy for the stabilized FE discretization. The approach is tested on a variety of prototype problems, that include MHD duct flows, an unstable hydromagnetic Kelvin–Helmholtz shear layer, and a 3D island coalescence problem used to model magnetic reconnection. Initial results that explore the scaling of the solution methods are also presented on up to 128K processors for problems with up to 1.8B unknowns on a CrayXK7.

97 MATHEMATICS AND COMPUTING↗

UQ and V&V techniques applied to experiments and simulations of heated pipes pressurized to failure

This report demonstrates versatile and practical model validation and uncertainty quantification techniques applied to the accuracy assessment of a computational model of heated steel pipes pressurized to failure. The Real Space validation methodology segregates aleatory and epistemic uncertainties to form straightforward model validation metrics especially suited for assessing models to be used in the analysis of performance and safety margins. The methodology handles difficulties associated with representing and propagating interval and/or probabilistic uncertainties from multiple correlated and uncorrelated sources in the experiments and simulations including: material variability characterized by non-parametric random functions (discrete temperature dependent stress-strain curves); very limited (sparse) experimental data at the coupon testing level for material characterization and at the pipe-test validation level; boundary condition reconstruction uncertainties from spatially sparse sensor data; normalization of pipe experimental responses for measured input-condition differences among tests and for random and systematic uncertainties in measurement/processing/inference of experimental inputs and outputs; numerical solution uncertainty from model discretization and solver effects.

97 MATHEMATICS AND COMPUTING↗

SU-G-TeP1-15: Toward a Novel GPU Accelerated Deterministic Solution to the Linear Boltzmann Transport Equation

Purpose: To develop a Graphic Processor Unit (GPU) accelerated deterministic solution to the Linear Boltzmann Transport Equation (LBTE) for accurate dose calculations in radiotherapy (RT). A deterministic solution yields the potential for major speed improvements due to the sparse matrix-vector and vector-vector multiplications and would thus be of benefit to RT. Methods: In order to leverage the massively parallel architecture of GPUs, the first order LBTE was reformulated as a second order self-adjoint equation using the Least Squares Finite Element Method (LSFEM). This produces a symmetric positive-definite matrix which is efficiently solved using a parallelized conjugate gradient (CG) solver. The LSFEM formalism is applied in space, discrete ordinates is applied in angle, and the Multigroup method is applied in energy. The final linear system of equations produced is tightly coupled in space and angle. Our code written in CUDA-C was benchmarked on an Nvidia GeForce TITAN-X GPU against an Intel i7-6700K CPU. A spatial mesh of 30,950 tetrahedral elements was used with an S4 angular approximation. Results: To avoid repeating a full computationally intensive finite element matrix assembly at each Multigroup energy, a novel mapping algorithm was developed which minimized the operations required at each energy. Additionally, a parallelized memory mapping for the kronecker product between the sparse spatial and angular matrices, including Dirichlet boundary conditions, was created. Atomicity is preserved by graph-coloring overlapping nodes into separate kernel launches. The one-time mapping calculations for matrix assembly, kronecker product, and boundary condition application took 452±1ms on GPU. Matrix assembly for 16 energy groups took 556±3s on CPU, and 358±2ms on GPU using the mappings developed. The CG solver took 93±1s on CPU, and 468±2ms on GPU. Conclusion: Three computationally intensive subroutines in deterministically solving the LBTE have been formulated on GPU, resulting in two orders of magnitude speedup. Funding support from Natural Sciences and Engineering Research Council and Alberta Innovates Health Solutions. Dr. Fallone is a co-founder and CEO of MagnetTx Oncology Solutions (under discussions to license Alberta bi-planar linac MR for commercialization).

60 APPLIED LIFE SCIENCES↗

Iterative methods for large scale static analysis of structures on a scalable multiprocessor supercomputer

A parallel Preconditioned Conjugate Gradient (PCG) iterative solver has been developed and implemented on the iPSC-860 scalable hypercube. This new implementation makes use of the Parallel Automated Runtime Toolkit at ICASE (PARTI) primitives to efficiently program irregular communications patterns that exist in general sparse matrices and in particular in the finite element sparse stiffness matrices. The iterative PCG has been used to solve the finite element equations that result from discretizing large scale aerospace structures. In particular, the static response of the High Speed Civil Transport (HSCT) finite element model is solved on the iPSC-860.

Sobh, Nahil Atef↗

HyKKT: a hybrid direct-iterative method for solving KKT linear systems

Here, we propose a solution strategy for the large indefinite linear systems arising in interior methods for nonlinear optimization. The method is suitable for implementation on hardware accelerators such as graphical processing units (GPUs). The current gold standard for sparse indefinite systems is the LBLT factorization where L is a lower triangular matrix and B is 1×1 or 2×2 block diagonal. However, this requires pivoting, which substantially increases communication cost and degrades performance on GPUs. Our approach solves a large indefinite system by solving multiple smaller positive definite systems, using an iterative solver on the Schur complement and an inner direct solve (via Cholesky factorization) within each iteration. Cholesky is stable without pivoting, thereby reducing communication and allowing reuse of the symbolic factorization. We demonstrate the practicality of our approach on large optimal power flow problems and show that it can efficiently utilize GPUs and outperform LBL T factorization of the full system.

97 MATHEMATICS AND COMPUTING↗

Stochastic multiscale flux basis for Stokes-Darcy flows

Three algorithms are developed for uncertainty quantification in modeling coupled Stokes and Darcy flows. The porous media may consist of multiple regions with different properties. The permeability is modeled as a non-stationary stochastic variable, with its log represented as a sum of local Karhunen-Loève (KL) expansions. The problem is approximated by stochastic collocation on either tensor-product or sparse grids, coupled with a multiscale mortar mixed finite element method for the spatial discretization. A non-overlapping domain decomposition algorithm reduces the global problem to a coarse scale mortar interface problem, which is solved by an iterative solver, for each stochastic realization. In the traditional domain decomposition implementation, each subdomain solves a local Dirichlet or Neumann problem in every interface iteration. To reduce this cost, two additional algorithms based on deterministic or stochastic multiscale flux basis are introduced. The basis consists of the local flux (or velocity trace) responses from each mortar degree of freedom. It is computed for each subdomain independently before the interface iteration begins. The use of the multiscale flux basis avoids the need for subdomain solves on each iteration. The deterministic basis is computed at each stochastic collocation and used only at this realization. The stochastic basis is formed by further looping over all local realizations of a subdomain's KL region before the stochastic collocation begins. It is used over multiple realizations. Numerical tests are presented to illustrate the performance of the three algorithms, with the stochastic multiscale flux basis showing significant savings in computational cost compared to the other two algorithms.

97 MATHEMATICS AND COMPUTING↗

COHERENT BACKSCATTERING VERIFIED NUMERICALLY FOR A FINITE VOLUME OF SPHERICAL PARTICLES

We consider electromagnetic scattering by a spherical volume sparsely and randomly populated by spherical particles of equal size and optical properties. The far-field scattering matrix of the entire volume is computed using an exact method and an approximate method. The former is a direct computer solver of the Maxwell equations called the superposition T-matrix method (STMM). The latter is a solver based on numerical Monte Carlo integration of the ladder and cyclical diagrams appearing in the microphysical theory of radiative transfer and coherent backscattering (RT-CB). The quantitative agreement between the STMM and RT-CB computations provides verification of the RT-CB theory. Prominent backscattering features exhibited by the STMM data cannot be reproduced by keeping only the ladder diagrams of RT. Our results strongly support the CB explanation of opposition brightness and polarization phenomena observed for a class of atmosphereless solar-system objects. Further research is necessary to determine the range of quantitative applicability of the RT-CB theory to densely packed particulate media.

79 ASTRONOMY AND ASTROPHYSICS↗

NASA Tech Briefs, August 2005

Topics include: Hidden Identification on Parts: Magnetic Machine-Readable Matrix Symbols; System for Processing Coded OFDM Under Doppler and Fading; Multipurpose Hyperspectral Imaging System; Magnetic-Flux-Compensated Voltage Divider; High-Performance Satellite/Terrestrial-Network Gateway; Internet-Based System for Voice Communication With the ISS; Stripline/Microstrip Transition in Multilayer Circuit Board; Dual-Band Feed for a Microwave Reflector Antenna; Quadratic Programming for Allocating Control Effort; Range Process Simulation Tool; Simulator of Space Communication Networks; Computing Q-D Relationships for Storage of Rocket Fuels; Contour Error Map Algorithm; Portfolio Analysis Tool; Glass Frit Filters for Collecting Metal Oxide Nanoparticles; Anhydrous Proton-Conducting Membranes for Fuel Cells; Portable Electron-Beam Free-Form Fabrication System; Miniature Laboratory for Detecting Sparse Biomolecules; Multicompartment Liquid-Cooling/Warming Protective Garments; Laser Metrology for an Optical-Path-Length Modulator; PCM Passive Cooling System Containing Active Subsystems; Automated Electrostatics Environmental Chamber; Estimating Aeroheating of a 3D Body Using a 2D Flow Solver; Artificial Immune System for Recognizing Patterns; Computing the Thermodynamic State of a Cryogenic Fluid; Safety and Mission Assurance Performance Metric; Magnetic Control of Concentration Gradient in Microgravity; Avionics for a Small Robotic Inspection Spacecraft; and Simulation of Dynamics of a Flexible Miniature Airplane.

Source record↗

On the scalability of the Albany/FELIX first-order Stokes approximation ice sheet solver for large-scale simulations of the Greenland and Antarctic ice sheets

We examine the scalability of the recently developed Albany/FELIX finite-element based code for the first-order Stokes momentum balance equations for ice flow. We focus our analysis on the performance of two possible preconditioners for the iterative solution of the sparse linear systems that arise from the discretization of the governing equations: (1) a preconditioner based on the incomplete LU (ILU) factorization, and (2) a recently-developed algebraic multigrid (AMG) preconditioner, constructed using the idea of semi-coarsening. A strong scalability study on a realistic, high resolution Greenland ice sheet problem reveals that, for a given number of processor cores, the AMG preconditioner results in faster linear solve times but the ILU preconditioner exhibits better scalability. A weak scalability study is performed on a realistic, moderate resolution Antarctic ice sheet problem, a substantial fraction of which contains floating ice shelves, making it fundamentally different from the Greenland ice sheet problem. Here, we show that as the problem size increases, the performance of the ILU preconditioner deteriorates whereas the AMG preconditioner maintains scalability. This is because the linear systems are extremely ill-conditioned in the presence of floating ice shelves, and the ill-conditioning has a greater negative effect on the ILU preconditioner than on the AMG preconditioner.

54 ENVIRONMENTAL SCIENCES↗

Scaling Structured Multigrid to 500K+ Cores Through Coarse-Grid Redistribution

The effcient solution of sparse, linear systems resulting from the discretization of partial differential equations is crucial to the performance of many physics-based simulations. The algorithmic optimality of multilevel approaches for common discretizations makes them a good candidate for an efficient parallel solver. Yet, modern architectures for high-performance computing systems continue to challenge the parallel scalability of multilevel solvers. While algebraic multigrid methods are robust for solving a variety of problems, the increasing importance of data locality and cost of data movement in modern architectures motivates the need to carefully exploit structure in the problem. Robust logically structured variational multigrid methods, such as Black Box Multigrid (BoxMG), maintain structure throughout the multigrid hierarchy. This avoids indirection and increased coarse- grid communication costs typical in parallel algebraic multigrid. Nevertheless, the parallel scalability of structured multigrid is challenged by coarse-grid problems where the overhead in communication dominates computation. In this paper, an algorithm is introduced for redistributing coarse-grid problems through incremental agglomeration. Guided by a predictive performance model, this algorithm provides robust redistribution decisions for structured multilevel solvers. A two-dimensional diffusion problem is used to demonstrate the significant gain in performance of this algorithm over the previous approach that used agglomeration to one processor. In addition, the parallel scalability of this approach

97 MATHEMATICS AND COMPUTING↗

Sparse chronology strategy for integrating seasonal energy storage in capacity expansion models

Here, this study develops the sparse chronology method to enhance the representative period framework in capacity expansion models, enabling the effective integration of long-duration energy storage modeling. Traditional representative period methods cannot capture the state of charge of seasonal energy storage systems because they do not establish effective inter-day linkages to connect the state of charge between periods. The sparse chronology approach addresses this limitation by establishing inter-day linkages that allow state of charge to shift inter-seasonally. At the same time, it groups identical representative days into partitions, applying constraints sparsely and implicitly to reduce computational load further. Validation results demonstrate that this method successfully simulates long-duration energy storage patterns, achieving close alignment with a continuous yearly benchmark model, with seasonal trends and state of charge cycles clearly represented. The computational load analysis reveals that the sparse chronology method efficiently applies constraints on maximum and minimum state of charge limits within the representative day framework, eliminating the need for detailed constraints on each individual day. By partitioning representative days and constraining only the start and end of each partition, the method significantly decreases computational requirements. Simulation results show that sparse chronology closely approximates the continuous yearly method's accuracy, even with as few as 20 representative days, achieving correlation values with the benchmark of nearly 0.9 in state of charge plots. Furthermore, it maintains computational efficiency, requiring only 4 % of the solver time compared to the continuous yearly method with 20 representative days. This approach allows capacity expansion models to incorporate long-duration energy storage with high temporal, spatial, and technological resolution, enabling more detailed modeling for large-scale power systems.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Sparse recovery of undersampled intensity patterns for coherent diffraction imaging at high X-ray energies

Coherent X-ray photons with energies higher than 50 keV offer new possibilities for imaging nanoscale lattice distortions in bulk crystalline materials using Bragg peak phase retrieval methods. However, the compression of reciprocal space at high energies typically results in poorly resolved fringes on an area detector, rendering the diffraction data unsuitable for the three-dimensional reconstruction of compact crystals. To address this problem, we propose a method by which to recover fine fringe detail in the scattered intensity. This recovery is achieved in two steps: multiple undersampled measurements are made by in-plane sub-pixel motion of the area detector, then this data set is passed to a sparsity-based numerical solver that recovers fringe detail suitable for standard Bragg coherent diffraction imaging (BCDI) reconstruction methods of compact single crystals. The key insight of this paper is that sparsity in a BCDI data set can be enforced by recognising that the signal in the detector, though poorly resolved, is band-limited. This requires fewer in-plane detector translations for complete signal recovery, while adhering to information theory limits. Lastly, we use simulated BCDI data sets to demonstrate the approach, outline our sparse recovery strategy, and comment on future opportunities.

36 MATERIALS SCIENCE↗