Nonintrusive approximation of parametrized limits of matrix power algorithms – application to matrix inverses and log-determinants

Fabien Casenave, Nissrine Akkari, Alexandre Charles, Christian ReySpringer Link (Chiba Institute of Technology) 2019 · DOI

TL;DR

This paper introduces a novel nonintrusive method for approximating matrix inverses and log-determinants of parametrized matrices, particularly when the parameter dependence is affine. By leveraging the Empirical Interpolation Method (EIM), the approach offers a computationally efficient way to obtain these quantities without modifying existing solvers, outperforming other nonintrusive methods in numerical tests.

What Problem Does This Paper Address?

Many scientific and engineering fields rely on solving complex models, often involving partial differential equations, where the solution needs to be computed numerous times for varying parameters (e.g., in sensitivity analysis or uncertainty quantification). Model Order Reduction (MOR) techniques aim to speed this up. While intrusive MOR methods (like POD or Reduced-Basis) can be highly effective, they require significant modifications to existing simulation codes. Nonintrusive methods, which treat the solver as a black-box, are desirable but can be less accurate or efficient. This paper focuses on a specific class of problems: approximating quantities derived from powers of parametrized matrices, such as their inverses or log-determinants, in a nonintrusive and efficient manner.

Methods

The core of the proposed method lies in approximating powers of parametrized matrices, specifically those with an affine dependence on parameters. The authors first establish a theoretical framework (Lemma 1) showing that any power $A^p$ can be expressed as a linear combination of specific matrices $T_{k,p}$ weighted by a function $g(k, \mu)$ that captures the parameter dependence. The key innovation is to apply the Empirical Interpolation Method (EIM) to approximate this function $g(k, \mu)$. EIM is an offline/online procedure: the offline stage learns the parameter dependence by selecting key parameter values and interpolation points, while the online stage rapidly computes the approximation. This EIM-based approximation of $g$ is then used to nonintrusively approximate matrix powers, and subsequently, matrix inverses and log-determinants. The method also incorporates iterative schemes for inverse computation and a specific formula for log-determinants derived from matrix powers.

Datasets

Not discussed in the paper. The paper focuses on a general methodology and demonstrates its application on test cases derived from physical problems (heat transfer, linear elasticity).

Key Insights and Ideas

  • EIM for $g(k, \mu)$ is the linchpin: The paper's central idea is that by applying EIM to the parameter-dependent function $g(k, \mu)$ (which describes how matrix powers are formed from affine components), one can efficiently approximate the matrix powers themselves. This avoids direct approximation of the large matrices.
  • Nonintrusivity is paramount: The method is designed to be nonintrusive, meaning it only requires access to the output of a high-fidelity solver (e.g., the matrix inverse or log-determinant at specific parameter values) and knowledge of the affine structure, not the internal workings of the solver.
  • Leveraging iterative schemes: The paper cleverly combines the EIM-based approximations with established iterative methods for computing matrix inverses and log-determinants, showing how the EIM approximation can be integrated to yield nonintrusive versions of these iterative schemes.
  • Theoretical error bounds: The authors provide theoretical upper bounds on the approximation error, which depend on the EIM approximation error and the convergence properties of the underlying iterative schemes.
  • POD for further reduction: In the analysis of convergence, Proper Orthogonal Decomposition (POD) is used on the EIM-generated snapshots to construct a reduced basis, further enhancing the theoretical analysis.

Key Results

  • The proposed nonintrusive method for approximating matrix inverses and log-determinants demonstrates good performance in numerical experiments.
  • In test cases involving a heat transfer problem and a mechanical elasticity problem, the proposed algorithm shows a better convergence rate compared to other nonintrusive methods like Gaussian processes, gradient boosting, random forests, and Bayesian ridge regression.
  • The method's performance is assessed by comparing the mean relative errors of the approximated solutions against reference solutions. For instance, in Figure 3, the proposed algorithm exhibits the best convergence rate among the nonintrusive methods tested.
  • The paper provides theoretical convergence guarantees for the approximation, showing that the error decreases with the number of EIM interpolation points and the order of the power series approximation.

Limitations and Future Work

  • Parameter dependence assumption: The method relies on the assumption of affine dependence of the matrices on the parameters. If this assumption is violated, the method's applicability and performance may be limited.
  • Curse of dimensionality: While the method is nonintrusive, the "curse of dimensionality" can still pose a challenge in high-dimensional parameter spaces, potentially affecting the efficiency of the EIM offline stage and the quality of the preconditioner.
  • Preconditioner existence: For the inverse approximation, the method relies on the existence of a good preconditioner uniformly across the parameter space. Finding such a preconditioner can be difficult in high-dimensional cases.
  • Computational cost of offline stage: While the online stage is fast, the offline stage of EIM can still be computationally demanding, especially for complex problems or when a large number of EIM points are required for accuracy.
  • Future work: The authors suggest that the derived convergence results are general and could be applied to other classes of models and problems. Further investigation into finding better preconditioners and exploring the method's applicability to non-affine parameter dependencies would be valuable. The numerical results also suggest that the EIM's ability to select relevant parameter values is crucial for its success.

Summary updated

Abstract

\nWe consider in this work quantities that can be obtained as limits of powers of parametrized matrices, for instance the inverse matrix or the logarithm of the determinant. Under the assumption of affine dependence in the parameters, we use the Empirical Interpolation Method (EIM) to derive an approximation for powers of these matrices, from which we derive a nonintrusive approximation for the aforementioned limits. We derive upper bounds of the error made by the obtained formula. Finally, numerical comparisons with classical intrusive and nonintrusive approximation techniques are provided: in the considered test-cases, our algorithm performs well compared to the nonintrusive ones.\n
BibTeX
@inproceedings{casenave2019nonintrusive,
  author = {Fabien Casenave and Nissrine Akkari and Alexandre Charles and Christian Rey},
  title = {{Nonintrusive approximation of parametrized limits of matrix power algorithms – application to matrix inverses and log-determinants}},
  booktitle = {Springer Link (Chiba Institute of Technology)},
  year = {2019},
  doi = {10.1051/m2an/2018048/pdf},
}
Figure