Search NASA⌕ Search

SEARCH · Search NASA

Results for “Krylov subspace”

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

Bound Constrained Partial DifferentialEquation Inverse Problem Solution by theSemi-Smooth Newton Method

We present the mathematical derivation, software implementation details, and computational results for a semi-smooth Newton method applied to two inverse problems governed by partial differential equations with bound constraints. The two problems share mathematical structural similarities to density-based topology optimization problems. The semi-smooth Newton method provides a mesh independent solution computation for the two test problems. A key step is that the complementarity part of the necessary optimality conditions are reformulated with the use of a complementarity functionφsuch that the complementarity conditions are satisfied if and only if a zero of a nonsmooth function has been obtained. The modular finite element package MFEM is utilized for the software implementation. In addition we constructed a matrix-free Operator to enable the use of efficient Krylov subspace IterativeSolver of MFEM for the solution of our two target problems.

97 MATHEMATICS AND COMPUTING↗

Filtered Rayleigh-Ritz is all you need

Recent work has shown that the (block) Lanczos algorithm can be used to extract approximate energy spectra and matrix elements from (matrices of) correlation functions in quantum field theory, and identified exact coincidences between Lanczos analysis methods and others. In this work, we note another coincidence: the Lanczos algorithm is equivalent to the well-known Rayleigh-Ritz method applied to Krylov subspaces. Rayleigh-Ritz provides optimal eigenvalue approximations within subspaces; we find that spurious-state filtering allows these optimality guarantees to be retained in the presence of statistical noise. We explore the relation between Lanczos and Prony's method, their block generalizations, generalized pencil of functions (GPOF), and methods based on the generalized eigenvalue problem (GEVP), and find they all fall into a larger "Prony-Ritz equivalence class", identified as all methods which solve a finite-dimensional spectrum exactly given sufficient correlation function (matrix) data. This equivalence allows simpler and more numerically stable implementations of (block) Lanczos analyses.

97 MATHEMATICS AND COMPUTING↗

TRANAIR - A computer code for transonic analyses of arbitrary configurations

Attention is given to a new approach to solving full potential equations about arbitrary configurations. Numerical algorithms from such fields as finite elements, preconditioned Krylov subspace methods, discrete Fourier analysis, and integral equations are combined to take advantage of the size and speed of current and emerging supercomputers. On the basis of this appraoch, a robust, efficient and easy to use computer code referred to as TRANAIR has been developed for transonic analysis of complex geometries.

Samant, S. S.↗

A new approach to the solution of boundary value problems involving complex configurations

A new approach for solving certain types of boundary value problems about complex configurations is presented. Numerical algorithms from such diverse fields as finite elements, preconditioned Krylov subspace methods, discrete Fourier analysis, and integral equations are combined to take advantage of the memory, speed and architecture of current and emerging supercomputers. Although the approach has application to many branches of computational physics, the present effort is concentrated in areas of Computational Fluid Dynamics (CFD) such as steady nonlinear aerodynamics, time harmonic unsteady aerodynamics, and aeroacoustics. The most significant attribute of the approach is that it can handle truly arbitrary boundary geometries and eliminates the difficult task of generating surface fitted grids.

Rubbert, P. E.↗

Controller reduction by preserving impulse response energy

A model order reduction algorithm based on a Krylov recurrence formulation is developed to reduce order of controllers. The reduced-order controller is obtained by projecting the full-order LQG controller onto a Krylov subspace in which either the controllability or the observability grammian is equal to the identity matrix. The reduced-order controller preserves the impulse response energy of the full-order controller and has a parameter-matching property. Two numerical examples drawn from other controller reduction literature are used to illustrate the efficacy of the proposed reduction algorithm.

Craig, Roy R., Jr.↗

Application of the TRANAIR rectangular grid approach to the aerodynamic analysis of complex configurations

A numerical method is described which uses a rectangular grid to solve the nonlinear full potential equation about complex configurations. The grid is locally refined to resolve high velocity gradients arising from leading edge expansions or shock waves. The grid penetrates the boundary (described by networks of quadrilateral panels) and is generated automatically. Discrete operators are constructed using the finite element method. The system of nonlinear discrete equations is solved iteratively using a Krylov subspace method preconditioned by an exterior Poisson solver and a direct sparse solver. The primary emphasis is to provide design engineers with an aerodynamic analysis tool (the TRANAIR code) which is accurate, reliable, economical, and flexible to use. Computational results for many interesting configurations are presented.

Johnson, Forrester T.↗

Parallel iterative methods for sparse linear and nonlinear equations

As three-dimensional models are gaining importance, iterative methods will become almost mandatory. Among these, preconditioned Krylov subspace methods have been viewed as the most efficient and reliable, when solving linear as well as nonlinear systems of equations. There has been several different approaches taken to adapt iterative methods for supercomputers. Some of these approaches are discussed and the methods that deal more specifically with general unstructured sparse matrices, such as those arising from finite element methods, are emphasized.

Saad, Youcef↗

Numerical methods in Markov chain modeling

Several methods for computing stationary probability distributions of Markov chains are described and compared. The main linear algebra problem consists of computing an eigenvector of a sparse, usually nonsymmetric, matrix associated with a known eigenvalue. It can also be cast as a problem of solving a homogeneous singular linear system. Several methods based on combinations of Krylov subspace techniques are presented. The performance of these methods on some realistic problems are compared.

Philippe, Bernard↗

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

Efficient solution of parabolic equations by Krylov approximation methods

Numerical techniques for solving parabolic equations by the method of lines is addressed. The main motivation for the proposed approach is the possibility of exploiting a high degree of parallelism in a simple manner. The basic idea of the method is to approximate the action of the evolution operator on a given state vector by means of a projection process onto a Krylov subspace. Thus, the resulting approximation consists of applying an evolution operator of a very small dimension to a known vector which is, in turn, computed accurately by exploiting well-known rational approximations to the exponential. Because the rational approximation is only applied to a small matrix, the only operations required with the original large matrix are matrix-by-vector multiplications, and as a result the algorithm can easily be parallelized and vectorized. Some relevant approximation and stability issues are discussed. We present some numerical experiments with the method and compare its performance with a few explicit and implicit algorithms.

Gallopoulos, E.↗

Iterative solution of linear systems

Recent advances in the field of iterative methods for solving large linear systems are reviewed. The main focus is on developments in the area of conjugate gradient-type algorithms and Krylov subspace methods for nonHermitian matrices.

Freund, Roland W.↗

Towards a generalized computational fluid dynamics technique for all Mach numbers

Currently there exists no single unified approach for efficiently and accurately solving computational fluid dynamics (CFD) problems across the Mach number regime, from truly low speed incompressible flows to hypersonic speeds. There are several CFD codes that have evolved into sophisticated prediction tools with a wide variety of features including multiblock capabilities, generalized chemistry and thermodynamics models among other features. However, as these codes evolve, the demand placed on the end user also increases simply because of the myriad of features that are incorporated into these codes. In order for a user to be able to solve a wide range of problems, several codes may be needed requiring the user to be familiar with the intricacies of each code and their rather complicated input files. Moreover, the cost of training users and maintaining several codes becomes prohibitive. The objective of the current work is to extend the compressible, characteristic-based, thermochemical nonequilibrium Navier-Stokes code GASP to very low speed flows and simultaneously improve convergence at all speeds. Before this work began, the practical speed range of GASP was Mach numbers on the order of 0.1 and higher. In addition, a number of new techniques have been developed for more accurate physical and numerical modeling. The primary focus has been on the development of optimal preconditioning techniques for the Euler and the Navier-Stokes equations with general finite-rate chemistry models and both equilibrium and nonequilibrium thermodynamics models. We began with the work of Van Leer, Lee, and Roe for inviscid, one-dimensional perfect gases and extended their approach to include three-dimensional reacting flows. The basic steps required to accomplish this task were a transformation to stream-aligned coordinates, the formulation of the preconditioning matrix, incorporation into both explicit and implicit temporal integration schemes, and modification of the numerical flux formulae. In addition, we improved the convergence rate of the implicit time integration schemes in GASP through the use of inner iteration strategies and the use of the GMRES (General Minimized Resisual) which belongs to the class of algorithms referred to as Krylov subspace iteration. Finally, we significantly improved the practical utility of GASP through the addition of mesh sequencing, a technique in which computations begin on a coarse grid and get interpolated onto successively finer grids. The fluid dynamic problems of interest to the propulsion community involve complex flow physics spanning different velocity regimes and possibly involving chemical reactions. This class of problems results in widely disparate time scales causing numerical stiffness. Even in the absence of chemical reactions, eigenvalue stiffness manifests itself at transonic and very low speed flows which can be quantified by the large condition number of the system and evidenced by slow convergence rates. This results in the need for thorough numerical analysis and subsequent implementation of sophisticated numerical techniques for these difficult yet practical problems. As a result of this work, we have been able to extend the range of applicability of compressible codes to very low speed inviscid flows (M = .001) and reacting flows.

Walters, R. W.↗

Preconditioned conjugate gradient methods for the Navier-Stokes equations

A preconditioned Krylov subspace method (GMRES) is used to solve the linear systems of equations formed at each time-integration step of the unsteady, two-dimensional, compressible Navier-Stokes equations of fluid flow. The Navier-Stokes equations are cast in an implicit, upwind finite-volume, flux-split formulation. Several preconditioning techniques are investigated to enhance the efficiency and convergence rate of the implicit solver based on the GMRES algorithm. The superiority of the new solver is established by comparisons with a conventional implicit solver, namely line Gauss-Seidel relaxation (LGSR). Computational test results for low-speed (incompressible flow over a backward-facing step at Mach 0.1), transonic flow (trailing edge flow in a transonic turbine cascade), and hypersonic flow (shock-on-shock interactions on a cylindrical leading edge at Mach 6.0) are presented. For the Mach 0.1 case, overall speedup factors of up to 17 (in terms of time-steps) and 15 (in terms of CPU time on a CRAY-YMP/8) are found in favor of the preconditioned GMRES solver, when compared with the LGSR solver. The corresponding speedup factors for the transonic flow case are 17 and 23, respectively. The hypersonic flow case shows slightly lower speedup factors of 9 and 13, respectively. The study of preconditioners conducted in this research reveals that a new LUSGS-type preconditioner is much more efficient than a conventional incomplete LU-type preconditioner.

Ajmani, Kumud↗

Implicity restarted Arnoldi/Lanczos methods for large scale eigenvalue calculations

Eigenvalues and eigenfunctions of linear operators are important to many areas of applied mathematics. The ability to approximate these quantities numerically is becoming increasingly important in a wide variety of applications. This increasing demand has fueled interest in the development of new methods and software for the numerical solution of large-scale algebraic eigenvalue problems. In turn, the existence of these new methods and software, along with the dramatically increased computational capabilities now available, has enabled the solution of problems that would not even have been posed five or ten years ago. Until very recently, software for large-scale nonsymmetric problems was virtually non-existent. Fortunately, the situation is improving rapidly. The purpose of this article is to provide an overview of the numerical solution of large-scale algebraic eigenvalue problems. The focus will be on a class of methods called Krylov subspace projection methods. The well-known Lanczos method is the premier member of this class. The Arnoldi method generalizes the Lanczos method to the nonsymmetric case. A recently developed variant of the Arnoldi/Lanczos scheme called the Implicitly Restarted Arnoldi Method is presented here in some depth. This method is highlighted because of its suitability as a basis for software development.

Sorensen, Danny C.↗

MGLab: An Interactive Multigrid Environment

MGLab is a set of Matlab functions that defines an interactive environment for experimenting with multigrid algorithms. The package solves two-dimensional elliptic partial differential equations discretized using either finite differences or finite volumes, depending on the problem. Built-in problems include the Poisson equation, the Helmholtz equation, a convection-diffusion problem, and a discontinuous coefficient problem. A number of parameters controlling the multigrid V-cycle can be set using a point-and-click mechanism. The menu-based user interface also allows a choice of several Krylov subspace methods, including CG, GMRES(k), and Bi-CGSTAB, which can be used either as stand-alone solvers or as multigrid acceleration schemes. The package exploits Matlab's visualization and sparse matrix features and has been structured to be easily extensible.

Bordner, James↗

Wavelet Sparse Approximate Inverse Preconditioners

There is an increasing interest in using sparse approximate inverses as preconditioners for Krylov subspace iterative methods. Recent studies of Grote and Huckle and Chow and Saad also show that sparse approximate inverse preconditioner can be effective for a variety of matrices, e.g. Harwell-Boeing collections. Nonetheless a drawback is that it requires rapid decay of the inverse entries so that sparse approximate inverse is possible. However, for the class of matrices that, come from elliptic PDE problems, this assumption may not necessarily hold. Our main idea is to look for a basis, other than the standard one, such that a sparse representation of the inverse is feasible. A crucial observation is that the kind of matrices we are interested in typically have a piecewise smooth inverse. We exploit this fact, by applying wavelet techniques to construct a better sparse approximate inverse in the wavelet basis. We shall justify theoretically and numerically that our approach is effective for matrices with smooth inverse. We emphasize that in this paper we have only presented the idea of wavelet approximate inverses and demonstrated its potential but have not yet developed a highly refined and efficient algorithm.

Chan, Tony F.↗

A Reduced Order Model of the Linearized Incompressible Navier-Strokes Equations for the Sensor/Actuator Placement Problem

A reduced order modeling approach of the Navier-Stokes equations is presented for the design of a distributed optimal feedback kernel. This approach is based oil a Krylov subspace method where significant modes of the flow are captured in the model This model is then used in all optimal feedback control design where sensing and actuation is performed oil tile entire flow field. This control design approach yields all optimal feedback kernel which provides insight into the placement of sensors and actuators in the flow field. As all evaluation of this approach, a two-dimensional shear layer and driven cavity flow are investigated.

Allan, Brian G.↗

Some Remarks on GMRES for Transport Theory

We review some work on the application of GMRES to the solution of the discrete ordinates transport equation in one-dimension. We note that GMRES can be applied directly to the angular flux vector, or it can be applied to only a vector of flux moments as needed to compute the scattering operator of the transport equation. In the former case we illustrate both the delights and defects of ILU right-preconditioners for problems with anisotropic scatter and for problems with upscatter. When working with flux moments we note that GMRES can be used as an accelerator for any existing transport code whose solver is based on a stationary fixed-point iteration, including transport sweeps and DSA transport sweeps. We also provide some numerical illustrations of this idea. We finally show how space can be traded for speed by taking multiple transport sweeps per GMRES iteration. Key Words: transport equation, GMRES, Krylov subspace

Patton, Bruce W.↗