When efficient linear solvers for shifted systems are unavailable, polynomial Krylov subspace methods are often the only methods of choice to compute $f(A)b$, the action of a matrix function on a vector. For less well conditioned problems the number of required Arnoldi steps may then become so large that storing the Arnoldi vectors exceeds the available memory and that orthogonalization costs...
We discuss a new augmented Krylov subspace method which allows for the efficient evaluation of a sequence of matrix function applications on a set of vectors using Krylov subspace recycling. If selected appropriately, the recycling subspace can be used to accelerate the convergence of each problem in the sequence, leading to an overall reduction in the computational overhead required to...
We consider the solution of large stiff systems of ordinary differential equations with explicit exponential Runge--Kutta integrators. These problems arise from semi-discretized semi-linear parabolic partial differential equations on continuous domains or on inherently discrete graph domains. A series of results reduces the requirement of computing linear combinations of $\varphi$-functions in...
In this talk we present some error bounds for the approximation of matrix-vector products $f(A) b$ and quadratic forms $b^T f(A) b$ with a matrix function $f(A)$, for a Hermitian matrix $A$ and a vector $b$ by means a rational Krylov subspace method. The error bounds are obtained by exploiting properties of rational Arnoldi decompositions and the Cauchy integral formula to link the matrix...
Though seemingly they belong to two different worlds, matrix functions and network science have some degree of overlap thanks to a very simple fact; powers of the adjacency matrix count traversals in the underlying network. This concept in turn allows for the definition of centrality measures in terms of entries (or sums thereof) of functions of the adjacency matrix.
In this talk, after...
We will provide a brief overview of the following topics for the focus groups:
1) Transfering knowledge among f(A)b, exponential integration, and related problems
2) High-performance and energy-aware computing for matrix functions and exponential integration
3) Building a f(A)bulous benchmark collection and comparison framework
Exponential integration has taken a more prominent role in scientific computing over the past decades. Exponential schemes offer computational savings for many problems involving large stiff systems of differential equations. Careful design of a practical exponential scheme is crucial, however, to ensure that the resulting method is efficient for a particular equation. In particular, to...
In this talk, we consider two efficient ways to approximate actions of $\varphi$-functions for matrices $A$ with a $d$-dimensional Kronecker sum structure, that is $A=A_d\oplus\cdots\oplus A_1$. The first one is based on the approximation of the integral representation of the $\varphi$-functions by Gaussian quadrature formulas combined with a scaling and squaring technique. The resulting...
In the computation of wall bounded flows, resolving the boundary layer requires a very fine resolution. The CFL condition then makes the use of explicit time integration schemes infeasible. However, these may be used in parts of the domain where the mesh is coarse, and using an implicit method only on the remainder. This gives rise to domain based IMEX methods. In this talk, we consider the...
Due to the importance of simulation in various fields of science and engineering, devising efficient numerical methods for solving high-dimensional evolutionary Partial Differential Equations is of considerable interest.
In this talk, we present an efficient technique to employ exponential integrators for solving evolutionary Advection-Diffusion-Reaction equations with spatially variable...
The numerical integration of stiff equations is a challenging problem that needs to be approached by specialized numerical methods. Exponential integrators [1] form a popular class of such methods since they are provably robust to stiffness and have been successfully applied to a variety of problems. The dynamical low-rank approximation [2] is a recent technique for solving high-dimensional...
Tensors are multidimensional arrays that can play a key role in the representation of big data. Decompositions of higher-order tensors have applications in biochemistry, signal processing, data mining, neuroscience, and elsewhere. Building on earlier decompositions (such as canonical/parallel factor (CANDECOMP/PARAFAC), Tucker or its variants), recent research efforts have been devoted to the...
It is well known that the Lanczos tridiagonal matrix can be transformed to an equivalent finite-difference scheme, with the coefficients obtained from the Stieltjes continued fraction. We show the usefulness of such representation on two seemingly unrelated problems.
The first one is "rigorous" computation of the exponential matrix moments $b^*\exp{-tA}b$. Here we use the finite-difference...
Numerical methods for evaluating a function $f$ at an $n \times n$ matrix $A$ can be based on a variety of different approaches, but for a large class of algorithms the matrix $f(A)$ is approximated by using only three operations:
- $Z \gets c_X X + c_Y Y,$ linear combination of matrices),
- $Z \gets X \cdot Y,$ (matrix multiplication),
- $Z \gets X^{-1} Y,$ (solution of a linear...
The problem of approximating the von Neumann entropy of a symmetric positive semidefinite matrix $A$, defined as ${\text tr} (f(A))$ where $f(x) = - x \log x$, is considered. After discussing some useful properties of this matrix function, approximation methods based on randomized trace estimation and probing techniques used in conjunction with polynomial and rational Krylov methods will be...
We consider the problem of estimating the trace of a matrix function $f(A)$. In certain situations, in particular if $f(A)$ cannot be well approximated by a low-rank matrix, combining probing methods [2] based on graph colorings with stochastic trace estimation techniques can yield very accurate approximations. So far, such methods have not been thoroughly analyzed, though, but were rather...
This work is concerned with computing low-rank approximations of a matrix function $f(A)$ for a large symmetric positive semi-definite matrix $A$, a task that arises in, e.g., statistical learning and inverse problems. The application of popular randomized methods, such as the randomized singular value decomposition or the Nyström approximation, to $f(A)$ requires multiplying $f(A)$ with a few...
When analyzing complex networks, an important task is the identification of nodes which play a leading role for the overall communicability of the network. In the context of modifying networks (or making them robust against targeted attacks or outages), it is also relevant to know how sensitive the network's communicability is to changes in certain nodes or edges.
Recently, the concept of...
In recent decades, graphs have become widely used for studying technological, biological, and social systems. For this reason, several methods have been proposed to measure the structural and dynamical properties of graphs, aiming to gain insights into the represented system. Among these methods, measures based on matrix functions have been introduced for assessing vertex centrality and...
