Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “sparse direct method”

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 91 records · Page 5

Indigo: A Domain-Specific Language for Fast, Portable Image Reconstruction

© 2018 IEEE. Linear operators used in iterative methods like conjugate gradient have typically been implemented either as ''matrix-driven'' subroutines backed by explicit sparse or dense matrices, or as ''matrix-free'' subroutines that implement specific linear operations directly (e.g. FFTs). The matrix-driven approach is generally more portable because it can target widely-Available BLAS libraries, but it can be inefficient in terms of time and space complexity. In contrast, the matrix-free approach is more performant because it leverages structure in operations, but it requires each operator be re-implemented on each new platform. To increase performance and portability, we propose a hybrid approach that represents linear operators as expression trees. Leaf nodes in the tree are either matrix-free or matrix-driven operators, and interior nodes represent mathematical compositions (sums, products, transposes) or structural compositions (stacks, block diagonals, etc.) of the leaf operators. This representation enables expert-guided reordering and fusion transformations that can improve performance or reduce memory pressure. We implement our approach in a domain-specific language called Indigo. We assess Indigo on image reconstruction problems arising in four application areas: magnetic resonance imaging, ptychography, magnetic particle imaging, and fluorescent microscopy. We give performance results from vendor BLAS libraries, and we introduce specializations to Sparse BLAS routines that achieve near-Roofline performance on multi-core, many-core, and GPU systems.

Driscoll, Michael↗

A graphics processing unit accelerated sparse direct solver and preconditioner with block low rank compression

We present the GPU implementation efforts and challenges of the sparse solver package STRUMPACK. The code is made publicly available on github with a permissive BSD license. STRUMPACK implements an approximate multifrontal solver, a sparse LU factorization which makes use of compression methods to accelerate time to solution and reduce memory usage. Multiple compression schemes based on rank-structured and hierarchical matrix approximations are supported, including hierarchically semi-separable, hierarchically off-diagonal butterfly, and block low rank. Here, in this paper, we present the GPU implementation of the block low rank (BLR) compression method within a multifrontal solver. Our GPU implementation relies on highly optimized vendor libraries such as cuBLAS and cuSOLVER for NVIDIA GPUs, rocBLAS and rocSOLVER for AMD GPUs and the Intel oneAPI Math Kernel Library (oneMKL) for Intel GPUs. Additionally, we rely on external open source libraries such as SLATE (Software for Linear Algebra Targeting Exascale), MAGMA (Matrix Algebra on GPU and Multi-core Architectures), and KBLAS (KAUST BLAS). SLATE is used as a GPU-capable ScaLAPACK replacement. From MAGMA we use variable sized batched dense linear algebra operations such as GEMM, TRSM and LU with partial pivoting. KBLAS provides efficient (batched) low rank matrix compression for NVIDIA GPUs using an adaptive randomized sampling scheme. The resulting sparse solver and preconditioner runs on NVIDIA, AMD and Intel GPUs. Interfaces are available from PETSc, Trilinos and MFEM, or the solver can be used directly in user code. We report results for a range of benchmark applications, using the Perlmutter system from NERSC, Frontier from ORNL, and Aurora from ALCF. For a high frequency wave equation on a regular mesh, using 32 Perlmutter compute nodes, the factorization phase of the exact GPU solver is about 6.5× faster compared to the CPU-only solver. The BLR-enabled GPU solver is about 13.8× faster than the CPU exact solver. For a collection of SuiteSparse matrices, the STRUMPACK exact factorization on a single GPU is on average 1.9× faster than NVIDIA’s cuDSS solver.

97 MATHEMATICS AND COMPUTING↗

Gamma-Ray Point-Source Localization and Sparse Image Reconstruction using Poisson Likelihood

Gamma-ray imaging trys to reconstruct the spatial and intensity distribution of gamma-emitting radionuclides from a set of measurements. Wholly, this problem is solved by discretizing the spatial dimensions and employing the maximum likelihood expectation maximization (ML-EM) algorithm, with or without some form of regularization. While the generality of this formulation enables use in a wide variety of scenarios, it is susceptible to overfitting, limited by the discretization of spatial coordinates, and can be computationally expensive. We present a novel approach to 3D gamma-ray image reconstruction for scenarios where sparsity may be assumed, for example radiological source search. In this work we first formulate a point-source localization (PSL) approach as an optimization problem where both position and source intensity are continuous variables. We then extend and generalize this formulation to an iterative algorithm called additive point-source localization (APSL) for sparse parametric image reconstruction. A set of simulated source search scenarios using a single non-directional detector are considered, finding improved image accuracy and computational efficiency with APSL over traditional grid-based methods.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

Control of multi-agent systems: Results, open problems, and applications

The purpose of this review article is to present some recent results on the modeling and control of large systems of agents. We focus on particular applications where the agents are capable of independent actions instead of simply reacting to external forces. In the literature, such agents were referred to as autonomous, intelligent, self-propelled, greedy, and others. The main applications we have in mind are social systems (as opinion dynamics), pedestrians’ movements (also called crowd dynamics), animal groups, and vehicular traffic. We note that the last three examples include physical constraints; however, the agents are able to inject energy into the system, thus preventing the typical conservation of momentum and energy. In addition, the control problems posed by such systems are new and require innovative methods. We illustrate some ideas developed recently, including the use of sparse controls, limiting the total variation of controls, and defining new control problems for measures. After reviewing various approaches, we discuss some future research directions of potential interest. The latter encompasses both new types of equations and new types of limiting procedures to connect several scales at which a system can be represented. We conclude by illustrating a recent real-life experiment using autonomous vehicles on an open highway to smooth traffic waves. This opens the door to a new era of interventions to control real-time multi-agent systems and to increase the societal impact of such interventions guided by control research.

97 MATHEMATICS AND COMPUTING↗

Source scaling comparison and validation in Central Italy: data intensive direct S waves versus the sparse data coda envelope methodology

SUMMARY Robustness of source parameter estimates is a fundamental issue in understanding the relationships between small and large events; however, it is difficult to assess how much of the variability of the source parameters can be attributed to the physical source characteristics or to the uncertainties of the methods and data used to estimate the values. In this study, we apply the coda method by Mayeda et al. using the coda calibration tool (CCT), a freely available Java-based code (https://github.com/LLNL/coda-calibration-tool) to obtain a regional calibration for Central Italy for estimating stable source parameters. We demonstrate the power of the coda technique in this region and show that it provides the same robustness in source parameter estimation as a data-driven methodology [generalized inversion technique (GIT)], but with much fewer calibration events and stations. The Central Italy region is ideal for both GIT and coda approaches as it is characterized by high-quality data, including recent well-recorded seismic sequences such as L'Aquila (2009) and Amatrice–Norcia–Visso (2016–2017). This allows us to apply data-driven methods such as GIT and coda-based methods that require few, but high-quality data. The data set for GIT analysis includes ∼5000 earthquakes and more than 600 stations, while for coda analysis we used a small subset of 39 events spanning 3.5 < Mw < 6.33 and 14 well-distributed broad-band stations. For the common calibration events, as well as an additional 247 events (∼1.7 < Mw < ∼5.0) not used in either calibration, we find excellent agreement between GIT-derived and CCT-derived source spectra. This confirms the ability of the coda approach to obtain stable source parameters even with few calibration events and stations. Even reducing the coda calibration data set by 75 per cent, we found no appreciable degradation in performance. This validation of the coda calibration approach over a broad range of event size demonstrates that this procedure, once extended to other regions, represents a powerful tool for future routine applications to homogeneously evaluate robust source parameters on a national scale. Furthermore, the coda calibration procedure can homogenize the Mw estimates for small and large events without the necessity of introducing any conversion scale between narrow-band measures such as local magnitude (ML) and Mw, which has been shown to introduce significant bias.

Morasca, Paola (ORCID:0000000265254867)↗

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↗

WE-G-BRF-04: Robust Real-Time Volumetric Imaging Based On One Single Projection

Purpose: Real-time volumetric imaging is highly desirable to provide instantaneous image guidance for lung radiation therapy. This study proposes a scheme to achieve this goal using one single projection by utilizing sparse learning and a principal component analysis (PCA) based lung motion model. Methods: A patient-specific PCA-based lung motion model is first constructed by analyzing deformable vector fields (DVFs) between a reference image and 4DCT images at each phase. At the training stage, we “learn” the relationship between the DVFs and the projection using sparse learning. Specifically, we first partition the projections into patches, and then apply sparse learning to automatically identify patches that best correlate with the principal components of the DVFs. Once the relationship is established, at the application stage, we first employ a patchbased intensity correction method to overcome the problem of different intensity scale between the calculated projection in the training stage and the measured projection in the application stage. The corrected projection image is then fed to the trained model to derive a DVF, which is applied to the reference image, yielding a volumetric image corresponding to the projection. We have validated our method through a NCAT phantom simulation case and one experiment case. Results: Sparse learning can automatically select those patches containing motion information, such as those around diaphragm. For the simulation case, over 98% of the lung region pass the generalized gamma test (10HU/1mm), indicating combined accuracy in both intensity and spatial domain. For the experimental case, the average tumor localization errors projected to the imager are 0.68 mm and 0.4 mm on the axial and tangential direction, respectively. Conclusion: The proposed method is capable of accurately generating a volumetric image using one single projection. It will potentially offer real-time volumetric image guidance to facilitate lung radiotherapy. This study is supported in part by NIH (1R01CA154747-01), The Core Technology Research in Strategic Emerging Industry, Guangdong, China(2011A081402003)

60 APPLIED LIFE SCIENCES↗

Acoustic- and elastic-waveform inversion with total generalized p-variation regularization

Geophysical models usually contain both sharp interfaces and smooth variations, and it is difficult to accurately account for both of these two types of medium parameter variations using conventional full-waveform inversion methods. We develop a novel full-waveform inversion method for acoustic and elastic waves using a total generalized p-variation regularization scheme to address these challenging problems. We decompose the full-waveform inversion into two subproblems and solve these two minimization subproblems using an alternating-direction minimization strategy. One significant advantage of the total generalized p-variation regularization scheme is that it can simultaneously reconstruct sharp interfaces and smooth background variations of geophysical parameters. Such capability can also effectively suppress the noises in source-encoded inversion and sparse-data inversion, or inversion of noisy data. We demonstrate the advantages of our full-waveform inversion method using a checkerboard model, a modified elastic SEG/EAGE overthrust model, and a land field seismic data set. Our conclusions of synthetic and field seismic data demonstrate that our method reconstructs both smooth background variations and sharp interfaces of subsurface geophysical properties accurately, and provides a useful tool for accurate and reliable inversion of field seismic data.

58 GEOSCIENCES↗

Recursive Factorization of the Inverse Overlap Matrix in Linear Scaling Quantum Molecular Dynamics Simulations

We present a reduced complexity algorithm to compute the inverse overlap factors required to solve the generalized eigenvalue problem in a quantum-based molecular dynamics (MD) simulation. Our method is based on the recursive iterative re nement of an initial guess Z of the inverse overlap matrix S. The initial guess of Z is obtained beforehand either by using an approximate divide and conquer technique or dynamically, propagated within an extended Lagrangian dynamics from previous MD time steps. With this formulation, we achieve long-term stability and energy conservation even under incomplete approximate iterative re nement of Z. Linear scaling performance is obtained using numerically thresholded sparse matrix algebra based on the ELLPACK-R sparse matrix data format, which also enables e cient shared memory parallelization. As we show in this article using selfconsistent density functional based tight-binding MD, our approach is faster than conventional methods based on the direct diagonalization of the overlap matrix S for systems as small as a few hundred atoms, substantially accelerating quantum-based simulations even for molecular structures of intermediate size. For a 4,158 atom water-solvated polyalanine system we nd an average speedup factor of 122 for the computation of Z in each MD step.

36 MATERIALS SCIENCE↗

A data-driven framework for sparsity-enhanced surrogates with arbitrary mutually dependent randomness

The challenge of quantifying uncertainty propagation in real-world systems is rooted in the high-dimensionality of the stochastic input and the frequent lack of explicit knowledge of its probability distribution. Traditional approaches show limitations for such problems, especially when the size of the training data is limited. To address these diculties, we have developed a general framework of constructing surrogate models on spaces of stochastic input with arbitrary probability measure irrespective of the mutual dependencies between individual components of the random inputs and the analytical form. The present Data-driven Sparsity-enhancing Rotation for Arbitrary Randomness (DSRAR) framework includes a data-driven construction of multivariate polynomial basis for arbitrary mutually dependent probability measure and a sparsity enhancement rotation procedure. This sparsity-enhancing rotation method was initially proposed in our previous work [1] for Gaussian density distributions, which may not be feasible for non-Gaussian distributions due to the loss of orthogonality after the rotation. To remedy such diculties, we developed a new data-driven approach to construct orthonormal polynomials for polynomials for arbitrary mutually dependent (amdP) randomness, ensuring the constructed basis maintains the orthogonality/near-orthogonality with respect to the density of the rotated random vector, where directly applying the regular polynomial chaos including arbitrary polynomial chaos (aPC) [2] shows limitations due to the assumption of the mutual independence between the components of the random inputs. The developed DSRAR framework leads to accurate recovery, with only limited training data, of a sparse representation of the target functions. The eectiveness of our method is demonstrated in challenging problems such as PDEs and realistic molecular systems within high-dimensional conformational space (O(10)) where the underlying density is implicitly represented by a large collection of sample data, as well as systems with explicitly given non-Gaussian probabilistic measures.

Lei, Huan↗

Combined Force-Frequency Sampling for Simulation of Systems Having Rugged Free Energy Landscapes.

An adaptive, machine learning-based sampling method is presented for simulation of systems having rugged, multidimensional free energy landscapes. The method's main strength resides in its ability to learn both from the frequency of visits to distinct states and the generalized force estimates that arise in a system as it evolves in phase space. This is accomplished by introducing a self-integrating artificial neural network, which generates an estimate of the free energy directly from its derivatives. The usefulness of the proposed combined approach is examined in the context of two concrete examples, namely, an alanine dipeptide molecule in water and a polymer diffusing through a narrow pore. This new method is found to be robust, faster, and more accurate than approaches that rely only on frequency-based or generalized force-based estimations. After combining the proposed approach with overfill protection and support for sparse data storage and training, the method is shown to be more effective than comparable, previously available techniques and capable of scaling efficiently to larger numbers of collective variables.

Sevgen, Emre↗

Compressed-sensing-based content-driven hierarchical reconstruction: Theory and application to C-arm cone-beam tomography

Purpose: This paper addresses the reconstruction of x-ray cone-beam computed tomography (CBCT) for interventional C-arm systems. Subsampling of CBCT is a significant issue with C-arms due to their slow rotation and to the low frame rate of their flat panel x-ray detectors. The aim of this work is to propose a novel method able to handle the subsampling artifacts generally observed with analytical reconstruction, through a content-driven hierarchical reconstruction based on compressed sensing. Methods: The central idea is to proceed with a hierarchical method where the most salient features (high intensities or gradients) are reconstructed first to reduce the artifacts these features induce. These artifacts are addressed first because their presence contaminates less salient features. Several hierarchical schemes aiming at streak artifacts reduction are introduced for C-arm CBCT: the empirical orthogonal matching pursuit approach with the ℓ{sub 0} pseudonorm for reconstructing sparse vessels; a convex variant using homotopy with the ℓ{sub 1}-norm constraint of compressed sensing, for reconstructing sparse vessels over a nonsparse background; homotopy with total variation (TV); and a novel empirical extension to nonlinear diffusion (NLD). Such principles are implemented with penalized iterative filtered backprojection algorithms. For soft-tissue imaging, the authors compare the use of TV and NLD filters as sparsity constraints, both optimized with the alternating direction method of multipliers, using a threshold for TV and a nonlinear weighting for NLD. Results: The authors show on simulated data that their approach provides fast convergence to good approximations of the solution of the TV-constrained minimization problem introduced by the compressed sensing theory. Using C-arm CBCT clinical data, the authors show that both TV and NLD can deliver improved image quality by reducing streaks. Conclusions: A flexible compressed-sensing-based algorithmic approach is proposed that is able to accommodate for a wide range of constraints. It is successfully applied to C-arm CBCT images that may not be so well approximated by piecewise constant functions.

60 APPLIED LIFE SCIENCES↗

Quantifying spatial and vertical variations in soil C:N relationships in permafrost-affected landscapes

Permafrost regions are experiencing rapid changes that affect carbon (C) and nitrogen (N) cycles, with implications for vegetation dynamics and gas exchanges with the atmosphere. Soil C:N ratio is a key indicator of organic matter quality, yet spatial estimates of N stocks and C:N ratios lag behind those for C. We used quantile regression forests to compare direct and indirect digital soil mapping approaches for predicting soil C:N ratios at 0–30, 30–60, and 60–100 cm depths across a latitudinal transect in Alaska. The indirect approach – deriving C:N from separately predicted C and N stocks – outperformed direct mapping for the surface layer (0–30 cm), while direct mapping was marginally better at greater depths. However, prediction accuracy decreased with depth for both methods. Temperature and topography were the most important predictors. Both approaches overestimated low and underestimated high C:N ratios, with direct mapping showing greater bias. Our results underscore the challenges of modeling C:N ratios in heterogeneous, data-sparse permafrost soils, but also suggest that indirect mapping holds promise if supported by more extensive datasets.

54 ENVIRONMENTAL SCIENCES↗

Modeling Alzheimer’s Disease Progression with Fused Laplacian Sparse Group Lasso

Alzheimer’s disease (AD), the most common type of dementia, not only imposes a huge financial burden on the health care system, but also a psychological and emotional burden on patients and their families. There is furthermore an urgent need to infer trajectories of cognitive performance over time and identify biomarkers predictive of the progression. Here, we introduce the multi-task learning with fused Laplacian sparse group lasso model, which can identify biomarkers closely related to cognitive measures due to its sparsity-inducing property, and model the disease progression with a general weighted (undirected) dependency graphs among the tasks. An efficient alternative directions method of multipliers based optimization algorithm is derived to solve the proposed non-smooth objective formulation. The effectiveness of the presented model is demonstrated by its superior prediction performance over multiple state-of-the-art methods and accurate identification of compact sets of cognition-relevant imaging biomarkers that are consistent with prior medical studies.

59 BASIC BIOLOGICAL SCIENCES↗

Hierarchy-Direction Selective Approach for Locally Adaptive Sparse Grids

We consider the problem of multidimensional adaptive hierarchical interpolation. We use sparse grids points and functions that are induced from a one dimensional hierarchical rule via tensor products. The classical locally adaptive sparse grid algorithm uses an isotropic refinement from the coarser to the denser levels of the hierarchy. However, the multidimensional hierarchy provides a more complex structure that allows for various anisotropic and hierarchy selective refinement techniques. We consider the more advanced refinement techniques and apply them to a number of simple test functions chosen to demonstrate the various advantages and disadvantages of each method. While there is no refinement scheme that is optimal for all functions, the fully adaptive family-direction-selective technique is usually more stable and requires fewer samples.

Stoyanov, Miroslav K↗

Beyond union of subspaces: Subspace pursuit on Grassmann manifold for data representation

Discovering the underlying structure of a high-dimensional signal or big data has always been a challenging topic, and has become harder to tackle especially when the observations are exposed to arbitrary sparse perturbations. Here in this paper, built on the model of a union of subspaces (UoS) with sparse outliers and inspired by a basis pursuit strategy, we exploit the fundamental structure of a Grassmann manifold, and propose a new technique of pursuing the subspaces systematically by solving a non-convex optimization problem using the alternating direction method of multipliers. This problem as noted is further complicated by non-convex constraints on the Grassmann manifold, as well as the bilinearity in the penalty caused by the subspace bases and coefficients. Nevertheless, numerical experiments verify that the proposed algorithm, which provides elegant solutions to the sub-problems in each step, is able to de-couple the subspaces and pursue each of them under time-efficient parallel computation.

97 MATHEMATICS AND COMPUTING↗

Subcell limiting strategies for discontinuous Galerkin spectral element methods

Here, we present a general family of subcell limiting strategies to construct robust high-order accurate nodal discontinuous Galerkin (DG) schemes. The main strategy is to construct compatible low order finite volume (FV) type discretizations that allow for convex blending with the high-order variant with the goal of guaranteeing additional properties, such as bounds on physical quantities and/or guaranteed entropy dissipation. For an implementation of this main strategy, four main ingredients are identified that may be combined in a flexible manner: (i) a nodal high-order DG method on Legendre–Gauss–Lobatto nodes, (ii) a compatible robust subcell FV scheme, (iii) a convex combination strategy for the two schemes, which can be element-wise or subcell-wise, and (iv) a strategy to compute the convex blending factors, which can be either based on heuristic troubled-cell indicators, or using ideas from flux-corrected transport methods. By carefully designing the metric terms of the subcell FV method, the resulting methods can be used on unstructured curvilinear meshes, are locally conservative, can handle strong shocks efficiently while directly guaranteeing physical bounds on quantities such as density, pressure or entropy. We further show that it is possible to choose the four ingredients to recover existing methods such as a provably entropy dissipative subcell shock-capturing approach or a sparse invariant domain preserving approach. We test the versatility of the presented strategies and mix and match the four ingredients to solve challenging simulation setups, such as the KPP problem (a hyperbolic conservation law with non-convex flux function), turbulent and hypersonic Euler simulations, and MHD problems featuring shocks and turbulence.

97 MATHEMATICS AND COMPUTING↗

Using Ambient Noise Seismic Interferometry and Local and Teleseismic Earthquakes to Determine Crustal Thickness and Moho Structure of the Northwestern Gulf of Mexico Margin

Abstract The northwestern part of the Gulf of Mexico has undergone two episodes of continental rifting and collision and produced structural artifacts that are now buried under many kilometers of sediments, complicating investigations of the region. The deep sedimentary package precludes outcrops and points to a need for the application of seismic techniques, but low rates of seismicity in the region and sparse seismic monitoring limit the utility of traditional seismic methods. We therefore use diverse data to perform two‐dimensional seismic tomography across the dry land portion of the margin. Data are gleaned from teleseismic and regional earthquakes, postcritical SsPmp arrivals, and direct P wave energy identified with seismic interferometry that were recorded by a broadband, three‐component array and partially overlapping short‐period, vertical‐component array. The Pn and postcritical SsPmp phase help constrain the Moho discontinuity, which a previous receiver function study suggested was absent beneath the seaward portion of this transect. A high‐velocity body is observed in the crust at the same location as the Houston Magnetic Anomaly, possibly marking rocks from the Alleghenian continental assembly. The crust thins from NW to SE, indicating that extension occurred mostly to the south of the Ouachita orogeny. Our model indicates that the margin's sediment package reaches a maximum thickness of ~15 km at the coast and becomes unresolvably thin near the Llano Uplift.

58 GEOSCIENCES↗