LEARNING OUTCOMES

The course aims to deepen the knowledge of numerical linear algebra, with particular reference to the numerical treatment of large matrices, favoring the understanding of the most efficient methods, both direct and iterative.

AIMS AND LEARNING OUTCOMES

The course aims to provide students with the mathematical tools necessary to identify, understand and solve linear problems related to large and/or structured matrices that are present in most of the current application fields, such as, for example, page ranking on the Internet, image processing, tomography and non-destructive analysis in the civil and biomedical fields, machine learning.

At the end of the course the student will have acquired sufficient theoretical knowledge:

- to know and identify the main problems of a linear nature that require specially developed algorithms to be able to manage the large dimensions characterizing models and/or data, such as, for example, page ranking on the internet, image processing, tomography and non-destructive analysis in the civil and biomedical fields, machine learning from examples;
- to choose and apply numerical linear algebra tools to solve these problems via computer;
- to optimize the algorithms and the numerical code implemented for the numerical resolution of these problems;
- to implement these algebraic methodologies in a high-level programming language.

PREREQUISITES

The mathematical prerequisites are contained in the linear algebra and numerical analysis courses of the three-year degree (I  cycle). For an in-depth understanding, however, it may be useful to have some rudiments concerning the analysis of functions of several variables, iterative methods for linear systems and measure theory. The topics of the "Numerical Calculus" course, an optional three-year degree course, may be useful, although not necessary.

TEACHING METHODS

Lectures (44 hours)

Laboratory (6 hours)

SYLLABUS/CONTENT

Sparse matrices, structured matrices. Analysis of sparse matrices using graphs and permutation techniques. Connection and irreducibility. Centrality indices. Perron-Frobenius theory for non-negative matrices. Regular splitting. 

Inverse of matrices with low-rank modifications, Woodbury-Sherman-Morrison formula.

Inverse of block partitioned matrices, Schur's complement and its applications.

QR method for sparse matrices.

Separable matrices, Kronecker product, Kronecker sum and associated matrix equations. Spectral decomposition of Kronecker products.

Integral equations, discretization and convolution. Structured matrices. Toeplitz matrices and Szego-Tyrtyshnikov theorem. Circulant matrices. Fast Fourier Transform (FFT) and its applications to matrix algebra and polynomial algebra.

Nonlinear systems.

Insights on conjugate gradient, convergence analysis in relation to the spectrum of the matrix. Preconditioning techniques.

RECOMMENDED READING/BIBLIOGRAPHY

• D. Bini, M. Capovani, O. Menchi, Metodi Numerici per l'Algebra Lineare (Zanichelli, Bologna, 1988);
• C. Estatico, Gradiente coniugato e regolarizzazione di problemi mal posti (Quaderni del Gruppo Nazionale per l’Informatica Matematica, C.N.R., I.N.d.A.M., 1996).
•  Notes provided during lessons