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 e altri)
-
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- Recap on Direct methods for linear systems & least-squares problems
3- Stability. Perturbation Theory. Backward Stability & error analysis
4- Direct methods for eigenvalue problems
5- Iterative Methods. Krylov subspace methods (for linear systems and eigenvalue problems)
6- Randomised algorithms (for linear systems & least squares)
7- Other Applications of SVD. Clustering and Nonnegative Matrix Factorization. Further Applications in Data Mining and Pattern recognition.
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 del corso e alcune note/dispense per diversi argomenti
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 di un elaborato che riassume 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).
Gli studenti che parteciperanno nella "didattica invertita" (flipped classroom) avranno anche il voto extra della loro esposizione.
Nel progetto 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.
È permesso svolgere il progetto in collaborazione con al più due altre persone (cioe, gruppi di un massimo di tre persone). Va consegnato in formato pdf e descrive i risultati ottenuti in al più 10-15 pagine; si raccomanda di scriverlo autonomamente. Deve essere consegnato, insieme ai nominativi del gruppo, tre-quattro giorni lavorativi prima della data concordata per la prova finale. Parte dell'esame verterà sul contenuto dell'elaborato, che permettera valutare la applicazione delle conoscenze acquisite.
Orario di ricevimento
Il ricevimento e per appuntamento via email.
Sustainable Development Goals
Aims
The main goals of the course are:
-
Knowledge (and understanding) of the Singular Value Decomposition and its wide uses.
-
Knowledge (and understanding) of state-of-the art algorithms for eigenvalue computation
of core algorithms for solving linear systems, including in particular iterative solution methods of Krylov subspace type -
Knowledge (and understanding) of some of the techniques for constructing and analyzing randomised algorithms.
-
Ability to construct and analyse the numerical algorithm. Ability 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.Randomized SVD
2- Direct methods for linear systems and least-squares problems
3- Stability. Perturbation Theory. Backward Stability & error analysis
4- Direct methods for eigenvalue problems
5- Krylov subspace methods (for eigenvalue problems and linear systems). Preconditioning
6- Randomised algorithms (for linear systems & least squares)
7- Other Applications of SVD. Clustering and Nonnegative Matrix Factorization. Further Applications in Data Mining and Pattern recognition.
Prerequisites
Solid knowledge of Analysis, Linear Algebra and basic Numerical Analysis.
Solid knowledge of MATLAB
Desiderable: Good knowledge of basic probability
Teaching form
Lectures in class and in the Lab.
We will use MATLAB for all computer examples, exercises and projects.
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.
Textbook and teaching resource
Different material will be provided during the course. The course has a big practical component for which we will use MATLAB
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 of a small project
2- a small (oral or written ) exam. Specifics on the oral or written exam will be given later on during the course.
The students who adhere to the flipped classroom will have the extra vote from their exposition.
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. The project should be handed four days before the before the date of 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.
Office hours
By appointment (that should be fixed by writing an email to me)
Sustainable Development Goals
Staff
-
Blanca Pilar Ayuso De Dios
