Search NASA⌕ Search

SEARCH · Search NASA

Results for “Arnoldi method”

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.

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↗

Calculation of Higher Eigenpairs of the Transport Equation Using IRAM Based on Domain Decomposition

The higher eigenpairs of the neutron transport (or diffusion) equation are useful in core flux distribution reconstruction, transient analysis, stability analysis, and loading pattern optimization. There are various methods for the calculation of higher eigenpairs, such as the power iteration method with filtering technique, the Generalized Modified Power Method (GMPM), the power iteration method with innovative boundary conditions for symmetric cores, and Krylov subspace methods. In regard to Krylov subspace methods, the Implicitly Restarted Arnoldi Method (IRAM) and ORTHOMIN were implemented to calculate higher eigenpairs for both transport and diffusion equations. In Warsa's work, however, there was a significant drawback that problems with energy upscatter could not be treated efficiently. In Modak's work, the mode to which his method was likely to converge depended on the shape of initial guess flux, and only one mode could be computed each time, making it impractical for real use. Furthermore, the computational burden for higher eigenpairs is generally much larger than for only the first eigenpair, especially for neutron transport equations. Therefore, the implementation of parallel computation for higher eigenpairs is essential to improve the efficiency, and no such work has been reported in literature so far. In this summary, we propose an innovative method to calculate higher eigenpairs of the neutron transport equation based on high performance computation. In this method, 2D Matrix Method of Characteristic (MMOC) is used to discretize the neutron transport equation; IRAM is used to evaluate higher eigenpairs; spatial domain decomposition is used to realize parallel computation. The highlight of this method is using the MGMD PGMRES (Multi-Group and Multi-Domain coupled Parallel Generalized Minimal Residual Method) algorithm to simultaneously accelerate the upscatter iterations and the inner interface angular fluxes iterations, avoiding the drawback in Warsa's method and the efficiency problem of conventional Jacobi iteration. To the best of our knowledge, our work represents the first application of IRAM based on domain decomposition for higher eigenpairs.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗

ORNL_AISD-Ex: Quantum chemical prediction of UV/Vis absorption spectra for over 10 million organic molecules

We performed calculations of electronic excitation energies and associated oscillator strengths based on the time-dependent density-functional tight-binding (TD-DFTB) method [1]. The SMILES (Simplified molecular-input line-entry system) strings of the molecules from the AISD HOMO-LUMO database [2] were converted to a 3D atomistic structure and stored in a PDB file after preliminary geometry optimization using the Merck Molecular Force Field (MMFF94) in RDKit [3,4]. The primary information stored in the PDB file archive consists of Cartesian coordinates for each atom of the molecule in their 3D location in space, along with summary information about the structure, sequence, and experiment. We then performed molecular geometry optimization using the density-functional tight-binding (DFTB) method [5] in the electronic ground state, followed by single-point excited states calculations, as described below. We note that, since RDKit employs a random choice for the generation of molecular conformers, the molecular geometries obtained in this dataset could be different from the ones that were generated when the AISD HOMO-LUMO dataset was generated. The computed excitation energies and associated oscillator strengths can be converted to predict UV/Vis absorption spectra, where excitation energies correspond to absorption peak positions, and oscillator strengths are a good measure of the probability of absorption of visible or UV light in transitions between electronic ground and excited states. The conversion of SMILES strings to 3D Cartesian coordinates of fully DFTB-optimized molecules was successful for 10,502,904 out of 10,502,917 molecules. For these molecules, both geometry optimizations and excited states calculations were successful. The DFTB calculations did not complete for 13 molecules of the original AISD HOMO-LUMO dataset. We still provide information about the geometry of these molecules. The molecules are diverse for chemical compositions (which span 5 non-hydrogen elements: oxygen, carbon, nitrogen, fluorine, sulfur) and molecular size (the smallest molecule contains 5 non-hydrogen atoms, and the largest molecule contains 71 non-hydrogen atoms). The DFTB method [5] is an approximation to density functional theory (DFT), utilizing a minimal basis set in conjunction with a two-center approximation to the electronic Hamiltonian and overlap matrix elements. The DFTB total energy is the sum of an electronic and a repulsive energy contribution, and their calculation requires optimized electronic parameters and diatomic repulsive potential energy functions. All DFTB calculations were performed using the DFTB+ code [6] (version 21.2) and the wrapper for DFTB+ in the Atomic Simulation Environment (ASE) (version 3.22.1) [7], which performed an internal conversion of Cartesian coordinates from PDB to the .gen file format. For the geometry optimizations on the electronic ground state potential energy surface of the molecules, we have chosen the third-order DFTB (DFTB3) method [5c] and employed the matching 3ob set of electronic parameters and repulsive potentials [8]. The empirical γ-damping for hydrogen bond correction, and Grimme's D3 empirical dispersion correction with Becke-Johnson damping (D3(BJ)) [9] dispersion correction was included to improve the description of non-covalent interactions. For excited states single-point energy calculations, we employed the TD-DFTB method in conjunction with the DFTB2 method [5b] and the matching mio [5b,10] and halorg [11] parameter sets. We opted to request the simultaneous calculation of 50 excited states for singlet transition to investigate sufficient number of excited states, based on linear response theory using the Casida equation [Ref: T. A. Niehaus, S. Suhai, F. Della Sala, P Lugli, M. Elstner, G. Seifert, and Th. Frauenheim. Tight-binding approach to time-dependent density-functional response theory. Phys. Rev. B, 63:085108, 2001] and the ARPACK diagonalizer [R. B. Lehoucq, D. C. Sorensen, and C. Yang. Arpack users guide: Solution of large-scale eigenvalue problems by implicitly restarted arnoldi methods, 1997. 46, 51]. The dataset contains 1001 tar.gz files. Tar files are named as “ornl_aisd_ex_1.tar.gz†through “ornl_aisd_ex_1000.tar.gzâ€. Additionally, the 13 failed molecules are in “ornl_aisd_ex_unprocessed.tar.gzâ€. Except for the tar files listed below, each tar file contains 10,500 molecules. Tar files numbered 34, 121, 128, 352, 360, 429, 495, 509, 518, 627, 676, 668, and 862 contain 10,499 molecules each. The last tar file numbered 1000 contains 13,417 molecules. The total size of the uncompressed dataset is over 283 Gigabytes. The code for calculating the electronic excitation energies and statistical analysis of the dataset is provided at the following GitLab repository: https://github.com/ORNL/Analysis-of-Large-Scale-Molecular-Datasets-with-Python Calculating the UV spectrum of a molecule requires performing 3 main operations: 1. Converting the smiles string representation of a molecule into a geometric structure where each atom is assigned XYZ coordinates. The geometric structure is written to the file smiles.pdb. 2. Using smiles.pdb to compute the relaxed geometry of the molecule, which corresponds with the position of the atoms at the position of equilibrium at the ground state. This generates the files band.out, detailed.out, and geo_end.gen. 3. Using geo_end.gen to calculate the UV spectrum of the molecule which is written into the file EXC.DAT. Every molecule in the dataset has its own directory. The files contained in each molecule directory are as follows: 1. geo_end.gen 2. detailed.out 3. band.out 4. EXC.DAT 5. smiles.pdb REFERENCES [1] Niehaus, T. A.; Suhai, S.; Della Salla, F.; Lugli, P.; Elstner, M.; Seifert, G.; Frauenheim, Th. Tight-binding approach to time-dependent density-functional response theory. Phys. Rev. B, 2001, 63, 085108/1-9. [2] Blanchard, A.; Gounley, J.; Metha, K.; Yoo, P.; Irle, S. AISD HOMO-LUMO. DOI: 10.13139/ORNLNCCS/1869409 [3] RDKit: Cheminformatics and Machine Learning Software. 2013, [http://www.rdkit.org] [4] Tosco, P.; Stiefl, N. and Landrum, G. Bringing the MMFF force field to the RDKit: implementation and validation. J Cheminform. 2014, 6, 1–4. [5] a) Porezag, D.; Frauenheim, T.; Kohler, T.; Seifert, G.; Kaschner, Construction of tight-binding-like potentials on the basis of density-functional theory: Application to carbon, R. Phys. Rev. B 1995, 51, 12947-12957; b) Elstner, M.; Porezag, D.; Jungnickel, G.; Elsner, J.; Haugk, M.; Frauenheim, Th.; Suhai, S.; Seifert, G.; Phys. Rev. B 1998, 58, 7260-7268; c) Gaus, M.; Cui, Q.; Elstner, M. DFTB3: Extension of the Self-Consistent-Charge Density-Functional Tight-Binding Method (SCC-DFTB), J. Chem. Theory Comput. 2011, 7, 931-948; d) Cui, Q.; Elstner, M. Density functional tight binding: values of semi-empirical methods in an ab initio era, Phys. Chem. Chem. Phys. 2014, 16, 14368-14377. [6] Hourahine, B. et al. DFTB+, a software package for efficient approximate density functional theory based atomistic simulations, J. Chem. Phys. 2020, 152, 124101/1-19. [7] Larsen, A. H. et al. The atomic simulation environment—a Python library for working with atoms. J. Phys.: Cond. Matter 2017, 29, 273002. [8] Kubillus, M.; Kubar, T.; Gaus, M.; Rezac, J.; Elstner, M. Parameterization of the DFTB3 Method for Br, Ca, Cl, F, I, K, and Na in Organic and Biological Systems, J. Chem. Theory Comput. 2015, 11, 332-342. [9] Brandenburg, J. G.; Grimme, S. Accurate Modeling of Organic Molecular Crystals by Dispersion-Corrected Density Functional Tight Binding (DFTB), J. Phys. Chem. Lett. 2014, 5, 1785−1789. [10] a) Niehaus, T. A.; Elstner, M.; Frauenheim, Th.; Suhai, S. Application of an approximate density-functional method to sulfur containing compounds. J. Mol. Struct.: THEOCHEM 2001, 541, 185-94; b) Elstner, M.; Hobza, P.; Frauenheim, Th.; Suhai, S.; Kaxiras, E. Hydrogen bonding and stacking interactions of nucleic acid base pairs: A density-functional-theory based treatment. J. Chem. Phys. 2001, 114, 5149-55. [11] Kubar, T.; Bodrog, Z.; Gaus, M.; Köhler, C.; Aradi, B.; Frauenheim, Th.; Elstner, M. Parametrization of the SCC-DFTB Method for Halogens. J. Chem. Theory Comput. 2013, 9, 2939-49.

36 MATERIALS SCIENCE↗

Polynomial Preconditioned Arnoldi with Stability Control

Polynomial preconditioning can improve the convergence of the Arnoldi method for computing eigenvalues. Such preconditioning significantly reduces the cost of orthogonalization; for difficult problems, it can also reduce the number of matrix-vector products. Parallel computations can particularly benefit from the reduction of communication-intensive operations. Additoinally, the GMRES algorithm provides a simple and effective way of generating the preconditioning polynomial. For some problems high degree polynomials are especially effective, but they can lead to stability problems that must be mitigated. A two-level “double polynomial preconditioning” strategy provides an effective way to generate high-degree preconditioners.

97 MATHEMATICS AND COMPUTING↗

A rank-exploiting infinite Arnoldi algorithm for nonlinear eigenvalue problems

We consider the nonlinear eigenvalue problem M ( λ ) x = 0, where M ( λ ) is a large parameter-dependent matrix. In several applications, M ( λ ) has a structure where the higher-order terms of its Taylor expansion have a particular low-rank structure. We propose a new Arnoldi-based algorithm that can exploit this structure. More precisely, the proposed algorithm is equivalent to Arnoldi's method applied to an operator whose reciprocal eigenvalues are solutions to the nonlinear eigenvalue problem. The iterates in the algorithm are functions represented in a particular structured vector-valued polynomial basis similar to the construction in the infinite Arnoldi method [Jarlebring, Michiels, and Meerbergen, Numer. Math., 122 (2012), pp. 169–195]. In this paper, the low-rank structure is exploited by applying an additional operator and by using a more compact representation of the functions. This reduces the computational cost associated with orthogonalization, as well as the required memory resources. The structure exploitation also provides a natural way in carrying out implicit restarting and locking without the need to impose structure in every restart. In conclusion, the efficiency and properties of the algorithm are illustrated with two large-scale problems.

97 MATHEMATICS AND COMPUTING↗

Recursive integral method with Cayley transformation

Summary The recently developed RIM (recursive integral method) finds eigenvalues in a region of the complex plane. It computes an indicator to test if the region contains eigenvalues using an approximate spectral projection. If the indicator shows that the region contains eigenvalues, it is subdivided into smaller regions, which are then recursively tested and subdivided until any eigenvalues are isolated to a specified precision. We propose an enhancement to RIM that uses Cayley transformations and Arnoldi's method to greatly decrease the number of factorizations required to solve the linear systems that arise from a discretized contour integral to compute the indicator, which substantially reduces the computational cost. We demonstrate the efficacy of our method with numerical examples and compare with the implicitly restarted Arnoldi method, as implemented in eigs in MATLAB.

Huang, R.↗

Low-synch Gram–Schmidt with delayed reorthogonalization for Krylov solvers

The parallel strong-scaling of iterative methods is often determined by the number of global reductions at each iteration. Low-synch Gram-Schmidt algorithms are applied here to the Arnoldi algorithm to reduce the number of global reductions and therefore to improve the parallel strong-scaling of iterative solvers for nonsymmetric matrices such as the GMRES and the Krylov-Schur iterative methods. In the Arnoldi context, the factorization is "left-looking" and processes one column at a time. Among the methods for generating an orthogonal basis for the Arnoldi algorithm, the classical Gram-Schmidt algorithm, with reorthogonalization (CGS2) requires three global reductions per iteration. A new variant of CGS2 that requires only one reduction per iteration is presented and applied to the Arnoldi algorithm. Delayed CGS2 (DCGS2) employs the minimum number of global reductions per iteration (one) for a one-column at-a-time algorithm. The main idea behind the new algorithm is to group global reductions by rearranging the order of operations. DCGS2 must be carefully integrated into an Arnoldi expansion or a GMRES solver. Numerical stability experiments assess robustness for Krylov-Schur eigenvalue computations. Performance experiments on the ORNL Summit supercomputer then establish the superiority of DCGS2 over CGS2.

97 MATHEMATICS AND COMPUTING↗

Iterated Gauss-Seidel GMRES

The GMRES algorithm of Saad and Schultz [SIAM J. Sci. Stat. Comput., 7 (1986), pp. 856-869] is an iterative method for approximately solving linear systems Ax = b, with initial guess x0 and residual r0 = b Ax0. The algorithm employs the Arnoldi process to generate the Krylov basis vectors (the columns of Vk ). It is well known that this process can be viewed as a QR factorization of the matrix Bk = [r0, AVk] at each iteration. Despite an O (..epsilon..)..kappa.. (Bk ) loss of orthogonality, for unit roundoff ..epsilon..and condition number ..kappa.. , the modified Gram-Schmidt formulation was shown to be backward stable in the seminal paper by Paige et al. [SIAM J. Matrix Anal.Appl., 28 (2006), pp. 264-284]. We present an iterated Gauss-Seidel formulation of the GMRES algorithm (IGS-GMRES) based on the ideas of Ruhe [Linear Algebra Appl., 52 (1983), pp. 591-601] and Swirydowicz et al. [Numer. Linear Algebra Appl., 28 (2020), pp. 1-20]. IGS-GMRES maintains orthogonality to the level O (..epsilon..)..kappa.. (Bk ) or O (..epsilon..), depending on the choice of one or two iterations; for two Gauss-Seidel iterations, the computed Krylov basis vectors remain orthogonal to working accuracy and the smallest singular value of Vk remains close to one. The resulting GMRES method is thus backward stable. We show that IGS-GMRES can be implemented with only a single synchronization point per iteration, making it relevant to large-scale parallel computing environments. We also demonstrate that, unlike MGS-GMRES, in IGS-GMRES the relative Arnoldi residual corresponding to the computed approximate solution no longer stagnates above machine precision even for highly nonnormal systems.

Arnoldi-QR↗

Equation-Free Coarse Control of Distributed Parameter Systems via Local Neural Operators

The control of high-dimensional distributed parameter systems (DPS) remains a challenge when explicit coarse-grained equations are unavailable. Classical equation-free (EF) approaches rely on fine-scale simulators treated as black-box timesteppers. However, repeated simulations for steady-state computation, linearization, and control design are often computationally prohibitive, or the microscopic timestepper may not even be available, leaving us with data as the only resource. We propose a data-driven alternative that uses local neural operators, trained on spatiotemporal microscopic/mesoscopic data, to obtain efficient short-time solution operators. These surrogates are employed within Krylov subspace methods to compute coarse steady and unsteady-states, while also providing Jacobian information in a matrix-free manner. Krylov-Arnoldi iterations then approximate the dominant eigenspectrum, yielding reduced models that capture the open-loop slow dynamics without explicit Jacobian assembly. Both discrete-time Linear Quadratic Regulator (dLQR) and pole-placement (PP) controllers are based on this reduced system and lifted back to the full nonlinear dynamics, thereby closing the feedback loop.

93B52, 93C20, 47N70, 65J15, 65M32, 68T07, 68T20, 6↗

Eigenvalue Solvers for Modeling Nuclear Reactors on Leadership Class Machines

In this paper, three complementary methods have been implemented in the code Denovo that accelerate neutral particle transport calculations with methods that use leadership-class computers fully and effectively: a multigroup block (MG) Krylov solver, a Rayleigh quotient iteration (RQI) eigenvalue solver, and a multigrid in energy (MGE) preconditioner. The MG Krylov solver converges more quickly than Gauss Seidel and enables energy decomposition such that Denovo can scale to hundreds of thousands of cores. RQI should converge in fewer iterations than power iteration (PI) for large and challenging problems. RQI creates shifted systems that would not be tractable without the MG Krylov solver. It also creates ill-conditioned matrices. The MGE preconditioner reduces iteration count significantly when used with RQI and takes advantage of the new energy decomposition such that it can scale efficiently. Each individual method has been described before, but this is the first time they have been demonstrated to work together effectively. The combination of solvers enables the RQI eigenvalue solver to work better than the other available solvers for large reactors problems on leadership-class machines. Using these methods together, RQI converged in fewer iterations and in less time than PI for a full pressurized water reactor core. These solvers also performed better than an Arnoldi eigenvalue solver for a reactor benchmark problem when energy decomposition is needed. The MG Krylov, MGE preconditioner, and RQI solver combination also scales well in energy. Finally, this solver set is a strong choice for very large and challenging problems.

22 GENERAL STUDIES OF NUCLEAR REACTORS↗

Variational treatment of electron–polyatomic-molecule scattering calculations using adaptive overset grids

In this paper, the complex Kohn variational method for electron–polyatomic-molecule scattering is formulated using an overset-grid representation of the scattering wave function. The overset grid consists of a central grid and multiple dense atom-centered subgrids that allow the simultaneous spherical expansions of the wave function about multiple centers. Scattering boundary conditions are enforced by using a basis formed by the repeated application of the free-particle Green's function and potential G ^ 0 + V ^ on the overset grid in a Born-Arnoldi solution of the working equations. The theory is shown to be equivalent to a specific Padé approximant to the T matrix and has rapid convergence properties, in both the number of numerical basis functions employed and the number of partial waves employed in the spherical expansions. The method is demonstrated in calculations on methane and CF 4 in the static-exchange approximation and compared in detail with calculations performed with the numerical Schwinger variational approach based on single-center expansions. Finally, an efficient procedure for operating with the free-particle Green's function and exchange operators (to which no approximation is made) is also described.

74 ATOMIC AND MOLECULAR PHYSICS↗

Balanced truncation-rational Krylov methods for model reduction in large scale dynamical systems

In this paper, we consider the balanced truncation method for model reductions in large-scale linear and time-independent dynamical systems with multi-inputs and multi-outputs. The method is based on the solutions of two large coupled Lyapunov matrix equations when the system is stable or on the computation of stabilizing positive and semi-definite solutions of some continuous-time algebraic Riccati equations when the dynamical system is not stable. Using the rational block Arnoldi, we show how to compute approximate solutions to these large Lyapunov or algebraic Riccati equations. The obtained approximate solutions are given in a factored form and used to build the reduced order model. We give some theoretical results and present numerical examples with some benchmark models.

97 MATHEMATICS AND COMPUTING↗