SEARCH · Search NASA

Results for “Lanczos 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.

SourceResearch connectionFrom yearThrough year

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 73 records · Page 4

All sources NASA NTRS DOE OSTI

DOE OSTI2017

A Fresh Math Perspective Opens New Possibilities for Computational Chemistry

By reformulating the TDDFT problem as a matrix function approximation, making use of a special transformation and taking advantage of the underlying symmetry with respect to a non-Euclidean metric, Yang and his colleagues were able to apply the Lanczos algorithm and a Kernal Polynomial Method (KPM) to approximate the absorption spectrum of several molecules. Both of these algorithms require relatively low-memory compared to non-symmetrical alternatives, which is the key to the computational savings.

Vu, Linda↗

NASA NTRS1998

New Parallel Algorithms for Structural Analysis and Design of Aerospace Structures

Subspace and Lanczos iterations have been developed, well documented, and widely accepted as efficient methods for obtaining p-lowest eigen-pair solutions of large-scale, practical engineering problems. The focus of this paper is to incorporate recent developments in vectorized sparse technologies in conjunction with Subspace and Lanczos iterative algorithms for computational enhancements. Numerical performance, in terms of accuracy and efficiency of the proposed sparse strategies for Subspace and Lanczos algorithm, is demonstrated by solving for the lowest frequencies and mode shapes of structural problems on the IBM-R6000/590 and SunSparc 20 workstations.

Nguyen, Duc T.↗

NASA NTRS1992

Efficient use of high performance computers for integrated controls and structures design

Simply transporting design codes from sequential-scalar computers to parallel-vector computers does not fully utilize the computational benefits offered by high performance computers. By performing integrated controls and structures design on an experimental truss platform with both sequential-scalar and parallel-vector design codes, conclusive results are presented to substantiate this claim. The efficiency of a Cholesky factorization scheme in conjunction with a variable-band row data structure is presented. In addition, the Lanczos eigensolution algorithm has been incorporated in the design code for both parallel and vector computations. Comparisons of computational efficiency between the initial design code and the parallel-vector design code are presented. It is shown that the Lanczos algorithm with the Cholesky factorization scheme is far superior to the sub-space iteration method of eigensolution when substantial numbers of eigenvectors are required for control design and/or performance optimization. Integrated design results show the need for continued efficiency studies in the area of element computations and matrix assembly.

Belvin, W. K.↗

NASA NTRS1989

The use of Lanczos's method to solve the large generalized symmetric definite eigenvalue problem

The generalized eigenvalue problem, Kx = Lambda Mx, is of significant practical importance, especially in structural enginering where it arises as the vibration and buckling problem. A new algorithm, LANZ, based on Lanczos's method is developed. LANZ uses a technique called dynamic shifting to improve the efficiency and reliability of the Lanczos algorithm. A new algorithm for solving the tridiagonal matrices that arise when using Lanczos's method is described. A modification of Parlett and Scott's selective orthogonalization algorithm is proposed. Results from an implementation of LANZ on a Convex C-220 show it to be superior to a subspace iteration code.

Jones, Mark T.↗

DOE OSTI2023

Hybrid eigensolvers for nuclear configuration interaction calculations

We examine and compare several iterative methods for solving large-scale eigenvalue problems arising from nuclear structure calculations. In particular, we discuss the possibility of using block Lanczos method, a Chebyshev filtering based subspace iterations and the residual minimization method accelerated by direct inversion of iterative subspace (RMM-DIIS) and describe how these algorithms compare with the standard Lanczos algorithm and the locally optimal block preconditioned conjugate gradient (LOBPCG) algorithm. Although the RMM-DIIS method does not exhibit rapid convergence when the initial approximations to the desired eigenvectors are not sufficiently accurate, it can be effectively combined with either the block Lanczos or the LOBPCG method to yield a hybrid eigensolver that has several desirable properties. We will describe a few practical issues that need to be addressed to make the hybrid solver efficient and robust.

97 MATHEMATICS AND COMPUTING↗

NASA NTRS2004

Open-Source Software for Modeling of Nanoelectronic Devices

The Nanoelectronic Modeling 3-D (NEMO 3-D) computer program has been upgraded to open-source status through elimination of license-restricted components. The present version functions equivalently to the version reported in "Software for Numerical Modeling of Nanoelectronic Devices" (NPO-30520), NASA Tech Briefs, Vol. 27, No. 11 (November 2003), page 37. To recapitulate: NEMO 3-D performs numerical modeling of the electronic transport and structural properties of a semiconductor device that has overall dimensions of the order of tens of nanometers. The underlying mathematical model represents the quantum-mechanical behavior of the device resolved to the atomistic level of granularity. NEMO 3-D solves the applicable quantum matrix equation on a Beowulf-class cluster computer by use of a parallel-processing matrix vector multiplication algorithm coupled to a Lanczos and/or Rayleigh-Ritz algorithm that solves for eigenvalues. A prior upgrade of NEMO 3-D incorporated a capability for a strain treatment, parameterized for bulk material properties of GaAs and InAs, for two tight-binding submodels. NEMO 3-D has been demonstrated in atomistic analyses of effects of disorder in alloys and, in particular, in bulk In(x)Ga(1-x)As and in In(0.6)Ga(0.4)As quantum dots.

Oyafuso, Fabiano↗

NASA NTRS2003

Numerical Modeling of Nanoelectronic Devices

Nanoelectronic Modeling 3-D (NEMO 3-D) is a computer program for numerical modeling of the electronic structure properties of a semiconductor device that is embodied in a crystal containing as many as 16 million atoms in an arbitrary configuration and that has overall dimensions of the order of tens of nanometers. The underlying mathematical model represents the quantummechanical behavior of the device resolved to the atomistic level of granularity. The system of electrons in the device is represented by a sparse Hamiltonian matrix that contains hundreds of millions of terms. NEMO 3-D solves the matrix equation on a Beowulf-class cluster computer, by use of a parallel-processing matrix vector multiplication algorithm coupled to a Lanczos and/or Rayleigh-Ritz algorithm that solves for eigenvalues. In a recent update of NEMO 3-D, a new strain treatment, parameterized for bulk material properties of GaAs and InAs, was developed for two tight-binding submodels. The utility of the NEMO 3-D was demonstrated in an atomistic analysis of the effects of disorder in alloys and, in particular, in bulk In(x)Ga(l-x)As and in In0.6Ga0.4As quantum dots.

Klimeck, Gerhard↗

DOE OSTI2021

Quarter 4 Report: Report on Final Findings and Opportunities for Future Work in the Use of Mixed Precision in Iterative Solvers

The fourth quarter of the project was spent developing an error analysis of the s-step Lanczos and CG algorithms. Our theoretical bounds and numerical experiments show that the numerical behavior of the algorithm can be significantly improved by using extra precision in a small part of the computation related to the computation and application of the Gram matrix. We have published a technical report which includes all steps of the analysis [8]; a shortened version for journal submission is in preparation. We plan to submit this paper in the following weeks. Activities related to this also include a collaboration with Ichitaro Yamazaki on gathering performance results for these new mixed precision s-step Krylov subspace methods using single/double precision on GPUs. Namely, we would like to obtain performance results that show that the performance overhead of using double the working precision in these select computations is minimal. Other activities include attending biweekly xSDK meetings and presenting a pitch talk on this work to the group on February 25, 2021. In the remainder of the document, we summarize our findings on the potential for mixed precision in classical Krylov subspace methods and s-step Krylov subspace methods, as well as key opportunities for future work.

97 MATHEMATICS AND COMPUTING↗

NASA NTRS1993

Computation of selected eigenvalues of generalized eigenvalue problems

The Arnoldi (1951) and Lanczos (1950) iterative algorithms are used to obtain a few selected eigenvalues of the generalized eigenvalue problem A(x) = lambdaB(x), where A and B are n x n nonsymmetric banded complex matrices. A shift-and-invert strategy is used to increase the rate of convergence toward the desired eigenvalues, and the two approaches are evaluated in view of their performance in a model problem concerning the linear stability of compressible boundary layers. A general scheme for computing the eigenvalues that lie within a 'box' in the complex plane is presented.

Nayar, Narinder↗

NASA NTRS1993

Some experiences with Krylov vectors and Lanczos vectors

This paper illustrates the use of Krylov vectors and Lanczos vectors for reduced-order modeling in structural dynamics and for control of flexible structures. Krylov vectors and Lanczos vectors are defined and illustrated, and several applications that have been under study at The University of Texas at Austin are reviewed: model reduction for undamped structural dynamics systems, component mode synthesis using Krylov vectors, model reduction of damped structural dynamics systems, and one-sided and two-sided unsymmetric block-Lanczos model-reduction algorithms.

Craig, Roy R., Jr.↗

NASA NTRS2009

The GMAO ADVAR System: Preliminary Results

The Goddard Earth Observing System (GEOS-S) Data Assimilation System is now configurable to run strong constraint 4DVAR. The system combines the 4DVAR-capable Grid-point Statistical Interpolation analysis with the GEOS-S general circulation model and an early version of the tangent linear and adjoint models of the finite-volume hydrodynamics with simplified physics. The GMAO 4DVAR uses a Lanczos-based conjugate gradient algorithm in a nested resolution inner-loop setting. A range of tests and experiments will have been carried out by the time of the Symposium. Results on balance-related issues, resolution configuration, and choice of assimilation time window will be shown. A comparison with the Global Modeling and Assimilation Office (GMAO) 3DVAR and a discussion of future directions of development will also be presented.

Todling, Ricardo↗

DOE OSTI2020

Sub-system quantum dynamics using coupled cluster downfolding techniques

In this paper, we discuss extending the sub-system embedding sub-algebra coupled cluster (SES-CC) formalism and the double unitary coupled cluster (DUCC) ansatz to the time domain. As we demonstrated in earlier studies, it is possible, using these formalisms, to calculate the energy of the entire system as an eigenvalue of downfolded/effective Hamiltonian in the active space, that is identifiable with the sub-system of the composite system. In these studies, we demonstrated that downfolded Hamiltonians integrate out Fermionic degrees of freedom that do not correspond to the physics encapsulated by the active space. We extend these results to the time-dependent Schrödinger equation, showing that a similar construct is possible to partition a system into a sub-system that varies slowly in time and a remaining subsystem that corresponds to fast oscillations. This time dependent formalism allows coupled cluster quantum dynamics to be extended to larger systems and for the formulation of novel quantum algorithms based on the quantum Lanczos approach, which have recently been considered in the literature.

coupled cluster, Electron correlation, quantum dyn↗

NASA NTRS1989

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

NASA NTRS1992

Implementation details of the coupled QMR algorithm

The original quasi-minimal residual method (QMR) relies on the three-term look-ahead Lanczos process, to generate basis vectors for the underlying Krylov subspaces. However, empirical observations indicate that, in finite precision arithmetic, three-term vector recurrences are less robust than mathematically equivalent coupled two-term recurrences. Therefore, we recently proposed a new implementation of the QMR method based on a coupled two-term look-ahead Lanczos procedure. In this paper, we describe implementation details of this coupled QMR algorithm, and we present results of numerical experiments.

Freund, Roland W.↗

NASA NTRS1986

Solving large-scale dynamic systems using band Lanczos method in Rockwell NASTRAN on CRAY X-MP

The improved cost effectiveness using better models, more accurate and faster algorithms and large scale computing offers more representative dynamic analyses. The band Lanczos eigen-solution method was implemented in Rockwell's version of 1984 COSMIC-released NASTRAN finite element structural analysis computer program to effectively solve for structural vibration modes including those of large complex systems exceeding 10,000 degrees of freedom. The Lanczos vectors were re-orthogonalized locally using the Lanczos Method and globally using the modified Gram-Schmidt method for sweeping rigid-body modes and previously generated modes and Lanczos vectors. The truncated band matrix was solved for vibration frequencies and mode shapes using Givens rotations. Numerical examples are included to demonstrate the cost effectiveness and accuracy of the method as implemented in ROCKWELL NASTRAN. The CRAY version is based on RPK's COSMIC/NASTRAN. The band Lanczos method was more reliable and accurate and converged faster than the single vector Lanczos Method. The band Lanczos method was comparable to the subspace iteration method which was a block version of the inverse power method. However, the subspace matrix tended to be fully populated in the case of subspace iteration and not as sparse as a band matrix.

Gupta, V. K.↗

NASA NTRS1992

Recent advances in Lanczos-based iterative methods for nonsymmetric linear systems

In recent years, there has been a true revival of the nonsymmetric Lanczos method. On the one hand, the possible breakdowns in the classical algorithm are now better understood, and so-called look-ahead variants of the Lanczos process have been developed, which remedy this problem. On the other hand, various new Lanczos-based iterative schemes for solving nonsymmetric linear systems have been proposed. This paper gives a survey of some of these recent developments.

Freund, Roland W.↗

NASA NTRS1986

Implementation of the Lanczos method for structural vibration analysis on a parallel computer

The use of the Lanczos method in a parallel environment is investigated by implementing the algorithm for structural vibration problems on a parallel computer. It is shown that introducing shifts, assigning each processor a different region in the eigenvalue spectrum, and implementing the Lanczos method in parallel is an effective strategy for speeding up calculations. Test problem results include examples of the 'Lanczos phenomenon' where roundoff error in the vector orthogonalization can result in spurious eigenvalues which must be identified and discarded. The calculation strategy described here permits straightforward determination of these spurious eigenvalues. It is demonstrated that significant speedups in calculation time can be realized over traditional sequential methods.

Bostic, S. W.↗

DOE OSTI2024

Quantum Davidson algorithm for excited states

Abstract Excited state properties play a pivotal role in various chemical and physical phenomena, such as charge separation and light emission. However, the primary focus of most existing quantum algorithms has been the ground state, as seen in quantum phase estimation and the variational quantum eigensolver (VQE). Although VQE-type methods have been extended to explore excited states, these methods grapple with optimization challenges. In contrast, the quantum Krylov subspace (QKS) method has been introduced to address both ground and excited states, positioning itself as a cost-effective alternative to quantum phase estimation. However, conventional QKS methodologies depend on a pre-generated subspace through real or imaginary-time evolutions. This subspace is inherently expansive and can be plagued with issues like slow convergence or numerical instabilities, often leading to relatively deep circuits. Our research presents an economic QKS algorithm, which we term the quantum Davidson (QDavidson) algorithm. This innovation hinges on the iterative expansion of the Krylov subspace and the incorporation of a pre-conditioner within the Davidson framework. By using the residues of eigenstates to expand the Krylov subspace, we manage to formulate a compact subspace that aligns closely with the exact solutions. This iterative subspace expansion paves the way for a more rapid convergence in comparison to other QKS techniques, such as the quantum Lanczos. Using quantum simulators, we employ the novel QDavidson algorithm to delve into the excited state properties of various systems, spanning from the Heisenberg spin model to real molecules. Compared to the existing QKS methods, the QDavidson algorithm not only converges swiftly but also demands a significantly shallower circuit. This efficiency establishes the QDavidson method as a pragmatic tool for elucidating both ground and excited state properties on quantum computing platforms.

97 MATHEMATICS AND COMPUTING↗