OVERVIEW

Numerical linear algebra deals with the study of problems related to the use of large and / or structured matrices. Many recent technological developments in the field of IT and data processing involve this kind of matrices. The aim of the course is to deepen the topics related to numerical linera algebra that were introduced during the bachelor degree.

AIMS AND CONTENT

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

TEACHERS AND EXAM BOARD

Exam Board

CRISTINA CAMPI (President)

ISABELLA FURCI

CLAUDIO ESTATICO (President Substitute)

LESSONS

Class schedule

The timetable for this course is available here: Portale EasyAcademy

EXAMS

EXAM DESCRIPTION

The exam consists in an oral test preceded by a brief discussion on the results obtained during the laboratory

ASSESSMENT METHODS

The oral test focuses on the theoretical topics developed during the lessons. Discussions and intuitive justification of theoretical concepts will be also carried on during the exam.

The discussion of the laboratory outocomes focuses on the codes written by the students and the interpretation if the results.

Exam schedule

FURTHER INFORMATION

Attendance, although not mandatory, is recommended.