Skip to main content
main-content

Über dieses Buch

This book gathers selected contributions presented at the INdAM Meeting Structured Matrices in Numerical Linear Algebra: Analysis, Algorithms and Applications, held in Cortona, Italy on September 4-8, 2017. Highlights cutting-edge research on Structured Matrix Analysis, it covers theoretical issues, computational aspects, and applications alike. The contributions, written by authors from the foremost international groups in the community, trace the main research lines and treat the main problems of current interest in this field. The book offers a valuable resource for all scholars who are interested in this topic, including researchers, PhD students and post-docs.

Inhaltsverzeichnis

Frontmatter

Spectral Measures

Abstract
The theory of spectral symbols links sequences of matrices with measurable functions expressing their asymptotic eigenvalue distributions. Usually, a sequence admits several spectral symbols, and it is not clear if a canonical one exists. Here we present a way to connect the sequences with the space of probability measure, so that each sequence admits a uniquely determined measure. The methods used are similar to those employed in the theory of generalized locally Toeplitz (GLT) sequences: a goal of this present contribution is in fact that of explaining how the two concepts are connected.
Giovanni Barbarino

Block Locally Toeplitz Sequences: Construction and Properties

Abstract
The theory of block locally Toeplitz (LT) sequences—along with its generalization known as the theory of block generalized locally Toeplitz (GLT) sequences—is a powerful apparatus for computing the spectral distribution of matrices arising from the discretization of differential problems. In this paper we develop the theory of block LT sequences, whereas the theory of block GLT sequences is the subject of the complementary paper (Chap. 3 of this book).
Carlo Garoni, Stefano Serra-Capizzano, Debora Sesana

Block Generalized Locally Toeplitz Sequences: Topological Construction, Spectral Distribution Results, and Star-Algebra Structure

Abstract
The theory of generalized locally Toeplitz (GLT) sequences is a powerful apparatus for computing the asymptotic singular value and eigenvalue distribution of matrices A n arising from virtually any kind of numerical discretization of differential equations (DEs). Indeed, when the discretization parameter n tends to infinity, these matrices A n give rise to a sequence {A n}n, which often turns out to be a GLT sequence or one of its ‘relatives’, i.e., a block GLT sequence or a reduced GLT sequence. In particular, block GLT sequences are encountered in the discretization of systems of DEs as well as in the higher-order finite element or discontinuous Galerkin approximation of scalar DEs. Despite the applicative interest, a solid theory of block GLT sequences is still missing. The purpose of the present paper is to develop this theory in a systematic way.
Carlo Garoni, Stefano Serra-Capizzano, Debora Sesana

On Matrix Subspaces with Trivial Quadratic Kernels

Abstract
Some subspaces of real matrices of the same order may contain nonsingular matrices, some may not. We prove that if the maximal rank matrix in the given subspace with trivial quad ratic kernel is symmetric, then it must be nonsingular. It immediately follows that any subspace of symmetric matrices with trivial quad ratic kernel contains a nonsingular matrix. We present some particular cases when this holds true without the assumption about symmetry. Whether this remains valid in the general case of real nonsymmetric matrices we still do not know.
Alexey Tretyakov, Eugene Tyrtyshnikov, Alexey Ustimenko

Error Analysis of TT-Format Tensor Algorithms

Abstract
The tensor train (TT) decomposition is a representation technique for arbitrary tensors, which allows efficient storage and computations. For a d-dimensional tensor with d ≥ 2, that decomposition consists of two ordinary matrices and d − 2 third-order tensors. In this paper we prove that the TT decomposition of an arbitrary tensor can be computed (or approximated, for data compression purposes) by means of a backward stable algorithm based on computations with Householder matrices. Moreover, multilinear forms with tensors represented in TT format can be computed efficiently with a small backward error.
Dario Fasino, Eugene E. Tyrtyshnikov

The Derivative of the Matrix Geometric Mean with an Application to the Nonnegative Decomposition of Tensor Grids

Abstract
We provide an expression for the derivative of the weighted matrix geometric mean, with respect to both the matrix arguments and the weights, that can be easily translated to an algorithm for its computation. As an application, we consider the problem of the approximate decomposition of a tensor grid M, a matrix whose entries are positive definite matrices. For different geometries on the set of positive definite matrices, we derive an approximate decomposition such that any column of M is a barycentric combination of the columns of a smaller tensor grid. This extends the Euclidean case, already considered in the literature, to the geometry in which the barycenter is the matrix geometric mean and the log-Euclidean geometry.
Bruno Iannazzo, Ben Jeuris, Filippo Pompili

Factoring Block Fiedler Companion Matrices

Abstract
When Fiedler published his “A note on Companion matrices” in 2003 on Linear Algebra and its Applications, he could not have foreseen the significance of this elegant factorization of a companion matrix into essentially two-by-two Gaussian transformations, which we will name (scalar) elementary Fiedler factors. Since then, researchers extended these results and studied the various resulting linearizations, the stability of Fiedler companion matrices, factorizations of block companion matrices, Fiedler pencils, and even looked at extensions to non-monomial bases. In this chapter, we introduce a new way to factor block Fiedler companion matrices into the product of scalar elementary Fiedler factors. We use this theory to prove that, e.g. a block (Fiedler) companion matrix can always be written as the product of several scalar (Fiedler) companion matrices. We demonstrate that this factorization in terms of elementary Fiedler factors can be used to construct new linearizations. Some linearizations have notable properties, such as low bandwidth, or allow for factoring the coefficient matrices into unitary-plus-low-rank matrices. Moreover, we will provide bounds on the low-rank parts of the resulting unitary-plus-low-rank decomposition. To present these results in an easy-to-understand manner, we rely on the flow-graph representation for Fiedler matrices recently proposed by Del Corso and Poloni in Linear Algebra and its Applications, 2017.
Gianna M. Del Corso, Federico Poloni, Leonardo Robol, Raf Vandebril

A Class of Quasi-Sparse Companion Pencils

Abstract
In this paper, we introduce a general class of quasi-sparse potential companion pencils for arbitrary square matrix polynomials over an arbitrary field, which extends the class introduced in [B. Eastman, I.-J. Kim, B. L. Shader, K.N. Vander Meulen, Companion matrix patterns. Linear Algebra Appl. 436 (2014) 255–272] for monic scalar polynomials. We provide a canonical form, up to permutation, for companion pencils in this class. We also relate these companion pencils with other relevant families of companion linearizations known so far. Finally, we determine the number of different sparse companion pencils in the class, up to permutation.
Fernando De Terán, Carla Hernando

On Computing Eigenvectors of Symmetric Tridiagonal Matrices

Abstract
The computation of the eigenvalue decomposition of symmetric matrices is one of the most investigated problems in numerical linear algebra. For a matrix of moderate size, the customary procedure is to reduce it to a symmetric tridiagonal one by means of an orthogonal similarity transformation and then compute the eigendecomposition of the tridiagonal matrix.
Recently, Malyshev and Dhillon have proposed an algorithm for deflating the tridiagonal matrix, once an eigenvalue has been computed. Starting from the aforementioned algorithm, in this manuscript we develop a procedure for computing an eigenvector of a symmetric tridiagonal matrix, once its associate eigenvalue is known.
We illustrate the behavior of the proposed method with a number of numerical examples.
Nicola Mastronardi, Harold Taeter, Paul Van Dooren

A Krylov Subspace Method for the Approximation of Bivariate Matrix Functions

Abstract
Bivariate matrix functions provide a unified framework for various tasks in numerical linear algebra, including the solution of linear matrix equations and the application of the Fréchet derivative. In this work, we propose a novel tensorized Krylov subspace method for approximating such bivariate matrix functions and analyze its convergence. While this method is already known for some instances, our analysis appears to result in new convergence estimates and insights for all but one instance, Sylvester matrix equations.
Daniel Kressner

Uzawa-Type and Augmented Lagrangian Methods for Double Saddle Point Systems

Abstract
We study different types of stationary iterative methods for solving a class of large, sparse linear systems with double saddle point structure. In particular, we propose a class of Uzawa-like methods including a generalized (block) Gauss-Seidel (GGS) scheme and a generalized (block) successive overrelaxation (GSOR) method. Both schemes rely on a relaxation parameter, and we establish convergence intervals for these parameters. Additionally, we investigate the performance of these methods in combination with an augmented Lagrangian approach. Numerical experiments are reported for test problems from two different applications, a mixed-hybrid discretization of the potential fluid flow problem and finite element modeling of liquid crystal directors. Our results show that fast convergence can be achieved with a suitable choice of parameters.
Michele Benzi, Fatemeh Panjeh Ali Beik

Generalized Block Tuned Preconditioners for SPD Eigensolvers

Abstract
Given an n × n symmetric positive definite (SPD) matrix A and an SPD preconditioner P, we propose a new class of generalized block tuned (GBT) preconditioners. These are defined as a p-rank correction of P with the property that arbitrary (positive) parameters γ 1, …, γ p are eigenvalues of the preconditioned matrix. We propose to employ these GBT preconditioners to accelerate the iterative solution of linear systems like (A − θI)s = r in the framework of iterative eigensolvers. We give theoretical evidence that a suitable, and effective, choice of the scalars γ j is able to shift p eigenvalues of P(A − θI) very close to one. Numerical experiments on various matrices of very large size show that the proposed preconditioner is able to yield an almost constant number of iterations, for different eigenpairs, irrespective of the relative separation between consecutive eigenvalues. We also give numerical evidence that the GBT preconditioner is always far superior to the spectral preconditioner (Numer. Linear Algebra Appl. 24(3):1–14, 2017), on matrices with highly clustered eigenvalues.
Luca Bergamaschi, Ángeles Martínez

Stability of Gyroscopic Systems with Respect to Perturbations

Abstract
A linear gyroscopic system is of the form:
$$\displaystyle M \ddot x + G\dot x + K x = 0, $$
where the mass matrix M is a symmetric positive definite real matrix, the gyroscopic matrix G is real and skew symmetric, and the stiffness matrix K is real and symmetric. The system is stable if and only if the quadratic eigenvalue problem \(\det (\lambda ^2 M+\lambda G + K)=0\) has all eigenvalues on the imaginary axis.
In this chapter, we are interested in evaluating robustness of a given stable gyroscopic system with respect to perturbations. In order to do this, we present an ODE-based methodology which aims to compute the closest unstable gyroscopic system with respect to the Frobenius distance.
A few examples illustrate the effectiveness of the methodology.
Nicola Guglielmi, Manuela Manetta

Energetic BEM for the Numerical Solution of 2D Hard Scattering Problems of Damped Waves by Open Arcs

Abstract
The energetic boundary element method (BEM) is a discretization technique for the numerical solution of wave propagation problems, introduced and applied in the last decade to scalar wave propagation inside bounded domains or outside bounded obstacles, in 1D, 2D, and 3D space dimension.
The differential initial-boundary value problem at hand is converted into a space–time boundary integral equations (BIEs), then written in a weak form through considerations on energy and discretized by a Galerkin approach.
The paper will focus on the extension of 2D wave problems of hard scattering by open arcs to the more involved case of damped waves propagation, taking into account both viscous and material damping.
Details will be given on the algebraic reformulation of Energetic BEM, i.e., on the so-called time-marching procedure that gives rise to a linear system whose matrix has a Toeplitz lower triangular block structure.
Numerical results confirm accuracy and stability of the proposed technique, already proved for the numerical treatment of undamped wave propagation problems in several space dimensions and for the 1D damped case.
Alessandra Aimi, Mauro Diligenti, Chiara Guardasoni

Efficient Preconditioner Updates for Semilinear Space–Time Fractional Reaction–Diffusion Equations

Abstract
The numerical solution of fractional partial differential equations poses significant computational challenges in regard to efficiency as a result of the nonlocality of the fractional differential operators. In this work we consider the numerical solution of nonlinear space–time fractional reaction–diffusion equations integrated in time by fractional linear multistep formulas. The Newton step needed to advance in (fractional) time requires the solution of sequences of large and dense linear systems because of the fractional operators in space. A preconditioning updating strategy devised recently is adapted and the spectrum of the underlying operators is briefly analyzed. Because of the quasilinearity of the problem, each Jacobian matrix of the Newton equations can be written as the sum of a multilevel Toeplitz plus a diagonal matrix and produced exactly in the code. Numerical tests with a population dynamics problem show that the proposed approach is fast and reliable with respect to standard direct, unpreconditioned, multilevel circulant/Toeplitz and ILU preconditioned iterative solvers.
Daniele Bertaccini, Fabio Durastante

A Nuclear-Norm Model for Multi-Frame Super-Resolution Reconstruction from Video Clips

Abstract
We propose a variational approach to obtain super-resolution images from multiple low-resolution frames extracted from video clips. First the displacement between the low-resolution frames and the reference frame is computed by an optical flow algorithm. Then a low-rank model is used to construct the reference frame in high resolution by incorporating the information of the low-resolution frames. The model has two terms: a 2-norm data fidelity term and a nuclear-norm regularization term. Alternating direction method of multipliers is used to solve the model. Comparison of our methods with other models on synthetic and real video clips shows that our resulting images are more accurate with less artifacts. It also provides much finer and discernable details.
Rui Zhao, Raymond HF Chan
Weitere Informationen

Premium Partner

    Bildnachweise