Code: 12RNA Robust Numerical Algorithms
Lecturer: doc. Ing. Pavel Váchal Ph.D. Weekly load: 1+1 Completion: A
Department: 14112 Credits: 2 Semester: W
Description:
This course aims to equip the students with basic knowledge, skills and sense for implementation of accurate and stable algorithms which do reliably work in real numerical computations. The theory is complemented by practical exercises and examples of applications in complex simulation codes and the students are given a possibility to participate in ongoing research projects.
Basic theory of finite precision computation, types of errors, their accumulation and interactions, stability of computations and increasing of the precision. Suitable techniques for summation, processing of polynomials and matrices. Computational geometry algorithms: intersections of lines, segments and polygons, triangulation and partitioning of polygons, Voronoi diagrams and Delaunay triangulation, plane arrangement, convex hulls, robot motion planning. Unconstrained and constrained linear and nonlinear numerical optimization.
Contents:
1. Finite precision computation
(types, accumulation and interactions of errors, increasing of precision, stability, myths and superstitions, design of a stable algorithm, floating point arithmetic)
2. Basic operations and techniques
(error analysis, summation, polynomials, matrices, stability of linear systems)
3. Intersections of lines, segments and polygons
(algorithms, difficulties; application: conservative remapping, raytracing)
4. Triangulation and polygon partitioning
(theory and algorithms of triangulation, area computation, convex polygon partitioning; application: mesh generation)
5. Voronoi diagrams, Delaunay triangulation, plane arrangement
(definitions, properties, algorithms; application: mesh adaptation - rezoning)
6. 2D and 3D Convex hull
(naive algorithms, Quickhull, divide and conquer,...)
7. Numerical optimization
(simple 1D methods (linesearch), directional search in multiple dimensions, conjugate gradients, simplex method, constrained quadratic programming; application: mesh quality optimization)

Seminar contents:
- The students will themselves implement (code) methods and problems discussed in the lectures and thus will discover and resolve particular issues on their own
- Embedded are examples of applications in selected real simulation codes being under development at Dept. of Physical Electronics (KFE) and in collaboration with other institutions
- If applicable, students will present and consult numerical computations contained in their current research projects (Bachelor or Masters)
- Students will be given the possibility to participate in ongoing research projects.
Recommended literature:
Key references:
[1] N.J. Higham: Accuracy and Stability in Numerical Algorithms
[2] J. O'Rourke: Computational Geometry in C

Recommended references:
[3] W.H. Press et al.: Numerical Recipes. The Art of Scientific Computing
[4] P.J. Schneider, D.H. Eberly: Geometric Tools for Computer Graphics
[5] F.P. Preparata, M.I. Shamos: Computational Geometry. An Introduction
[6] M. de Berg et al.: Computational Geometry. Algorithms and Applications
[7] O. Hjelle, M. Daehlen: Triangulations and Applications
[8] J. Nocedal, S.J. Wright: Numerical Optimization
[9] J.F. Bonnans et al: Numerical Optimization. Theoretical and Practical Aspects
[10] www.geometrictools.com
[11] Wikipedia, MathWorld, ...

Equipment:
- Computer laboratory with UNIX/Linux OS and suitable programming languages (C, Fortran, Matlab, resp. Pascal)
Keywords:
Numerical algorithms, precision, accuracy, stability, computational geometry, numerical optimization.

Abbreviations used:

Semester:

Mode of completion of the course:

Weekly load (hours per week):