Sparse tensor decompositions have become increasingly popular in the literature due to their capability to naturally model high dimensional sparse data with many features, and glean hidden relations owing to underlying low-rank structures within the data. They have been successfully employed in many application settings including recommender systems, graph analytics, healthcare data analytics,...
We propose guaranteed and fully computable upper bound on the energy norm of the error in low rank Tensor Train (TT) approximate solutions of (possibly) high dimensional reaction-diffusion problems. The error bound is obtained from Euler-Lagrange equations for a complementary flux reconstruction problem, which are solved in the low rank TT representation using the block Alternating Linear...
We consider the rank-structured tensor approach for numerical modeling of long-range potentials in many-particle systems. The method of grid-based assembled tensor summation of the electrostatic potentials on 3D finite lattices [3] exhibits the computational complexity of the order of $O(L)$ which is much less than $O(L^3)$ in traditional Ewald-type summation.
Novel range-separated (RS)...
We prove the convergence of the multigrid method for parameter-dependent symmetric positive definite linear systems. We present the smoothing and approximation properties for such problems and prove the smoothing property for the parameter-dependent damped Richardson as well as the parameter-dependent damped Jacobi method.
Our theoretical results require a parameter-dependent representation...
We discuss the problem of computing roots of systems of multivariate polynomials by approaches from numerical linear and multilinear algebra.The key concept in our approach is the Macaulay matrix, a large and highly structured matrix that contains the coefficients of the polynomials systems. The roots can be retrieved from the nullspace of this matrix. We then show how this root retrieval can...
Automatic Face Recognition has become increasingly important in the past few years due to its several applications in daily life. Numerical linear algebra tools have been extensively used for classification purposes. However, since several factors can affect the image, multilinear algebra tools seem to be a natural choice to deal with image classification.
We propose a new algorithm based...
We consider the nonsymmetric T-Riccati equation
$$ 0 = \mathcal{R}_T(X):=DX+X^TA-X^TBX+C,\qquad (1) $$ where $A,B,C,D\in\mathbb{R}^{n\times n}$ and sufficient conditions for the existence and uniqueness of a minimal (w.r.t. entry-wise comparison) solution $X_{\min}\in\mathbb{R}^{n\times n}$ are provided. To date, the nonlinear matrix equation (1) is still an unexplored problem in...
The numerical solution of the algebraic Riccati matrix equation
$$(1)\quad A^T X + XA − XSX + Q = 0,$$
where $A$, $S$, $Q\in\mathbb{R}^{n\times n}$ , is an interesting and still challenging task especially when the problem dimension is very large, say $n > 10^4$ , as the dense solution $X$ cannot be store and a memory-saving approximation has to be sought.
A vast portion of the...
Our goal is the feedback stabilization of a two-dimensional two-phase Stefan problem coupled with (Navier-)Stokes equations. The Stefan problem can model solidification and melting of pure materials and gets its name from the purely algebraic Stefan condition which describes the coupling between the temperature of the material and its melting process.
After linearization and discretization,...
We consider the numerical solution of large-scale, differential matrix Riccati equations (DRE). Projection methods have recently arisen as a promising class of solution strategies. Existing approaches in this class focus on polynomial or extended Krylov subspaces as approximation space. We show that great computational and memory advantages are obtained with fully rational Krylov subspaces and...
We consider the differential Riccati equation,
$$\dot{X} = A^T X + X A - X BB^T X + C^T C.$$
The differential Riccati equation as well as the algebraic Riccati equation play important roles in applied mathematics like control theory and system theory. In our talk, we focus on the large-scale case. The numerical solution of these equation is challenging, in particular, because of the...
Matrix equations have arisen as the natural setting for various PDE discretization methods such as finite differences, isogeometric analysis, spectral and finite elements.
Thanks to major recent computational advances, solving certain classes of linear matrix equations is a competitive alternative to dealing with the large (vector) linear systems classically stemming from the aforementioned...
In this paper, we present an efficient algorithm for model reduction of discrete-time index-2 descriptor systems arising in context of linear time invariant (LTI) control and stability of descriptor systems. We propose a balanced truncation based model order reduction (MOR) strategy which consists of two stages. In the first stage, we reformulate the descriptor system into a generalized system...
The treatment of two-dimensional random walks in the quarter plane leads to Markov processes which involve semi-infinite matrices having Toeplitz or block Toeplitz structure plus a low-rank correction. In particular, finding the steady state probability distribution requires computing the minimal nonnegative solution of the quadratic matrix equation $A_1X^2+A_0X+A_{-1}=X$, where the...
PDE-constrained optimization problems arise in a broad number of applications. The resulting large-scale saddle-point systems are challenging to solve and acquiring a full solution is often infeasible. We present a new framework to find a low-rank approximation to the solution by reformulating the system into a system of Sylvester-like matrix equations. These matrix equations are subsequently...
Consider the algebraic Riccati equation
$$A^{*}X + XA + C^*C - XBB^{*}X = 0$$
with large and sparse $A\in \mathbb{C}^{n\times n}$ and $B\in \mathbb{C}^{n\times m}$, $C\in \mathbb{C}^{p\times n}$. The goal is to find an approximate solution $X$ such that the rank of the Riccati residual remains equal to $p$. A method to determine an approximate solution to Riccati equations with this rank...
A stochastic cubical tensor is a three-mode array (or hypermatrix) with nonnegative entries, whose $1$-mode fibers (i.e., columns) sum up to $1$. Such tensors appear in certain higher-order Markov chains and random walks with memory, exactly as stochastic matrices describe classical discrete Markov chains and random walks.
The interest in higher-order stochastic processes is significantly...
Graph (or network) analysis is concerned with knowledge discovery from graph data. Corresponding analysis methods usually have their roots in graph theory, matrix computations, and statistics.
A growing class of analysis algorithms consists of methods based on the graph's Laplacian matrix. These include traditional methods using Laplacian eigenvectors such as spectral partitioning, spectral...
Among other things, M.E.S.S. can solve Lyapunov and Riccati equations, and perform model reduction of systems in state space and structured differential algebraic form. While until version 1.0.1 the work focused on algebraic equations and autonomous differential Riccati equations (DREs), the latest release adds support also for non-autonomous DREs.
In the first place, the poster presented will give an overview on the matrix equations that appear in the low-rank parameter-dependent fluid-structure interaction (FSI) framework. In contrast to linear FSI problems, the equations that result after finite element discretization of parameter-dependent nonlinear FSI problems are not translatable to a single matrix equation. Such a discretization...
We deduce a procedure to use balanced truncation for parameter-dependent differential-algebraic systems. For this, we have to solve parameter-dependent Lyapunov equations. Since solving large-scale Lyapunov equations for every parameter leads to very high computational costs we utilize the reduced-basis method to get a reduced Lyapunov equation that we can solve instead. In order to use this...
Matrix equations and their solutions play a key role in several problems arising in science and engineering. Our primary focus lies on matrix equations appearing in model-order reduction problems, where several well-known procedures, such as balanced truncation and interpolation-based methods, can be set up in the matrix equations form. In the last five years, several model reduction schemes...
In system theory, the so-called system Gramian matrices are operators encoding certain properties of an underlying input-output system. Usually, these system Gramians are computed as solutions to matrix equations, such as the Lyapunov equation and Sylvester equation. This means, the solution to certain matrix equations coincides with these system Gramians. Now, if the system Gramians are...
The MORLAB, Model Order Reduction LABoratoy, toolbox [1] is a free and open source software solution in MATLAB and GNU Octave for linear model reduction problems. Providing system theoretic model order reduction methods, the basis of the highly efficient implementation is built by a large variety of dense matrix equation solvers based on iterative methods like the matrix sign function, Newton...
We consider $\mathcal{H}_2 \otimes \mathcal{L}_2$-optimal model order reduction of parametric linear time-invariant dynamical systems, where coupled matrix integral equations arise in the first-order necessary conditions (FONC). The quality of the reduced-order model is measured using the $\mathcal{H}_2$ norm for the parametric system, which is averaged in the $\mathcal{L}_2$-norm over the...
Dynamical low-rank approximation is introduced and a numerical integrator that computes a symmetric or skew-symmetric low-rank approximation to large symmetric or skew-symmetric time-dependent matrices that are either given explicitly or are the unknown solution to a matrix differential equation is presented. We show that low-rank time-dependent matrices are reproduced exactly, and the error...
Port-Hamiltonian (pH) systems are a very important modeling structure for large classes of technical systems. In the optimal control problem for pH systems, the resulting boundary value problems and Lure/Riccati/Lyapunov have a double structure.
It is a big challenge to make use of this double structure inan effective way, but also in the solution of the associated structured eigenvalue...
Evaluating the action of a matrix function on a vector, that is $x=f(\mathcal M)v$, is an ubiquitous task in applications. When the matrix $\mathcal M$ is large, subspace projection method, such as the rational Krylov method, are usually employed.
In this work, we provide a quasi-optimal pole choice for rational Krylov methods applied to this task when $f(z)$ is either Cauchy-Stieltjes or...
We describe a way to implement the matrix sign iteration $H_{k+1} = \frac12 (H_k^{\mathstrut}+H_k^{-1})$ on a dense Hamiltonian matrix of the form
$$H_k = \begin{bmatrix}A_k & B_kB_k^T\\ C_k^TC_k & -A_k^T & \end{bmatrix}$$ in such a way that the blocks in positions $(1,2)$ and $(2,1)$ are kept in low-rank factored form. The algorithm operates on their generators $B_k$ and $C_k$...
