Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “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 1,189 records · Page 66
All sourcesNASA NTRSDOE OSTI
NASA NTRS1992

Mapping unstructured grid computations to massively parallel computers

Investigated here is this mapping problem: assign the tasks of a parallel program to the processors of a parallel computer such that the execution time is minimized. First, a taxonomy of objective functions and heuristics used to solve the mapping problem is presented. Next, we develop a highly parallel heuristic mapping algorithm, called Cyclic Pairwise Exchange (CPE), and discuss its place in the taxonomy. CPE uses local pairwise exchanges of processor assignments to iteratively improve an initial mapping. A variety of initial mapping schemes are tested and recursive spectral bipartitioning (RSB) followed by CPE is shown to result in the best mappings. For the test cases studied here, problems arising in computational fluid dynamics and structural mechanics on unstructured triangular and tetrahedral meshes, RSB and CPE outperform methods based on simulated annealing. Much less time is required to do the mapping and the results obtained are better. Compared with random and naive mappings, RSB and CPE reduce the communication time two fold for the test problems used. Finally, we use CPE in two applications on a CM-2. The first application is a data parallel mesh-vertex upwind finite volume scheme for solving the Euler equations on 2-D triangular unstructured meshes. CPE is used to map grid points to processors. The performance of this code is compared with a similar code on a Cray-YMP and an Intel iPSC/860. The second application is parallel sparse matrix-vector multiplication used in the iterative solution of large sparse linear systems of equations. We map rows of the matrix to processors and use an inner-product based matrix-vector multiplication. We demonstrate that this method is an order of magnitude faster than methods based on scan operations for our test cases.

Hammond, Steven Warren↗
NASA NTRS1991

Characterization of frequency standard instability by estimation of their covariance matrix

The popular 3-cornered hat method used for evaluating the noise contributions of individual frequency standards is revisited. This method is used in several cases, but sometimes the results are not consistent because one or more estimated clock variances turn out to be negative. Different causes of this unacceptable result have been conjectured: among them one regards the hypothesis of uncorrelated clocks, essential in this method. Since recently realistic cases of correlation between clocks, mainly due to the environmental conditions, have been observed, this paper proposes an entirely revisited version of the 3-cornered hat method which permits to evaluate the individual variances and also the possible covariances between clocks, by relaxing the hypothesis of uncorrelation. The uncertainty and the lack of contemporaneity of the measurement series are assumed to be negligible. The lack of the uncorrelation hypothesis calls for a more general mathematical model leading to an underdetermined linear system. The estimates of the (co)variances of the measurement series us well us those of the individual clocks are introduced by means of the scalar product of the related time series and arranged in the respective covariance matrices S and R. Since covariance matrix is positive definite by definition, the problem consists in estimating the unknown R, subject to the constraint of positive definiteness, from the known S. Unfortunately, this constraint is not sufficient to estimate R. Therefore a suitable optimization criterion is proposed, which assures the positive definiteness of R and, at the same time, minimizes the global correlation among clocks. Examples of frequency instability measurements processed by the "classical" 3-cornered hat method and the here-revisited method are presented showing that the solutions are identical only when the uncorrelation hypothesis doesn't violate the positive definiteness of R.

PatriziaTravella↗
NASA NTRS1991

Parallel variable-band Choleski solvers for computational structural analysis applications on vector multiprocessor supercomputers

A Choleski method used to solve linear systems of equations that arise in large scale structural analyses is described. The method uses a novel variable-band storage scheme and is structured to exploit fast local memory caches while minimizing data access delays between main memory and vector registers. Several parallel implementations of this method are described for the CRAY-2 and CRAY Y-MP computers demonstrating the use of microtasking and autotasking directives. A portable parallel language, FORCE, is also used for two different parallel implementations, demonstrating the use of CRAY macrotasking. Results are presented comparing the matrix factorization times for three representative structural analysis problems from runs made in both dedicated and multi-user modes on both the CRAY-2 and CRAY Y-MP computers. CPU and wall clock timings are given for the various parallel methods and are compared to single processor timings of the same algorithm. Computation rates over 1 GIGAFLOP (1 billion floating point operations per second) on a four processor CRAY-2 and over 2 GIGAFLOPS on an eight processor CRAY Y-MP are demonstrated as measured by wall clock time in a dedicated environment. Reduced wall clock times for the parallel methods relative to the single processor implementation of the same Choleski algorithm are also demonstrated for runs made in multi-user mode.

Poole, E. L.↗
NASA NTRS1992

Application of a generalized minimal residual method to 2D unsteady flows

A generalized minimum residual scheme (GMRES), previously developed for solving nonlinear and linear systems of equations, has been applied to the numerical solution of 2D unsteady compressible flows. It is found that the use of GMRES significantly increases the time step that may be used, compared to noniterative implicit schemes. The feasibility of reducing the memory requirements of the GMRES scheme using a multigrid strategy has also been explored. Several sample steady and unsteady viscous flow applications are presented.

Hixon, Ray↗
NASA NTRS1993

Preconditioned conjugate-gradient methods for low-speed flow calculations

An investigation is conducted into the viability of using a generalized Conjugate Gradient-like method as an iterative solver to obtain steady-state solutions of very low-speed fluid flow problems. Low-speed flow at Mach 0.1 over a backward-facing step is chosen as a representative test problem. The unsteady form of the two dimensional, compressible Navier-Stokes equations is integrated in time using discrete time-steps. The Navier-Stokes equations are cast in an implicit, upwind finite-volume, flux split formulation. The new iterative solver is used to solve a linear system of equations at each step of the time-integration. Preconditioning techniques are used with the new solver to enhance the stability and convergence rate of the solver and are found to be critical to the overall success of the solver. A study of various preconditioners reveals that a preconditioner based on the Lower-Upper Successive Symmetric Over-Relaxation iterative scheme is more efficient than a preconditioner based on Incomplete L-U factorizations of the iteration matrix. The performance of the new preconditioned solver is compared with a conventional Line Gauss-Seidel Relaxation (LGSR) solver. Overall speed-up factors of 28 (in terms of global time-steps required to converge to a steady-state solution) and 20 (in terms of total CPU time on one processor of a CRAY-YMP) are found in favor of the new preconditioned solver, when compared with the LGSR solver.

Ajmani, Kumud↗
NASA NTRS1991

Path planning for assembly of strut-based structures

A path planning method with collision avoidance for a general single chain nonredundant or redundant robot is proposed. Joint range boundary overruns are also avoided. The result is a sequence of joint vectors which are passed to a trajectory planner. A potential field algorithm in joint space computes incremental joint vectors delta-q = delta-q(sub a) + delta-q(sub c) + delta-q(sub r). Adding delta-q to the robot's current joint vector leads to the next step in the path. Delta-q(sub a) is obtained by computing the minimum norm solution of the underdetermined linear system J delta-q(sub a) = x(sub a) where x(sub a) is a translational and rotational force vector that attracts the robot to its goal position and orientation. J is the manipulator Jacobian. Delta-q(sub c) is a collision avoidance term encompassing collisions between the robot (links and payload) and obstacles in the environment as well as collisions among links and payload of the robot themselves. It is obtained in joint space directly. Delta-q(sub r) is a function of the current joint vector and avoids joint range overruns. A higher level discrete search over candidate safe positions is used to provide alternatives in case the potential field algorithm encounters a local minimum and thus fails to reach the goal. The best first search algorithm A* is used for graph search. Symmetry properties of the payload and equivalent rotations are exploited to further enlarge the number of alternatives passed to the potential field algorithm.

Muenger, Rolf↗
NASA NTRS1993

Galilean covariant harmonic oscillator

A Galilean covariant approach to classical mechanics of a single particle is described. Within the proposed formalism, all non-covariant force laws defining acting forces which become to be defined covariantly by some differential equations are rejected. Such an approach leads out of the standard classical mechanics and gives an example of non-Newtonian mechanics. It is shown that the exactly solvable linear system of differential equations defining forces contains the Galilean covariant description of harmonic oscillator as its particular case. Additionally, it is demonstrated that in Galilean covariant classical mechanics the validity of the second Newton law of dynamics implies the Hooke law and vice versa. It is shown that the kinetic and total energies transform differently with respect to the Galilean transformations.

Horzela, Andrzej↗
NASA NTRS1993

Preconditioned Conjugate Gradient methods for low speed flow calculations

An investigation is conducted into the viability of using a generalized Conjugate Gradient-like method as an iterative solver to obtain steady-state solutions of very low-speed fluid flow problems. Low-speed flow at Mach 0.1 over a backward-facing step is chosen as a representative test problem. The unsteady form of the two dimensional, compressible Navier-Stokes equations are integrated in time using discrete time-steps. The Navier-Stokes equations are cast in an implicit, upwind finite-volume, flux split formulation. The new iterative solver is used to solve a linear system of equations at each step of the time-integration. Preconditioning techniques are used with the new solver to enhance the stability and the convergence rate of the solver and are found to be critical to the overall success of the solver. A study of various preconditioners reveals that a preconditioner based on the lower-upper (L-U)-successive symmetric over-relaxation iterative scheme is more efficient than a preconditioner based on incomplete L-U factorizations of the iteration matrix. The performance of the new preconditioned solver is compared with a conventional line Gauss-Seidel relaxation (LGSR) solver. Overall speed-up factors of 28 (in terms of global time-steps required to converge to a steady-state solution) and 20 (in terms of total CPU time on one processor of a CRAY-YMP) are found in favor of the new preconditioned solver, when compared with the LGSR solver.

Ajmani, Kumud↗
NASA NTRS1992

Initial value and two point boundary value solutions to the Clohessy-Wiltshire equations

The nonhomogeneous Clohessy-Wiltshire (C-W) equations are formulated and solved as an initial value problem in the form structure of linear systems theory. The state transition matrix (STM) and its inverse are obtained explicitly in both Newtonian and Hamiltonian form. It is shown that the STM for the C-2 equations possesses a special property making its inverse easily obtainable. Since solutions to the C-W equations are needed in two-point boundary value form to construct a good mission design tool for orbit transfer, the Lambert problem is solved in the context of the C-W equations.

Mullins, Larry D.↗
NASA NTRS1993

Laplace's equation and the Dirichlet-Neumann map in multiply connected domains

A variety of problems in material science and fluid dynamics require the solution of Laplace's equation in multiply connected domains. Integral equation methods are natural candidates for such problems, since they discretize the boundary alone, require no special effort for free boundaries, and achieve superalgebraic convergence rates on sufficiently smooth domains in two space dimensions, regardless of shape. Current integral equation methods for the Dirichlet problem, however, require the solution of M independent problems of dimension N, where M is the number of boundary components and N is the total number of points in the discretization. In this paper, we present a new boundary integral equation approach, valid for both interior and exterior problems, which requires the solution of a single linear system of dimension N + M. We solve this system by making use of an iterative method (GMRES) combined with the last multipole method for the rapid calculation of the necessary matrix vector products. For a two-dimensional system with 200 components and 100 points on each boundary, we gain a speedup of a factor of 100 from the new analytic formulation and a factor of 50 from the fast multipole method. The resulting scheme brings large scale calculations in extremely complex domains within practical reach.

Greenbaum, A.↗
NASA NTRS1993

Three-dimensional unstructured grid Euler computations using a fully-implicit, upwind method

A method has been developed to solve the Euler equations on a three-dimensional unstructured grid composed of tetrahedra. The method uses an upwind flow solver with a linearized, backward-Euler time integration scheme. Each time step results in a sparse linear system of equations which is solved by an iterative, sparse matrix solver. Local-time stepping, switched evolution relaxation (SER), preconditioning and reuse of the Jacobian are employed to accelerate the convergence rate. Implicit boundary conditions were found to be extremely important for fast convergence. Numerical experiments have shown that convergence rates comparable to that of a multigrid, central-difference scheme are achievable on the same mesh. Results are presented for several grids about an ONERA M6 wing.

Whitaker, David L.↗
NASA NTRS1954

A study of the application of power-spectral methods of generalized harmonic analysis to gust loads on airplanes

The applicability of some results from the theory of generalized harmonic analysis (or power-spectral analysis) to the analysis of gust loads on airplanes in continuous rough air is examined. The general relations for linear systems between power spectrums of a random input disturbance and an output response are used to relate the spectrum of airplane load in rough air to the spectrum of atmospheric gust velocity. The power spectrum of loads is shown to provide a measure of the load intensity in terms of the standard deviation (root mean square) of the load distribution for an airplane in flight through continuous rough air. For the case of a load output having a normal distribution, which appears from experimental evidence to apply to homogeneous rough air, the standard deviation is shown to describe the probability distribution of loads or the proportion of total time that the load has given values. Thus, for airplane in flight through homogeneous rough air, the probability distribution of loads may be determined from a power-spectral analysis. In order to illustrate the application of power-spectral analysis to gust-load analysis and to obtain an insight into the relations between loads and airplane gust-response characteristics, two selected series of calculations are presented. The results indicate that both methods of analysis yield results that are consistent to a first approximation.

Press, Harry↗
NASA NTRS1990

A superlinear interior points algorithm for engineering design optimization

We present a quasi-Newton interior points algorithm for nonlinear constrained optimization. It is based on a general approach consisting of the iterative solution in the primal and dual spaces of the equalities in Karush-Kuhn-Tucker optimality conditions. This is done in such a way to have primal and dual feasibility at each iteration, which ensures satisfaction of those optimality conditions at the limit points. This approach is very strong and efficient, since at each iteration it only requires the solution of two linear systems with the same matrix, instead of quadratic programming subproblems. It is also particularly appropriate for engineering design optimization inasmuch at each iteration a feasible design is obtained. The present algorithm uses a quasi-Newton approximation of the second derivative of the Lagrangian function in order to have superlinear asymptotic convergence. We discuss theoretical aspects of the algorithm and its computer implementation.

Herskovits, J.↗
NASA NTRS1993

An upwind multigrid method for solving viscous flows on unstructured triangular meshes

A multigrid algorithm is combined with an upwind scheme for solving the two dimensional Reynolds averaged Navier-Stokes equations on triangular meshes resulting in an efficient, accurate code for solving complex flows around multiple bodies. The relaxation scheme uses a backward-Euler time difference and relaxes the resulting linear system using a red-black procedure. Roe's flux-splitting scheme is used to discretize convective and pressure terms, while a central difference is used for the diffusive terms. The multigrid scheme is demonstrated for several flows around single and multi-element airfoils, including inviscid, laminar, and turbulent flows. The results show an appreciable speed up of the scheme for inviscid and laminar flows, and dramatic increases in efficiency for turbulent cases, especially those on increasingly refined grids.

Bonhaus, Daryl Lawrence↗
NASA NTRS1993

Multigrid properties of upwind-biased data reconstructions

The multigrid properties of two data reconstruction methods used for achieving second-order spatial accuracy when solving the two-dimensional Euler equations are examined. The data reconstruction methods are used with an implicit upwind algorithm which uses linearized backward-Euler time-differencing. The solution of the resulting linear system is performed by an iterative procedure. In the present study only regular quadrilateral grids are considered, so a red-black Gauss-Seidel iteration is used. Although the Jacobian is approximated by first-order upwind extrapolation, two alternative data reconstruction techniques for the flux integral that yield higher-order spatial accuracy at steady state are examined. The first method, probably most popular for structured quadrilateral grids, is based on estimating the cell gradients using one-dimensional reconstruction along curvilinear coordinates. The second method is based on Green's theorem. Analysis and numerical results for the two dimensional Euler equations show that data reconstruction based on Green's theorem has superior multigrid properties as compared to the one-dimensional data reconstruction method.

Warren, Gary P.↗
NASA NTRS1993

Simplified, inverse, ejector design tool

A simple lumped parameter based inverse design tool has been developed which provides flow path geometry and entrainment estimates subject to operational, acoustic, and design constraints. These constraints are manifested through specification of primary mass flow rate or ejector thrust, fully-mixed exit velocity, and static pressure matching. Fundamentally, integral forms of the conservation equations coupled with the specified design constraints are combined to yield an easily invertible linear system in terms of the flow path cross-sectional areas. Entrainment is computed by back substitution. Initial comparison with experimental and analogous one-dimensional methods show good agreement. Thus, this simple inverse design code provides an analytically based, preliminary design tool with direct application to High Speed Civil Transport (HSCT) design studies.

Dechant, Lawrence J.↗
NASA NTRS1993

Nested Krylov methods and preserving the orthogonality

Recently the GMRESR inner-outer iteraction scheme for the solution of linear systems of equations was proposed by Van der Vorst and Vuik. Similar methods have been proposed by Axelsson and Vassilevski and Saad (FGMRES). The outer iteration is GCR, which minimizes the residual over a given set of direction vectors. The inner iteration is GMRES, which at each step computes a new direction vector by approximately solving the residual equation. However, the optimality of the approximation over the space of outer search directions is ignored in the inner GMRES iteration. This leads to suboptimal corrections to the solution in the outer iteration, as components of the outer iteration directions may reenter in the inner iteration process. Therefore we propose to preserve the orthogonality relations of GCR in the inner GMRES iteration. This gives optimal corrections; however, it involves working with a singular, non-symmetric operator. We will discuss some important properties, and we will show by experiments that, in terms of matrix vector products, this modification (almost) always leads to better convergence. However, because we do more orthogonalizations, it does not always give an improved performance in CPU-time. Furthermore, we will discuss efficient implementations as well as the truncation possibilities of the outer GCR process. The experimental results indicate that for such methods it is advantageous to preserve the orthogonality in the inner iteration. Of course we can also use iteration schemes other than GMRES as the inner method; methods with short recurrences like GICGSTAB are of interest.

Desturler, Eric↗
NASA NTRS1993

Application of multigrid methods to the solution of liquid crystal equations on a SIMD computer

We will describe a finite difference code for computing the equilibrium configurations of the order-parameter tensor field for nematic liquid crystals in rectangular regions by minimization of the Landau-de Gennes Free Energy functional. The implementation of the free energy functional described here includes magnetic fields, quadratic gradient terms, and scalar bulk terms through the fourth order. Boundary conditions include the effects of strong surface anchoring. The target architectures for our implementation are SIMD machines, with interconnection networks which can be configured as 2 or 3 dimensional grids, such as the Wavetracer DTC. We also discuss the relative efficiency of a number of iterative methods for the solution of the linear systems arising from this discretization on such architectures.

Farrell, Paul A.↗