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.

Mini-Courses

Prof. D. Bertaccini (Italy, Univ. di Roma "Tor Vergata")
Iterative methods for large sparse structured linear systems
Note: the seminar taken by S. Filippone (see below) is a mandatory complement of this course.

Prof. C. Di Fiore and P. Zellini (Italy, Univ. di Roma "Tor Vergata")
Displacement decompositions, matrix algebras, triangular Toeplitz matrices, Bernoulli numbers
3 lectures - Moscow Part, 6 lectures - Rome part
Prof. D. Fasino (Italy, Univ. degli studi di Udine)
Applied spectral graph analysis
4 lectures - Moscow Part

Prof. Kh. D. Ikramov (Russia, Moscow State University)
Introduction to commutative algebra (Hilbert theorems, Groebner bases)
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
Dr. I. E. Kaporin (Russia, Moscow, Computer Center RAS)
Preconditioning techniques for general sparse symmetric positive definite matrices
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.
Prof. I. V. Oseledets (Russia, Moscow, INM-RAS)
Numerical methods in higher dimensions: theory, algorithms, software
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
Prof. M. Picardello (Italy, Univ. di Roma "Tor Vergata")
Global Illumination in Computer Graphics
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:
1. Radiometry, photometry, bidirection reflectance distribution function, flux, radiance, the rendering equation: hemisphere and area formulation.
2. Probabilistic methods for computing integrals: Monte-Carlo, samples with assigned distribution, variance and variance-minimizing probability distribution. Variance reduction, stratified sampling.
3. Importance function and the Green kernel of the rendering operator: Global reflectance distribution function.
4. Stochastic Ray Tracing and its variance.
5. Stochastic radiosity: stochastic Jacobi relaxation, discrete random walk methods, continuous random walks (photon tracing), variance of all these methods.
6. Outline of multipass methods: final gathering, Metropolis light transport, Irradiance caching.
7. Photon mapping, photon density and radiance gathering via nearest neighbour photons.
This brief introduction has no aim to completeness. Therefore the topics will be covered briefly, and parts 3 and 6 will be skipped altogether; part 7 will be covered only if there is some time, and anyway very quickly; part 5 may be shortened according to the amount of time left. Although the natural way to study this material is by programming a computer to develop a photorealistic renderer, thare will be absolutely no time for this, and students will not be expected to have this type of abilities. However, they are expected to understand the pseudo-codes arising from the mathematical modeling.
Exercises
Prof. E. E. Tyrtyshnikov and O. Lebedeva (Russia, Moscow, INM-RAS)
Matrices, tensors, computations
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
Prof. Y. Vassilevski (Russia, Moscow, INM-RAS)
Introduction to multigrid and multilevel methods
6 lectures - Moscow Part

Prof. N. L. Zamarashkin and S. A. Goreinov (Russia, Moscow, INM-RAS)
Shannon, codes, practical computations
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

Seminars

Prof. A. De Rossi (Italy, Univ. degli studi di Torino)
Some Topics on Numerical Linear Algebra for Meshfree Approximation
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.
Prof. F. Di Benedetto (Italy, Univ. degli studi di Genova)
Preconditioning and Regularization
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.
Prof. S. Fanelli (Italy, Univ. di Roma "Tor Vergata")
First order pseudo-BFGS methods with O(n) complexity and superlinear convergence
1 lecture - Rome Part

S. Filippone (Italy, Univ. di Roma "Tor Vergata")
Some issues on high performance numerical methods for large sparse linear systems
1 lecture - Rome Part
Note: this seminar is a mandatory complement of the course taken by Prof. D. Bertaccini (see above).

Prof. C. Manni (Italy, Univ. di Roma "Tor Vergata")
Totally positive bases and matrices
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.
F. Tudisco (Italy, Univ. di Roma "Tor Vergata")
Matrices which leave a cone invariant
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