Engineering Papers⌕ Search

SEARCH · Engineering Papers

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 217 records · Page 12
All sourcesNASA NTRSDOE OSTI
NASA NTRS2003

Performance Analysis of a Hybrid Overset Multi-Block Application on Multiple Architectures

This paper presents a detailed performance analysis of a multi-block overset grid compu- tational fluid dynamics app!ication on multiple state-of-the-art computer architectures. The application is implemented using a hybrid MPI+OpenMP programming paradigm that exploits both coarse and fine-grain parallelism; the former via MPI message passing and the latter via OpenMP directives. The hybrid model also extends the applicability of multi-block programs to large clusters of SNIP nodes by overcoming the restriction that the number of processors be less than the number of grid blocks. A key kernel of the application, namely the LU-SGS linear solver, had to be modified to enhance the performance of the hybrid approach on the target machines. Investigations were conducted on cacheless Cray SX6 vector processors, cache-based IBM Power3 and Power4 architectures, and single system image SGI Origin3000 platforms. Overall results for complex vortex dynamics simulations demonstrate that the SX6 achieves the highest performance and outperforms the RISC-based architectures; however, the best scaling performance was achieved on the Power3.

Djomehri, M. Jahed↗
DOE OSTI2024

A Fast Algebraic Multigrid Solver and Accurate Discretization for Highly Anisotropic Heat Flux I: Open Field Lines

We present a novel solver technique for the anisotropic heat flux equation, aimed at the high level of anisotropy seen in magnetic confinement fusion plasmas. Such problems pose two major challenges: (i) discretization accuracy and (ii) efficient implicit linear solvers. We simultaneously address each of these challenges by constructing a new finite element discretization with excellent accuracy properties, tailored to a novel solver approach based on algebraic multigrid (AMG) methods designed for advective operators. We pose the problem in a mixed formulation, introducing the directional temperature gradient as an auxiliary variable. The temperature and auxiliary fields are discretized in a scalar discontinuous Galerkin space with upwinding principles used for discretizations of advection. We demonstrate the proposed discretization’s superior accuracy over other discretizations of anisotropic heat flux, achieving error 1000x smaller for anisotropy ratio of 10 9 , for closed field lines. The block matrix system is reordered and solved in an approach where the two advection operators are inverted using AMG solvers based on approximate ideal restriction, which is particularly efficient for upwind discontinuous Galerkin discretizations of advection. To ensure that the advection operators are nonsingular, in this paper we restrict ourselves to considering open (acyclic) magnetic field lines for the linear solvers. We demonstrate fast convergence of the proposed iterative solver in highly anisotropic regimes where other diffusion-based AMG methods fail.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Nonlinear Elimination Applied to Radiation Diffusion

We apply a nonlinearly preconditioned, quasi-Newton framework to accelerate the numerical solution of the thermal radiative transfer (TRT) equations. This framework was inspired by the unpublished method that has existed for years in Teton, Lawrence Livermore National Laboratory’s deterministic TRT code. In this paper, we cast this iteration scheme within a formal nonlinear preconditioning framework and compare its performance against other iteration schemes in the framework. With proper choices of iteration controls for the various levels of the solver, we can recover the standard linearized one-step method, a full nonlinear Newton scheme, as well as the method in Teton. In brief, the nonlinear preconditioning TRT scheme formally eliminates the material temperature equation from the nonlinear system in a nonlinear analog of a Schur complement. This nonlinear elimination step involves solving a decoupled nonlinear equation for each spatial degree of freedom and is therefore inexpensive. By applying a quasi-Newton iteration scheme on the new system, we obtain a three-level iteration scheme that is at least as efficient as commonly used TRT schemes. The new method allows full convergence to the nonlinear backward Euler time-discretized system, increasing accuracy and robustness, while using a similar number of linear iterations as the more common linearized one-step methods Eq. (4).

77 NANOSCIENCE AND NANOTECHNOLOGY↗
NASA NTRS2018

PURE: Scalable Phase Unwrapping with Spatial Redundant Arcs

Phase unwrapping is a key problem in many coherent imaging systems, such as syntheticapertureradar(SAR)interferometry. Ageneralformulationforredundant integration of finite differences for phase unwrapping (Costantini et al., 2010) was shown to produce a more reliable solution by exploiting redundant differential estimates. However, this technique requires a commercial linear programming solver for large-scale problems. For a linear cost function, we propose a method based on Dual Decomposition that breaks the given problem defined over a nonplanar graph into tractable sub-problems over planar subgraphs. We also propose a decomposition technique that exploits the underlying graph structure for solving thesub-problemsefficientlyandguaranteesasymptoticconvergencetotheglobally optimal solution. The experimental results demonstrate that the proposed approach is comparable to the existing state-of-the-art methods in terms of the estimate with a better runtime and memory footprint.

Lanka, Ravi↗
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 OSTI2021

Asynchronous Iterative Solvers for Extreme-Scale Computing

The Asynchronous Iterative Solvers for Extreme-Scale Computing (AsyncIS) project aims to explore more efficient numerical algorithms by decreasing their overhead. AsyncIS does this by replacing the outer Krylov subspace solver with an asynchronous optimized Schwarz method, thereby removing the global synchronization and bulk synchronous operations typically used in numerical codes. AsyncIS—a U.S. Department of Energy (DOE)-funded collaboration between Georgia Tech, the University of Tennessee, Knoxville, Temple University, and Sandia National Laboratories—also focuses on the development and optimization of asynchronous preconditioners (i.e., preconditioners that are generated and/or applied in an asynchronous fashion). The novel preconditioning algorithms that provide fine-grained parallelism enable preconditioned Krylov solvers to run efficiently on large-scale distributed systems and manycore accelerators like GPUs.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Constrained Local Approximate Ideal Restriction for Advection-Diffusion Problems

Herein this paper focuses on developing a reduction-based algebraic multigrid (AMG) method that is suitable for solving general (non)symmetric linear systems and is naturally robust from pure advection to pure diffusion. Initial motivation comes from a new reduction-based AMG approach, $\ell \text{AIR}$ (local approximate ideal restriction), that was developed for solving advection-dominated problems. Though this new solver is very effective in the advection-dominated regime, its performance degrades in cases where diffusion becomes dominant. This is consistent with the fact that in general, reduction-based AMG methods tend to suffer from growth in complexity and/or convergence rates as the problem size is increased, especially for diffusion-dominated problems in two or three dimensions. Motivated by the success of $\ell \text{AIR}$ in the advective regime, our aim in this paper is to generalize the AIR framework with the goal of improving the performance of the solver in diffusion-dominated regimes. To do so, we propose a novel way to combine mode constraints as used commonly in energy-minimization AMG methods with the local approximation of ideal operators used in $\ell \text{AIR}$. The resulting constrained $\ell \text{AIR}$ algorithm is able to achieve fast scalable convergence on advective and diffusive problems. In addition, it is able to achieve standard low complexity hierarchies in the diffusive regime through aggressive coarsening, something that was previously difficult for reduction-based methods.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1987

Solution of the two-dimensional Navier-Stokes equations using sparse matrix solvers

The use of direct sparse matrix solvers in the solution of the Navier-Stokes equations is investigated. The Yale Sparse Matrix Package and its implementation in the solution algorithm is described. The streamfunction-vorticity form of the Navier-Stokes equations are discretized and linearized and the resulting system of equations are solved using this package. Several viscous flow problems are investigated, including flow in a cavity and flow around a NACA0012 airfoil. Massively separated flow around a sine wave airfoil is investigated and high Reynolds number solutions are obtained. A solution of the unsteady flow around a Joukowski airfoil at high angle of attack is presented.

Bender, Erich E.↗
NASA NTRS1994

Parallel Preconditioning for CFD Problems on the CM-5

Up to today, preconditioning methods on massively parallel systems have faced a major difficulty. The most successful preconditioning methods in terms of accelerating the convergence of the iterative solver such as incomplete LU factorizations are notoriously difficult to implement on parallel machines for two reasons: (1) the actual computation of the preconditioner is not very floating-point intensive, but requires a large amount of unstructured communication, and (2) the application of the preconditioning matrix in the iteration phase (i.e. triangular solves) are difficult to parallelize because of the recursive nature of the computation. Here we present a new approach to preconditioning for very large, sparse, unsymmetric, linear systems, which avoids both difficulties. We explicitly compute an approximate inverse to our original matrix. This new preconditioning matrix can be applied most efficiently for iterative methods on massively parallel machines, since the preconditioning phase involves only a matrix-vector multiplication, with possibly a dense matrix. Furthermore the actual computation of the preconditioning matrix has natural parallelism. For a problem of size n, the preconditioning matrix can be computed by solving n independent small least squares problems. The algorithm and its implementation on the Connection Machine CM-5 are discussed in detail and supported by extensive timings obtained from real problem data.

Simon, Horst D.↗
DOE OSTI2022

An efficient high-order numerical solver for diffusion equations with strong anisotropy

In this paper, we present an interior penalty discontinuous Galerkin finite element scheme for solving diffusion problems with strong anisotropy arising in magnetized plasmas for fusion applications. Additionally, we demonstrate the accuracy produced by the high-order scheme and develop an efficient preconditioning technique to solve the corresponding linear system, which is robust to the mesh size and anisotropy of the problem. Several numerical tests are provided to validate the accuracy and efficiency of the proposed algorithm.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Assessing the Feasibility of Bordered Block Diagonal Reordering in Power System Matrices using Fully Convolutional Network

In electromagnetic transient (EMT) simulations for power systems and inverter-based resources (IBRs), the arrangement of states within the system's linear equations, represented by matrix A in Ax=b, is critical. The state ordering in matrix A can highlight distinct characteristics of the system's graph, and identifying an optimal state ordering is crucial for efficient computation. The choice of state ordering, however, is dependent on the solver used, as each solver may perform optimally with different matrix patterns. With a wide array of matrix reordering algorithms available, selecting the most suitable one becomes challenging without insights into the matrix's ideal configuration. To address this, the paper proposes a fully convolutional network (FCN) to evaluate the reordering potential of the A matrix into a bordered block diagonal (BBD) pattern, which is commonly observed in power system and IBR modeling. The FCN's assessment aims to streamline the solver's operation, which in turn could substantially reduce the computational time required to find a solution.

Xia, Qianxue↗
DOE OSTI2026

Linear complexity

We present factorization and solution phases for a new linear complexity direct solver designed for concurrent batch operations on fine-grained parallel architectures, for matrices amenable to hierarchical representation. We focus on the strong-admissibility-based $\mathscr{H}^{2}$ format, where strong recursive skeletonization factorization compresses remote interactions. We build upon previous implementations of $\mathscr{H}^{2}$ matrix construction for efficient factorization and solution algorithm design, which are illustrated graphically in stepwise detail. The algorithms are ‘blackbox’ in the sense that the only inputs are the matrix and right-hand side, without analytical or geometrical information about the origin of the system. We demonstrate linear complexity scaling in both time and memory on four representative families of dense matrices up to one million in size. Parallel scaling up to 16 threads is enabled by a multi-level matrix graph coloring and avoidance of dynamic memory allocations thanks to prefix-sum memory management. An experimental backward error analysis is included. We break down the timings of different phases, identify phases that are memory-bandwidth limited, and discuss alternatives for phases that may be sensitive to the trend to employ lower precisions for performance.

Boukaram, Wajih↗
DOE OSTI2024

Impact of Reordering on the LU Factorization Performance of Bordered Block-Diagonal Sparse Matrix

Power engineers rely on computer-based simulation tools to assess grid performance and ensure security. At the core of these tools are solvers for sparse linear equations. When transformed into a bordered block-diagonal (BBD) structure, part of the sparse linear equation solving can be parallelized. This work focuses on using the Schur-complement-based method for LU factorization on BBD matrices, specifically, Jacobian matrices from large-scale systems. Our findings show that the natural ordering method outperforms the default ordering method in computational performance for each block of the BBD matrix. This observation is validated using synthetic 25k-bus and 70k-bus cases, showing a speedup of up to 38% when using natural ordering without permutation. Additionally, the impact of the number of partitions is studied, and the result shows that computational performance improves with more, smaller partitions in the BBD matrices.

BBD matrix↗
DOE OSTI2020

A low-rank solver for the stochastic unsteady Navier–Stokes problem

Here we study a low-rank iterative solver for the unsteady Navier–Stokes equations for incompressible flows with a stochastic viscosity. The equations are discretized using the stochastic Galerkin method, and we consider an all-at-once formulation where the algebraic systems at all the time steps are collected and solved simultaneously. The problem is linearized with Picard’s method. To efficiently solve the linear systems at each step, we use low-rank tensor representations within the Krylov subspace method, which leads to significant reductions in storage requirements and computational costs. Combined with effective mean-based preconditioners and the idea of inexact solve, we show that only a small number of linear iterations are needed at each Picard step. The proposed algorithm is tested with a model of flow in a two-dimensional symmetric step domain with different settings to demonstrate the computational efficiency.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Design Considerations for GPU-based Mixed Integer Programming on Parallel Computing Platforms

Mixed Integer Programming (MIP) is a powerful abstraction in combinatorial optimization that finds real-life application across many significant sectors. The recent proliferation of graphical processing unit (GPU)-based accelerated computing architectures in large-scale parallel computing or supercomputing presents new opportunities as well as challenges in the advancement of MIP solver technology to effectively use the new accelerated computing platforms and scale to large parallel systems. Here, we recount the conventional processor-based strategies and focus on configurations where the most promising intersection lies between parallel MIP solver approaches and the specific strengths of accelerated parallel platforms. We note that the best potential lies in solving problems whose individual matrix sizes (of the linear program relaxation) fit entirely within one accelerator's memory and whose branch-and-bound (or branch-and-cut) trees cannot be fully contained within a small number of computational nodes. Additionally, we identify ideal features of computational linear algebra support on GPU accelerators that would help advance this direction of scalable parallel solution of MIP problems on GPU-based accelerated computing architectures.

Perumalla, Kalyan↗
NASA NTRS1989

Cooperative control of two active spacecraft during proximity operations

A cooperative autopilot is developed for the control of the relative attitude, relative position and absolute attitude of two maneuvering spacecraft during on orbit proximity operations. The autopilot consists of an open-loop trajectory solver which computes a nine dimensional linearized nominal state trajectory at the beginning of each maneuver and a phase space regulator which maintains the two spacecraft on the nominal trajectory during coast phases of the maneuver. A linear programming algorithm is used to perform jet selection. Simulation tests using a system of two space shuttle vehicles are performed to verify the performance of the cooperative controller and comparisons are made to a traditional passive target/active pursuit vehicle approach to proximity operations. The cooperative autopilot is shown to be able to control the two vehicle system when both the would be pursuit vehicle and the target vehicle are not completely controllable in six degrees of freedom. The cooperative controller is also shown to use as much as 37 percent less fuel and 57 percent fewer jet firings than a single pursuit vehicle during a simple docking approach maneuver.

Polutchko, Robert J.↗
NASA NTRS1994

Parallel implicit unstructured grid Euler solvers

A mesh-vertex finite volume scheme for solving the Euler equations on triangular unstructured meshes is implemented on an MIMD (multiple instruction/multiple data stream) parallel computer. An explicit four-stage Runge-Kutta scheme is used to solve two-dimensional flow problems. A family of implicit schemes is also developed to solve these problems, where the linear system that arises at each time step is solved by a preconditioned GMRES algorithm. Two partitioning strategies are employed, one that partitions triangles and the other that partitions vertices. The choice of the preconditioner in a distributed memory setting is discussed. All the methods are compared both in terms of elapsed times and convergence rates. It is shown that the implicit schemes offer adequate parallelism at the expense of minimal sequential overhead. The use of a global coarse grid to further minimize this overhead is also investigated. The schemes are implemented on a distributed memory parallel computer, the iPSC/860.

Venkatakrishnan, V.↗
NASA NTRS1994

Parallel implicit unstructured grid Euler solvers

A mesh-vertex finite volume scheme for solving the Euler equations on triangular unstructured meshes is implemented on a multiple-instruction/multiple-data stream parallel computer. An explicit four-stage Runge-Kutta scheme is used to solve two-dimensional flow problems. A family of implicit schemes is also developed to solve these problems, where the linear system that arises at each time step is solved by a preconditioned GMRES algorithm. Two partitioning strategies are employed: one that partitions triangles and the other that partitions vertices. The choice of the preconditioner in a distributed memory setting is discussed. All of the methods are compared both in terms of elapsed times and convergence rates. It is shown that the implicit schemes offer adequate parallelism at the expense of minimal sequential overhead. The use of a global coarse grid to further minimize this overhead is also investigated. The schemes are implemented on a distributed memory parallel computer, the Intel iPSC/860.

TRT-THEORETICAL↗