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

Lecturers and Courses

Lecturers of the mini-courses of the School will be mainly professors of TV, LMSU and INM-RAS.
There will be also seminars held by professors of other academic and research institutions.
Note: the seminar taken by S. Filippone (see below) is a mandatory complement of this course.

3 lectures - Moscow Part, 6 lectures - Rome part

4 lectures - Moscow Part

7 lectures - Rome Part

An important part of algebraic geometry is the study
of systems of polynomial equations in one or more
variables. It asks such questions as: Does the system
have finitely many solutions, and if so, how can one
find them? If there are infinitely many solutions, how
can they be described and manipulated?

Commutative algebra can be regarded as a section of abstract algebra that serves the needs of algebraic geometry. For instance, the solutions of a system of polynomial equations form a geometric object called a variety; the corresponding algebraic object is an ideal.

Commutative algebra as an instrument of algebraic geometry originates from two famous theorems proved by Hilbert in the 1890s, namely, the Hilbert basis theorem and Hilbert's Nullstellensatz. These theorems are a theoretical foundation that makes possible to answer the above questions about systems of polynomial equations. However, algorithmic tools required for dealing with such systems were developed only in the 1960s. In that time, the important concept of a Groebner basis of an ideal was invented by B. Buchberger, and an algorithm that constructs such a basis (Buchberger's algorithm) was found. It can be viewed as a generalization of the division algorithm for polynomials in one variable.

This series of lectures will be based on Chapters 1-4 of the wonderful book "Ideals, Varieties, and Algorithms" by D. Cox, J. Little, and D. O'Shea.

Problems

Rules

Commutative algebra can be regarded as a section of abstract algebra that serves the needs of algebraic geometry. For instance, the solutions of a system of polynomial equations form a geometric object called a variety; the corresponding algebraic object is an ideal.

Commutative algebra as an instrument of algebraic geometry originates from two famous theorems proved by Hilbert in the 1890s, namely, the Hilbert basis theorem and Hilbert's Nullstellensatz. These theorems are a theoretical foundation that makes possible to answer the above questions about systems of polynomial equations. However, algorithmic tools required for dealing with such systems were developed only in the 1960s. In that time, the important concept of a Groebner basis of an ideal was invented by B. Buchberger, and an algorithm that constructs such a basis (Buchberger's algorithm) was found. It can be viewed as a generalization of the division algorithm for polynomials in one variable.

This series of lectures will be based on Chapters 1-4 of the wonderful book "Ideals, Varieties, and Algorithms" by D. Cox, J. Little, and D. O'Shea.

Problems

Rules

4 lectures - Moscow Part

L1. The preconditioned conjugate gradient (CG) method for linear
systems. Convergence rate estimates via spectral and K-condition
numbers as the theoretical basis for preconditioning strategies.

slides

L2. Approximate triangular factorization "by value". Estimating the sparsity of approximate factor via truncation threshold. First- and second-order factorizations with estimates of the condition numbers.

L3. Incomplete inverse Cholesky factorizations (a.k.a. FSAI) as the K-optimum CG preconditionings. The block version with approximate inversion of submatrices and its relation to the Overlapping Domain Decomposition Methods.

L4. Miscellaneous related topics: polynomial preconditionings; the use of preconditionings in eigenvalue computations etc.; parallel implementation issues.

slides

L2. Approximate triangular factorization "by value". Estimating the sparsity of approximate factor via truncation threshold. First- and second-order factorizations with estimates of the condition numbers.

L3. Incomplete inverse Cholesky factorizations (a.k.a. FSAI) as the K-optimum CG preconditionings. The block version with approximate inversion of submatrices and its relation to the Overlapping Domain Decomposition Methods.

L4. Miscellaneous related topics: polynomial preconditionings; the use of preconditionings in eigenvalue computations etc.; parallel implementation issues.

3 lectures - Rome Part

High-dimensional problems were always fascinating numerical analysts.
Here we talk not about large scale-problems, but about problems on
"impossible"-scale to standard numerical methods. For example, this
can be an equation in d-dimensional space with d being as high as 10,
100, or even 1000. Exponential dependence from the dimension is known
as the curse of dimensionality. Such kind of problems appear in many
applications, mainly in chemisty and physics, but were usually avoided
by mathematicians. In my lections I will talk about new mathematical
results that open new perspectives for numerical treatment of
high-dimensional methods, based on so-called numerical tensor methods.

Theoretical results are rather sparse and are mainly algebraical. The algorithms are far beyond the theoretical justification: we can solve high-dimensional problems, but we do not yet know why low-parametric solution exists. But if it exists (this is our main assumption), then we can find it in a robust way, and this is a great breakthrough in comparison with previously used numerical techniques. Algorithms working with high-dimensional arrays (tensors) play the main role here, and they will be explained it details.

The software is the third, but the very crucial point of numerical algorithms, which is usually ignored. It is almost not possible to give a new algorithm without numerical experiments. The algorithms should be reusable by many researchers (here we have MATLAB as a standard for technical computing), but should be still eligible for production versions. This is a very important point, and I will spend some time in describing modern technologies for the creation of easy-to-use and effective software packages based on the Python ecosystem.

Problems

Theoretical results are rather sparse and are mainly algebraical. The algorithms are far beyond the theoretical justification: we can solve high-dimensional problems, but we do not yet know why low-parametric solution exists. But if it exists (this is our main assumption), then we can find it in a robust way, and this is a great breakthrough in comparison with previously used numerical techniques. Algorithms working with high-dimensional arrays (tensors) play the main role here, and they will be explained it details.

The software is the third, but the very crucial point of numerical algorithms, which is usually ignored. It is almost not possible to give a new algorithm without numerical experiments. The algorithms should be reusable by many researchers (here we have MATLAB as a standard for technical computing), but should be still eligible for production versions. This is a very important point, and I will spend some time in describing modern technologies for the creation of easy-to-use and effective software packages based on the Python ecosystem.

Problems

4 lectures - Moscow Part

This is a short introduction to the mathematical modeling of photorealistic rendering in Computer Graphic. The steps to this goal are as follows:

Exercises

- Radiometry, photometry, bidirection reflectance distribution function, flux, radiance, the rendering equation: hemisphere and area formulation.
- Probabilistic methods for computing integrals: Monte-Carlo, samples with assigned distribution, variance and variance-minimizing probability distribution. Variance reduction, stratified sampling.
- Importance function and the Green kernel of the rendering operator: Global reflectance distribution function.
- Stochastic Ray Tracing and its variance.
- Stochastic radiosity: stochastic Jacobi relaxation, discrete random walk methods, continuous random walks (photon tracing), variance of all these methods.
- Outline of multipass methods: final gathering, Metropolis light transport, Irradiance caching.
- Photon mapping, photon density and radiance gathering via nearest neighbour photons.

Exercises

6 lectures - Moscow Part, 6 lectures - Rome Part

Canonical tensor decomposition. Canonical tensor ranks. The ALS method.
Canonical decomposition and simultaneous diagonalization of matrices.
Preservation of linear constraints. Existence of generic tensor rank in the
complex case. Kruskal theorem on uniqueness of canonical decomposition.
Kruskal ranks and sparse solutions to linear systems. The uncertainty
principle. Tucker decomposition. Reduction of dimensionality. Tensor-Train
and Hierarchical-Tucker decompositions. TT-SVD algorithm. TT rounding
algorithm. DMRG algorithm. Cross interpolation algorithms.

Exercises

Notes and slides:

T1 T2 T3

Exercises

Notes and slides:

T1 T2 T3

6 lectures - Moscow Part

8 lectures - Moscow Part, 4 lectures - Rome Part

Introduction to information theory, Shannon theorem. Constructive examples
of Shannon
codes, low-density parity check codes. Method of polarization. Polar codes.
Belief
propagation algorithms, application to polar codes design. Decoding with
advanced BP.
Introduction to martingal theory. Convergence theorem. Guide to practical
Shannon
codes, concatenation of codes.

Exercises

Exercises

2 lectures - Rome Part

In the seminars a brief introduction to meshfree
approximation using
radial basis functions is presented.
Then we consider some problems about the ill-conditioning of
interpolation matrices and we review a
few preconditioning techniques usually used. The case of
collocation matrices is
also outlined.
Finally, some open problems are proposed.

*References:*

G.E. Fasshauer, Meshfree Approximation Methods with Matlab, World Scientific Publishing, Singapore, 2007.

G.E. Fasshauer, Meshfree Approximation Methods with Matlab, World Scientific Publishing, Singapore, 2007.

2 lectures - Rome Part

In the first seminar we give a survey of the general approach to preconditioning in a matrix algebra, focusing on computational issues and spectral properties for structured linear systems.
In the second seminar we treat the problem of solving discrete ill-posed problems by iterative methods, discussing how an appropriate choice of the preconditioner can preserve the regularization effect.

*References:*

F. Di Benedetto, Gram matrices of fast algebras have a rank structure. SIAM J. Matrix Anal. Appl. 31 (2009), 526-545.

C. Estatico, A classification scheme for regularizing preconditioners, with application to Toeplitz systems, Linear Algebra Appl., 397 (2005), pp. 107-131.

F. Di Benedetto, Gram matrices of fast algebras have a rank structure. SIAM J. Matrix Anal. Appl. 31 (2009), 526-545.

C. Estatico, A classification scheme for regularizing preconditioners, with application to Toeplitz systems, Linear Algebra Appl., 397 (2005), pp. 107-131.

1 lecture - Rome Part

1 lecture - Rome Part

Note: this seminar is a mandatory complement of the course taken by Prof. D. Bertaccini (see above).1 lecture - Rome Part

Total positivity plays a crucial role in different areas of pure and
applied Mathematics.
In this talk we summarize the main properties of totally positive matrices
and bases, focusing on their consequences
on the shape of curves and on optimal geometric representations of curves
and surfaces. Some open problems will be presented too.

1 lecture - Moscow Part, 1 lecture - Rome Part

Given a proper cone C of R^n, we consider the set M(C) of those matrices which map C onto itself. In particular we try to present some classical results concerning the spectrum of a generic matrix in M(C), also approaching to few new observations and open problems. Martices in M(C) are a natural generalizations of entrywise nonnegative matrices which is the set of matrices that leaves the cone of nonnegative vectors invariant. Many results of the renowned Perron-Frobenious theory thus follow.

Notes

Notes