Matrix Functions and Matrix Equations

The following sections are included:

• Preface
• Contents

The following sections are included:

• Introduction
• History
• Theory
• Applications
• Problem classification
• Methods for f(A)
• Methods for f(A)b
• Concluding remarks
• References

This paper contains a short course on the construction, analysis, and implementation of exponential integrators for time dependent partial differential equations. A much more detailed recent review can be found in Hochbruck and Ostermann (2010). Here, we restrict ourselves to one-step methods for autonomous problems.

A basic principle for the construction of exponential integrators is the linearization of a semilinear or a nonlinear evolution equation. We distinguish exponential Runge–Kutta methods, using a fixed linearization and exponential Rosenbrock-type methods, which use a continuous linearization at the current approximation of the solution. We present some of the convergence results and give a proof for the simplest method, the exponential Euler method.

The fact that it is possible to construct explicit exponential integrators which obey error bounds even for abstract evolution equations comes at the price that one has to approximate products of matrix functions with vectors in the spatially discrete case. For an efficient implementation one has to combine the integrator with well-chosen algorithms from numerical linear algebra. We briefly sketch Krylov subspace methods for this task.

We review model order reduction methods for linear time invariant systems and the numerical solution of related matrix equations. The basic ideas of the methods, such as Padé approximation, moment matching, rational interpolation, modal truncation, balanced truncation and related methods, are presented. The numerical algorithms used for implementing the methods are discussed. For balanced truncation and the balancing related methods, Lyapunov equations or Riccati equations need to be solved. Algorithms for solving these matrix equations are introduced.

Four classes of eigenvalue problems that admit similar minmax principles and the Cauchy interlacing inequalities as the symmetric eigenvalue problem famously does are investigated. These min-max principles pave ways for effcient numerical solutions for extreme eigenpairs by optimizing the so-called Rayleigh quotient functions. In fact, scientists and engineers have already been doing that for computing the eigenvalues and eigenvectors of Hermitian matrix pencils A − λB with B being positive definite, the first class of our eigenvalue problems. But little attention has gone to the other three classes: positive semidefinite pencils, linear response eigenvalue problems, and hyperbolic eigenvalue problems, in part because most min-max principles for the latter were discovered only very recently and some more are being discovered. It is expected that they will drive the effort to design better optimization based numerical methods for years to come.

Effcient solution of large-scale, ill-conditioned and highlyinde finite algebraic equations often relies on high quality preconditioners together with iterative solvers. Because of their robustness, factorization-based algorithms play a significant role in developing scalable solvers. We discuss the state-of-the-art, high performance sparse factorization techniques which are used to build sparse direct solvers, domain-decomposition type direct/iterative hybrid solvers, and approximate factorization preconditioners. In addition to algorithmic principles, we also address the key parallelism issues and practical aspects that need to be taken under consideration in order to deliver high speed and robustness to the users of today's sophisticated high performance computers.