Search NASA⌕ Search

SEARCH · Search NASA

Results for “sparse matrix”

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 199 records · Page 11

Real-space solution to the electronic structure problem for nearly a million electrons

We report a Kohn–Sham density functional theory calculation of a system with more than 200 000 atoms and 800 000 electrons using a real-space high-order finite-difference method to investigate the electronic structure of large spherical silicon nanoclusters. Our system of choice was a 20 nm large spherical nanocluster with 202 617 silicon atoms and 13 836 hydrogen atoms used to passivate the dangling surface bonds. To speed up the convergence of the eigenspace, we utilized Chebyshev-filtered subspace iteration, and for sparse matrix–vector multiplications, we used blockwise Hilbert space-filling curves, implemented in the PARSEC code. For this calculation, we also replaced our orthonormalization + Rayleigh–Ritz step with a generalized eigenvalue problem step. We utilized all of the 8192 nodes (458 752 processors) on the Frontera machine at the Texas Advanced Computing Center. We achieved two Chebyshev-filtered subspace iterations, yielding a good approximation of the electronic density of states. Our work pushes the limits on the capabilities of the current electronic structure solvers to nearly 106 electrons and demonstrates the potential of the real-space approach to efficiently parallelize large calculations on modern high-performance computing platforms.

Chemistry↗

MADmap: A MASSIVELY PARALLEL MAXIMUM LIKELIHOOD COSMIC MICROWAVE BACKGROUND MAP-MAKER

MADmap is a software application used to produce maximum likelihood images of the sky from time-ordered data which include correlated noise, such as those gathered by cosmic microwave background (CMB) experiments. It works efficiently on platforms ranging from small workstations to the most massively parallel supercomputers. Map-making is a critical step in the analysis of all CMB data sets, and the maximum likelihood approach is the most accurate and widely applicable algorithm; however, it is a computationally challenging task. This challenge will only increase with the next generation of ground-based, balloon-borne, and satellite CMB polarization experiments. The faintness of the B-mode signal that these experiments seek to measure requires them to gather enormous data sets. MADmap is already being run on up to O(10{sup 11}) time samples, O(10{sup 8}) pixels, and O(10{sup 4}) cores, with ongoing work to scale to the next generation of data sets and supercomputers. We describe MADmap's algorithm based around a preconditioned conjugate gradient solver, fast Fourier transforms, and sparse matrix operations. We highlight MADmap's ability to address problems typically encountered in the analysis of realistic CMB data sets and describe its application to simulations of the Planck and EBEX experiments. The massively parallel and distributed implementation is detailed and scaling complexities are given for the resources required. MADmap is capable of analyzing the largest data sets now being collected on computing resources currently available, and we argue that, given Moore's Law, MADmap will be capable of reducing the most massive projected data sets.

79 ASTRONOMY AND ASTROPHYSICS↗

Algorithm for simulation of quantum many-body dynamics using dynamical coarse-graining

An algorithm for simulation of quantum many-body dynamics having su(2) spectrum-generating algebra is developed. The algorithm is based on the idea of dynamical coarse-graining. The original unitary dynamics of the target observables--the elements of the spectrum-generating algebra--is simulated by a surrogate open-system dynamics, which can be interpreted as weak measurement of the target observables, performed on the evolving system. The open-system state can be represented by a mixture of pure states, localized in the phase space. The localization reduces the scaling of the computational resources with the Hilbert-space dimension n by factor n{sup 3/2}(ln n){sup -1} compared to conventional sparse-matrix methods. The guidelines for the choice of parameters for the simulation are presented and the scaling of the computational resources with the Hilbert-space dimension of the system is estimated. The algorithm is applied to the simulation of the dynamics of systems of 2x10{sup 4} and 2x10{sup 6} cold atoms in a double-well trap, described by the two-site Bose-Hubbard model.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

The plug-based nanovolume Microcapillary Protein Crystallization System (MPCS)

The Microcapillary Protein Crystallization System (MPCS) embodies a new semi-automated plug-based crystallization technology which enables nanolitre-volume screening of crystallization conditions in a plasticware format that allows crystals to be easily removed for traditional cryoprotection and X-ray diffraction data collection. Protein crystals grown in these plastic devices can be directly subjected to in situ X-ray diffraction studies. The MPCS integrates the formulation of crystallization cocktails with the preparation of the crystallization experiments. Within microfluidic Teflon tubing or the microfluidic circuitry of a plastic CrystalCard, {approx}10-20 nl volume droplets are generated, each representing a microbatch-style crystallization experiment with a different chemical composition. The entire protein sample is utilized in crystallization experiments. Sparse-matrix screening and chemical gradient screening can be combined in one comprehensive 'hybrid' crystallization trial. The technology lends itself well to optimization by high-granularity gradient screening using optimization reagents such as precipitation agents, ligands or cryoprotectants.

59 BASIC BIOLOGICAL SCIENCES↗

Detector alignment for X-ray crystallography using Millepede-II

I describe a method for accurately refining the geometrical parameters of segmented X-ray area detectors on the basis of serial crystallography data, using 'Millepede' – an algorithm created for a very similar problem in high-energy physics. The Millepede method for serial crystallography builds on the approach of Brewster et al. [Acta Cryst. (2018), D74, 877–894], in which the detector parameters are refined simultaneously with the parameters for each individual crystal. This accounts for the mutual dependency between the parameters and thereby avoids the bias and slow convergence problems that have afflicted older approaches in which the deviations between observed and calculated Bragg peak positions were taken directly as the updates for the detector panel positions. The Millepede method uses the special structure of the least-squares normal equations to reduce them to a much smaller form that can be solved very quickly, even compared with the sparse matrix methods used previously. This makes it practical to refine the detector geometry frequently and thereby maintain accurate calibration without specialized alignment campaigns. Tilts of detector panels out of the plane can be reliably refined, as can the overall distance of the detector in the beam direction. With a simulated test case, the new method produced panel shifts within 7% of the correct values with only one iteration, and produced almost exactly correct shifts after a second iteration. A simulated out-of-plane panel rotation was correctly determined to within 0.001°. Applied to experimental data from an X-ray free-electron laser, the method increased the indexable fraction of frames from 30% to 91% in a single iteration, and to 96% after two further iterations. Computing the geometry updates on the basis of 2060 crystals took only 0.819 s on desktop computing hardware, including the time taken to read the required data from disk. The scaling was found to be very close to linear for up to 100 980 sets of crystal parameters, which took only 78.2 s to process under the same conditions. The method has been applied as part of a real-time feedback system at a synchrotron radiation beamline, in which an out-of-plane detector tilt of 0.04° was detected and corrected. Possible further applications are also described here.

Millepede-II↗

Crystallization and preliminary X-ray analysis of a phosphopentomutase from Bacillus cereus

Phosphopentomutases (PPMs) interconvert D-ribose 5-phosphate and {alpha}-D-ribose 1-phosphate to link glucose and nucleotide metabolism. PPM from Bacillus cereus was overexpressed in Escherichia coli, purified to homogeneity and crystallized. Bacterial PPMs are predicted to contain a di-metal reaction center, but the catalytically relevant metal has not previously been identified. Sparse-matrix crystallization screening was performed in the presence or absence of 50 mM MnCl{sub 2}. This strategy resulted in the formation of two crystal forms from two chemically distinct conditions. The crystals that formed with 50 mM MnCl{sub 2} were more easily manipulated and diffracted to higher resolution. These results suggest that even if the catalytically relevant metal is not known, the crystallization of putative metalloproteins may still benefit from supplementation of the crystallization screens with potential catalytic metals.

59 BASIC BIOLOGICAL SCIENCES↗

Purification, crystallization and preliminary X-ray diffraction analysis of the carbohydrate-binding region of the Streptococcus gordonii adhesin GspB

The carbohydrate-binding region of the bacterial adhesin GspB from Streptococcus gordonii strain M99 (GspB{sub BR}) was expressed in Escherichia coli and purified using affinity and size-exclusion chromatography. Separate sparse-matrix screening of GspB{sub BR} buffered in either 20 mM Tris pH 7.4 or 20 mM HEPES pH 7.5 resulted in different crystallographic behavior such that different precipitants, salts and additives supported crystallization of GspB{sub BR} in each buffer. While both sets of conditions supported crystal growth in space group P2{sub 1}2{sub 1}2{sub 1}, the crystals had distinct unit-cell parameters of a = 33.3, b = 86.7, c = 117.9 {angstrom} for crystal form 1 and a = 34.6, b = 98.3, c = 99.0 {angstrom} for crystal form 2. Additive screening improved the crystals grown in both conditions such that diffraction extended to beyond 2 {angstrom} resolution. A complete data set has been collected to 1.3 {angstrom} resolution with an overall R{sub merge} value of 0.04 and an R{sub merge} value of 0.33 in the highest resolution shell.

59 BASIC BIOLOGICAL SCIENCES↗

Architecture Independent Integrated Early Performance and Energy Estimation

The end of Dennard’s scaling, coupled to the necessity to keep increasing computational performance in constrained power envelopes, is leading developers towards the need to opti- mize applications not only for performance, but also for energy consumption. In such a scenario, solutions that enable estimating performance and energy consumption of a program as early as possible, even during development and without the necessity to access the final target hardware, can become fundamental tools to reduce the design space, the optimization effort, and provide potential opportunities to automate the optimization process itself. In this position paper, we discuss the design of a performance and energy estimation framework based on a retargetable com- piler. Our proposed approach targets the Intermediate Repre- sentation (IR) of the LLVM compiler. The IR based approach enables, after a model is built, estimation from a host different from the target architecture, even considering dynamic infor- mation. We present the rationale behind such a framework, identify opportunities and components readily available (such as the provided static analysis, quick ways to add instrumentation for dynamic profiling, and the multiple backends), and aspects that still need further research efforts (such as more effective non-linear, or machine learning based models). We also discuss a hand-developed case study, based on a simple sparse matrix vector multiplication with a linear model, to motivate the needs for such a framework.

Estimation, Compilers, Performance Analysis↗

Parallelizing the QUDA Library for Multi-GPU Calculations in Lattice Quantum Chromodynamics

Graphics Processing Units (GPUs) are having a transformational effect on numerical lattice quantum chromodynamics (LQCD) calculations of importance in nuclear and particle physics. The QUDA library provides a package of mixed precision sparse matrix linear solvers for LQCD applications, supporting single GPUs based on NVIDIA's Compute Unified Device Architecture (CUDA). This library, interfaced to the QDP++/Chroma framework for LQCD calculations, is currently in production use on the "9g" cluster at the Jefferson Laboratory, enabling unprecedented price/performance for a range of problems in LQCD. Nevertheless, memory constraints on current GPU devices limit the problem sizes that can be tackled. In this contribution we describe the parallelization of the QUDA library onto multiple GPUs using MPI, including strategies for the overlapping of communication and computation. We report on both weak and strong scaling for up to 32 GPUs interconnected by InfiniBand, on which we sustain in excess of 4 Tflops.

43 PARTICLE ACCELERATORS↗

TU-C-17A-05: Dose Domain Optimization of MLC Leaf Patterns for Highly Complicated 4Ï€ IMRT Plans

Purpose: Highly conformal non-coplanar 4π radiotherapy plans typically require more than 20 intensity-modulated fields to deliver. A novel method to calculate multileaf collimator (MLC) leaf patterns is introduced to maximize delivery efficiency, accuracy and plan quality. Methods: 4 GBM patients, with a prescription dose of 59.4 Gy or 60 Gy, were evaluated using the 4π algorithm using 20 beams. The MLC calculation utilized a least square minimization of the dose distribution, with an anisotropic total variation regularization term to encourage piecewise continuity in the fluence maps. Transforming the fluence to the dose domain required multiplying the fluence with a sparse matrix. Exploiting this property made it feasible to solve the problem using CVX, a MATLAB-based convex modeling framework. The fluence was stratified into even step sizes, and the MLC segments, limited to 300, were calculated. The patients studied were replanned using Eclipse with the same beam angles. Results: Compared to the original 4π plan, the stratified 4π plan increased the maximum/mean dose for, in Gy, by 1.0/0.0 (brainstem), 0.5/0.2 (chiasm), 0.0/0.0 (spinal cord), 1.9/0.3 (L eye), 0.7/0.2 (R eye), 0.4/0.4 (L lens), 0.3/0.3 (R lens), 1.0/0.8 (L Optical Nerve), 0.5/0.3 (R Optical Nerve), 0.3/0.2 (L Cochlea), 0.1/0.1 (R Cochlea), 4.6/0.2 (brain), 2.4/0.1 (brain-PTV), 5.1/0.9 (PTV). Compared to Eclipse, which generated an average of 607 segments, the stratified plan reduced (−) or increased (+) the maximum/mean dose, in Gy, by −10.2/−4.1 (brainstem), −10.5/−8.9 (chiasm), +0.0/−0.1 (spinal cord), −4.9/−3.4 (L eye), −4.1/−2.5 (R eye), −2.8/−2.7 (L lens), −2.1/−1.9 (R lens), −7.6/−6.5 (L Optical Nerve), −8.9/−6.1 (R Optical Nerve), −1.3/−1.9 (L Cochlea), −1.8/−1.8 (R Cochlea), +1.7/−2.1 (brain), +3.2/−2.6 (brain-PTV), +1.8/+0.3 Gy (PTV. The stratified plan was also more homogeneous in the PTV. Conclusion: This novel solver can transform complicated fluence maps into significantly fewer deliverable MLC segments than the commercial system while achieving superior dosimetry. Funding support partially contributed by Varian.

60 APPLIED LIFE SCIENCES↗

Parallel implementation and performance optimization of the configuration-interaction method

The configuration-interaction (CI) method, long a popular approach to describe quantum many-body systems, is cast as a very large sparse matrix eigenpair problem with matrices whose dimension can exceed one billion. Such formulations place high demands on memory capacity and memory bandwidth - - two quantities at a premium today. In this paper, we describe an efficient, scalable implementation, BIGSTICK, which, by factorizing both the basis and the interaction into two levels, can reconstruct the nonzero matrix elements on the fly, reduce the memory requirements by one or two orders of magnitude, and enable researchers to trade reduced resources for increased computational time. We optimize BIGSTICK on two leading HPC platforms - - the Cray XC30 and the IBM Blue Gene/Q. Specifically, we not only develop an empirically-driven load balancing strategy that can evenly distribute the matrix-vector multiplication across 256K threads, we also developed techniques that improve the performance of the Lanczos reorthogonalization. Combined, these optimizations improved performance by 1.3-8× depending on platform and configuration.

97 MATHEMATICS AND COMPUTING↗

Brief Announcement: Communication Optimal Sparse LU Factorization for Planar Matrices

We introduce a new parallel algorithm for solving sparse LU factorization of planar matrices, which commonly arise in the finite element method for 2D PDEs. Existing scalable methods, such as the multifrontal approach with subtree-to-subcube mapping by Gupta et al. [1] and right-looking with 3D mapping by Sao et al. [2] fail to achieve optimal communication costs for these matrices. Our new algorithm combines 3D mapping and subtree-to-subcube mapping to minimize communication costs while allowing trade-offs between extra memory and reduced communication. We demonstrate that our proposed algorithm attains the communication lower bound up to a factor of O(log log n) in the memory-optimal case and up to a factor of O(log P) in the memory-independent case for an n-dimensional planar sparse matrix on P processors.

Sao, Piyush↗

Fast Sparse-Vector Cosine Similarity in Go

This software provides a fast way to perform efficient sparse matrix multiplication followed by top-n multiplication result selection. Functionality for performing matrix multiplication / cosine similarity separately is included in this package as well. This package is a pure Go port of a Python package developed by ING Bank (https://github.com/ing-bank/sparse_dot_topn) which uses Cython to execute the matrix multiplication in C++. Instructions for compiling bindings which can be called from Python are included with this package as well.

Shivers, Ryan [Oak Ridge National Lab. (ORNL), Oak↗

Tacho

SAND2022-7470 O Tacho is a performance portable sparse direct solver for use with various sparse matrix problems which typically arise from finite element methods. The code relies on the Kokkos parallel programming model porting to both CPUs and GPUs. It is also part of the Trilinos library. Sandia National Laboratories is a multimission laboratory managed and operated by National Technology & Engineering Solutions of Sandia, LLC, a wholly owned subsidiary of Honeywell International Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA0003525.

Kim, Kyungjoo↗

BLINK v1

We introduce the Binned Large Interval Network Kernel approach for scoring fragmentation mass spectra similarity which takes advantage of sparse matrix multiplication. This enables BLINK to perform 100 million comparisons while maintaining 98% accuracy in 2.2 seconds making it over 1,000 times faster than the current implementations.

Bowen, Benjamin↗

Development and Benchmarking of a Hybrid PIC Code For Dense Plasmas and Fast Ignition (Final Report)

Radiation processes play an important role in the study of both fast ignition and other inertial confinement schemes, such as plasma jet driven magneto-inertial fusion, both in their effect on energy balance, and in generating diagnostic signals. In the latter case, warm and hot dense matter may be produced by the convergence of a plasma shell formed by the merging of an assembly of high Mach number plasma jets. This innovative approach has the potential advantage of creating matter of high energy densities in voluminous amount compared with high power lasers or particle beams. An important application of this technology is as a plasma liner for the flux compression of magnetized plasma to create ultra-high magnetic fields and burning plasmas. HyperV Technologies Corp. has been developing plasma jet accelerator technology in both coaxial and linear railgun geometries to produce plasma jets of sufficient mass, density, and velocity to create such imploding plasma liners. An enabling tool for the development of this technology is the ability to model the plasma dynamics, not only in the accelerators themselves, but also in the resulting magnetized target plasma and within the merging/interacting plasma jets during transport to the target. Welch pioneered numerical modeling of such plasmas (including for fast ignition) using the LSP simulation code. Lsp is an electromagnetic, parallelized, plasma simulation code under development since 1995. It has a number of innovative features making it uniquely suitable for modeling high energy density plasmas including a hybrid fluid model for electrons that allows electrons in dense plasmas to be modeled with a kinetic or fluid treatment as appropriate. In addition to in-house use at Voss Scientific, several groups carrying out research in Fast Ignition (LLNL, SNL, UCSD, AWE (UK), and Imperial College (UK)) also use LSP. A collaborative team consisting of HyperV Technologies Corp., Voss Scientific LLC, FAR-TECH, Inc., Prism Computational Sciences, Inc. and Advanced Energy Systems Inc. joined efforts to develop new physics and numerical models for LSP in several key areas to enhance the ability of LSP to model high energy density plasmas (HEDP). This final report details those efforts. Areas addressed in this research effort include: adding radiation transport to LSP, first in 2D and then fully 3D, extending the EMHD model to 3D, implementing more advanced radiation and electrode plasma boundary conditions, and installing more efficient implicit numerical algorithms to speed complex 2-D and 3-D computations. The new capabilities allow modeling of the dominant processes in high energy density plasmas, and further assist the development and optimization of plasma jet accelerators, with particular attention to MHD instabilities and plasma/wall interaction (based on physical models for ion drag friction and ablation/erosion of the electrodes). In the first funding cycle we implemented a solver for the radiation diffusion equation. To solve this equation in 2-D, we used finite-differencing and applied the parallelized sparse-matrix solvers in the PETSc library (Argonne National Laboratory) to the resulting system of equations. A database of the necessary coefficients for materials of interest was assembled using the PROPACEOS and ATBASE codes from Prism. The model was benchmarked against Prism's 1-D radiation hydrodynamics code HELIOS, and against experimental data obtained from HyperV's separately funded plasma jet accelerator development program. Work in the second funding cycle focused on extending the radiation diffusion model to full 3-D, continued development of the EMHD model, optimizing the direct-implicit model to speed up calculations, add in multiply ionized atoms, and improved the way boundary conditions are handled in LSP. These new LSP capabilities were then used, along with analytic calculations and Mach2 runs, to investigate plasma jet merging, plasma detachment and transport, restrike and advanced jet accelerator design. In addition, a strong linkage to diagnostic measurements was made by modeling plasma jet experiments on PLX to support benchmarking of the code. A large number of upgrades and improvements advancing hybrid PIC algorithms were implemented in LSP during the second funding cycle. These include development of fully 3D radiation transport algorithms, new boundary conditions for plasma-electrode interactions, and a charge conserving equation of state that permits multiply ionized high-Z ions. The final funding cycle focused on 1) mitigating the effects of a slow-growing grid instability which is most pronounced in plasma jet frame expansion problems using the two-fluid Eulerian remap algorithm, 2) extension of the Eulerian Smoothing Algorithm to allow EOS/Radiation modeling, 3) simulations of collisionless shocks formed by jet merging, 4) simulations of merging jets using high-Z gases, 5) generation of PROPACEOS EOS/Opacity databases, 6) simulations of plasma jet transport experiments, 7) simulations of plasma jet penetration through transverse magnetic fields, and 8) GPU PIC code development. The tools developed during this project are applicable not only to the study of plasma jets, but also to a wide variety of HEDP plasmas of interest to DOE, including plasmas created in short-pulse laser experiments performed to study fast ignition concepts for inertial confinement fusion.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

LDRD Report: Scheduling Irregular Algorithms

This LDRD project was a campus exec fellowship to fund (in part) Donald Nguyen’s PhD research at UT-Austin. His work has focused on parallel programming models, and scheduling irregular algorithms on shared-memory systems using the Galois framework. Galois provides a simple but powerful way for users and applications to automatically obtain good parallel performance using certain supported data containers. The naïve user can write serial code, while advanced users can optimize performance by advanced features, such as specifying the scheduling policy. Galois was used to parallelize two sparse matrix reordering schemes: RCM and Sloan. Such reordering is important in high-performance computing to obtain better data locality and thus reduce run times.

97 MATHEMATICS AND COMPUTING↗

Computing the Properties of Hadrons, Nuclei, and Nuclear Matter from Quantum Chromodynamics, UNC-CH Final Report.

This is the final technical report for the UNC-CH component of a SciDAC3 project. This project served to coordinate the software development effort which the nuclear physics lattice QCD community is developing to ensure that lattice calculations can make optimal use of forthcoming leadership-class and dedicated hardware, including those of the national laboratories, and prepares for the exploitation of future computational resources in the exascale era. The project developed and optimized simulation software for lattice QCD calculations on leadership class computers and on GPUaccelerated heterogeneous architectures. The participating team at multiple instritutions improved and extended software libraries (Chroma, CPS, MILC, QLUA, QPhiX, QDP++, QDP-jit) by providing interfaces for heterogeneous computing environments and through the optimization of gauge field evolution algorithms and sparse matrix inverters. The former includes the development of new multi-time scale integrators and the latter focused on the development of new multi-grid and domain decomposition inverters for several QCD fermion discretization schemes. The sub-project at the University of North Carolina worked towards the development a domain specific language for lattice QCD computations with the express purpose of generating code with uncompromised performance.

97 MATHEMATICS AND COMPUTING↗