Search NASA⌕ Search

SEARCH · Search NASA

Results for “Eigenvalue algorithm”

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 NTRS1989

On polynomial preconditioning for indefinite Hermitian matrices

The minimal residual method is studied combined with polynomial preconditioning for solving large linear systems (Ax = b) with indefinite Hermitian coefficient matrices (A). The standard approach for choosing the polynomial preconditioners leads to preconditioned systems which are positive definite. Here, a different strategy is studied which leaves the preconditioned coefficient matrix indefinite. More precisely, the polynomial preconditioner is designed to cluster the positive, resp. negative eigenvalues of A around 1, resp. around some negative constant. In particular, it is shown that such indefinite polynomial preconditioners can be obtained as the optimal solutions of a certain two parameter family of Chebyshev approximation problems. Some basic results are established for these approximation problems and a Remez type algorithm is sketched for their numerical solution. The problem of selecting the parameters such that the resulting indefinite polynomial preconditioners speeds up the convergence of minimal residual method optimally is also addressed. An approach is proposed based on the concept of asymptotic convergence factors. Finally, some numerical examples of indefinite polynomial preconditioners are given.

Freund, Roland W.↗
NASA NTRS1992

Robust Assignment Of Eigensystems For Flexible Structures

Improved method for placement of eigenvalues and eigenvectors of closed-loop control system by use of either state or output feedback. Applied to reduced-order finite-element mathematical model of NASA's MAST truss beam structure. Model represents deployer/retractor assembly, inertial properties of Space Shuttle, and rigid platforms for allocation of sensors and actuators. Algorithm formulated in real arithmetic for efficient implementation. Choice of open-loop eigenvector matrix and its closest unitary matrix believed suitable for generating well-conditioned eigensystem with small control gains. Implication of this approach is that element of iterative search for "optimal" unitary matrix appears unnecessary in practice for many test problems.

Juang, Jer-Nan↗
NASA NTRS2003

Quantum Adiabatic Optimization and Combinatorial Landscapes

In this paper we analyze the performance of the Quantum Adiabatic Evolution (QAE) algorithm on a variant of Satisfiability problem for an ensemble of random graphs parametrized by the ratio of clauses to variables, gamma = M / N. We introduce a set of macroscopic parameters (landscapes) and put forward an ansatz of universality for random bit flips. We then formulate the problem of finding the smallest eigenvalue and the excitation gap as a statistical mechanics problem. We use the so-called annealing approximation with a refinement that a finite set of macroscopic variables (verses only energy) is used, and are able to show the existence of a dynamic threshold gamma = gammad, beyond which QAE should take an exponentially long time to find a solution. We compare the results for extended and simplified sets of landscapes and provide numerical evidence in support of our universality ansatz.

Smelyanskiy, V. N.↗
NASA NTRS1979

Linear state feedback, quadratic weights, and closed loop eigenstructures

Results are given on the relationships between closed loop eigenstructures, state feedback gain matrices of the linear state feedback problem, and quadratic weights of the linear quadratic regulator. Equations are derived for the angles of general multivariable root loci and linear quadratic optimal root loci, including angles of departure and approach. The generalized eigenvalue problem is used for the first time to compute angles of approach. Equations are also derived to find the sensitivity of closed loop eigenvalues and the directional derivatives of closed loop eigenvectors (with respect to a scalar multiplying the feedback gain matrix or the quadratic control weight). An equivalence class of quadratic weights that produce the same asymptotic eigenstructure is defined, sufficient conditions to be in it are given, a canonical element is defined, and an algorithm to find it is given. The behavior of the optimal root locus in the nonasymptotic region is shown to be different for quadratic weights with the same asymptotic properties.

Thompson, P. M.↗
NASA NTRS1983

Accelerating an iterative process by explicit annihilation

A slowly convergent stationary iterative process can be accelerated by explicitly annihilating (i.e., eliminating) the dominant eigenvector component of the error. The dominant eigenvalue or complex pair of eigenvalues can be estimated from the solution during the iteration. The corresponding eigenvector or complex pair of eigenvectors can then be annihilated by applying an explicit Richardson process over the basic iterative method. This can be done entirely in real arithmetic by analytically combining the complex conjugate annihilation steps. The technique is applied to an implicit algorithm for the calculation of two dimensional steady transonic flow over a circular cylinder using the equations of compressible inviscid gas dynamics. This demonstrates the use of explicit annihilation on a nonlinear problem.

Jespersen, D. C.↗
NASA NTRS1985

Accelerating an iterative process by explicit annihilation

A slowly convergent stationary iterative process can be accelerated by explicitly annihilating (i.e., eliminating) the dominant eigenvector component of the error. The dominant eigenvalue or complex pair of eigenvalues can be estimated from the solution during the iteration. The corresponding eigenvector or complex pair of eigenvectors can then be annihilated by applying an explicit Richardson process over the basic iterative method. This can be done entirely in real arithmetic by analytically combining the complex conjugate annihilation steps. The technique is applied to an implicit algorithm for the calculation of two dimensional steady transonic flow over a circular cylinder using the equations of compressible inviscid gas dynamics. This demonstrates the use of explicit annihilation on a nonlinear problem.

Jespersen, D. C.↗
NASA NTRS1992

On adaptive weighted polynomial preconditioning for Hermitian positive definite matrices

The conjugate gradient algorithm for solving Hermitian positive definite linear systems is usually combined with preconditioning in order to speed up convergence. In recent years, there has been a revival of polynomial preconditioning, motivated by the attractive features of the method on modern architectures. Standard techniques for choosing the preconditioning polynomial are based only on bounds for the extreme eigenvalues. Here a different approach is proposed, which aims at adapting the preconditioner to the eigenvalue distribution of the coefficient matrix. The technique is based on the observation that good estimates for the eigenvalue distribution can be derived after only a few steps of the Lanczos process. This information is then used to construct a weight function for a suitable Chebyshev approximation problem. The solution of this problem yields the polynomial preconditioner. In particular, we investigate the use of Bernstein-Szego weights.

Fischer, Bernd↗
NASA NTRS1985

An Eigensystem Realization Algorithm for Application to Modal Testing

Important features of the Eigensystem Realization Algorithm (ERA) are summarized as follows: (1) from the computational standpoint, the algorithm is attractive, since only simple numerical operations are needed; (2) the computational procedure is numerically stable; (3) the structural dynamics requirements for modal parameter identification and the control design requirements for a reduced-state space model are satisfied; (4) data from more than one test can be used simultaneously to efficiently identify the closely spaced eigenvalues; and (5) no restrictions on number of measurements are imposed.

Juang, J. N.↗
NASA NTRS1988

Attitude determination and parameter estimation using vector observations

Procedures for attitude determination based on Wahba's loss function are generalized to include the estimation of parameters other than the attitude, such as sensor biases. Optimization with respect to the attitude requires either the singular value decomposition of a 3x3 matrix or finding the maximum eigenvalue and corresponding eigenvector of a 4x4 symmetric matrix, but does not require an a priori estimate of the attitude. Optimization with respect to the other parameters employs an iterative approach, which does require an a priori estimate of these parameters. Conventional state estimation methods require a priori estimates of both the parameters and the attitude, while the algorithms presented in this paper always compute the exact optimal attitude for given values of the parameters. The proposed method is shown to give the correct solution of an example problem. An expression for the covariance of the attitude and parameter estimates is derived.

Markley, F. Landis↗
NASA NTRS1987

Improvements to the fastex flutter analysis computer code

Modifications to the FASTEX flutter analysis computer code (UDFASTEX) are described. The objectives were to increase the problem size capacity of FASTEX, reduce run times by modification of the modal interpolation procedure, and to add new user features. All modifications to the program are operable on the VAX 11/700 series computers under the VAX operating system. Interfaces were provided to aid in the inclusion of alternate aerodynamic and flutter eigenvalue calculations. Plots can be made of the flutter velocity, display and frequency data. A preliminary capability was also developed to plot contours of unsteady pressure amplitude and phase. The relevant equations of motion, modal interpolation procedures, and control system considerations are described and software developments are summarized. Additional information documenting input instructions, procedures, and details of the plate spline algorithm is found in the appendices.

Taylor, Ronald F.↗
NASA NTRS1987

Robust eigensystem assignment for flexible structures

An improved method is developed for eigenvalues and eigenvectors placement of a closed-loop control system using either state or output feedback. The method basically consists of three steps. First, the singular value of QR decomposition is used to generate an orthonormal basis that spans admissible eigenvector space corresponding to each assigned eigenvalue. Secondly, given a unitary matrix, the eigenvector set which best approximates the given matrix in the least-square sense and still satisfy eigenvalue cosntraints is determined. Thirdly, a unitary matrix is sought to minimize the error between the unitary matrix and the assignable eigenvector matrix. For use as the desired eigenvector set, two matrices, namely, the open-loop eigenvector matrix and its closest unitary matrix are proposed. The latter matrix generally encourages both minimum conditioning and control gains. In addition, the algorithm is formulated in real arithmetic for efficient implementation. To illustrate the basic concepts, numerical examples are included.

Juang, Jer-Nan↗
NASA NTRS1990

Krylov subspace methods - Theory, algorithms, and applications

Projection methods based on Krylov subspaces for solving various types of scientific problems are reviewed. The main idea of this class of methods when applied to a linear system Ax = b, is to generate in some manner an approximate solution to the original problem from the so-called Krylov subspace span. Thus, the original problem of size N is approximated by one of dimension m, typically much smaller than N. Krylov subspace methods have been very successful in solving linear systems and eigenvalue problems and are now becoming popular for solving nonlinear equations. The main ideas in Krylov subspace methods are shown and their use in solving linear systems, eigenvalue problems, parabolic partial differential equations, Liapunov matrix equations, and nonlinear system of equations are discussed.

Sad, Youcef↗
NASA NTRS1992

The relationship between pressure-based and density-based algorithms

The PISO, pressure-based algorithm, is compared with implicit time-marching systems to ascertain their similarities and differences. Both methods are expressed in vector form for comparison purposes. The vector form of the PISO method is triangular, allowing an uncoupled solution procedure, while the Euler implicit method requires the simultaneous solution of all equations. Upwind differencing is performed according to the direction of the eigenvalues in both systems, but this is the particle velocity in the PISO method and the acoustic velocity in the Euler method. Vector stability calculations show that the PISO method is conditionally stable depending on the time step, but that it provides adequate damping at small time steps to enable good convergence. Unconditional stability can be provided by retaining the energy coupling terms in the time derivative. Transforming the Euler implicit equations to the PISO variables along with a modification of the time derivatives gives the density-based method the same amplification factors at low speeds as the pressure-based method without affecting their behavior at high speeds.

Merkle, Charles L.↗
NASA NTRS1988

Multi-time-step integration using nodal partitioning

An algorithm is presented which integrates different groups of nodes of a finite element mesh with different time steps and different integrators. Since the nodal groups are updated independently no unsymmetric systems need be solved. Stability is demonstrated by showing that an energy norm of the solution decreases after every update if the time step is less than a given critical value. The element eigenvalue inequality theorem is used to give the critical time step in terms of element eigenvalues.

Smolinski, P.↗
NASA NTRS1982

Interactive digital signal processor

The Interactive Digital Signal Processor (IDSP) is examined. It consists of a set of time series analysis Operators each of which operates on an input file to produce an output file. The operators can be executed in any order that makes sense and recursively, if desired. The operators are the various algorithms used in digital time series analysis work. User written operators can be easily interfaced to the sysatem. The system can be operated both interactively and in batch mode. In IDSP a file can consist of up to n (currently n=8) simultaneous time series. IDSP currently includes over thirty standard operators that range from Fourier transform operations, design and application of digital filters, eigenvalue analysis, to operators that provide graphical output, allow batch operation, editing and display information.

Mish, W. H.↗
NASA NTRS1989

A fast, preconditioned conjugate gradient Toeplitz solver

A simple factorization is given of an arbitrary hermitian, positive definite matrix in which the factors are well-conditioned, hermitian, and positive definite. In fact, given knowledge of the extreme eigenvalues of the original matrix A, an optimal improvement can be achieved, making the condition numbers of each of the two factors equal to the square root of the condition number of A. This technique is to applied to the solution of hermitian, positive definite Toeplitz systems. Large linear systems with hermitian, positive definite Toeplitz matrices arise in some signal processing applications. A stable fast algorithm is given for solving these systems that is based on the preconditioned conjugate gradient method. The algorithm exploits Toeplitz structure to reduce the cost of an iteration to O(n log n) by applying the fast Fourier Transform to compute matrix-vector products. Matrix factorization is used as a preconditioner.

Pan, Victor↗
NASA NTRS2003

Algorithmic Enhancements to the VULCAN Navier-Stokes Solver

VULCAN (Viscous Upwind aLgorithm for Complex flow ANalysis) is a cell centered, finite volume code used to solve high speed flows related to hypersonic vehicles. Two algorithms are presented for expanding the range of applications of the current Navier-Stokes solver implemented in VULCAN. The first addition is a highly implicit approach that uses subiterations to enhance block to block connectivity between adjacent subdomains. The addition of this scheme allows more efficient solution of viscous flows on highly-stretched meshes. The second algorithm addresses the shortcomings associated with density-based schemes by the addition of a time-derivative preconditioning strategy. High speed, compressible flows are typically solved with density based schemes, which show a high level of degradation in accuracy and convergence at low Mach numbers (M less than or equal to 0.1). With the addition of preconditioning and associated modifications to the numerical discretization scheme, the eigenvalues will scale with the local velocity, and the above problems will be eliminated. With these additions, VULCAN now has improved convergence behavior for multi-block, highly-stretched meshes and also can solve the Navier-Stokes equations for very low Mach numbers.

Litton, D. K.↗
NASA NTRS2000

Ordering Unstructured Meshes for Sparse Matrix Computations on Leading Parallel Systems

The ability of computers to solve hitherto intractable problems and simulate complex processes using mathematical models makes them an indispensable part of modern science and engineering. Computer simulations of large-scale realistic applications usually require solving a set of non-linear partial differential equations (PDES) over a finite region. For example, one thrust area in the DOE Grand Challenge projects is to design future accelerators such as the SpaHation Neutron Source (SNS). Our colleagues at SLAC need to model complex RFQ cavities with large aspect ratios. Unstructured grids are currently used to resolve the small features in a large computational domain; dynamic mesh adaptation will be added in the future for additional efficiency. The PDEs for electromagnetics are discretized by the FEM method, which leads to a generalized eigenvalue problem Kx = AMx, where K and M are the stiffness and mass matrices, and are very sparse. In a typical cavity model, the number of degrees of freedom is about one million. For such large eigenproblems, direct solution techniques quickly reach the memory limits. Instead, the most widely-used methods are Krylov subspace methods, such as Lanczos or Jacobi-Davidson. In all the Krylov-based algorithms, sparse matrix-vector multiplication (SPMV) must be performed repeatedly. Therefore, the efficiency of SPMV usually determines the eigensolver speed. SPMV is also one of the most heavily used kernels in large-scale numerical simulations.

Oliker, Leonid↗