Numerical Algorithms

Areas of Research:

• Krylov Subspace Methods
  • Iterative Linear Solvers
    (Contacts: Michael A. Heroux, Raymond S. Tuminaro, David M. Day)
    Many important scientific engineering applications at Sandia require the use of linear solvers for solving large-scale linear equations. Some of the methods that are considered to be the most effective for solving these systems are Krylov subspace methods. Many of these methods can be found in the Aztec (http://www.cs.sandia.gov/CRF/aztec1.html) iterative solver package, which grew out of a specific application: modeling reacting flows (MPSalsa). It provides state-of-the-art iterative methods that perform well on parallel computers and at the same time are easy to use for application engineers. The iterative methods found in Aztec are: CG, CGS, BiCGSTAB, GMRES, and TFQMR.
    
    Recent research in software design has resulted in AztecOO
    (http://software.sandia.gov/Trilinos/packages/aztecoo/index.html), which provides an object-oriented interface the the well-known Aztec solver library. It improves upon Aztec by offering a more flexible construction of matrix and vector arguments (through Epetra) and additional functionality not found in Aztec. Equivalent Real Forms (ERFs) have been used to create Komplex, an extension of AztecOO which solves complex linear systems.
    
    
  • Iterative Block Linear Solvers
    (Contacts: Heidi K. Thornquist, Michael A. Heroux)
    Research has shown that block linear solvers are effective when multiple solutions are required for the same system of equations. This situation can occur frequently in perturbation analysis, optimization, and inside block eigensolvers. Furthermore, block linear solvers can accelerate convergence of linear systems in the case that the operator has a handful of small eigenvalues.
    
    The Belos block iterative solver package will contain our next-generation linear solvers in an extensible and inter-operable framework. Our goal is to provide robust iterative methods for solving large-scale systems of linear equations with multiple right-hand sides. One of the strengths of Belos is its ability to allow the user the flexibility to specify the data representation for the matrix and vectors and so leverage any existing software investment. The iterative methods that are currently available through Belos are Block GMRES (Generalized Minimal RESidual) and Block CG (Conjugate-Gradient).
    
    
  • Eigensolvers
    (Contacts: Heidi K. Thornquist, Richard B. Lehoucq, Ulrich Hetmaniuk)
    Similar to linear solvers, eigensolvers are also an important part of many scientific engineering applications. The Implicitly Restarted Arnoldi Method (IRAM) found in ARPACK has been very effective for performing stability and bifurcation analysis in many applications here at Sandia. Furthermore, research has also shown that block eigensolvers are effective at reliably determining multiple and/or clustered eigenvalues. This has led us to study the performance of various block eigensolvers (IRAM, LOBPCG, and a Generalized Davidson scheme) in situations where the user is interested in several eigenpairs (more than a couple). The Anasazi block eigensolvers package provides an extensible and inter-operable framework for solving large-scale eigenvalue algorithms. The eigensolver currently available through Anasazi is Block Implicitly Restarted Arnoldi.
    
    
• Preconditioning Methods
• Algebraic Preconditioning
  (Contact: Michael A. Heroux)
  
  
• Multigrid Preconditioning Methods
  (Contacts: Raymond S. Tuminaro, Jonathan J. Hu, Marzio Sala)
  Multigrid methods are a powerful class of preconditioning techniques. For elliptic partial differential equations, multigrid is provably linear in the work per unknown. ML is Sandia's multilevel preconditioning software package. It provides a variety of two-level domain decomposition, geometric, and algebraic multigrid methods. ML is available as part of the publicly-released Trilinos framework package. Available smoothers include point and block SOR methods, Chebychev polynomials, a specialized distributed relaxation scheme, incomplete factorization methods, and Krylov iterative methods. (The latter two are actually implemented in AztecOO.)
  

• Finite Element Discretizations
  (Contact: Pavel B. Bochev)
  
  
• Time Integration Methods
  (Contacts: Todd S. Coffey, David M. Day, David L. Ropp, Richard B. Lehoucq)
  Current research in time integration methods is investigating methods for ODEs and DAEs that have current and potential use in application codes at Sandia. These include semi-implicit methods, which historically have been popular, and fully-implicit methods, which have improved accuracy and stability properties, as well as operator-splitting and segregated physics methods, which are useful when coupling codes with different physics or multiple timescales. This work has had an impact on the Premo and Xyce codes, and may influence other codes such as Alegra, Calore, Fuego, and Goma. A library of time integration methods is being developed within the Trilinos framework to allow code developers at Sandia and elsewhere to evaluate and incorporate various methods quickly and easily.
  
  
• Geometric Time Integrators
  (Contact: Richard B. Lehoucq)
  Geometric integrators are methods that preserve various phase-flow invariants such as symplectic structure or time-reversal symmetry. Either of these two properties can be shown to imply discrete energy conservation that is probably the most crucial phase flow invariant to mimic for Hamiltonian systems. A canonical integrator is the popular Verlet method, the predominant method in molecular dynamics. Our current work researches alternatives to Verlet's method where the time step can be increased but still realize a reduction in time for the simulation.
  
  
• Time Integration Methods for PDEs on Manifolds
  (Contact: Richard B. Lehoucq)
  We consider the spatial discretization of time evolution problems whose solutions evolve on manifolds. A prototype model equation is the incompressible Stokes problem. An objective is to gain an understanding of how traditional mixed order and consistently stabilized FEMs evolve on a manifold. A practical motivation for this research has been an observed pressure instability in Galerkin-Least-Squares methods when implicit time integration is applied with a very small (driven by e.g., chemistry) time step.
  
  
• Krylov-based Exponential Time Integrators (KBEIs)
  (Contact: Richard B. Lehoucq)
  Exponential integrators remove the CFL restriction on the time step that constrains explicit time stepping schemes. Although exponential integrators have been successfully used for systems of model systems of ODEs, their extension to more realistic problems has not been undertaken. For instance, the use of KBEIs for differential algebraic equations (DAEs) and molecular dynamics is typically not undertaken. We are currently involved in projects to investigate their use in these applications.
  
  
• Preconditioned Iterative Solvers for the Discretization of Helmholtz Problems
  (Contact: Ulrich Hetmaniuk)
  The principal targeted applications for this research are vibrating phenomena in the frequency regime involving acoustic, elastic, electromagnetic, seismic, and or structural vibrations. While each problem has its own details, the numerical difficulties and challenges remain the same. The discretization requires highly resolved meshes to achieve sufficient accuracy. The resulting algebraic systems are linear, indefinite, typically complex, and extremely large. Consequently, the computation needs large amounts of memory. The size of the system suggests to use an iterative method. But the indefiniteness decreases or prevents the convergence of such a method.

  Therefore, our goal is to solve efficiently these indefinite linear systems using preconditioned iterative methods and to provide a robust multilevel preconditioned iterative method that is scalable not only with respect to the mesh size and the subdomain size but also with respect to the frequency.

Program Contact: David E. Womble

 
Return to Top of the Page

Newsnotes | Info and Events (internal - SNL only) | Open-Source Software Downloads | Privacy and Security
Sandia National Laboratories Home Page - External or Internal (SNL only)

Maintained by: Bernadette M. Watts
Modified on: June 10, 2011