Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “direct solver”

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 37 records · Page 2
All sourcesNASA NTRSDOE OSTI
NASA NTRS1993

Extending substructure based iterative solvers to multiple load and repeated analyses

Direct solvers currently dominate commercial finite element structural software, but do not scale well in the fine granularity regime targeted by emerging parallel processors. Substructure based iterative solvers--often called also domain decomposition algorithms--lend themselves better to parallel processing, but must overcome several obstacles before earning their place in general purpose structural analysis programs. One such obstacle is the solution of systems with many or repeated right hand sides. Such systems arise, for example, in multiple load static analyses and in implicit linear dynamics computations. Direct solvers are well-suited for these problems because after the system matrix has been factored, the multiple or repeated solutions can be obtained through relatively inexpensive forward and backward substitutions. On the other hand, iterative solvers in general are ill-suited for these problems because they often must restart from scratch for every different right hand side. In this paper, we present a methodology for extending the range of applications of domain decomposition methods to problems with multiple or repeated right hand sides. Basically, we formulate the overall problem as a series of minimization problems over K-orthogonal and supplementary subspaces, and tailor the preconditioned conjugate gradient algorithm to solve them efficiently. The resulting solution method is scalable, whereas direct factorization schemes and forward and backward substitution algorithms are not. We illustrate the proposed methodology with the solution of static and dynamic structural problems, and highlight its potential to outperform forward and backward substitutions on parallel computers. As an example, we show that for a linear structural dynamics problem with 11640 degrees of freedom, every time-step beyond time-step 15 is solved in a single iteration and consumes 1.0 second on a 32 processor iPSC-860 system; for the same problem and the same parallel processor, a pair of forward/backward substitutions at each step consumes 15.0 seconds.

Farhat, Charbel↗
NASA NTRS1998

Parallel Directionally Split Solver Based on Reformulation of Pipelined Thomas Algorithm

In this research an efficient parallel algorithm for 3-D directionally split problems is developed. The proposed algorithm is based on a reformulated version of the pipelined Thomas algorithm that starts the backward step computations immediately after the completion of the forward step computations for the first portion of lines This algorithm has data available for other computational tasks while processors are idle from the Thomas algorithm. The proposed 3-D directionally split solver is based on the static scheduling of processors where local and non-local, data-dependent and data-independent computations are scheduled while processors are idle. A theoretical model of parallelization efficiency is used to define optimal parameters of the algorithm, to show an asymptotic parallelization penalty and to obtain an optimal cover of a global domain with subdomains. It is shown by computational experiments and by the theoretical model that the proposed algorithm reduces the parallelization penalty about two times over the basic algorithm for the range of the number of processors (subdomains) considered and the number of grid nodes per subdomain.

Povitsky, A.↗
NASA NTRS1992

Shape reanalysis and sensitivities utilizing preconditioned iterative boundary solvers

The computational advantages associated with the utilization of preconditined iterative equation solvers are quantified for the reanalysis of perturbed shapes using continuum structural boundary element analysis (BEA). Both single- and multi-zone three-dimensional problems are examined. Significant reductions in computer time are obtained by making use of previously computed solution vectors and preconditioners in subsequent analyses. The effectiveness of this technique is demonstrated for the computation of shape response sensitivities required in shape optimization. Computer times and accuracies achieved using the preconditioned iterative solvers are compared with those obtained via direct solvers and implicit differentiation of the boundary integral equations. It is concluded that this approach employing preconditioned iterative equation solvers in reanalysis and sensitivity analysis can be competitive with if not superior to those involving direct solvers.

Guru Prasad, K.↗
DOE OSTI2025

Hardware acceleration for HPS algorithms in two and three dimensions

We provide a flexible, open-source framework for hardware acceleration, namely massively-parallel execution on general-purpose graphics processing units (GPUs), applied to the hierarchical Poincaré–Steklov (HPS) family of algorithms for building fast direct solvers for linear elliptic partial differential equations. To take full advantage of the power of hardware acceleration, we propose two variants of HPS algorithms to improve performance on two- and three-dimensional problems. In the two-dimensional setting, we introduce a novel recomputation strategy that minimizes costly data transfers to and from the GPU; in three dimensions, we modify and extend the adaptive discretization technique of Geldermans and Gillman [1] to greatly reduce peak memory usage. We provide an open-source implementation of these methods written in JAX, a high-level accelerated linear algebra package, which allows for the first integration of a high-order fast direct solver with automatic differentiation tools. We conclude with extensive numerical examples showing our methods are fast and accurate on two- and three-dimensional problems.

Fast direct solvers↗
NASA NTRS2021

Evaluation of Higher-order Quadrature Schemes in Improving Computational Efficiency for Orientation-averaged Single-Scattering Properties of Nonspherical Ice Particles

We evaluate several high-order quadrature schemes for accuracy and efficacy in obtaining orientation-averaged single-scattering properties (SSPs). We use the highly efficient MIDAS to perform electromagnetic scattering calculations to evaluate the gain in efficiency from these schemes. MIDAS is shown to be superior to DDSCAT, a popular discrete dipole approximation (DDA) method. This study is motivated by the fact that quality physical precipitation retrievals rely on using accurate orientation-averaged SSPs derived from realistic hydrometeors as input to radiative transfer Models (RTMs). The DDA has been a popular choice for single-scattering calculations, due to its versatility with respect to target geometry. However, being iterative-solver-based (ISB), the most used DDA codes, e.g. DDSCAT and ADDA, must solve the scattering problem for each orientation of the target separately. As the size parameter and geometric anisotropy of the hydrometeor increase, the number of orientations needed to obtain accurate orientation-averages can increase drastically and so does the computation cost incurred by the ISB-DDA methods. MIDAS is a Direct-Solver-Based (DSB) code, its decomposition of the original large matrix with a high rank into multiple more manageable smaller matrices of lower ranks makes it much more computationally efficient while maintaining excellent accuracy. In addition, direct solvers consider all requested orientations at once, giving MIDAS further advantage over popular ISB-DDA methods. MIDAS, when combined with high-order quadrature for orientation averaging, can be greater than three orders of magnitude more efficient in obtaining RTM-ready SSPs of complex-shaped hydrometeors than existing ISB-DDA methods, with the native quadrature schemes they offer.

Ines Fenni↗
NASA NTRS1991

Parallel-vector computation for linear structural analysis and non-linear unconstrained optimization problems

Several parallel-vector computational improvements to the unconstrained optimization procedure are described which speed up the structural analysis-synthesis process. A fast parallel-vector Choleski-based equation solver, pvsolve, is incorporated into the well-known SAP-4 general-purpose finite-element code. The new code, denoted PV-SAP, is tested for static structural analysis. Initial results on a four processor CRAY 2 show that using pvsolve reduces the equation solution time by a factor of 14-16 over the original SAP-4 code. In addition, parallel-vector procedures for the Golden Block Search technique and the BFGS method are developed and tested for nonlinear unconstrained optimization. A parallel version of an iterative solver and the pvsolve direct solver are incorporated into the BFGS method. Preliminary results on nonlinear unconstrained optimization test problems, using pvsolve in the analysis, show excellent parallel-vector performance indicating that these parallel-vector algorithms can be used in a new generation of finite-element based structural design/analysis-synthesis codes.

Nguyen, D. T.↗
NASA NTRS2000

User's Manual for PCSMS (Parallel Complex Sparse Matrix Solver)

PCSMS (Parallel Complex Sparse Matrix Solver) is a computer code written to make use of the existing real sparse direct solvers to solve complex, sparse matrix linear equations. PCSMS converts complex matrices into real matrices and use real, sparse direct matrix solvers to factor and solve the real matrices. The solution vector is reconverted to complex numbers. Though, this utility is written for Silicon Graphics (SGI) real sparse matrix solution routines, it is general in nature and can be easily modified to work with any real sparse matrix solver. The User's Manual is written to make the user acquainted with the installation and operation of the code. Driver routines are given to aid the users to integrate PCSMS routines in their own codes.

Reddy, C. J.↗
DOE OSTI2022

High performance sparse multifrontal solvers on modern GPUs

Here, we have ported the numerical factorization and triangular solve phases of the sparse direct solver STRUMPACK to GPU. STRUMPACK implements sparse LU factorization using the multifrontal algorithm, which performs most of its operations in dense linear algebra operations on so-called frontal matrices of various sizes. Our GPU implementation off-loads these dense linear algebra operations, as well as the sparse scatter–gather operations between frontal matrices. For the larger frontal matrices, our GPU implementation relies on vendor libraries such as cuBLAS and cuSOLVER for NVIDIA GPUs and rocBLAS and rocSOLVER for AMD GPUs. For the smaller frontal matrices we developed custom CUDA and HIP kernels to reduce kernel launch overhead. Overall, high performance is achieved by identifying submatrix factorizations corresponding to sub-trees of the multifrontal assembly tree which fit entirely in GPU memory. The multi-GPU setting uses SLATE (Software for Linear Algebra Targeting Exascale) as a modern GPU-aware replacement for ScaLAPACK. On 4 nodes of SUMMIT the code runs ~10X faster when using all 24 V100 GPUs compared to when it only uses the 168 POWER9 cores. On 8 SUMMIT nodes, using 48 V100 GPUs, the sparse solver reaches over 50TFlop/s. Compared to SuperLU, on a single V100, for a set of 17 matrices our implementation is faster for all but one matrix, and is on average 5X (median 4X) faster

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

xSDK-batched Subcontract - Ginkgo Batched Iterative Solver Development (Final Report)

Iterative solvers are fundamentally different from direct solvers in terms of execution as they generally do not execute a pre-defined sequence of operations or steps, but adapt the number of iterations to the specific problem and the preset solution quality. Generally, the adaptation of the iteration count to the problem is realized by monitoring the solver convergence and stopping the iteration process once the monitored metric, e.g., the residual norm, hits a pre-defined threshold. When addressing a set of problems with different properties, it is necessary to monitor the threshold for each problem individually and break up the SIMD execution style to avoid excess iterations for “easier” problems. Ginkgo integrates a simple but customizable stopping criterion for the residual norm and generally uses a pre-defined (relative or absolute) residual norm as the stopping criterion. In order to avoid the overhead of launching a kernel at every iteration, the iteration convergence and iteration control is part of the solver kernel. Each thread maintains its own copy of the iteration count.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1991

Comparing direct and iterative equation solvers in a large structural analysis software system

Two direct Choleski equation solvers and two iterative preconditioned conjugate gradient (PCG) equation solvers used in a large structural analysis software system are described. The two direct solvers are implementations of the Choleski method for variable-band matrix storage and sparse matrix storage. The two iterative PCG solvers include the Jacobi conjugate gradient method and an incomplete Choleski conjugate gradient method. The performance of the direct and iterative solvers is compared by solving several representative structural analysis problems. Some key factors affecting the performance of the iterative solvers relative to the direct solvers are identified.

Poole, E. L.↗
DOE OSTI2024

Large-scale harmonic balance simulations with Krylov subspace and preconditioner recycling

The multi-harmonic balance method combined with numerical continuation provides an efficient framework to compute a family of time-periodic solutions, or response curves, for large-scale, nonlinear mechanical systems. The predictor and corrector steps repeatedly solve a sequence of linear systems that scale by the model size and number of harmonics in the assumed Fourier series approximation. In this paper, a novel Newton–Krylov iterative method is embedded within the multi-harmonic balance and continuation algorithm to efficiently compute the approximate solutions from the sequence of linear systems that arise during the prediction and correction steps. Further, the method recycles, or reuses, both the preconditioner and the Krylov subspace generated by previous linear systems in the solution sequence. A delayed frequency preconditioner refactorizes the preconditioner only when the performance of the iterative solver deteriorates. The GCRO-DR iterative solver recycles a subset of harmonic Ritz vectors to initialize the solution subspace for the next linear system in the sequence. The performance of the iterative solver is demonstrated on two exemplars with contact-type nonlinearities and benchmarked against a direct solver with traditional Newton–Raphson iterations.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1993

Implementing abstract multigrid or multilevel methods

Multigrid methods can be formulated as an algorithm for an abstract problem that is independent of the partial differential equation, domain, and discretization method. In such an abstract setting, problems not arising from partial differential equations can be treated. A general theory exists for linear problems. The general theory was motivated by a series of abstract solvers (Madpack). The latest version was motivated by the theory. Madpack now allows for a wide variety of iterative and direct solvers, preconditioners, and interpolation and projection schemes, including user callback ones. It allows for sparse, dense, and stencil matrices. Mildly nonlinear problems can be handled. Also, there is a fast, multigrid Poisson solver (two and three dimensions). The type of solvers and design decisions (including language, data structures, external library support, and callbacks) are discussed. Based on the author's experiences with two versions of Madpack, a better approach is proposed. This is based on a mixed language formulation (C and FORTRAN + preprocessor). Reasons for not using FORTRAN, C, or C++ (individually) are given. Implementing the proposed strategy is not difficult.

Douglas, Craig C.↗
NASA NTRS2001

Challenges Facing Design and Analysis Tools

The design and analysis of future aerospace systems will strongly rely on advanced engineering analysis tools used in combination with risk mitigation procedures. The implications of such a trend place increased demands on these tools to assess off-nominal conditions, residual strength, damage propagation, and extreme loading conditions in order to understand and quantify these effects as they affect mission success. Advances in computer hardware such as CPU processing speed, memory, secondary storage, and visualization provide significant resources for the engineer to exploit in engineering design. The challenges facing design and analysis tools fall into three primary areas. The first area involves mechanics needs such as constitutive modeling, contact and penetration simulation, crack growth prediction, damage initiation and progression prediction, transient dynamics and deployment simulations, and solution algorithms. The second area involves computational needs such as fast, robust solvers, adaptivity for model and solution strategies, control processes for concurrent, distributed computing for uncertainty assessments, and immersive technology. Traditional finite element codes still require fast direct solvers which when coupled to current CPU power enables new insight as a result of high-fidelity modeling. The third area involves decision making by the analyst. This area involves the integration and interrogation of vast amounts of information - some global in character while local details are critical and often drive the design. The proposed presentation will describe and illustrate these areas using composite structures, energy-absorbing structures, and inflatable space structures. While certain engineering approximations within the finite element model may be adequate for global response prediction, they generally are inadequate in a design setting or when local response prediction is critical. Pitfalls to be avoided and trends for emerging analysis tools will be described.

Knight, Norman F., Jr.↗
DOE OSTI2021

Considering computational speed vs. accuracy: Choosing appropriate mesoscale RVE boundary conditions

Modeling a material’s microstructure using continuum theories allows for inspection of the relationship between coarse scale and fine scale behaviors. Computational limits generally require selection of a sub-volume from a bulk sample in order to directly model the microstructure. Boundary conditions are applied to the sub-volume to mimic the excluded bulk material. Appropriate selection of boundary conditions helps effectively determine the appropriate spatial scale required of the sub-volume. Applicable boundary conditions include direct displacement, periodic, and uniform traction. While direct displacement and periodic boundary conditions are commonly used, uniform traction boundary conditions have seen limited use due to rigid body stability issues in simulations of compression or shear deformation. A new application of uniform traction boundary conditions was developed through linear constraint equations, similar to approaches employed by direct displacement and periodic boundary conditions, to quench rigid body motions with minimal interference of the relative deformation of the model. These boundary conditions were tested by compressing several synthetically generated periodic microstructures using the finite element method. Evaluating the effective stiffness along the compression axis, the direct displacement boundary condition produced the stiffest response, whereas the uniform traction boundary condition produced the most compliant. Periodic boundary conditions produced the same response for all volumes analyzed and both the direct displacement and uniform traction boundary conditions trended toward the periodic response as the domain volume increased. Computational performance was also evaluated for each boundary condition using implicit and explicit solvers. Direct displacement boundary conditions presented the lowest computational cost of all of the boundary conditions followed by periodic then uniform traction. The computational expense of periodic and uniform traction boundary conditions limited the viable spatial scale and mesh resolutions able to be simulated. Selection of appropriate boundary conditions for specific uses need to be a balance between allowable computational expense and accuracy of the method. Techniques for evaluating which boundary conditions to use are discussed.

42 ENGINEERING↗
NASA NTRS1992

Optimum design of ninety degree bends

An algorithm for the optimum design of an internal flow component to obtain the maximum pressure rise is presented. Maximum pressure rise in a duct with simultaneous turning and diffusion is shown to be related to the control of flow separation on the passage walls. Such a flow is usually associated with downstream conditions that are desirable in turbomachinery and propulsion applications to ensure low loss and stable performance. The algorithm requires the solution of an 'adjoint' problem in addition to the 'direct' equations governing the flow in a body, which in the present analysis are assumed to be the laminar Navier-Stokes equations. The theoretical framework and computational algorithms presented in this study are for the steady Navier-Stokes equations. A procedure is developed for the numerical solution of the adjoint equations. This procedure is coupled with a direct solver in a design iteration loop, that provides a new shape with a higher pressure rise. This procedure is first validated for the design of optimum plane diffusers in two-dimensional flow. The direct Navier-Stokes and the 'adjoint' equations are solved using a finite volume formulation for spatial discretization in an artificial compressibility framework. A simplified version of the above approach is then utilized to design ninety degree diffusing bends. Calculations were carried out for a mean radius ratio at inlet of 2.5 and Reynolds numbers varying from 100 to 500. While at this stage laminar flows is assumed, it is shown that a similar approach can be conceived for turbulent flows.

Modi, Vijay↗
DOE OSTI2023

Batched Sparse Linear Algebra (Final Report for Subcontract B648960)

This report finalizes design specifications for developing batched kernels for small tensor operations for unassembled matrix-free iterative solvers, batched solvers for partially assembled operators, and batched solvers with support for various sparse formats. The outcome of the project milestones is a set of interfaces to Batched Sparse LA solvers running on hardware accelerators for use in ECP Libraries and Applications. It is part of the development of sparse batched kernels, solvers/preconditioners as well as creating interoperability in xSDK libraries with sparse and dense batched functions to benefit ECP applications. The participants included representatives from ECP libraries (not limited to the xSDK project), applications, and vendors (AMD, Intel, and NVIDIA). Batched sparse linear algebra solvers form the new frontier for algorithmic development and performance engineering. Many applications (ECP and non-ECP alike) require simultaneous solutions of small linear systems of equations that are structurally sparse. To move towards high hardware utilization, it is important to provide these applications with appropriate interfaces to efficient batched sparse solvers running on modern hardware accelerators. We present interface designs in use by HPC software libraries supporting batched sparse linear algebra and the development of sparse batched kernel codes for solvers and preconditioners. We also address the potential interoperability opportunities to keep the software portable between the major hardware accelerators from AMD, Intel, and NVIDIA. The presented interface specifications includes batched band, sparse iterative, and sparse direct solvers. This report summarizes progress in Kokkos Kernels and the xSDK libraries MAGMA, Ginkgo, hypre, SUNDIALS, and SuperLU_dist.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1990

A multigrid solver for semi-implicit global shallow-water models

A multigrid solver is developed for the discretized two-dimensional elliptic equation on the sphere that arises from a semiimplicit time discretization of the global shallow-water equations. Different formulations of the semiimplicit scheme result in variable-coefficient Helmholtz-type equations for which no fast direct solvers are available. The efficiency of the multigrid solver is optimal, in the sense that the total operation count is proportional to the number of unknowns. Numerical experiments using initial data derived from actual 300-mb height and wind velocity fields indicate that the present model has very good accuracy and stability properties.

Barros, Saulo R. M.↗