Search NASA⌕ Search

SEARCH · Search NASA

Results for “Krylov”

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 19 records

Hierarchical Krylov and nested Krylov methods for extreme-scale computing

The solution of large, sparse linear systems is typically a dominant phase of computation for simulations based on partial differential equations, which are ubiquitous in scientific and engineering applications. While preconditioned Krylov methods are widely used and provide many advantages for solving sparse linear systems that do not have highly convergent, geometric multigrid solvers or specialized fast solvers, Krylov methods encounter well-known scaling difficulties for over 10,000 processor cores because each iteration requires at least one vector inner product, which in turn requires a global synchronization that scales poorly because of internode latency. To aid in overcoming these difficulties, we have developed hierarchical Krylov methods and nested Krylov methods in the PETSc library that reduce the number of global inner products required across the entire system (where they are expensive), though freely allow vector inner products across smaller subsets of the entire system (where they are inexpensive) or use inner iterations that do not invoke vector inner products at all. Nested Krylov methods are a generalization of inner-outer iterative methods with two or more layers. Hierarchical Krylov methods are a generalization of block Jacobi and overlapping additive Schwarz methods, where each block itself is solved by Krylov methods on smaller blocks. Conceptually, the hierarchy can continue recursively to an arbitrary number of levels of smaller and smaller blocks. As a specific case, we introduce the hierarchical FGMRES method, or h-FGMRES, and we demonstrate the impact of two-level h-FGMRES with a variable preconditioner on the PFLOTRAN subsurface flow application. We also demonstrate the impact of nested FGMRES, BiCGStab and Chebyshev methods. These hierarchical Krylov methods and nested Krylov methods significantly reduced overall PFLOTRAN simulation time on the Cray XK6 when using 10,000 through 224,000 cores through the combined effects of reduced global synchronization due to fewer global inner products and stronger inner hierarchical or nested preconditioners.

97 MATHEMATICS AND COMPUTING↗

Block Krylov Subspace Methods for Functions of Matrices II: Modified Block FOM

We analyze an expansion of the generalized block Krylov subspace framework of [Electron. Trans. Numer. Anal., 47 (2017), pp. 100--126]. This expansion allows the use of low-rank modifications of the matrix projected onto the block Krylov subspace and contains, as special cases, the block GMRES method and the new block Radau--Arnoldi method. Within this general setting, we present results that extend the interpolation property from the nonblock case to a matrix polynomial interpolation property for the block case, and we relate the eigenvalues of the projected matrix to the latent roots of these matrix polynomials. Some error bounds for these modified block FOM methods for solving linear systems are presented. We then show how cospatial residuals can be preserved in the case of families of shifted linear block systems. This result is used to derive computationally practical restarted algorithms for block Krylov approximations that compute the action of a matrix function on a set of several vectors simultaneously. Finally, we prove some error bounds and present numerical results showing that two modifications of FOM, the block harmonic and the block Radau--Arnoldi methods for matrix functions, can significantly improve the convergence behavior.

97 MATHEMATICS AND COMPUTING↗

A Jacobian-free Newton Krylov method for mortar-discretized thermomechanical contact problems

Multibody contact problems are common within the field of multiphysics simulation. Applications involving thermomechanical contact scenarios are also quite prevalent. Such problems can be challenging to solve due to the likelihood of thermal expansion affecting contact geometry which, in turn, can change the thermal behavior of the components being analyzed. This paper explores a simple model of a light water reactor nuclear fuel rod, which consists of cylindrical pellets of uranium dioxide (UO{sub 2}) fuel sealed within a Zircalloy cladding tube. The tube is initially filled with helium gas, which fills the gap between the pellets and cladding tube. The accurate modeling of heat transfer across the gap between fuel pellets and the protective cladding is essential to understanding fuel performance, including cladding stress and behavior under irradiated conditions, which are factors that affect the lifetime of the fuel. The thermomechanical contact approach developed here is based on the mortar finite element method, where Lagrange multipliers are used to enforce weak continuity constraints at participating interfaces. In this formulation, the heat equation couples to linear mechanics through a thermal expansion term. Lagrange multipliers are used to formulate the continuity constraints for both heat flux and interface traction at contact interfaces. The resulting system of nonlinear algebraic equations are cast in residual form for solution of the transient problem. A Jacobian-free Newton Krylov method is used to provide for fully-coupled solution of the coupled thermal contact and heat equations.

11 NUCLEAR FUEL CYCLE AND FUEL MATERIALS↗

Multigrid in energy preconditioner for Krylov solvers

We have added a new multigrid in energy (MGE) preconditioner to the Denovo discrete-ordinates radiation transport code. This preconditioner takes advantage of a new multilevel parallel decomposition. A multigroup Krylov subspace iterative solver that is decomposed in energy as well as space-angle forms the backbone of the transport solves in Denovo. The space-angle-energy decomposition facilitates scaling to hundreds of thousands of cores. The multigrid in energy preconditioner scales well in the energy dimension and significantly reduces the number of Krylov iterations required for convergence. This preconditioner is well-suited for use with advanced eigenvalue solvers such as Rayleigh Quotient Iteration and Arnoldi.

97 MATHEMATICS AND COMPUTING↗

Solving phase appearance/disappearance two-phase flow problems with high resolution staggered grid and fully implicit schemes by the Jacobian-free Newton–Krylov Method

The phase appearance/disappearance issue presents serious numerical challenges in two-phase flow simulations. Many existing reactor safety analysis codes use different kinds of treatments for the phase appearance/disappearance problem. However, to our best knowledge, there are no fully satisfactory solutions. Additionally, the majority of the existing reactor system analysis codes were developed using low-order numerical schemes in both space and time. In many situations, it is desirable to use high-resolution spatial discretization and fully implicit time integration schemes to reduce numerical errors. In this work, we adapted a high-resolution spatial discretization scheme on staggered grid mesh and fully implicit time integration methods (such as BDF1 and BDF2) to solve the two-phase flow problems. The discretized nonlinear system was solved by the Jacobian-free Newton Krylov (JFNK) method, which does not require the derivation and implementation of analytical Jacobian matrix. These methods were tested with a few two-phase flow problems with phase appearance/disappearance phenomena considered, such as a linear advection problem, an oscillating manometer problem, and a sedimentation problem. The JFNK method demonstrated extremely robust and stable behaviors in solving the two-phase flow problems with phase appearance/disappearance. No special treatments such as water level tracking or void fraction limiting were used. High-resolution spatial discretization and second- order fully implicit method also demonstrated their capabilities in significantly reducing numerical errors.

97 MATHEMATICS AND COMPUTING↗

Strong and almost strong modes of Floquet spin chains in Krylov subspaces

Integrable Floquet spin chains are known to host strong zero and π modes which are boundary operators that respectively commute and anticommute with the Floquet unitary generating stroboscopic time evolution, in addition to anticommuting with a discrete symmetry of the Floquet unitary. Thus the existence of strong modes implies a characteristic pairing structure of the full spectrum. Weak interactions modify the strong modes to almost strong modes that almost commute or anticommute with the Floquet unitary. Manifestations of strong and almost strong modes are presented in two different Krylov subspaces. One is a Krylov subspace obtained from a Lanczos iteration that maps the time evolution generated by the Floquet Hamiltonian onto dynamics of a single particle on a fictitious chain with nearest-neighbor hopping. The second is a Krylov subspace obtained from the Arnoldi iteration that maps the time evolution generated directly by the Floquet unitary onto dynamics of a single particle on a fictitious chain with longer-range hopping. While the former Krylov subspace is sensitive to the branch of the logarithm of the Floquet unitary, the latter obtained from the Arnoldi scheme is not. In this work, the effective single-particle models in the Krylov subspace are discussed, and the topological properties of the Krylov chain that ensure stable zero and π modes at the boundaries are highlighted. The role of interactions is discussed. Expressions for the lifetime of the almost strong modes are derived in terms of the parameters of the Krylov subspace, and are compared with exact diagonalization.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗

Building Krylov complexity from circuit complexity

Krylov complexity has emerged as a probe of operator growth in a wide range of nonequilibrium quantum dynamics. However, a fundamental issue remains in such studies: the definition of the distance between basis states in Krylov space is ambiguous. Here we show that Krylov complexity can be rigorously established from circuit complexity when dynamical symmetries exist. Whereas circuit complexity characterizes the geodesic distance in a multidimensional operator space, Krylov complexity measures the height of the final operator in a particular direction. The geometric representation of circuit complexity thus unambiguously designates the distance between basis states in Krylov space. This geometric approach also applies to time-dependent Liouvillian superoperators, where a single Krylov complexity is no longer sufficient. Multiple Krylov complexity may be exploited jointly to fully describe operator dynamics. Published by the American Physical Society 2024

Lv, Chenwei (ORCID:0000000250952582)↗

Newton-Krylov-Schwarz: An implicit solver for CFD

Newton-Krylov methods and Krylov-Schwarz (domain decomposition) methods have begun to become established in computational fluid dynamics (CFD) over the past decade. The former employ a Krylov method inside of Newton's method in a Jacobian-free manner, through directional differencing. The latter employ an overlapping Schwarz domain decomposition to derive a preconditioner for the Krylov accelerator that relies primarily on local information, for data-parallel concurrency. They may be composed as Newton-Krylov-Schwarz (NKS) methods, which seem particularly well suited for solving nonlinear elliptic systems in high-latency, distributed-memory environments. We give a brief description of this family of algorithms, with an emphasis on domain decomposition iterative aspects. We then describe numerical simulations with Newton-Krylov-Schwarz methods on aerodynamics applications emphasizing comparisons with a standard defect-correction approach, subdomain preconditioner consistency, subdomain preconditioner quality, and the effect of a coarse grid.

Cai, Xiao-Chuan↗

Improvements in Block-Krylov Ritz Vectors and the Boundary Flexibility Method of Component Synthesis

A method of dynamic substructuring is presented which utilizes a set of static Ritz vectors as a replacement for normal eigenvectors in component mode synthesis. This set of Ritz vectors is generated in a recurrence relationship, proposed by Wilson, which has the form of a block-Krylov subspace. The initial seed to the recurrence algorithm is based upon the boundary flexibility vectors of the component. Improvements have been made in the formulation of the initial seed to the Krylov sequence, through the use of block-filtering. A method to shift the Krylov sequence to create Ritz vectors that will represent the dynamic behavior of the component at target frequencies, the target frequency being determined by the applied forcing functions, has been developed. A method to terminate the Krylov sequence has also been developed. Various orthonormalization schemes have been developed and evaluated, including the Cholesky/QR method. Several auxiliary theorems and proofs which illustrate issues in component mode synthesis and loss of orthogonality in the Krylov sequence have also been presented. The resulting methodology is applicable to both fixed and free- interface boundary components, and results in a general component model appropriate for any type of dynamic analysis. The accuracy is found to be comparable to that of component synthesis based upon normal modes, using fewer generalized coordinates. In addition, the block-Krylov recurrence algorithm is a series of static solutions and so requires significantly less computation than solving the normal eigenspace problem. The requirement for less vectors to form the component, coupled with the lower computational expense of calculating these Ritz vectors, combine to create a method more efficient than traditional component mode synthesis.

Carney, Kelly Scott↗

Moment method and continued fraction expansion in Floquet operator Krylov space

Recursion methods such as Krylov techniques map complex dynamics to an effective noninteracting problem in one dimension. For example, the operator Krylov space for Floquet dynamics can be mapped to the dynamics of an edge operator of the one-dimensional Floquet inhomogeneous transverse field Ising model (ITFIM), where the latter, after a Jordan-Wigner transformation, is a Floquet model of noninteracting Majorana fermions and the couplings correspond to Krylov angles. We present an application of this showing that a moment method exists where given an autocorrelation function, one can construct the corresponding Krylov angles and from that the corresponding Floquet ITFIM. Consequently, when no solutions for the Krylov angles are obtained, it indicates that the autocorrelation is not generated by unitary dynamics. We highlight this by studying certain special cases: stable m-period dynamics derived using the method of continued fractions, exponentially decaying, and power-law decaying stroboscopic dynamics. Remarkably, our examples of stable m-period dynamics correspond to m-period edge modes for the Floquet ITFIM where, deep in the chain, the couplings correspond to a critical phase. Furthermore our results pave the way to engineer Floquet systems with desired properties of edge modes and also provide examples of persistent edge modes in gapless Floquet systems.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗

Understanding performance variability in standard and pipelined parallel Krylov solvers

In this work, we collect data from runs of Krylov subspace methods and pipelined Krylov algorithms in an effort to understand and model the impact of machine noise and other sources of variability on performance. We find large variability of Krylov iterations between compute nodes for standard methods that is reduced in pipelined algorithms, directly supporting conjecture, as well as large variation between statistical distributions of runtimes across iterations. Based on these results, we improve upon a previously introduced nondeterministic performance model by allowing iterations to fluctuate over time. We present our data from runs of various Krylov algorithms across multiple platforms as well as our updated non-stationary model that provides good agreement with observations. We also suggest how it can be used as a predictive tool.

97 MATHEMATICS AND COMPUTING↗

Solving Coupled Cluster Equations by the Newton Krylov Method

We describe using the Newton Krylov method to solve the coupled cluster equation. The method uses a Krylov iterative method to compute the Newton correction to the approximate coupled cluster amplitude. The multiplication of the Jacobian with a vector, which is required in each step of a Krylov iterative method such as the Generalized Minimum Residual (GMRES) method, is carried out through a finite difference approximation, and requires an additional residual evaluation. The overall cost of the method is determined by the sum of the inner Krylov and outer Newton iterations. We discuss the termination criterion used for the inner iteration and show how to apply pre-conditioners to accelerate convergence. We will also examine the use of regularization technique to improve the stability of convergence and compare the method with the widely used direct inversion of iterative subspace (DIIS) methods through numerical examples.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Quantum Krylov subspace algorithms for ground- and excited-state energy estimation

Quantum Krylov subspace diagonalization (QKSD) algorithms provide a low-cost alternative to the conventional quantum phase estimation algorithm for estimating the ground- and excited-state energies of a quantum many-body system. While QKSD algorithms typically rely on using the Hadamard test for estimating Krylov subspace matrix elements of the form $\langle \phi_i|e^{-\widehat{H}τ}|\phi_j\rangle$, the associated quantum circuits require an ancilla qubit with controlled multiqubit gates that can be quite costly for near-term quantum hardware. In this paper, we show that a wide class of Hamiltonians relevant to condensed-matter physics and quantum chemistry contain symmetries that can be exploited to avoid the use of the Hadamard test. We propose a multifidelity estimation protocol that can be used to compute such quantities, showing that our approach, when combined with efficient single-fidelity estimation protocols, provides a substantial reduction in circuit depth. In addition, here we develop a unified theory of quantum Krylov subspace algorithms and present three quantum-classical algorithms for the ground- and excited-state energy estimation problems, where each algorithm provides various advantages and disadvantages in terms of total number of calls to the quantum computer, gate depth, classical complexity, and stability of the generalized eigenvalue problem within the Krylov subspace.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Krylov spaces for truncated spectrum methodologies

We propose herein an extension of truncated spectrum methodologies, a nonperturbative numerical approach able to elucidate the low energy properties of quantum field theories. TSMs, in their various flavors, involve a division of a computational Hilbert space, H , into two parts, one part, H 1 that is “kept” for the numerical computations, and one part, H 2 , that is discarded or “truncated.” Even though H 2 is discarded, truncated spectrum methodologies will often try to incorporate the effects of H 2 in some effective way. In these terms, we propose to keep the dimension of H 1 small. We pair this choice of H 1 with a Krylov subspace iterative approach able to take into account the effects of H 2 . This iterative approach can be taken to arbitrarily high order and so offers the ability to compute quantities to arbitrary precision. In many cases it also offers the advantage of not needing an explicit UV cutoff. To compute the matrix elements that arise in the Krylov iterations, we employ a Feynman diagrammatic representation that is then evaluated with Monte Carlo techniques. Each order of the Krylov iteration is variational and is guaranteed to improve upon the previous iteration. The first Krylov iteration is akin to the next-to-leading order approach of Elias-Miró [NLO renormalization in the Hamiltonian truncation, ]. To demonstrate this approach, we focus on the ( 1 + 1 d )-dimensional ϕ 4 model and compute the bulk energy and mass gaps in both the Z 2 -broken and unbroken sectors. We estimate the critical ϕ 4 coupling in the broken phase to be g c = 0.2645 ± 0.002 . Published by the American Physical Society 2024

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗

Spectral functions with the density matrix renormalization group: Krylov-space approach for correction vectors

Frequency-dependent correlations, such as the spectral function and the dynamical structure factor, help illustrate condensed matter experiments. Within the density matrix renormalization group (DMRG) framework, an accurate method for calculating spectral functions directly in frequency is the correction-vector method. The correction vector can be computed by solving a linear equation or by minimizing a functional. Our paper proposes an alternative to calculate the correction vector: to use the Krylov-space approach. Further, this paper also studies the accuracy and performance of the Krylov-space approach, when applied to the Heisenberg, the t-J, and the Hubbard models. The cases we studied indicate that the Krylov-space approach can be more accurate and efficient than the conjugate gradient, and that the error of the former integrates best when a Krylov-space decomposition is also used for ground state DMRG.

36 MATERIALS SCIENCE↗

Block-Krylov component synthesis method for structural model reduction

A new analytical method is presented for generating component shape vectors, or Ritz vectors, for use in component synthesis. Based on the concept of a block-Krylov subspace, easily derived recurrence relations generate blocks of Ritz vectors for each component. The subspace spanned by the Ritz vectors is called a block-Krylov subspace. The synthesis uses the new Ritz vectors rather than component normal modes to reduce the order of large, finite-element component models. An advantage of the Ritz vectors is that they involve significantly less computation than component normal modes. Both 'free-interface' and 'fixed-interface' component models are derived. They yield block-Krylov formulations paralleling the concepts of free-interface and fixed-interface component modal synthesis. Additionally, block-Krylov reduced-order component models are shown to have special disturbability/observability properties. Consequently, the method is attractive in active structural control applications, such as large space structures. The new fixed-interface methodology is demonstrated by a numerical example. The accuracy is found to be comparable to that of fixed-interface component modal synthesis.

Craig, Roy R., Jr.↗