Efficient Computational Algorithms

This course provides a comprehensive overview of the concepts of algorithm analysis and computing development. We will review 14 computing algorithms with the greatest influence on the development and practice of computing and engineering in the 20th century. We consider the following list of algorithms: Metropolis Algorithm for Monte Carlo, Simplex Method for Linear Programming, Krylov Subspace Iteration Methods, The Decompositional Approach to Matrix Computations, QR Algorithm for Computing Eigenvalues, Quicksort Algorithm for Sorting, Fast Fourier Transform, Integer Relation Detection, Fast Multipole Methods, Gradient Descent and Stochastic Gradient Descent, Randomized Low-rank Approximation, Sparse Grids, Hierarchical Matrices and Wavelets.

This course provides an introduction to some relevant computational algorithms from Computational Sciences and Machine Learning. It covers the algorithmic paradigms used to solve these problems as well as their practical applications. The course emphasizes the relationship between algorithms and programming, and introduces performance measures for quality, cost and analysis techniques for these problems. The course primarily targets students from the Master double degree programme from FAU Erlangen on Computational Engineering and USI on Computational Science as well as students from the EUMaster4HPC program. In particular, it will be offered in a hybrid (online/offline) format.

In presence

The students select one of the possible computational algorithms, summarize it in class (45-90 min, and if applicable include a software implementation) and provide a written report.

100% of the grade is determined by a mandatory graded project presentation and report.