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:
- 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.
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