Course Syllabus
Obiettivi
Gli obiettivi principali del corso sono:
-
Fornire conoscenze della SVD, gli algoritmi per il suo calcolo e le sue multiple applicazioni.
-
Fornire conoscenze dei metodi numerici per la risoluzione di probleimi matriciale (tra cui: sistemi lineari & calcolo autovalori)
-
Fornire conoscenze della costruzione e analisi di algoritmi iterativi di Krylov
-
Fornire conoscenze della costruzione e analisi di algoritmi randomizzati
-
Capacita di implementare in modo efficiente i diversi algoritmi. Capacita di interpretare e analizzare i risoltati numerici
Contenuti sintetici
Il corso inizia studiando gli algoritmi basilari per la risoluzione di problemi che coinvolgono le matrici, tra cui: decomposizione a valori singolari, sistemi lineari, calcolo autovalori e minimi quadrati. Verranno introdotte diverse tecniche basilari per la costruzione e analisis di algoritmi efficienti, a seconda della dimensione delle matrici. In particolare verrano considerati metodi diretti, metodi iterativi e metodi randomizzati.
Gli argomenti verrano coperti dal punto di vista matematico, studiando come costruire e analizzare esplorando le sue proprietà e validando gli algoritmi in problemi concreti.
Programma esteso
0- Introduction. Recap on Linear Algebra concepts and basic matrix decompositions.
1- SVD and its properties. Applications of SVD. Truncated SVD. Randomized SVD
2- Stability. Perturbation Theory. Backward Stability & error analysis
3- Direct methods for eigenvalue problems. Recap of direct methods for Linear Systems & LS
4- Iterative Methods. Krylov subspace methods (for linear systems and eigenvalue problems)
6- Randomised algorithms (for linear systems & least squares). Sketching. Randomized SVD
7- Further Applications in Data Mining, Pattern recognition and Machine Learning (this will be study mostly through projects)
Prerequisiti
Si assumono buone conoscenze di Analisi e di Algebra Lineare.
Si assumono conoscenze di Analisi Numerico di Base. Buona conoscenze di MATLAB
Auspicabile: buone conoscenze di base di probabilita
Modalità didattica
Lezioni frontali e nel laboratorio.
MATLAB verra usato per gli esempi, esercizi, e progetti.
Si offrira la possibilita (opzionale!) di usare "flipped classroom" (o inverse-blended teaching) per alcuni argomenti del corso, per gli studenti che vogliano aderire.
Materiale didattico
Verrano distribuite slides e note del corso e alcune note/dispense per diversi argomenti
Non si segue un libro unico. Si fornirano anche i programmi.
Bibliografia :
-Lars Elden, Matrix Methods in Data Mining and Pattern Recognition, SIAM (2019)
-N. J. Higham, : Accuracy and Stability of Algorithms, SIAM (2002)
-Horn and Johnson: Matrix Analysis (2012)
-D. S. Watkins, Fundamentals of Matrix Computation, Wiley, (2002)
-D. S. Watkins, The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods, SIAM (2007)
-J. Demmel: Applied Numerical Linear Algebra (1997)
-Per-Gunnar Martinsson &J. Tropp, Randomized Numerical Linear Algebra: Foundations & Algorithms (2021)
-G. Strang, Linear Algebra and Learning from Data, SIAM, (2019)
-G. Strang, Linear Algebra for Everyone, Cambridge (2020)
-Golub-Van Loan : Matrix Computations (2012)
-Trefethen-Bau: Numerical Linear Algebra (1997) (also 2022)
Periodo di erogazione dell'insegnamento
Primo semestre
Modalità di verifica del profitto e valutazione
L'esame consiste di due parti:
--lo sviluppo e la esposizione di un piccolo progetto a scelta e
--una piccola prova finale (orale o scritta) individuale.
Ogni parte verrà valutata indipendentemente e concorrerà in egual misura alla determinazione del voto complessivo finale (sempre che entrambi voti siano maggiore o uguale a 18). Per sostenere la prova finale individuale e necessario ottenere un punteggio maggiore o uguale a 18 sull'progetto. Il voto finale, espresso in trentesimi con eventuale lode, e' dato dalla media delle due prove (sempre che entrambi voti siano maggiore o uguale a 18).
Il progetto e la sua esposizione si valuta la conoscenza degli algoritmi sviluppati durante il corso richiedendo la scrittura di alcuni programmi in MATLAB per la risoluzione di problemi matriciali. Viene valutato in termini di completezza, rigore, accuratezza, nonche chiarezza espositiva e capacita di analisi.
Il colloquio orale individuale e' teso ad approfondire il livello delle conoscenze acquisite; l’autonomia di analisi e giudizio; le capacità espositive dello studente. In particolare nella suddetta prova orale/scritta si richiede la capacità di esporre gli enunciati e le dimostrazioni dei teoremi, le definizioni, gli esempi/controesempi e le tecniche di calcolo introdotte.
Il progetto potrà essere scelto da un elenco, che verrà messo a disposizione verso la fine del corso e ha validità fino al primo appello della successiva edizione del corso. Solitamente si lavorera su un argomento applicato o su un paper di ricerca.
È permesso svolgere il progetto in collaborazione con al più due altre persone (cioe, gruppi di un massimo di tre persone). La esposizione sara individuale.
Una traccia del progetto va consegnata insieme ai nominativi del gruppo, tre-quattro giorni lavorativi prima della data concordata per la esposizione del progetto e la prova finale. Si raccomanda di scriverlo autonomamente. Parte dell'esame verterà sul contenuto dell'a esposizione del progetto, che permettera valutare la applicazione delle conoscenze acquisite.
A parte del esame gli studenti potranno avere dei punti extra participando alle diverse attivita di lezione:
Gli studenti che parteciperanno nella "didattica invertita" (flipped classroom) avranno anche il voto extra della loro esposizione.
Gli studenti che parteciperanno alla risoluzione in classe degli esercizi avranno anche un voto extra per la loro partecipazione- esposizione.
Orario di ricevimento
Il ricevimento e per appuntamento via email.
Sustainable Development Goals
Aims
The main goals of the course are:
Knowledge and understanding. The student will learn the fundamental Singular Value Decomposition and its application. The state-of-the art algorithms for eigenvalue computation & solution
of linear systems. In particular: iterative solution methods of Krylov subspace type and Randomized algorithm
Applying knowledge and understanding. By means of several examples and exercises, the student will develop the ability of constructing and analysing numerical linear algebra algorithms (for both eigenvalue computation & solution
of linear systems)
Making judgements. The student will be able to face critically problems concerning numerical linear algebra, identifying by himself/herself the most appropriate tools among those introduced in the course. He will be able to interpret and analyse numerical results
Communication skills. The student will become familiar with the introduced language and mathematical formalism, which will make him/her able to communicate with rigor and clarity the acquired knowledge.
Learning skills. The student will be able to apply the acquired knowledge to different applications coming from physics, partial differential equations, data science and Machine Learning which require a good numertical linear algebra background.
The student will be able to interpret and analyse numerical results
Contents
This course builds on elementary linear algebra and in it we derive, describe and analyse a number of widely used constructive methods (algorithms) for various problems involving matrices. Numerical Methods for solving linear systems of equations, computing eigenvalues and singular values and various related problems involving matrices will be the main focus of this course.
We will present different approaches (depending on the size of the matrices,-small,large, huge-), for designing and analzying solution techniques. Namely, direct methods, iterative methods and randomized methods.
We shall consider the subject from mathematical point of view, studying how to construct modern computational algorithms, exploring their properties and validating the algorithms in concrete problems.
Detailed program
0- Introduction. Recap on Linear Algebra concepts and basic matrix decompositions.
1- SVD and its properties. Applications of SVD. Truncated SVD.
2- Stability. Perturbation Theory. Backward Stability & error analysis
3- Direct methods for eigenvalue problems. Recap of direct methods for Linear Systems & LS
4- Iterative Methods. Krylov subspace methods (for linear systems and eigenvalue problems)
6- Randomised algorithms (for linear systems & least squares). Sketching. Randomized SVD
7- Further Applications in Data Mining, Pattern recognition and Machine Learning (this will be study mostly through projects)
Prerequisites
Solid knowledge of Analysis, Linear Algebra and basic Numerical Analysis.
Solid knowledge of MATLAB or any programming language
Auspicable: Good knowledge of basic probability
Teaching form
Lectures in class and in the Lab.
We will mostly use MATLAB for all computer examples, exercises and projects. You can alternatively use Python.
The students will be given the possibility of adhering to the use of "flipped classroom" (or inverse-blended teaching)for a few of the topics of the course. This option will be completely optional and will provide some extra mark for the final vote.
Textbook and teaching resource
Different material (slides and notes)will be provided during the course. The course has a big practical component for which we will use MATLAB (but you can use any other language you like). Programs will be also provided.
We will use several books( several chapters in each of them to cover the different topics)
Bibliography:
-Lars Elden, Matrix Methods in Data Mining and Pattern Recognition, SIAM (2019)
-N. J. Higham, : Accuracy and Stability of Algorithms, (2002)
-Horn and Johnson: Matrix Analysis (2012)
-D. S. Watkins, Fundamentals of Matrix Computation, Wiley, (2002)
-D. S. Watkins, The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods, SIAM (2007)
-J. Demmel: Applied Numerical Linear Algebra (1997)
-Per-Gunnar Martinsson &J. Tropp, Randomized Numerical Linear Algebra: Foundations & Algorithms (2021)
-G. Strang, Linear Algebra and Learning from Data, SIAM, (2019)
-I. Ipsen, Numerical Matrix Analysis, SIAM, 2009
-Golub-Van Loan : Matrix Computations (2012)
-Trefethen-Bau: Numerical Linear Algebra (1997) (also 2022)
Semester
First semester
Assessment method
The evaluation of the course has two parts:
1- the development and presentation of a small project (on a topic related to the course and chosen by the student/students) and
2- a small (oral or written ) exam. Specifics on the oral or written exam will be given at the begining of the course.
The small project could be chosen from a list of projects that will be made available to the students towards the end of the course. The projects will either require students to delve deeper into one of the topics of the course or try to apply many of the techniques for some particular application that can be written as a matrix problem. Students are encouraged to work on the project in groups of at most two or three people.
A small trace or guide of the project should be handed four days before the before the date of project exposition and the small exam. Part of the small exam will be devoted to the discussion of the project, allowing to validate the knowledge and capabilities of the students related to the course.
The project will be chosen by the students. A List of possible topics will be made available towards the end of the course.
The students who adhere to the flipped classroom will have the extra marks from their participation-exposition.
The students who participate in the exercises classes (by solving and discussing exercises and computer exercises) will have extra marks from their participation-exposition.
Office hours
By appointment (that should be fixed by writing an email to me)
Sustainable Development Goals
Staff
-
Blanca Pilar Ayuso De Dios
