Algebraic and Combinatorial Techniques for Computing

Teacher(s)

Jungers Raphaël; Remacle Jean-François;

Language

English
> French-friendly

Prerequisites

Basic formation in Linear Algebra and numerical computing (LEPL1101, LINMA1170).

Main themes

This course builds on the solid mathematical foundations of matrix 
theory and graph theory to develop algorithmic solutions to 
engineering problems. 
● Polynomial and structured matrices: Euclidean algorithm, 
Smith and Hermite normal forms, fast algorithms 
● Matrix semigroups: algebraic structure, algorithms, and 
applications (e.g., nonnegative factorization, joint spectral 
characteristics )
● Sparse matrices and chordal structures 
● Preconditioning of iterative methods, preconditioned 
conjugate gradients 
● Advanced topics to be presented in a seminar 
(combinatorial optimization and algebraic techniques, 
spectral and algebraic graph theory, tropical algebra, 
tensors and multilinear algebra, symbolic computation, 
matroid theory)

Learning outcomes

At the end of this learning unit, the student is able to :

The course enhances the following learning outcomes:  ● AA1.1, AA1.2  ● AA5.5  ● AA6.3  More precisely, the student will be able to :  ● Master advanced linear algebra  ● Analyze the mathematical properties of various problems  in applied mathematics and design algorithmic solutions  using advanced mathematical theories.  ● Apply or develop specific algorithms for applications in  statistics, signal processing, imaging, and dynamic systems.  ● Implement methods in high-level software and validate  their behavior on practical problems.  Transversal skills:  ● Collaborate in small teams to numerically solve  mathematical problems

Content

1. Canonical forms and computing on the quotient of a set 
2. Jordan’s theorem: proof and consequences 
3. Polynomial matrices: Smith and Hermite normal forms, fast 
algorithms 
4. Structured matrices 
5. Joint spectral characteristics 
6. Direct methods for solving systems: LU, Cholesky, pivoting, 
reordering (RCMK), sparse storage, fill-in. 
7. Krylov iterative methods: Arnoldi iteration, conjugate gradients, 
GMRES, Lanczos. 
8. Sparse matrices and chordal structures 
9. Preconditioning of iterative methods, preconditioned conjugate 
gradients

Teaching methods

• Courses Ex-cathedra
• Homeworks by group of students
• Flipped classrooms presentations by the students

Evaluation methods

The evaluation of the students is partly based on a written (or 
oral, depending of the circumstances) exam organized according 
to the rules imposed by the EPL. The exam material corresponds 
to the content of the lectures and lecture notes, with the 
possible exception of certain parts specified after the last session 
of the course. 
For a written exam, in case of doubt, the teacher might invite the 
student for a supplementary oral exam.
The exam is graded out of 14 points (E).

The other part of the evaluation (H) is based on the assignments (4 points) and 
presentation (2 points) made during the semester, and will be taken into 
account both in january and september These assignements and presentation account 6 points of the final grade, if the written exam is successfully passed (>=7/14). In the opposite case, only the exam grade counts as the final note.
Quizzes will be proposed at the end of some courses, and will be announced in advance. A bonus (B) of up to 1 point will be applied to the final grade in case of sufficient participation to the quizzes.
Final grade = min(20, max{E + H + B, E*20/14+B}),   if E ≥ 7
Final grade = E*20/14,   if E < 7

Online resources

http://moodleucl.uclouvain.be/course/view.php?id=7969

Bibliography

Ouvrages de référence :
● G.H. Golub and C.F. Van Loan (1989). Matrix 
Computations, 2nd Ed, Johns Hopkins University Press, 
Baltimore. 
● P. Lancaster and M. Tismenetsky (1985). The Theory of 
Matrices, 2nd Ed, Academic Press, New York 
● Trefethen, L. N., & Bau III, D. Numerical linear algebra 
(Vol. 50). Siam.

Teaching materials

• LINMA 2380 Course notes by R.J. et al.

Faculty or entity

> MAP