Rome-Moscow school of Matrix Methods and Applied Linear Algebra 2016

Lecturers and Courses

This is a tentative list of courses held at the school. The organization is currently in progress. Daniele Bertaccini, with Fabio Durastante

Incomplete factorization preconditioners and their
updates with applications

The aim of this set of lectures is the presentation
of some state of the art techniques for the
computation of incomplete factorizations of given
large and sparse matrices. We will recall the
general setting in which this kind of strategy have
been devised and some applications.
We will focus our attention mainly on two particular
class of algorithms, the one that descends from the
modification of the classical LU factorization,
namely the Incomplete LU factorization with its
variants, and the use of incomplete biconjugation
technique for the direct computation of an
approximate inverse. Both algorithmical and
mathematical issues will be addressed. At the end
of this overview we will focus on some techniques
for computing a cost-effective update of the
incomplete factorization.

Lecture Notes P1

Lecture Notes P2

Lecture Notes P3

Exercises

** 2 lectures (Moscow) - 3 lectures (Rome)**

References:

[1] Bertaccini, Daniele, and Filippone Salvatore. "Sparse approximate inverse preconditioners on high performance GPU platforms." Computers & Mathematics with Applications 71.3 (2016): 693-711.

[2] Van Duin, Arno CN. "Scalable parallel preconditioning with the sparse approximate inverse of triangular matrices." SIAM journal on matrix analysis and applications 20.4 (1999): 987-1006.

[3] Benzi, Michele. "Preconditioning techniques for large linear systems: a survey."Journal of computational Physics 182.2 (2002): 418-477.

Michael BotchevLecture Notes P1

Lecture Notes P2

Lecture Notes P3

Exercises

References:

[1] Bertaccini, Daniele, and Filippone Salvatore. "Sparse approximate inverse preconditioners on high performance GPU platforms." Computers & Mathematics with Applications 71.3 (2016): 693-711.

[2] Van Duin, Arno CN. "Scalable parallel preconditioning with the sparse approximate inverse of triangular matrices." SIAM journal on matrix analysis and applications 20.4 (1999): 987-1006.

[3] Benzi, Michele. "Preconditioning techniques for large linear systems: a survey."Journal of computational Physics 182.2 (2002): 418-477.

Selected topics in matrix theory of time
integration methods

3-4 lectures (Moscow)

3-4 lectures (Rome)

Dario Fasino3-4 lectures (Rome)

Matrix methods in network analysis

Graphs are ubiquitous in the real world;
social networks, transport networks, computer
networks are objects
that can be satisfactorily modeled as graphs:
the so-called complex networks. In various contexts,
matrix theory and techniques borrowed from numerical
linear algebra play a major role in their analysis
and treatment.
For example, matrix functions and eigenvector
computations are
required by certain centrality indices to understand
roles or find out rankings of nodes and edges; and
spectral techniques are efficient, widespread tools
to solve community detection and network
partitioning problems. The aim of this mini-course
is to introduce students to the basic tools in
linear algebra and matrix theory that underpin the
modern complex network science.

**Short outline:**

Perron-Frobenius theory, nodal domains, spectral properties of graph matrices (adjacency, laplacian, modularity matrices) and their applications in complex network analysis: eigenvector-based centrality indices, graph partitioning and community detection problems.

**10 lectures**

Sergei Goreinov Perron-Frobenius theory, nodal domains, spectral properties of graph matrices (adjacency, laplacian, modularity matrices) and their applications in complex network analysis: eigenvector-based centrality indices, graph partitioning and community detection problems.

Convex optimization and applications

This course will not be an advanced study of convex analysis, nor a survey of all
possible algorithms for convex optimization. Instead, we will concentrate only on few
good algorithms (including barrier and interior-point methods) and few interesting
applications (including pass-band filter design and wireless channel estimation).
Our main goal will be to develop a working and concrete knowledge of convex
optimization: an ability to recognize and solve convex optimization problems.

**Short outline:**

Convex sets. Separating hyperplanes. Convex functions. Conjugate function. Duality. Optimality conditions. Theorems on alternatives. Best approximation in C-norm. Optimal detector design and hypothesis testing. Distance between sets. Extremal volume ellipsoids. Primal-dual interior-point methods.

**8 lectures **

Vladimir LyashevConvex sets. Separating hyperplanes. Convex functions. Conjugate function. Duality. Optimality conditions. Theorems on alternatives. Best approximation in C-norm. Optimal detector design and hypothesis testing. Distance between sets. Extremal volume ellipsoids. Primal-dual interior-point methods.

Linear Algebra Issues in Wireless Communications

Brief introduction in the state-of-the-art problems of matrix
calculations in wireless communication should allow participants to
understand importance of matrix methods for systems, which become part
of our life.

The course is presented by 3 parts:

Part 1. September 9. Introduction in wireless communication and its relation to linear algebra problems (90 minutes)**3 lectures **

Summary

Lecture 1 Lecture 2 Lecture 3

Carla ManniThe course is presented by 3 parts:

Part 1. September 9. Introduction in wireless communication and its relation to linear algebra problems (90 minutes)

- System model of wireless communication
- Capacity of the system and linear space extension
- Definition of system matrix and its properties discussion
- Outlook of matrix methods that are playing important role in telecom.
- Some tasks for the weekend.

- Not well-posed problems in the sense of Hadamard (ill-posed problems)
- \(QR\), \(LU\), iterative methods and requirements to them from wireless systems
- Important role of \(SVD\) in ultra-high rate communications
- Belief propagation approach in detection problems
- Topic for next time discussion (task for home preparation)

- The simplest one doesn't mean the fastest one
- Robustness & accuracy
- Task analysis and discussion

Summary

Lecture 1 Lecture 2 Lecture 3

Spectral analysis of matrices arising from isogeometric analysis

Isogeometric Analysis (IgA) is a paradigm for the analysis of problems governed
by partial differential equations. Its goal is to improve the connection between
numerical simulation and Computer Aided Design (CAD) systems. In its original
formulation, the main idea in IgA is to use directly the geometry provided by CAD
systems and to approximate the unknown solutions of differential equations by the
same type of functions. Tensor-product B-splines and their rational extension, the
so-called NURBS, are the dominant technology in CAD systems used in engineering and thus also in IgA. Galerkin discretizations have been intensively employed in the
IgA context. This talk is devoted to the study of the spectrum of the resulting stiffness
matrices, when the fineness parameters tend to zero so that the related
matrix-size tends to infinity. We consider elliptic problems with constant coefficients.

**1 seminar**

Reference

Excercises

Nicola MastronardiReference

Excercises

Numerical analysis of Symmetric matrices

3-4 lectures (Moscow)

Eigenvalues, Jordan and Weyr structures

Reference
3-4 lectures (Rome)

Roberto Peirone Self-similar energies on Fractals

Definition and construction of self-similar fractals. Self-similar energies on finitely ramified self-similar fractals. Eigenforms. Existence and specially uniqueness of eigenforms. The uniqueness problem is treated by means of the Perron-Frobenius theory.

Stefano Serra-Capizzano,Spectral properties of Generalized Locally Toeplitz matrix-sequences and Applications

Recently, the class of Generalized Locally Toeplitz (GLT) sequences has been introduced as a generalization both of classical Toeplitz sequences and of variable coefficient differential operators and, for every sequence of the class, it has been demonstrated that it is possible to give a rigorous description of the asymptotic spectrum in terms of a function (the symbol) that can be easily identified.

This generalizes the notion of a symbol for differential operators (discrete and continuous) or for Toeplitz sequences for which it is identified through the Fourier coefficients and is related to the classical Fourier Analysis.

The GLT class has nice algebraic properties and indeed it has been proven that it is stable under linear combinations, products, and inversion when the sequence which is inverted shows a sparsely vanishing symbol (sparsely vanishing symbol means a symbol which vanishes at most in a set of zero Lebesgue measure). Furthermore, the GLT class virtually includes any approximation by local methods (Finite Difference, Finite Element, Isogeometric Analysis etc) of partial differential equations (PDEs) and, based on this, we demonstrate that our results on GLT sequences can be used in a PDE setting in various directions:

**Keywords:** Toeplitz and Generalized Locally Toeplitz matrices, approximations of PDE and related methods, such as Finite Differences, Finite Volumes, Finite Elements. Isogeometric Analysis: collocations, Galerkin and discontinuous Galerkin

,br> Selected Bibliography

** 2 lectures (Rome) **

Eugene Tyrtyshnikov This generalizes the notion of a symbol for differential operators (discrete and continuous) or for Toeplitz sequences for which it is identified through the Fourier coefficients and is related to the classical Fourier Analysis.

The GLT class has nice algebraic properties and indeed it has been proven that it is stable under linear combinations, products, and inversion when the sequence which is inverted shows a sparsely vanishing symbol (sparsely vanishing symbol means a symbol which vanishes at most in a set of zero Lebesgue measure). Furthermore, the GLT class virtually includes any approximation by local methods (Finite Difference, Finite Element, Isogeometric Analysis etc) of partial differential equations (PDEs) and, based on this, we demonstrate that our results on GLT sequences can be used in a PDE setting in various directions:

- as a generalized Fourier Analysis for the design and for the study of preconditioned iterative and semi-iterative methods, when dealing with variable coefficients, non rectangular domains, non uniform gridding or triangulations,
- for a multigrid analysis of convergence and for providing spectral information on large preconditioned systems in the variable coefficient case,
- in order to provide a tool for the stability analysis of PDE numerical schemes (e.g. a necessary von Neumann criterium for variable coefficient systems of PDEs is obtained, uniformly with respect to the boundary conditions), etc.

,br> Selected Bibliography

Norms and Inequalities

Norms, convexity, separation. Majorization and doubly stochastic matrices.
Interlacing properties for the eigenvalues of Hermitian matrices.
Weyl inequalities and Hoffman-Wieland theorem. Lidskii theorem.
Unitarily invariant norms. Ky Fan norms. John von Neumann and Mirski
theorems.

Excercises

**3+3 lectures**

Nikolai Zamarashkin, with Olga LebedevaExcercises

Semidefinite Programming

The idea of the course is to introduce the theory of
semidefinite programming (optimization).
SDP is not only a powerful numerical approach but
also a very useful analytical tool for finding
approximate solutions of several NP hard problems.
We will consider some basic facts about semidefinite
programs and some nontrivial examples of so called
semidefinite relaxations of NP hard problems.

Lecture Notes P1 Exercises

** 4 lectures + 4 seminars**

Lecture Notes P1 Exercises

Aleksei Ustimenko

Tensor Decomposition

Notes
2-3 seminars