Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Sparse linear systems”

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 55 records · Page 3
All sourcesNASA NTRSDOE OSTI
NASA NTRS1992

An incremental strategy for calculating consistent discrete CFD sensitivity derivatives

In this preliminary study involving advanced computational fluid dynamic (CFD) codes, an incremental formulation, also known as the 'delta' or 'correction' form, is presented for solving the very large sparse systems of linear equations which are associated with aerodynamic sensitivity analysis. For typical problems in 2D, a direct solution method can be applied to these linear equations which are associated with aerodynamic sensitivity analysis. For typical problems in 2D, a direct solution method can be applied to these linear equations in either the standard or the incremental form, in which case the two are equivalent. Iterative methods appear to be needed for future 3D applications; however, because direct solver methods require much more computer memory than is currently available. Iterative methods for solving these equations in the standard form result in certain difficulties, such as ill-conditioning of the coefficient matrix, which can be overcome when these equations are cast in the incremental form; these and other benefits are discussed. The methodology is successfully implemented and tested in 2D using an upwind, cell-centered, finite volume formulation applied to the thin-layer Navier-Stokes equations. Results are presented for two laminar sample problems: (1) transonic flow through a double-throat nozzle; and (2) flow over an isolated airfoil.

Korivi, Vamshi Mohan↗
NASA NTRS1993

Methodology for sensitivity analysis, approximate analysis, and design optimization in CFD for multidisciplinary applications

In this study involving advanced fluid flow codes, an incremental iterative formulation (also known as the delta or correction form) together with the well-known spatially-split approximate factorization algorithm, is presented for solving the very large sparse systems of linear equations which are associated with aerodynamic sensitivity analysis. For smaller 2D problems, a direct method can be applied to solve these linear equations in either the standard or the incremental form, in which case the two are equivalent. Iterative methods are needed for larger 2D and future 3D applications, however, because direct methods require much more computer memory than is currently available. Iterative methods for solving these equations in the standard form are generally unsatisfactory due to an ill-conditioning of the coefficient matrix; this problem can be overcome when these equations are cast in the incremental form. These and other benefits are discussed. The methodology is successfully implemented and tested in 2D using an upwind, cell-centered, finite volume formulation applied to the thin-layer Navier-Stokes equations. Results are presented for two sample airfoil problems: (1) subsonic low Reynolds number laminar flow; and (2) transonic high Reynolds number turbulent flow.

Taylor, Arthur C., III↗
NASA NTRS1996

Methodology for Sensitivity Analysis, Approximate Analysis, and Design Optimization in CFD for Multidisciplinary Applications

An incremental iterative formulation together with the well-known spatially split approximate-factorization algorithm, is presented for solving the large, sparse systems of linear equations that are associated with aerodynamic sensitivity analysis. This formulation is also known as the 'delta' or 'correction' form. For the smaller two dimensional problems, a direct method can be applied to solve these linear equations in either the standard or the incremental form, in which case the two are equivalent. However, iterative methods are needed for larger two-dimensional and three dimensional applications because direct methods require more computer memory than is currently available. Iterative methods for solving these equations in the standard form are generally unsatisfactory due to an ill-conditioned coefficient matrix; this problem is overcome when these equations are cast in the incremental form. The methodology is successfully implemented and tested using an upwind cell-centered finite-volume formulation applied in two dimensions to the thin-layer Navier-Stokes equations for external flow over an airfoil. In three dimensions this methodology is demonstrated with a marching-solution algorithm for the Euler equations to calculate supersonic flow over the High-Speed Civil Transport configuration (HSCT 24E). The sensitivity derivatives obtained with the incremental iterative method from a marching Euler code are used in a design-improvement study of the HSCT configuration that involves thickness. camber, and planform design variables.

Taylor, Arthur C., III↗
NASA NTRS1976

A variant of nested dissection for solving n by n grid problems

Nested dissection orderings are known to be very effective for solving the sparse positive definite linear systems which arise from n by n grid problems. In this paper nested dissection is shown to be the final step of incomplete nested dissection, an ordering which corresponds to the premature termination of dissection. Analyses of the arithmetic and storage requirements for incomplete nested dissection are given, and the ordering is shown to be competitive with nested dissection under certain conditions.

George, A.↗
NASA NTRS1978

Incomplete nested dissection for solving n by n grid problems

Nested dissection orderings are known to be very effective for solving sparse positive definite linear systems which arise from n by n grid problems. In this paper we consider incomplete nested dissection, an ordering which corresponds to the premature termination of nested dissection. Analyses of the arithmetic and storage requirements for incomplete nested dissection are given and the ordering is shown to be competitive with nested dissection with regard to arithmetic operations and superior to that ordering in storage requirements.

George, A.↗
NASA NTRS1978

Analysis of dissection algorithms for vector computers

Recently two dissection algorithms (one-way and incomplete nested dissection) have been developed for solving the sparse positive definite linear systems arising from n by n grid problems. Concurrently, vector computers (such as the CDC STAR-100 and TI ASC) have been developed for large scientific applications. An analysis of the use of dissection algorithms on vector computers dictates that vectors of maximum length be utilized thereby implying little or no dissection; on the other hand, minimizing operation counts suggest that considerable dissection be performed. In this paper we discuss the resolution of this conflict by minimizing the total time required by vectorized versions of the two algorithms.

George, A.↗
NASA NTRS1987

Automated problem scheduling and reduction of synchronization delay effects

It is anticipated that in order to make effective use of many future high performance architectures, programs will have to exhibit at least a medium grained parallelism. A framework is presented for partitioning very sparse triangular systems of linear equations that is designed to produce favorable preformance results in a wide variety of parallel architectures. Efficient methods for solving these systems are of interest because: (1) they provide a useful model problem for use in exploring heuristics for the aggregation, mapping and scheduling of relatively fine grained computations whose data dependencies are specified by directed acrylic graphs, and (2) because such efficient methods can find direct application in the development of parallel algorithms for scientific computation. Simple expressions are derived that describe how to schedule computational work with varying degrees of granularity. The Encore Multimax was used as a hardware simulator to investigate the performance effects of using the partitioning techniques presented in shared memory architectures with varying relative synchronization costs.

Saltz, Joel H.↗
NASA NTRS1987

Optimal pre-scheduling of problem remappings

A large class of scientific computational problems can be characterized as a sequence of steps where a significant amount of computation occurs each step, but the work performed at each step is not necessarily identical. Two good examples of this type of computation are: (1) regridding methods which change the problem discretization during the course of the computation, and (2) methods for solving sparse triangular systems of linear equations. Recent work has investigated a means of mapping such computations onto parallel processors; the method defines a family of static mappings with differing degrees of importance placed on the conflicting goals of good load balance and low communication/synchronization overhead. The performance tradeoffs are controllable by adjusting the parameters of the mapping method. To achieve good performance it may be necessary to dynamically change these parameters at run-time, but such changes can impose additional costs. If the computation's behavior can be determined prior to its execution, it can be possible to construct an optimal parameter schedule using a low-order-polynomial-time dynamic programming algorithm. Since the latter can be expensive, the performance is studied of the effect of a linear-time scheduling heuristic on one of the model problems, and it is shown to be effective and nearly optimal.

Nicol, David M.↗
NASA NTRS1990

Implementation of two projection methods on a shared memory multiprocessor - DEC VAX 6240

The relative performance of two iterative schemes, based on projection techniques, is compared on a shared memory multiprocessor - VAX 6240. The CG accelerated Block-SSOR method and the CG accelerated Symmetric-Kaczmarz method are considered for the solution of large sparse nonsymmetric systems of linear equations. It is shown that the regular structure of many matrices can be exploited by the CG-accelerated Block-SSOR method to provide good speedup in a multiprocessing environment. However, the CG accelerated Symmetric-Kaczmarz method, while being a viable alternative on a scalar machine, is unable to benefit from multiprocessing.

Kamath, C.↗
NASA NTRS1994

Preconditioned domain decomposition scheme for three-dimensional aerodynamic sensitivity analysis

A discrete sensitivity analysis algorithm had previously been developed and applied to two-dimensional aerodynamic optimization problems, where the computational domains were discretized by using single grids. The sparse, unsymmetric systems of linear equations resulting from this algorithm were solved by a direct matrix inversion matrix. However, for large two-dimensional problems and, practically, all three-dimensional problems, direct inversion methods become inapplicable, primarily due to the prohibitive computer storage needed. In an attempt to alleviate such hindrances, the sensitivity analysis with domain decomposition (SADD) scheme was developed. This scheme divides the computational domain into smaller and nonoverlapping subdomains (multiblock grids) that are solved separately. Then, the final solution is constructed from the subdomain solutions. As the number of grid points in the interface boundaries of the subdomains becomes large, the computer memory required to store the effective coefficient matrix of these interface points starts to increase. Presented in this Technical Note is a preconditioned iterative procedure to overcome this particular problem.

Eleshaky, Mohamed E.↗
NASA NTRSDate not supplied

Efficient Parametric Uncertainty Analysis of an Earth Entry Vehicle Concept Using Least Angle Regression

The objective of this work was to outline and apply an efficient and accurate parametric un-certainty propagation approach to the analysis of convective heating on an Earth entry vehicle concept. The described approach was based on Least Angle Regression used to solve a sparse and underdetermined linear system in the point-collocation non-intrusive polynomial chaos surrogate method. This approach involved an iterative process to computing the non-zero terms of the underlying polynomial chaos model using only enough samples to converge uncertainty interval predictions and Sobol index values based global nonlinear sensitivity estimates. The Earth entry vehicle was analyzed at three points along a representative trajectory for a Mars return mission. 329 sources of uncertainty were identified in the computational fluid dynamics model used to predict the forebody convective heating. These included uncertainty in flow field chemical rates, collision integrals, heats of formation, surface finite rate char model reaction rates, wall roughness height, and the turbulent Schmidt number. Results from this study showed that convective heating uncertainty as high as 50% of the nominal was predicted with only about 50 evaluations of the computational model. This was far fewer than would be required for a sampling-based approach or a full basis polynomial chaos model, which would have required over 50,000 samples. Additionally, results showed that over 90% of the total convective heating uncertainty was due to uncertainty in the N2catalytic rate on the surface, while the remainder of the uncertainty was attributed to the turbulent Schmidt number and the wall roughness uncertainties.

Thomas K West IV↗
NASA NTRS1972

Elimination on sparse symmetric systems of a special structure.

Consideration of the problem of finding a permutation of rows and columns and an algorithm for solving ordered systems of linear algebraic equations with sparse matrices having a certain regular structure. Two approaches to the solution of this problem, in which the sparsity is used to some extent, are outlined. One of them is a very general approach where optimal (or nearly optimal) ordering is sought and the algorithm for solving the ordered system treats the matrix element by element to perform only necessary operations. The other approach involves the use of band matrices. After comparing these two approaches, a third approach is then suggested which involves the use of pipe matrices, and a means of ordering the rows and columns to obtain this type of matrix is presented. Examples of matrices reordered by the proposed procedure are cited.

Segethova, J.↗
NASA NTRS1977

Timing formulas for dissection algorithms on vector computers

The use of the finite element and finite difference methods often leads to the problem of solving large, sparse, positive definite systems of linear equations. MACSYMA plays a major role in the generation of formulas representing the time required for execution of the dissection algorithms. The use of MACSYMA in the generation of those formulas is described.

Poole, W. G., Jr.↗
NASA NTRS1991

An implementation of the look-ahead Lanczos algorithm for non-Hermitian matrices

The nonsymmetric Lanczos method can be used to compute eigenvalues of large sparse non-Hermitian matrices or to solve large sparse non-Hermitian linear systems. However, the original Lanczos algorithm is susceptible to possible breakdowns and potential instabilities. An implementation is presented of a look-ahead version of the Lanczos algorithm that, except for the very special situation of an incurable breakdown, overcomes these problems by skipping over those steps in which a breakdown or near-breakdown would occur in the standard process. The proposed algorithm can handle look-ahead steps of any length and requires the same number of matrix-vector products and inner products as the standard Lanczos process without look-ahead.

Freund, Roland W.↗
NASA NTRS1990

An implementation of the look-ahead Lanczos algorithm for non-Hermitian matrices, part 1

The nonsymmetric Lanczos method can be used to compute eigenvalues of large sparse non-Hermitian matrices or to solve large sparse non-Hermitian linear systems. However, the original Lanczos algorithm is susceptible to possible breakdowns and potential instabilities. We present an implementation of a look-ahead version of the Lanczos algorithm which overcomes these problems by skipping over those steps in which a breakdown or near-breakdown would occur in the standard process. The proposed algorithm can handle look-ahead steps of any length and is not restricted to steps of length 2, as earlier implementations are. Also, our implementation has the feature that it requires roughly the same number of inner products as the standard Lanczos process without look-ahead.

Freund, Roland W.↗
NASA NTRS1990

An implementation of the look-ahead Lanczos algorithm for non-Hermitian matrices, part 2

It is shown how the look-ahead Lanczos process (combined with a quasi-minimal residual QMR) approach) can be used to develop a robust black box solver for large sparse non-Hermitian linear systems. Details of an implementation of the resulting QMR algorithm are presented. It is demonstrated that the QMR method is closely related to the biconjugate gradient (BCG) algorithm; however, unlike BCG, the QMR algorithm has smooth convergence curves and good numerical properties. We report numerical experiments with our implementation of the look-ahead Lanczos algorithm, both for eigenvalue problem and linear systems. Also, program listings of FORTRAN implementations of the look-ahead algorithm and the QMR method are included.

Freund, Roland W.↗
NASA NTRS2016

An Optimized Multicolor Point-Implicit Solver for Unstructured Grid Applications on Graphics Processing Units

In the field of computational fluid dynamics, the Navier-Stokes equations are often solved using an unstructuredgrid approach to accommodate geometric complexity. Implicit solution methodologies for such spatial discretizations generally require frequent solution of large tightly-coupled systems of block-sparse linear equations. The multicolor point-implicit solver used in the current work typically requires a significant fraction of the overall application run time. In this work, an efficient implementation of the solver for graphics processing units is proposed. Several factors present unique challenges to achieving an efficient implementation in this environment. These include the variable amount of parallelism available in different kernel calls, indirect memory access patterns, low arithmetic intensity, and the requirement to support variable block sizes. In this work, the solver is reformulated to use standard sparse and dense Basic Linear Algebra Subprograms (BLAS) functions. However, numerical experiments show that the performance of the BLAS functions available in existing CUDA libraries is suboptimal for matrices representative of those encountered in actual simulations. Instead, optimized versions of these functions are developed. Depending on block size, the new implementations show performance gains of up to 7x over the existing CUDA library functions.

Zubair, Mohammad↗
NASA NTRS1983

M-step preconditioned conjugate gradient methods

Preconditioned conjugate gradient methods for solving sparse symmetric and positive finite systems of linear equations are described. Necessary and sufficient conditions are given for when these preconditioners can be used and an analysis of their effectiveness is given. Efficient computer implementations of these methods are discussed and results on the CYBER 203 and the Finite Element Machine under construction at NASA Langley Research Center are included.

Adams, L.↗