Search NASA⌕ Search

SEARCH · Search NASA

Results for “Linear systems solvers”

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 235 records · Page 13

Adaptive Model Reduction for Parareal in Time Method for Transient Stability Simulations

Real time or faster than real time simulation can enable system operators to foresee the effect of crucial contingencies on the power system dynamics and take timely actions to prevent system instability. Parareal in time method uses concurrent computations on different segments of the time domain of interest to speed up the dynamic simulations. This paper describes the application of an adaptive nonlinear model reduction method in improving computational speed of the Parareal solver. The proposed method adaptively switches between a hybrid system with selective linearization and a completely linear system based on the size of a disturbance. The functions in the hybrid system are linearized based on the electrical distance between specific generators and the area where disturbances originated. The proposed method is tested on the 327-machine 2383-bus Polish system.

Osipov, Denis↗

Structured Multifrontal Sparse Solver

StruMF is an algebraic structured preconditioner for the interative solution of large sparse linear systems. The preconditioner corresponds to a multifrontal variant of sparse LU factorization in which some dense blocks of the factors are approximated with low-rank matrices. It is algebraic in that it only requires the linear system itself, and the approximation threshold that determines the accuracy of individual low-rank approximations. Favourable rank properties are obtained using a block partitioning which is a refinement of the partitioning induced by nested dissection ordering.

Napov, Artem↗

Computational complexities and storage requirements of some Riccati equation solvers

The linear optimal control problem of an nth-order time-invariant dynamic system with a quadratic performance functional is usually solved by the Hamilton-Jacobi approach. This leads to the solution of the differential matrix Riccati equation with a terminal condition. The bulk of the computation for the optimal control problem is related to the solution of this equation. There are various algorithms in the literature for solving the matrix Riccati equation. However, computational complexities and storage requirements as a function of numbers of state variables, control variables, and sensors are not available for all these algorithms. In this work, the computational complexities and storage requirements for some of these algorithms are given. These expressions show the immensity of the computational requirements of the algorithms in solving the Riccati equation for large-order systems such as the control of highly flexible space structures. The expressions are also needed to compute the speedup and efficiency of any implementation of these algorithms on concurrent machines.

Utku, Senol↗

Scalable domain decomposition solvers for stochastic PDEs in high performance computing

Stochastic spectral finite element models of practical engineering systems may involve solutions of linear systems or linearized systems for non-linear problems with billions of unknowns. For stochastic modeling, it is therefore essential to design robust, parallel and scalable algorithms that can efficiently utilize high-performance computing to tackle such large-scale systems. Domain decomposition based iterative solvers can handle such systems. And though these algorithms exhibit excellent scalabilities, significant algorithmic and implementational challenges exist to extend them to solve extreme-scale stochastic systems using emerging computing platforms. Intrusive polynomial chaos expansion based domain decomposition algorithms are extended here to concurrently handle high resolution in both spatial and stochastic domains using an in-house implementation. Sparse iterative solvers with efficient preconditioners are employed to solve the resulting global and subdomain level local systems through multi-level iterative solvers. We also use parallel sparse matrix–vector operations to reduce the floating-point operations and memory requirements. Numerical and parallel scalabilities of these algorithms are presented for the diffusion equation having spatially varying diffusion coefficient modeled by a non-Gaussian stochastic process. Scalability of the solvers with respect to the number of random variables is also investigated.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Some fast elliptic solvers on parallel architectures and their complexities

The discretization of separable elliptic partial differential equations leads to linear systems with special block triangular matrices. Several methods are known to solve these systems, the most general of which is the Block Cyclic Reduction (BCR) algorithm which handles equations with nonconsistant coefficients. A method was recently proposed to parallelize and vectorize BCR. Here, the mapping of BCR on distributed memory architectures is discussed, and its complexity is compared with that of other approaches, including the Alternating-Direction method. A fast parallel solver is also described, based on an explicit formula for the solution, which has parallel computational complexity lower than that of parallel BCR.

Gallopoulos, E.↗

Some fast elliptic solvers on parallel architectures and their complexities

The discretization of separable elliptic partial differential equations leads to linear systems with special block tridiagonal matrices. Several methods are known to solve these systems, the most general of which is the Block Cyclic Reduction (BCR) algorithm which handles equations with nonconstant coefficients. A method was recently proposed to parallelize and vectorize BCR. In this paper, the mapping of BCR on distributed memory architectures is discussed, and its complexity is compared with that of other approaches including the Alternating-Direction method. A fast parallel solver is also described, based on an explicit formula for the solution, which has parallel computational compelxity lower than that of parallel BCR.

Gallopoulos, E.↗

Algebraic multigrid for directed graph Laplacian linear systems (NS‐LAMG)

Summary We propose nonsymmetric lean algebraic multigrid (NS‐LAMG), a new algebraic multigrid algorithm for directed graph Laplacian systems that combines ideas from undirected graph Laplacian multigrid solvers and multigrid algorithms for Markov chain stationary distribution systems. Low‐degree elimination, proposed in LAMG for undirected graphs, is generalized to directed graphs and is a key component of NS‐LAMG. In the setup phase, we propose a simple stationary‐aggregation multigrid algorithms for Markov chain stationary distribution systems solver enhanced by low‐degree elimination to find the right null‐space vector that is used for the intergrid transfer operators. Numerical results show that low‐degree elimination improves performance and that NS‐LAMG outperforms generalized minimal residual method with restart and stable bi‐conjugate gradient method for real‐world, directed graph Laplacian linear systems.

Fox, Alyson↗

A scalable geometric multigrid solver for nonsymmetric elliptic systems with application to variable-density flows

A geometric multigrid algorithm is introduced for solving nonsymmetric linear systems resulting from the discretization of the variable density Navier–Stokes equations on nonuniform structured rectilinear grids and high-Reynolds number flows. The restriction operation is defined such that the resulting system on the coarser grids is symmetric, thereby allowing for the use of efficient smoother algorithms. To achieve an optimal rate of convergence, the sequence of interpolation and restriction operations are determined through a dynamic procedure. A parallel partitioning strategy is introduced to minimize communication while maintaining the load balance between all processors. To test the proposed algorithm, we consider two cases: 1) homogeneous isotropic turbulence discretized on uniform grids and 2) turbulent duct flow discretized on stretched grids. Testing the algorithm on systems with up to a billion unknowns shows that the cost varies linearly with the number of unknowns. This O (N) behavior confirms the robustness of the proposed multigrid method regarding ill-conditioning of large systems characteristic of multiscale high-Reynolds number turbulent flows. The robustness of our method to density variations is established by considering cases where density varies sharply in space by a factor of up to 104, showing its applicability to two-phase flow problems. Strong and weak scalability studies are carried out, employing up to 30,000 processors, to examine the parallel performance of our implementation. Excellent scalability of our solver is shown for a granularity as low as 104 to 105 unknowns per processor. At its tested peak throughput, it solves approximately 4 billion unknowns per second employing over 16,000 processors with a parallel efficiency higher than 50%.

Computer Science↗

Fast and Scalable Sparse Triangular Solver for Multi-GPU Based HPC Architectures

Designing efficient and scalable sparse linear algebra kernels on modern multi-GPU based HPC systems is a daunting task due to significant irregular memory references and workload imbalance across the GPUs. This is particularly the case for \textit{Sparse Triangular Solver (SpTRSV)} which introduces additional two-dimensional computation dependencies among subsequent computation steps. Dependency information is exchanged and shared among GPUs, thus warrant for efficient memory allocation, data partitioning, and workload distribution as well as fine-grained communication and synchronization support. In this work, we demonstrate that directly adopting unified memory can adversely affect the performance of SpTRSV on multi-GPU architectures, despite linking via fast interconnect like NVLinks and NVSwitches. Alternatively, we employ the latest NVSHMEM technology based on Partitioned Global Address Space programming model to enable efficient fine-grained communication and drastic synchronization overhead reduction. Furthermore, to handle workload imbalance, we propose a malleable task-pool execution model which can further enhance the utilization of GPUs. By applying these techniques, our experiments on the NVIDIA multi-GPU supernode V100-DGX-1 and DGX-2 systems demonstrate that our design can achieve on average 3.53x (up to 9.86x) speedup on a DGX-1 system and 3.66x (up to 9.64x) speedup on a DGX-2 system with 4-GPUs over the Unified-Memory design. The comprehensive sensitivity and scalability studies also show that the proposed zero-copy SpTRSV is able to fully utilize the computing and communication resources of the multi-GPU system.

Xie, Chenhao↗

Optimal Power Flow Derived Sparse Linear Solver Benchmarks

Due to the changing nature of the power grid, it is increasingly important to be able to solve a high-fidelity optimal power-flow models on large power networks. This high-fidelity problem, called AC Optimal Power Flow (ACOPF), is a nonlinear, nonconvex optimization problem. One of the few reliable ways of solving such a problem is interior point methods. These methods result in sparse linear systems where the coefficient matrix is symmetric, indefinite and nearly always ill-conditioned. As such, they are particularly challenging for sparse linear solvers and represent a considerable computational bottleneck in solving the ACOPF problem. In this paper, we introduce a repository of linear systems captured from ACOPF problems when solved by the open-source optimizer IPOPT. These matrices are meant to be used as a test suite for sparse linear solver development.

97 MATHEMATICS AND COMPUTING↗

Verification and application of numerically generated magnetic coordinate systems in gyrokinetics

In the context of linear gyrokinetic simulations, an analysis of the application of field-aligned coordinate systems generated numerically from magnetohydrodynamic equilibria is presented. This family of systems allows some flexibility in the choice of the coordinates, and gyrokinetic solvers often differ in this respect. Certain transformations are therefore required in order to compare physics results. Accordingly, benchmarks of a linear microinstability are carried out between two similar gyrokinetic codes. Effort is also put on the verification of the special properties of the generated systems through certain diagnostics.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

Development of the FHR advanced natural circulation analysis code and application to FHR safety analysis

The University of California, Berkeley (UCB) is performing thermal hydraulics safety analysis to develop the technical basis for design and licensing of fluoride-salt-cooled, high-temperature reactors (FHRs). FHR designs investigated by UCB use natural circulation for emergency, passive decay heat removal when normal decay heat removal systems fail. The FHR advanced natural circulation analysis (FANCY) code has been developed for assessment of passive decay heat removal capability and safety analysis of these innovative system designs. The FANCY code uses a one-dimensional, semi-implicit scheme to solve for pressure-linked mass, momentum and energy conservation equations. Graph theory is used to automatically generate a staggered mesh for complicated pipe network systems. Heat structure models have been implemented for three types of boundary conditions (Dirichlet, Neumann and Robin boundary conditions). Heat structures can be composed of several layers of different materials, and are used for simulation of heat structure temperature distribution and heat transfer rate. Control models are used to simulate sequences of events or trips of safety systems. A proportional-integral controller is also used to automatically make thermal hydraulic systems reach desired steady state conditions. A point kinetics model is used to model reactor kinetics behavior with temperature reactivity feedback. The underlying large sparse linear systems in these models are efficiently solved by using direct and iterative solvers provided by the SuperLU code on high performance machines. Input interfaces are designed to increase the flexibility of simulation for complicated thermal hydraulic systems. In conclusion, this paper mainly focuses on the methodology used to develop the FANCY code, and safety analysis of the Mark 1 pebble-bed FHR under development at UCB is performed.

21 SPECIFIC NUCLEAR REACTORS AND ASSOCIATED PLANTS↗

All-electron APW+ lo calculation of magnetic molecules with the SIRIUS domain-specific package

We report APW+lo (augmented plane wave plus local orbital) density functional theory (DFT) calculations of large molecular systems using the domain specific SIRIUS multi-functional DFT package. The APW and FLAPW (full potential linearized APW) task and data parallelism options and the advanced eigen-system solver provided by SIRIUS can be exploited for performance gains in ground state Kohn–Sham calculations on large systems. This approach is distinct from our prior use of SIRIUS as a library backend to another APW+lo or FLAPW code. We benchmark the code and demonstrate performance on several magnetic molecule and metal organic framework systems. We show that the SIRIUS package in itself is capable of handling systems as large as a several hundred atoms in the unit cell without having to make technical choices that result in the loss of accuracy with respect to that needed for the study of magnetic systems.

Chemistry↗

An investigation of Newton-Sketch and subsampled Newton methods

Sketching, a dimensionality reduction technique, has received much attention in the statistics community. In this paper, we study sketching in the context of Newton's method for solving finite-sum optimization problems in which the number of variables and data points are both large. In this work, we study two forms of sketching that perform dimensionality reduction in data space: Hessian subsampling and randomized Hadamard transformations. Each has its own advantages, and their relative tradeoffs have not been investigated in the optimization literature. Additionally, our study focuses on practical versions of the two methods in which the resulting linear systems of equations are solved approximately, at every iteration, using an iterative solver. The advantages of using the conjugate gradient method vs. a stochastic gradient iteration are revealed through a set of numerical experiments, and a complexity analysis of the Hessian subsampling method is presented.

97 MATHEMATICS AND COMPUTING↗

Linear Microbunching Gain Estimation Including CSR, LSC And Linac Geometric Impedances In Recirculation Arcs

It is known that microbunching instability (MBI) has been one of the most challenging issues with the design of magnetic compressor chicanes for X-ray FEL or linear colliders, as well as the transport lines for recirculating or energy recovery linacs. To more accurately quantify MBI in a single-pass system and for more complete analyses, we extend our previously developed linear Vlasov solver [1] to incorporate more relevant impedance models into the code, including transient and steady-state coherent synchrotron radiation (CSR), the longitudinal space charge (LSC), and the linac geometric impedance models. Then we self-consistently solve the linearized Vlasov equation for the gain amplification factor. With application of this code to two specially designed recirculation arcs [2], the resultant gain functions and spectra are presented and some results are compared with particle tracking simulation by ELEGANT. We also discuss some underlying physics with inclusion of these collective effects. It is anticipated this more complete analysis can further improve the understanding of the MBI mechanisms and shed light on how to suppress or compensate MBI effects in lattice designs. [1] C. -Y. Tsai et al., Theoretical investigation of coherent synchrotron radiation induced microbunching instability in transport and recirculation arcs, Proceedings of FEL 14, available at http://arxiv.org/abs/1408.5542 [2] D. Douglas et al., Control of Coherent Synchrotron Radiation and Micro-Bunching Effects During Transport of High Brightness Electron Beams, JLAB-ACP-14-1751, available at http://arxiv.org/abs/1403.2318 Authored by Jefferson Science Associates, LLC under U.S. DOE Contract No. DE-AC05-06OR23177.

Tsai, C. -Y.↗

Development of Geomechanical Screening Tools to Identify Risk: An Experimental and Modeling Approach for Secure CO 2 Storage Final Technical Report

CO 2 injection in the subsurface introduces additional complexity in terms of interactions of the reservoir host pore fluid with natural heterogeneity of hydro-mechanical properties of the rock. Natural heterogeneity of the reservoir rock and caprock formations includes spatial variation of hydro-mechanical properties as well as the presence of natural fractures. We developed a coupled mathematical modeling and experimental framework that takes into account the effect of rock heterogeneity on effective mechanical properties of the rock in contact with CO 2 . We performed accurate laboratory experiments to determine the changes in rock mechanical properties due to mineral dissolution in the presence of carbonic acid generated by CO 2 injection. A two-scale adaptive homogenization framework was then developed to consistently upscale petrophysical and geomechanical properties to the field scale. Further, we also developed high-fidelity, numerical solution schemes, non-linear and linear solvers and preconditioners to solve the coupled flow, reactive transport and geomechanical system. The numerical model was then used to study field scale CO 2 sequestration problems for the two selected field sites: (1) Frio formation and (2) Cranfield site. We also developed robust schemes for field data assimilation, model calibration such that the residual uncertainty at the end of the data assimilation procedures can be faithfully represented while taking into account the coupled geochemical and geomechanical processes.

42 ENGINEERING↗

Development of iterative techniques for the solution of unsteady compressible viscous flows

The development of efficient iterative solution methods for the numerical solution of two- and three-dimensional compressible Navier-Stokes equations is discussed. Iterative time marching methods have several advantages over classical multi-step explicit time marching schemes, and non-iterative implicit time marching schemes. Iterative schemes have better stability characteristics than non-iterative explicit and implicit schemes. In this work, another approach based on the classical conjugate gradient method, known as the Generalized Minimum Residual (GMRES) algorithm is investigated. The GMRES algorithm has been used in the past by a number of researchers for solving steady viscous and inviscid flow problems. Here, we investigate the suitability of this algorithm for solving the system of non-linear equations that arise in unsteady Navier-Stokes solvers at each time step.

Sankar, Lakshmi N.↗