A Low-Rank Inexact Newton-Krylov Method for Stochastic Eigenvalue Problems

Peter Benner, Akwum Onwunta, Martin Stoll

TL;DR

This paper introduces a novel low-rank inexact Newton-Krylov method to efficiently solve high-dimensional stochastic eigenvalue problems that arise in various scientific and engineering fields. By exploiting the inherent tensor product structure of these problems, the method significantly reduces computational cost and memory requirements, making previously intractable problems solvable.

What Problem Does This Paper Address?

Many real-world physical systems exhibit uncertainties in their parameters, leading to stochastic eigenvalue problems (SEVPs). These problems are crucial for understanding phenomena like vibrations and buckling in structural mechanics. Traditional methods for solving deterministic eigenvalue problems become computationally prohibitive when applied to SEVPs, especially when using the stochastic Galerkin method (SGM) for discretization. SGM, while powerful for capturing the full statistical characteristics of the solution, results in extremely high-dimensional systems with a tensor product structure. This "curse of dimensionality" makes direct application of standard solvers infeasible due to overwhelming memory and computational time demands. The paper addresses this challenge by developing a method that specifically leverages this tensor product structure to overcome these limitations.

Methods

The core of the paper is the development of a globalized low-rank inexact Newton-Krylov method.

  • Stochastic Galerkin Method (SGM): The paper starts by discretizing the SEVP using SGM, which leads to a system of nonlinear algebraic equations with a tensor product structure.
  • Inexact Newton Method (INM): To solve these nonlinear equations, the authors employ an inexact Newton method. This iterative approach approximates the solution by solving a sequence of linear systems (Newton equations) at each step.
  • Globalization (Backtracking): To ensure robustness and convergence, especially when initial guesses are not close to the solution, a backtracking line-search strategy is incorporated. This strategy adjusts the step size to guarantee sufficient progress towards a solution.
  • Low-Rank Krylov Solver: The key innovation is the use of a low-rank version of a Krylov subspace method (specifically BiCGstab is mentioned) to solve the linear systems arising from the inexact Newton steps. This approach assumes that the solution matrices admit a low-rank representation. By exploiting this, the method only needs to store and manipulate a small number of vectors, drastically reducing memory requirements and computational cost.
  • Preconditioning: A mean-based block-diagonal preconditioner is used to further accelerate the convergence of the Krylov solver.

Datasets

Not discussed in the paper. The paper focuses on a numerical example derived from a stochastic eigenvalue problem related to a 2D domain.

Key Insights and Ideas

  • Leveraging Tensor Product Structure: The paper demonstrates that the inherent tensor product structure of SGM-discretized SEVPs is not just a challenge but also an opportunity. By exploiting it with low-rank approximations, significant computational gains can be achieved.
  • Low-Rank for High Dimensions: The "curse of dimensionality" in SEVPs can be effectively tackled by low-rank techniques, which are typically used for problems with large numbers of random variables or high spatial discretization. This paper shows their applicability to SEVPs.
  • Inexact Newton with Backtracking and Low-Rank: Combining an inexact Newton method with backtracking globalization and a low-rank Krylov solver provides a robust and efficient framework for solving these challenging problems.
  • Significant Memory Savings: The low-rank approach leads to dramatic reductions in memory usage, making it possible to solve problems that would otherwise be intractable due to memory limitations.

Key Results

The paper presents numerical experiments that highlight the effectiveness of the proposed low-rank inexact Newton-Krylov method.

  • Computational Efficiency: For a problem with a Jacobian matrix of size 10,500, the method computed the spectral coefficients of an eigenpair in a few seconds.
  • Memory Reduction: The low-rank solution required approximately one-quarter of the memory compared to the full method solution.
  • Scalability: For a much larger problem with a Jacobian matrix of size 82,468,050, the full method (FM) failed due to "out of memory" errors. In contrast, the low-rank INBM handled this problem in about 200 minutes, demonstrating its ability to tackle extremely large-scale problems.
  • Robustness: The backtracking globalization strategy proved effective in ensuring convergence.

Limitations and Future Work

  • Single Eigenvalue Computation: The current implementation primarily computes one eigenvalue nearest to the initial guess. The authors note that computing multiple distinct eigenvalues would require specialized techniques, which are currently under investigation.
  • Parameter Tuning: Like many iterative methods, the performance can be influenced by parameter choices (e.g., forcing terms, backtracking parameters). While the paper suggests common choices and demonstrates their effectiveness, further research into adaptive parameter selection could be beneficial.
  • Generalization to Other Krylov Solvers: While the paper focuses on BiCGstab, the low-rank approach is noted to be extendable to other Krylov solvers.
  • Other Globalization Strategies: The paper primarily uses backtracking. Exploring other globalization strategies like trust-region methods could be a direction for future work.

Summary updated

Abstract

This paper aims at the efficient numerical solution of stochastic eigenvalue problems. Such problems often lead to prohibitively high-dimensional systems with tensor product structure when discretized with the stochastic Galerkin method. Here, we exploit this inherent tensor product structure to develop a globalized low-rank inexact Newton method with which we tackle the stochastic eigenproblem. We illustrate the effectiveness of our solver with numerical experiments.
BibTeX
@inproceedings{benner2019low,
  author = {Peter Benner and Akwum Onwunta and Martin Stoll},
  title = {{A Low-Rank Inexact Newton-Krylov Method for Stochastic Eigenvalue Problems}},
  booktitle = {Comput. Methods Appl. Math},
  year = {2019},
  url = {https://openreview.net/forum?id=pD6jDCKeOp},
}
Figure