Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “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 343 records · Page 19
All sourcesNASA NTRSDOE OSTI
DOE OSTI2016

A Hartree-Fock Application Using UPC++ and the New DArray Library

The Hartree-Fock (HF) method is the fundamental first step for incorporating quantum mechanics into many-electron simulations of atoms and molecules, and it is an important component of computational chemistry toolkits like NWChem. The GTFock code is an HF implementation that, while it does not have all the features in NWChem, represents crucial algorithmic advances that reduce communication and improve load balance by doing an up-front static partitioning of tasks, followed by work stealing whenever necessary. To enable innovations in algorithms and exploit next generation exascale systems, it is crucial to support quantum chemistry codes using expressive and convenient programming models and runtime systems that are also efficient and scalable. Here, this paper presents an HF implementation similar to GTFock using UPC++, a partitioned global address space model that includes flexible communication, asynchronous remote computation, and a powerful multidimensional array library. UPC++ offers runtime features that are useful for HF such as active messages, a rich calculus for array operations, hardware-supported fetch-and-add, and functions for ensuring asynchronous runtime progress. We present a new distributed array abstraction, DArray, that is convenient for the kinds of random-access array updates and linear algebra operations on block-distributed arrays with irregular data ownership. Finally, we analyze the performance of atomic fetch-and-add operations (relevant for load balancing) and runtime attentiveness, then compare various techniques and optimizations for each. Our optimized implementation of HF using UPC++ and the DArrays library shows up to 20% improvement over GTFock with Global Arrays at scales up to 24,000 cores.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2018

A Study of Clustering Techniques and Hierarchical Matrix Formats for Kernel Ridge Regression

We present memory-efficient and scalable algorithms for kernel methods used in machine learning. Using hierarchical matrix approximations for the kernel matrix the memory requirements, the number of floating point operations, and the execution time are drastically reduced compared to standard dense linear algebra routines. We consider both the general H matrix hierarchical format as well as Hierarchically Semi-Separable (HSS) matrices. Furthermore, we investigate the impact of several preprocessing and clustering techniques on the hierarchical matrix compression. Effective clustering of the input leads to a ten-fold increase in efficiency of the compression. The algorithms are implemented using the STRUMPACK solver library. These results confirm that - with correct tuning of the hyperparameters - classification using kernel ridge regression with the compressed matrix does not lose prediction accuracy compared to the exact - not compressed - kernel matrix and that our approach can be extended to O(1M) datasets, for which computation with the full kernel matrix becomes prohibitively expensive. We present numerical experiments in a distributed memory environment up to 1,024 processors of the NERSC's Cori supercomputer using well-known datasets to the machine learning community that range from dimension 8 up to 784.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Co-design for Particle Applications at Exascale

Co-design across the Exascale Computing Project (ECP) has been critical for both enabling science applications and bringing disparate communities together. Developing and porting applications to the various high-performance computing (HPC) architectures on pre-exascale and exascale computers has been quite challenging due to the diversity of hardware features and software stacks. The Co-design Center for Particle Applications (CoPA) has developed and enhanced the Cabana and PROGRESS/BML libraries to facilitate the creation of new particle applications, make existing particle applications exascale capable, and allow teams to explore new capabilities. Particle methods from atomistic, mesoscale, continuum, through cosmological scales have been built with Cabana, along with new possibilities for application coupling. Similarly, the PROGRESS/BML library has enabled quantum particle applications with linear algebra solvers to use advanced hardware. Across these CoPA-developed libraries, the co-design abstraction layer combines performance portability with math library support to facilitate separation of concerns and directly support science runs.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2019

Accelerating DCA++ (Dynamical Cluster Approximation) Scientific Application on the Summit supercomputer

Optimizing scientific applications on today’s accelerator-based high performance computing systems can be challenging, especially when multiple GPUs and CPUs with heterogeneous memories and persistent non-volatile memories are present. An example is Summit, an accelerator-based system at the Oak Ridge Leadership Computing Facility (OLCF) that is rated as the world’s fastest supercomputer to-date. New strategies are thus needed to expose the parallelism in legacy applications, while being amenable to efficient mapping to the underlying architecture.In this paper we discuss our experiences and strategies to port a scientific application, DCA++, to Summit. DCA++ is a highperformance research application that solves quantum manybody problems with a cutting edge quantum cluster algorithm, the dynamical cluster approximation.Our strategies aim to synergize the strengths of the different programming models in the code. These include: (a) streamlining the interactions between the CPU threads and the GPUs, (b) implementing computing kernels on the GPUs and decreasing CPU-GPU memory transfers, (c) allowing asynchronous GPU communications, and (d) increasing compute intensity by combining linear algebraic operations.Full-scale production runs using all 4600 Summit nodes attained a peak performance of 73.5 PFLOPS with a mixed precision implementation.We observed a perfect strong and weak scaling for the quantum Monte Carlo solver in DCA++, while encountering about 2× input/output (I/O) and MPI communication overhead on the time-to-solution for the full machine run. Our hardware agnostic optimizations are designed to alleviate the communication and I/O challenges observed, while improving the compute intensity and obtaining optimal performance on a complex, hybrid architecture like Summit.

Balduzzi, Giovanni↗
DOE OSTI2023

Automatic Code Generation for High-Performance Graph Algorithms

Graph problems are common across fields of scientific computing and social sciences. However, despite their importance, implementing graph algorithms effectively on modern computing systems is a challenging task that requires significant programming effort and generally results in customized implementations. Current computing and memory hierarchies are not architected for irregular computations resulting in challenges for graph algorithms to achieve high performance on those architectures. In this paper, we present GraphX, a novel compiler framework and DSL designed to simplify the development of efficient graph algorithms and achieve high performance on modern computing systems. GraphX consists of a DSL for efficient implementation of graph algorithms, various optimizations, such as support for sparse linear algebra and workspace transformations, optimized graph primitives, including semiring and masking, and a high-performance code generation engine. Using GraphX, users can implement graph algorithms using a semantically-rich language with graph-oriented operators. GraphX uses these semantics to automatically generate efficient code for target architectures, increasing performance and portability across architectures. The composable nature of GraphX makes it possible to extend the set of optimizations and architectures without modifying the source code. We demonstrate GraphX outperforms state-of-the-art graph libraries, such as LAGraph, up to $3.7 speedup in semiring operations, $2.19 speedup in an important sparse computational kernel, and $9.05 speedup in graph processing algorithms.

compiler, graph algorithms, semiring, masking, wor↗
DOE OSTI2018

Attacking the Opioid Epidemic: Determining the Epistatic and Pleiotropic Genetic Architectures for Chronic Pain and Opioid Addiction

We describe the CoMet application for large-scale epistatic Genome-Wide Association Studies (eGWAS) and pleiotropy studies. High performance is attained by transforming the underlying vector comparison methods into highly performant generalized distributed dense linear algebra operations. The 2-way and 3-way Proportional Similarity metric and Custom Correlation Coefficient are implemented using native or adapted GEMM kernels optimized for GPU architectures. By aggressive overlapping of communications, transfers and computations, high efficiency with respect to single GPU kernel performance is maintained up to the full Titan and Summit systems. Nearly 300 quadrillion element comparisons per second and over 2.3 mixed precision ExaOps are reached on Summit by use of Tensor Core hardware on the Nvidia Volta GPUs. Performance is four to five orders of magnitude beyond comparable state of the art. CoMet is currently being used in projects ranging from bioenergy to clinical genomics, including for the genetics of chronic pain and opioid addiction.

Joubert, Wayne↗
DOE OSTI2024

ChatBLAS: The First AI-Generated and Portable BLAS Library

We present ChatBLAS, the first AI-generated and portable Basic Linear Algebra Subprograms (BLAS) library on different CPU/GPU configurations. The purpose of this study is (i) to evaluate the capabilities of current large language models (LLMs) to generate a portable and HPC library for BLAS operations and (ii) to define the fundamental practices and criteria to interact with LLMs for HPC targets to elevate the trustworthiness and performance levels of the AI-generated HPC codes. The generated C/C++ codes must be highly optimized using device-specific solutions to reach high levels of performance. Additionally, these codes are very algorithm-dependent, thereby adding an extra dimension of complexity to this study. We used OpenAI’s LLM ChatGPT and focused on vector-vector BLAS level-1 operations. ChatBLAS can generate functional and correct codes, achieving high-trustworthiness levels, and can compete or even provide better performance against vendor libraries.

Valero Lara, Pedro↗
DOE OSTI2017

An Augmented Lagrangian Filter Method for Real-Time Embedded Optimization

We present a filter line-search algorithm for nonconvex continuous optimization that combines an augmented Lagrangian function and a constraint violation metric to accept and reject steps. The approach is motivated by real-time optimization applications that need to be executed on embedded computing platforms with limited memory and processor speeds. The proposed method enables primal–dual regularization of the linear algebra system that in turn permits the use of solution strategies with lower computing overheads. We prove that the proposed algorithm is globally convergent and we demonstrate the developments using a nonconvex real-time optimization application for a building heating, ventilation, and air conditioning system. Our numerical tests are performed on a standard processor and on an embedded platform. Lastly, we demonstrate that the approach reduces solution times by a factor of over 1000.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2018

Symmetric Indefinite Linear Solver Using OpenMP Task on Multicore Architectures

Recently, the Open Multi-Processing (OpenMP) standard has incorporated task-based programming, where a function call with input and output data is treated as a task. At run time, OpenMP's superscalar scheduler tracks the data dependencies among the tasks and executes the tasks as their dependencies are resolved. On a shared-memory architecture with multiple cores, the independent tasks are executed on different cores in parallel, thereby enabling parallel execution of a seemingly sequential code. With the emergence of many-core architectures, this type of programming paradigm is gaining attention-not only because of its simplicity, but also because it breaks the artificial synchronization points of the program and improves its thread-level parallelization. In this paper, we use these new OpenMP features to develop a portable high-performance implementation of a dense symmetric indefinite linear solver. Obtaining high performance from this kind of solver is a challenge because the symmetric pivoting, which is required to maintain numerical stability, leads to data dependencies that prevent us from using some common performance-improving techniques. To fully utilize a large number of cores through tasking, while conforming to the OpenMP standard, we describe several techniques. Our performance results on current many-core architectures-including Intel's Broadwell, Intel's Knights Landing, IBM's Power8, and Arm's ARMv8-demonstrate the portable and superior performance of our implementation compared with the Linear Algebra PACKage (LAPACK). The resulting solver is now available as a part of the PLASMA software package.

Computer Science↗
DOE OSTI2022

Failure Probability Constrained AC Optimal Power Flow

Despite cascading failures being the central cause of blackouts in power transmission systems, existing operational and planning decisions are made largely by ignoring their underlying cascade potential. This paper posits a reliability-aware AC Optimal Power Flow formulation that seeks to design a dispatch point which has a low operator-specified likelihood of triggering a cascade starting from any single component outage. By exploiting a recently developed analytical model of the probability of component failure, our Failure Probability-constrained ACOPF (FP-ACOPF) utilizes the system's expected first failure time as a smoothly tunable and interpretable signature of cascade risk. Here, we use techniques from bilevel optimization and numerical linear algebra to efficiently formulate and solve the FP-ACOPF using off-the-shelf solvers. Extensive simulations on the IEEE 118-bus case show that, when compared to the unconstrained and N-1 security-constrained ACOPF, our probability-constrained dispatch points can significantly lower the probabilities of long severe cascades and of large demand losses, while incurring only minor increases in total generation costs.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2018

Light Scattering by Small Multilayer Particles: A Generalized Separation of Variables Method

A Rayleigh approximation is constructed for light scattering by small multilayer axisymmetric particles, in which their polarizability is determined by the generalized separation of variables method (SVM). In this method, scalar potentials, the gradients of which yield the electric-field strengths, are represented as expansions in spherical harmonics of the Laplace equation. Unknown coefficients of expansions are determined from the boundary conditions, which are reduced to infinite systems of linear algebraic equations (ISLAEs), since the separation of variables is incomplete. The T matrix of the electrostatic problem, principal element T{sub 11} of which is proportional to the particle polarizability, is determined. The necessary condition for the ISLAEs solvability for the SVM coincides with the condition of the correct application of the extended boundary conditions method (EBCM). However, numerical calculations in which finite-dimensional (i.e., reduced) systems are solved, yield different results in ranges of variation of parameters that are close to the boundary of the range of applicability. An analysis of the numerical calculations of the scattering and absorption cross sections for two-layer confocal spheroids, an exact solution for which can be obtained using spheroidal harmonics, shows that the SVM is preferable to the EBCM. It turned out that the proposed method yields workable results in a wider range of variation of parameters. Even outside the range of applicability, in which it should be regarded as a certain approximate solution, its use in a number of cases is quite acceptable. Additional calculations for three-layer nonconfocal spheroids, as well as for three-layer similar pseudospheroids and Pascal’s snails, which can be obtained from spheroids as a result of the inversion with respect to the coordinate origin and one of the foci, respectively, confirm these inferences. We note that, for certain values of the parameters, the shapes of the latter particles are nonconvex.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2014

Conductance matrix of multiterminal semiconductor devices with edge channels

A method for determining the conductance matrix of multiterminal semiconductor structures with edge channels is proposed. The method is based on the solution of a system of linear algebraic equations based on Kirchhoff equations, made up of potential differences U{sub ij} measured at stabilized currents I{sub kl}, where i, j, k, l are terminal numbers. The matrix obtained by solving the system of equations completely describes the structure under study, reflecting its configuration and homogeneity. This method can find wide application when using the known Landauer-Buttiker formalism to analyze carrier transport in the quantum Hall effect and quantum spin Hall effect modes. Within the proposed method, the contribution of the contact area resistances R{sub c} to the formation of conductance matrix elements is taken into account. The possibilities of practical application of the results obtained in developing analog cryptographic devices are considered.

36 MATERIALS SCIENCE↗
DOE OSTI2017

Is the Multigrid Method Fault Tolerant? The Two-Grid Case

The predicted reduced resiliency of next-generation high performance computers means that it will become necessary to take into account the effects of randomly occurring faults on numerical methods. Further, in the event of a hard fault occurring, a decision has to be made as to what remedial action should be taken in order to resume the execution of the algorithm. The action that is chosen can have a dramatic effect on the performance and characteristics of the scheme. Ideally, the resulting algorithm should be subjected to the same kind of mathematical analysis that was applied to the original, deterministic variant. The purpose of this work is to provide the first rigorous analysis of the behavior of the multigrid algorithm in the presence of faults. Specifically, we prove estimates on the behavior of the Two Grid Method similar to the classical asymptotic results. Multigrid is arguably the method of choice for the solution of large-scale linear algebra problems arising from discretization of partial differential equations, and it is of considerable importance to anticipate its behavior on an exascale machine. The analysis of resilience of algorithms is in its infancy, and the current work is perhaps the first to provide a mathematical model for faults and analyze the behavior of a state-of-the-art algorithm under the model. It is shown that the Two Grid Method fails to be resilient to faults. Attention is then turned to identifying the minimal necessary remedial action required to restore the rate of convergence to that enjoyed by the ideal fault-free method.

Mathematics↗
DOE OSTI2018

Hybrid Finite Element--Spectral Method for the Fractional Laplacian: Approximation Theory and Efficient Solver

Here, a numerical scheme is presented for approximating fractional order Poisson problems in two and three dimensions. The scheme is based on reformulating the original problem posed over $\Omega$ on the extruded domain $\mathcal{C}=\Omega\times[0,\infty)$ following. The resulting degenerate elliptic integer order PDE is then approximated using a hybrid FEM-spectral scheme. Finite elements are used in the direction parallel to the problem domain $\Omega$, and an appropriate spectral method is used in the extruded direction. The spectral part of the scheme requires that we approximate the true eigenvalues of the integer order Laplacian over $\Omega$. We derive an a priori error estimate which takes account of the error arising from using an approximation in place of the true eigenvalues. We further present a strategy for choosing approximations of the eigenvalues based on Weyl's law and finite element discretizations of the eigenvalue problem. The system of linear algebraic equations arising from the hybrid FEM-spectral scheme is decomposed into blocks which can be solved effectively using standard iterative solvers such as multigrid and conjugate gradient. Numerical examples in two and three dimensions suggest that the approach is quasi-optimal in terms of complexity.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2019

A Relaxed Physical Factorization Preconditioner for Mixed Finite Element Coupled Poromechanics

In this work, we introduce a relaxed physical factorization (RPF) preconditioner for the efficient iterative solution of the linearized algebraic system arising from the mixed finite element discretization of coupled poromechanics equations. The preconditioner is obtained by using a proper factorization of the $3\times3$ block matrix and setting a relaxation parameter $\alpha$. The preconditioner is inspired by the relaxed dimensional factorization introduced by Benzi et al. [J. Comput. Phys., 230 (2011), pp. 6185--6202; Comput. Methods Appl. Mech. Engrg., 300 (2016), pp. 129--145]. A stable algorithm is advanced to compute the optimal value of $\alpha$, along with a lower bound to control the possible ill-conditioning of the $\alpha$ dependent inner blocks. Lastly, numerical experiments in both theoretical benchmarks and real-world applications are presented and discussed to investigate the RPF properties, performance, and robustness.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

Surrogate-Based Autotuning for Randomized Sketching Algorithms in Regression Problems

Algorithms from Randomized Numerical Linear Algebra (RandNLA) are known to be effective in handling high-dimensional computational problems, providing high-quality empirical performance as well as strong probabilistic guarantees. However, their practical application is complicated by the fact that the user needs to set various algorithm-specific tuning parameters which are different from those used in traditional NLA. This paper demonstrates how a surrogate-based autotuning approach can be used to address fundamental problems of parameter selection in RandNLA algorithms. In particular, we provide a detailed investigation of surrogate-based autotuning for sketch-and-precondition (SAP)-based randomized least squares methods, which have been one of the great success stories in modern RandNLA. Empirical results show that our surrogate-based autotuning approach can achieve near-optimal performance with much less tuning cost than a random search (up to about 7.6x fewer trials of different parameter configurations). Moreover, while our experiments focus on least squares, our results demonstrate a general-purpose autotuning pipeline applicable to any kind of RandNLA algorithm.

Cho, Younghyun↗
DOE OSTI2018

Integrated Model, Batch and Domain Parallelism in Training Neural Networks

We propose a new integrated method of exploiting model, batch and domain parallelism for the training of deep neural networks (DNNs) on large distributed-memory computers using minibatch stochastic gradient descent (SGD). Our goal is to find an efficient parallelization strategy for a fixed batch size using $P$ processes. Our method is inspired by the communication-avoiding algorithms in numerical linear algebra. We see $P$ processes as logically divided into a $P_r \times P_c$ grid where the $P_r$ dimension is implicitly responsible for model/domain parallelism and the $P_c$ dimension is implicitly responsible for batch parallelism. In practice, the integrated matrix-based parallel algorithm encapsulates these types of parallelism automatically. We analyze the communication complexity and analytically demonstrate that the lowest communication costs are often achieved neither with pure model nor with pure data parallelism. We also show how the domain parallel approach can help in extending the theoretical scaling limit of the typical batch parallel method.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2018

A Parallel Solver for Graph Laplacians

Problems from graph drawing, spectral clustering, network flow and graph partitioning can all be expressed in terms of graph Laplacian matrices. There are a variety of practical approaches to solving these problems in serial. However, as problem sizes increase and single core speeds stagnate, parallelism is essential to solve such problems quickly. We present an unsmoothed aggregation multigrid method for solving graph Laplacians in a distributed memory setting. We introduce new parallel aggregation and low degree elimination algorithms targeted specifically at irregular degree graphs. These algorithms are expressed in terms of sparse matrix-vector products using generalized sum and product operations. This formulation is amenable to linear algebra using arbitrary distributions and allows us to operate on a 2D sparse matrix distribution, which is necessary for parallel scalability. Our solver outperforms the natural parallel extension of the current state of the art in an algorithmic comparison. We demonstrate scalability to 576 processes and graphs with up to 1.7 billion edges.

Konolige, Tristan↗