Search NASA⌕ Search

SEARCH · Search NASA

Results for “Numerical 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 73 records · Page 4

Petascale Computing Enabling Technologies Project Final Report

The Petascale Computing Enabling Technologies (PCET) project addressed challenges arising from current trends in computer architecture that will lead to large-scale systems with many more nodes, each of which uses multicore chips. These factors will soon lead to systems that have over one million processors. Also, the use of multicore chips will lead to less memory and less memory bandwidth per core. We need fundamentally new algorithmic approaches to cope with these memory constraints and the huge number of processors. Further, correct, efficient code development is difficult even with the number of processors in current systems; more processors will only make it harder. The goal of PCET was to overcome these challenges by developing the computer science and mathematical underpinnings needed to realize the full potential of our future large-scale systems. Our research results will significantly increase the scientific output obtained from LLNL large-scale computing resources by improving application scientist productivity and system utilization. Our successes include scalable mathematical algorithms that adapt to these emerging architecture trends and through code correctness and performance methodologies that automate critical aspects of application development as well as the foundations for application-level fault tolerance techniques. PCET's scope encompassed several research thrusts in computer science and mathematics: code correctness and performance methodologies, scalable mathematics algorithms appropriate for multicore systems, and application-level fault tolerance techniques. Due to funding limitations, we focused primarily on the first three thrusts although our work also lays the foundation for the needed advances in fault tolerance. In the area of scalable mathematics algorithms, our preliminary work established that OpenMP performance of the AMG linear solver benchmark and important individual kernels on Atlas did not match the predictions of our simple initial model. Our investigations demonstrated that a poor default memory allocation mechanism degraded performance. We developed a prototype NUMA library to provide generic mechanisms to overcome these issues, resulting in significantly improved OpenMP performance. After additional testing, we will make this library available to all users, providing a simple means to improve threading on LLNL's production Linux platforms. We also made progress on developing new scalable algorithms that target multicore nodes. We designed and implemented a new AMG interpolation operator with improved convergence properties for very low complexity coarsening schemes. This implementation will also soon be available to LLNL's application teams as part of the hypre library. We presented results for both topics in an invited plenary talk entitled 'Efficient Sparse Linear Solvers for Multi-Core Architectures' at the 2009 HPCMP Institutes Annual Meeting/CREATE Annual All-Hands Meeting. The interpolation work was summarized in a talk entitled 'Improving Interpolation for Aggressive Coarsening' at the 14th Copper Mountain Conference on Multigrid Methods and in a research paper that will appear in Numerical Linear Algebra with Applications. In the area of code correctness, we significantly extended our behavior equivalence class identification mechanism. Specifically, we not only demonstrated it works well at very large scales but we also added the ability to classify MPI tasks not only by function call traces, but also by specific call sites (source code line numbers) being executed by tasks. More importantly, we developed a new technique to determine relative logical execution progress of tasks in the equivalence classes by combining static analysis with our original dynamic approach. We applied this technique to a correctness issue that arose at 4096 tasks during the development of the new AMG interpolation operator discussed above. This scale isat the limit of effectiveness of production tools, but our technique quickly located the erroneous source code, demonstrating the power of understanding relationships between behavioral equivalence classes. This work is the subject of a paper recently accepted to SC09, as well as a presentation entitled 'Providing Order to Extreme Scale Debugging Chaos' given at the ParaDyn Week annual conference in College Park, MD. In addition to this theoretical extension, we have made significant progress in developing a front end for this tool set, and the front-end is now available on several of LLNL's largescale computing resources. In addition, we explored mechanisms to identify exact locations of erroneous MPI usage in application source code. In this work, we developed a new model that led to a highly efficient algorithm for detecting deadlock during dynamic software testing. This work was the subject of a well-received paper at ICS 2009 [4].

99 GENERAL AND MISCELLANEOUS↗

Lecture Notes on Multigrid Methods

The Lecture Notes are primarily based on a sequence of lectures given by the author while been a Fulbright scholar at 'St. Kliment Ohridski' University of Sofia, Sofia, Bulgaria during the winter semester of 2009-2010 academic year. The notes are somewhat expanded version of the actual one semester class he taught there. The material covered is slightly modified and adapted version of similar topics covered in the author's monograph 'Multilevel Block-Factorization Preconditioners' published in 2008 by Springer. The author tried to keep the notes as self-contained as possible. That is why the lecture notes begin with some basic introductory matrix-vector linear algebra, numerical PDEs (finite element) facts emphasizing the relations between functions in finite dimensional spaces and their coefficient vectors and respective norms. Then, some additional facts on the implementation of finite elements based on relation tables using the popular compressed sparse row (CSR) format are given. Also, typical condition number estimates of stiffness and mass matrices, the global matrix assembly from local element matrices are given as well. Finally, some basic introductory facts about stationary iterative methods, such as Gauss-Seidel and its symmetrized version are presented. The introductory material ends up with the smoothing property of the classical iterative methods and the main definition of two-grid iterative methods. From here on, the second part of the notes begins which deals with the various aspects of the principal TG and the numerous versions of the MG cycles. At the end, in part III, we briefly introduce algebraic versions of MG referred to as AMG, focusing on classes of AMG specialized for finite element matrices.

99 GENERAL AND MISCELLANEOUS↗

Research in Computational Aeroscience Applications Implemented on Advanced Parallel Computing Systems

Improving the numerical linear algebra routines for use in new Navier-Stokes codes, specifically Tim Barth's unstructured grid code, with spin-offs to TRANAIR is reported. A fast distance calculation routine for Navier-Stokes codes using the new one-equation turbulence models is written. The primary focus of this work was devoted to improving matrix-iterative methods. New algorithms have been developed which activate the full potential of classical Cray-class computers as well as distributed-memory parallel computers.

Wigton, Larry↗

A Shift Selection Strategy for Parallel Shift-Invert Spectrum Slicing in Symmetric Self-Consistent Eigenvalue Computation

The central importance of large scale eigenvalue problems in scientific computation necessitates the development massively parallel algorithms for their solution. Recent advances in dense numerical linear algebra have enabled the routine treatment of eigenvalue problems with dimensions on the order of hundreds of thousands on the world's largest supercomputers. In cases where dense treatments are not feasible, Krylov subspace methods offer an attractive alternative due to the fact that they do not require storage of the problem matrices. However, demonstration of scalability of either of these classes of eigenvalue algorithms on computing architectures capable of expressing excessive parallelism is non-trivial due to communication requirements and serial bottlenecks, respectively. In this work, we introduce the SISLICE method: a parallel shift-invert algorithm for the solution of the symmetric self-consistent field (SCF) eigenvalue problem. The SISLICE method drastically reduces the communication requirement of current parallel shift-invert eigenvalue algorithms through various shift selection and migration techniques based on density of states estimation and k-means clustering, respectively. This work demonstrates the robustness and parallel performance of the SISLICE method on a representative set of SCF eigenvalue problems and outlines research directions which will be explored in future work.

97 MATHEMATICS AND COMPUTING↗

Leverage Score Sampling for Parametric PDEs (Final Technical Report)

This final technical report summarizes the accomplishments of work performed under DOE Office of Science Award DE-SC0022266, which is titled “Leverage Score Sampling for Parametric PDEs”. The goal of the project was to extend methods from Randomized Numerical Linear Algebra (RandNLA) to tackle central computational challenges in model order reduction and uncertainty quantification (UQ) for parametric partial differential equations (PDEs). In particular, we sought to use importance sampling methods originally developed for RandNLA to develop sample efficient active learning algorithms for approximating high-dimensional scalar functions, e.g. by polynomials, Gaussian process models, and simple neural networks. Such methods can be immediately applied to developing surrogate models or to approximating quantity of interest (QoI) surfaces. In the context of PDEs, each sample used for learning equates to the solution of the differential equation for a particular set of parameters, so sample efficiency translates to improved computational efficiency for a variety of downstream tasks.

97 MATHEMATICS AND COMPUTING↗

Hydrologic Model Analyses for Decision Support at the Los Alamos National Laboratory Site - 18363

Modeling hydrologic flow and transport in the subsurface presents a number of challenges including large datasets that contain limited information about the properties of the subsurface and models with a large number of parameters characterizing the properties of the subsurface and the ambient hydrologic conditions (e.g., groundwater recharge). This, in turn, leads to substantial uncertainty in predictions about quantities of interest (e.g., the concentration of a contaminant at points of compliance). We present a number of methods and tools that have recently been developed to address these problems. The model calibration tools are capable of assimilating large datasets (for example, on the order of 1,000,000 model calibration targets) into numerical models, calibrating models with a large number of model parameters (on the order of 1,000,000), or both. These tools leverage recently developed methods in numerical linear algebra such as matrix-free methods and randomized matrix sketching. The uncertainty quantification tools are highly-parallel and enable us to robustly quantify the uncertainties in model parameters (and therefore uncertainty in quantities of interest). Having these capabilities in model analysis tools enables more informed decision making related to remediation of groundwater contaminants. The model analyses that we present are related to the Los Alamos National Laboratory (LANL) chromium site. The analyses are performed by MADS (Model Analysis and Decision Support; http://mads.lanl.gov). (authors)

12 MANAGEMENT OF RADIOACTIVE AND NON-RADIOACTIVE W↗

MAGMA: Enabling exascale performance with accelerated BLAS and LAPACK for diverse GPU architectures

MAGMA (Matrix Algebra for GPU and Multicore Architectures) is a pivotal open-source library in the landscape of GPU-enabled dense and sparse linear algebra computations. With a repertoire of approximately 750 numerical routines across four precisions, MAGMA is deeply ingrained in the DOE software stack, playing a crucial role in high-performance computing. Notable projects such as ExaConstit, HiOP, MARBL, and STRUMPACK, among others, directly harness the capabilities of MAGMA. In addition, the MAGMA development team has been acknowledged multiple times for contributing to the vendors’ numerical software stacks. Looking back over the time of the Exascale Computing Project (ECP), we highlight how MAGMA has adapted to recent changes in modern HPC systems, especially the growing gap between CPU and GPU compute capabilities, as well as the introduction of low precision arithmetic in modern GPUs. We also describe MAGMA’s direct impact on several ECP projects. Maintaining portable performance across NVIDIA and AMD GPUs, and with current efforts toward supporting Intel GPUs, MAGMA ensures its adaptability and relevance in the ever-evolving landscape of GPU architectures.

97 MATHEMATICS AND COMPUTING↗

Numerical stability in problems of linear algebra.

Mathematical problems are introduced as mappings from the space of input data to that of the desired output information. Then a numerical process is defined as a prescribed recurrence of elementary operations creating the mapping of the underlying mathematical problem. The ratio of the error committed by executing the operations of the numerical process (the roundoff errors) to the error introduced by perturbations of the input data (initial error) gives rise to the concept of lambda-stability. As examples, several processes are analyzed from this point of view, including, especially, old and new processes for solving systems of linear algebraic equations with tridiagonal matrices. In particular, it is shown how such a priori information can be utilized as, for instance, a knowledge of the row sums of the matrix. Information of this type is frequently available where the system arises in connection with the numerical solution of differential equations.

Babuska, I.↗

Gauge-invariant perturbation expansion in powers of electric charge for the density-of-states of a network model for charged-particle motion in a uniform background magnetic flux density

An explicitly gauge-invariant expansion in powers of e/$\hbar$ times the magnetic flux density is formally obtained for the density of states [as characterized by the trace of the resolvent $\hat{G}$ = (ω-$\hat{ℎ}$)-1] of a charged particle moving on a Hermitian quantum network that is embedded in a Euclidean background that supports a uniform magnetic flux density. The explicit expressions, given here up to third order in the flux density, are also valid for the “local trace” (the trace of $\hat{P}_i\hat{G}$ , where $\hat{P}_i$ is the projector on a network node) and do not appear to have been previously given.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Hybrid programming-model strategies for GPU offloading of electronic structure calculation kernels

To address the challenge of performance portability and facilitate the implementation of electronic structure solvers, we developed the basic matrix library (BML) and Parallel, Rapid O(N), and Graph-based Recursive Electronic Structure Solver (PROGRESS) library. The BML implements linear algebra operations necessary for electronic structure kernels using a unified user interface for various matrix formats (dense and sparse) and architectures (CPUs and GPUs). Focusing on density functional theory and tight-binding models, PROGRESS implements several solvers for computing the single-particle density matrix and relies on BML. In this paper, we describe the general strategies used for these implementations on various computer architectures, using OpenMP target functionalities on GPUs, in conjunction with third-party libraries to handle performance critical numerical kernels. In this study, we demonstrate the portability of this approach and its performance in benchmark problems.

36 MATERIALS SCIENCE↗

Exploiting Multiple Levels of Parallelism in Sparse Matrix-Matrix Multiplication

Sparse matrix-matrix multiplication (or SpGEMM) is a key primitive for many high-performance graph algorithms as well as for some linear solvers, such as algebraic multigrid. The scaling of existing parallel implementations of SpGEMM is heavily bound by communication. Even though 3D (or 2.5D) algorithms have been proposed and theoretically analyzed in the flat MPI model on Erdös-Rényi matrices, those algorithms had not been implemented in practice and their complexities had not been analyzed for the general case. In this work, we present the first implementation of the 3D SpGEMM formulation that exploits multiple (intranode and internode) levels of parallelism, achieving significant speedups over the state-of-the-art publicly available codes at all levels of concurrencies. We extensively evaluate our implementation and identify bottlenecks that should be subject to further research.

2.5D algorithms↗

Computing rank‐revealing factorizations of matrices stored out‐of‐core

This paper describes efficient algorithms for computing rank-revealing factorizations of matrices that are too large to fit in main memory (RAM), and must instead be stored on slow external memory devices such as disks (out-of-core or out-of-memory). Traditional algorithms for computing rank-revealing factorizations (such as the column pivoted QR factorization and the singular value decomposition) are very communication intensive as they require many vector-vector and matrix-vector operations, which become prohibitively expensive when data is not in RAM. Randomization allows to reformulate new methods so that large contiguous blocks of the matrix are processed in bulk. The paper describes two distinct methods. The first is a blocked version of column pivoted Householder QR, organized as a “left-looking” method to minimize the number of the expensive write operations. The second method results employs a UTV factorization. It is organized as an algorithm-by-blocks to overlap computations and I/O operations. As it incorporates power iterations, it is much better at revealing the numerical rank. Numerical experiments on several computers demonstrate that the new algorithms are almost as fast when processing data stored on slow memory devices as traditional algorithms are for data stored in RAM.

97 MATHEMATICS AND COMPUTING↗

Hierarchical Model Reduction Driven by Machine Learning for Parametric Advection-Diffusion-Reaction Problems in the Presence of Noisy Data

Abstract We propose a new approach to generate a reliable reduced model for a parametric elliptic problem, in the presence of noisy data. The reference model reduction procedure is the directional HiPOD method, which combines Hierarchical Model reduction with a standard Proper Orthogonal Decomposition, according to an offline/online paradigm. In this paper we show that directional HiPOD looses in terms of accuracy when problem data are affected by noise. This is due to the interpolation driving the online phase, since it replicates, by definition, the noise trend. To overcome this limit, we replace interpolation with Machine Learning fitting models which better discriminate relevant physical features in the data from irrelevant unstructured noise. The numerical assessment, although preliminary, confirms the potentialities of the new approach.

97 MATHEMATICS AND COMPUTING↗

ROOT: A C++ framework for petabyte data storage, statistical analysis and visualization

ROOT is an object-oriented C++ framework conceived in the high-energy physics (HEP) community, designed for storing and analyzing petabytes of data in an efficient way. Any instance of a C++ class can be stored into a ROOT file in a machine-independent compressed binary format. In ROOT the TTree object container is optimized for statistical data analysis over very large data sets by using vertical data storage techniques. These containers can span a large number of files on local disks, the web or a number of different shared file systems. In order to analyze this data, the user can chose out of a wide set of mathematical and statistical functions, including linear algebra classes, numerical algorithms such as integration and minimization, and various methods for performing regression analysis (fitting). In particular, the RooFit package allows the user to perform complex data modeling and fitting while the RooStats library provides abstractions and implementations for advanced statistical tools. Multivariate classification methods based on machine learning techniques are available via the TMVA package. A central piece in these analysis tools are the histogram classes which provide binning of one- and multi-dimensional data. Results can be saved in high-quality graphical formats like Postscript and PDF or in bitmap formats like JPG or GIF. The result can also be stored into ROOT macros that allow a full recreation and rework of the graphics. Users typically create their analysis macros step by step, making use of the interactive C++ interpreter CINT, while running over small data samples. Once the development is finished, they can run these macros at full compiled speed over large data sets, using on-the-fly compilation, or by creating a stand-alone batch program. Finally, if processing farms are available, the user can reduce the execution time of intrinsically parallel tasks - e.g. data mining in HEP - by using PROOF, which will take care of optimally distributing the work over the available resources in a transparent way.

99 GENERAL AND MISCELLANEOUS↗

On the effective implementation of a boundary element code on graphics processing units unsing an out-of-core LU algorithm

A collocation boundary element code for solving the three-dimensional Laplace equation, publicly available from \url{http://www.intetec.org}, has been adapted to run on an Nvidia Tesla general purpose graphics processing unit (GPU). Global matrix assembly and LU factorization of the resulting dense matrix were performed on the GPU. Out-of-core techniques were used to solve problems larger than available GPU memory. The code achieved over eight times speedup in matrix assembly and about 56~Gflops/sec in the LU factorization using only 512~Mbytes of GPU memory. Details of the GPU implementation and comparisons with the standard sequential algorithm are included to illustrate the performance of the GPU code.

99 GENERAL AND MISCELLANEOUS↗

A parallel strategy for density functional theory computations on accelerated nodes

Using the Löwdin orthonormalization of tall-skinny matrices as a proxy-app for wavefunction-based Density Functional Theory solvers, we investigate a distributed memory parallel strategy focusing on Graphics Processing Unit (GPU)-accelerated nodes as available on some of the top ranked supercomputers at the present time. Here we present numerical results in the strong limit regime, as it is particularly relevant for First-Principles Molecular Dynamics. We also examine how matrix product-based iterative solvers provide a competitive alternative to dense eigensolvers on GPUs, allowing to push the strong scaling limit of these computations to a larger number of distributed tasks. Our strategy, which relies on replicated Gram matrices and efficient collective communications using the NCCL library, leads to a time-to-solution under 0.5 s for the Löwdin orthonormalization of a tall-skinny matrix of 3000 columns on Summit at Oak Ridge Leadership Facility (OLCF). Given the similarity in computational operations between one iteration of a DFT solver and this proxy-app, this shows the possibility of solving accurately the DFT equations well under a minute for 3000 electronic wave functions, and thus perform First-Principles molecular dynamics of physical systems much larger than traditionally solved on CPU systems.

97 MATHEMATICS AND COMPUTING↗

Communication: Charge-population based dispersion interactions for molecules and materials

We introduce a system-independent method to derive effective atomic C{sub 6} coefficients and polarizabilities in molecules and materials purely from charge population analysis. This enables the use of dispersion-correction schemes in electronic structure calculations without recourse to electron-density partitioning schemes and expands their applicability to semi-empirical methods and tight-binding Hamiltonians. We show that the accuracy of our method is en par with established electron-density partitioning based approaches in describing intermolecular C{sub 6} coefficients as well as dispersion energies of weakly bound molecular dimers, organic crystals, and supramolecular complexes. We showcase the utility of our approach by incorporation of the recently developed many-body dispersion method [Tkatchenko et al., Phys. Rev. Lett. 108, 236402 (2012)] into the semi-empirical density functional tight-binding method and propose the latter as a viable technique to study hybrid organic-inorganic interfaces.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗