Engineering Papers⌕ Search

SEARCH · Engineering Papers

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 91 records · Page 5

A Look at the Truths and Misconceptions of the Variational Quantum Eigensolver and the Implications of Overparameterization

In this work, we investigate loss landscapes of the variational quantum eigensolver (VQE) by quantifying the number of local minima through empirical analyses. We focus on minimal models in chemistry and physics so that we can do a complete analysis using more computationally expensive tools. We employ Hessian eigenvalue calculations and the nudged elastic band algorithm to characterize these landscapes. Our results expand upon the existing literature by highlighting the optimization challenges faced by VQE. We find that, as the number of parameters in our ansatz increases, the number of basins increases while the corresponding loss function values converge toward the global minimum value. This observation implies that overparameterization may lead to an ``effective convexity'' in VQE loss landscapes, a phenomenon supported by theoretical and numerical work in classical machine learning.

quantum computing↗

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.↗

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.↗

Efficient numerical simulation of electron states in quantum wires

A new algorithm is presented for the numerical simulation of electrons in a quantum wire as described by a two-dimensional eigenvalue problem for Schroedinger's equation coupled with Poisson's equation. Initially, the algorithm employs an underrelaxed fixed point iteration to generate an approximation which is reasonably close to the solution. Subsequently, this approximate solution is employed as an initial guess for a Jacobian-free implementation of an approximate Newton method. In this manner the nonlinearity in the model is dealt with effectively. The effectiveness of this approach is demonstrated in a set of numerical experiments which study the electron states on the cross section of a quantum wire structure based on III-V semiconductors at 4.2 and 77 K.

Kerkhoven, Thomas↗

Bunch-Kaufman factorization for real symmetric indefinite banded matrices

The Bunch-Kaufman algorithm for factoring symmetric indefinite matrices was rejected for banded matrices because it destroys the banded structure of the matrix. Herein, it is shown that for a subclass of real symmetric matrices which arise in solving the generalized eigenvalue problem using Lanczos's method, the Bunch-Kaufman algorithm does not result in major destruction of the bandwidth. Space time complexities of the algorithm are given and used to show that the Bunch-Kaufman algorithm is a significant improvement over LU factorization.

Jones, Mark T.↗

Inclusion of elastically connected members in exact buckling and frequency calculations

A standard stiffness matrix procedure which permits any combination of rigid, elastic, pinned or sliding connections of the degrees of freedom at the ends of a member to the nodes of its parent structure is described, in order to show how easily it can be extended to allow an existing algorithm to be used to ensure that no eigenvalues of the parent structure can be missed even when 'exact' member theory is used. The eigenvalues are the natural frequencies of undamped free vibration analyses or the critical load factors of buckling problems. The method preserves the exactness of the member theory and an efficient method for computer application is indicated. The theory also permits any combination of rigid, elastic, pinned or sliding connections between the freedoms of a substructure and those of its parent structure.

Williams, F. W.↗

Rapid solution of large-scale systems of equations

The analysis and design of complex aerospace structures requires the rapid solution of large systems of linear and nonlinear equations, eigenvalue extraction for buckling, vibration and flutter modes, structural optimization and design sensitivity calculation. Computers with multiple processors and vector capabilities can offer substantial computational advantages over traditional scalar computer for these analyses. These computers fall into two categories: shared memory computers and distributed memory computers. This presentation covers general-purpose, highly efficient algorithms for generation/assembly or element matrices, solution of systems of linear and nonlinear equations, eigenvalue and design sensitivity analysis and optimization. All algorithms are coded in FORTRAN for shared memory computers and many are adapted to distributed memory computers. The capability and numerical performance of these algorithms will be addressed.

Storaasli, Olaf O.↗

A Shifted Block Lanczos Algorithm 1: The Block Recurrence

In this paper we describe a block Lanczos algorithm that is used as the key building block of a software package for the extraction of eigenvalues and eigenvectors of large sparse symmetric generalized eigenproblems. The software package comprises: a version of the block Lanczos algorithm specialized for spectrally transformed eigenproblems; an adaptive strategy for choosing shifts, and efficient codes for factoring large sparse symmetric indefinite matrices. This paper describes the algorithmic details of our block Lanczos recurrence. This uses a novel combination of block generalizations of several features that have only been investigated independently in the past. In particular new forms of partial reorthogonalization, selective reorthogonalization and local reorthogonalization are used, as is a new algorithm for obtaining the M-orthogonal factorization of a matrix. The heuristic shifting strategy, the integration with sparse linear equation solvers and numerical experience with the code are described in a companion paper.

Grimes, Roger G.↗

An eigenvalue/eigenvector assignment algorithm using output feedback

An eigenvalue/eigenvector assignment algorithm using stationary output feedback is presented. The algorithm permits assignment of min (n, m + r - 1) eigenvalues and max (m-1, r-1) eigenvectors, where n, m, r refer to the system state, input and output dimensions, respectively. An example is given to illustrate the design procedures.

Mielke, R. R.↗

A parallel householder tridiagonalization stratagem using scattered row decomposition

Householder's method for tridiagonalizing a real symmetric matrix, a major step in evaluating eigenvalues of the matrix, is modified into a parallel algorithm for a concurrent machine of message passing type. Each processor of the concurrent machine has its own CPU, communications control and local memory. Messages are passed through connections between processors. Although the basic algorithm is inherently serial, the computations can be spread over all processors by scattering different rows of the matrix into processors, hence the term 'Scattered Row Decomposition'. The steps in the serial and the parallel algorithms are identified. Expressions for efficiency and speedup are given in terms of problem and machine parameters. For a concurrent machine of ring type interconnection, a selected representative problem of large order exhibits efficiency approaching 66 per cent.

Chang, H. Y.↗

Solution and sensitivity analysis of a complex transcendental eigenproblem with pairs of real eigenvalues

This paper considers complex transcendental eigenvalue problems where one is interested in pairs of eigenvalues that are restricted to take real values only. Such eigenvalue problems arise in dynamic stability analysis of nonconservative physical systems, i.e., flutter analysis of aeroelastic systems. Some available solution methods are discussed and a new method is presented. Two computational approaches are described for analytical evaluation of the sensitivities of these eigenvalues when they are dependent on other parameters. The algorithms presented are illustrated through examples.

Murthy, Durbha V.↗

Solution and sensitivity analysis of a complex transcendental eigenproblem with pairs of real eigenvalues

This paper considers complex transcendental eigenvalue problems where one is interested in pairs of eigenvalues that are restricted to take real values only. Such eigenvalue problems arise in dynamic stability analysis of nonconservative physical systems, i.e., flutter analysis of aeroelastic systems. Some available solution methods are discussed and a new method is presented. Two computational approaches are described for analytical evaluation of the sensitivities of these eigenvalues when they are dependent on other parameters. The algorithms presented are illustrated through examples.

Murthy, D. V.↗

Full and reduced order observer based controller design for H2-optimization

The most general H2 control problem is considered. The authors derive necessary and sufficient conditions when the infimum is attained by state feedback. They do the same for the measurement feedback case where necessary and sufficient conditions are derived when the infimum is attained by proper dynamic compensator. Reduced-order compensators are investigated if some states are observable without noise. For all of these cases the freedom that the non-uniqueness of optimal compensators gives in assigning the closed-loop eigenvalues is discussed. The case when the infimum cannot be attained is investigated. A constructive algorithm is presented to find a minimizing sequence of stabilizing controllers and the freedom in the asymptotic locations of the closed-loop eigenvalues is discussed. This procedure is repeated for three different cases: static state feedback, full-order measurement feedback, and reduced-order measurement feedback.

Stoorvogel, Anton A.↗

Genetic Optimization of a Tensegrity Structure

Marshall Space Flight Center (MSFC) is charged with developing advanced technologies for space telescopes. The next generation of space optics will be very large and lightweight. Tensegrity structures are built of compressive members (bars), and tensile members (strings). For most materials, the tensile strength of a longitudinal member is larger than its buckling strength; therefore a large stiffness to mass ratio can be achieved by increasing the use of tensile members. Tensegrities are the epitome of lightweight structures, since they take advantage of the larger tensile strength of materials. The compressive members of tensegrity structures are disjoint allowing compact storage of the structure. The structure has the potential to eliminate the requirement for assembly by man in space; it can be deployed by adjustments in its cable tension. A tensegrity structure can be more reliably modeled since none of the individual members experience bending moments. (Members that experience deformation in more than one dimension are much harder to model.) Structures that can be more precisely modeled can be more precisely controlled. Furthermore, an astoundingly wide variety of natural systems, including carbon atoms, water molecules, proteins, viruses, cells, tissues and even human and other living creatures are tensegrity structures. Through the process of evolution, nature continually improves the design of living creatures for the environment they live in. Since tensegrities are nature's structure of choice, it is conceivable that they have other benefits we are unaware of. A. Keane and S. Brown designed a satellite boom truss system with an enhanced vibration performance. They started with a standard truss system, then used a genetic algorithm to alter the design, while optimizing the vibration performance. An improvement of over 20,000% in frequency-averaged energy levels was obtained using this approach. In this report an introduction to tensegrity structures is given, along with a description of how to generate the nodal coordinates and connectivity of a multiple stage cylindrical tensegrity structure. A description of how finite elements can be used to develop a stiffness and mass matrix so that the modes of vibration can be determined from the eigenvalue problem is shown. A brief description of a micro genetic algorithm is then presented.

Jaime R. Taylor↗

An O(N squared) method for computing the eigensystem of N by N symmetric tridiagonal matrices by the divide and conquer approach

An efficient method is proposed to solve the eigenproblem of N by N Symmetric Tridiagonal (ST) matrices. Unlike the standard eigensolvers which necessitate O(N cubed) operations to compute the eigenvectors of such ST matrices, the proposed method computes both the eigenvalues and eigenvectors with only O(N squared) operations. The method is based on serial implementation of the recently introduced Divide and Conquer (DC) algorithm. It exploits the fact that by O(N squared) of DC operations, one can compute the eigenvalues of N by N ST matrix and a finite number of pairs of successive rows of its eigenvector matrix. The rest of the eigenvectors--all of them or one at a time--are computed by linear three-term recurrence relations. Numerical examples are presented which demonstrate the superiority of the proposed method by saving an order of magnitude in execution time at the expense of sacrificing a few orders of accuracy.

Gill, Doron↗

Design of reduced-order state estimators for linear time-varying multivariable systems

The design of reduced-order state estimators for linear time-varying multivariable systems is considered. Employing the concepts of matrix operators and the method of canonical transformations, this paper shows that there exists a reduced-order state estimator for linear time-varying systems that are 'lexicography-fixedly observable'. In addition, the eigenvalues of the estimator can be arbitrarily assigned. A simple algorithm is proposed for the design of the state estimator.

Nguyen, Charles C.↗