Robust Numerical Algorithms

Garant předmětu:

Pavel Váchal

Lecturer:

Pavel Váchal

Tutor:

Pavel Váchal

Supervisor:

Department of Physical Electronics

Synopsis:

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.

Requirements:

Mandatory:

- No particular subject needed for qualification

Recommended:

- Practical knowledge of at least one suitable programming language (C, Fortran, Pascal, Matlab, etc.)

- Knowledge of basics of linear algebra (1st term level)

Syllabus of lectures:

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)

Syllabus of tutorials:

- 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.

Study Objective:

Knowledge:

- selected classical algorithms of numerical mathematics, associated difficulties and pitfalls and their possible solutions

Skills:

- basic techniques and sense for implementation of accurate and stable algorithms which do reliably work in real numerical computations

- solution of a given numerical problem as a whole, from the design of a suitable method all the way to practical implementation

Study materials:

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)

Note:

Time-table for winter semester 2023/2024:

Time-table is not available yet

Time-table for summer semester 2023/2024:

Time-table is not available yet

The course is a part of the following study plans:

• Fyzikální elektronika - Počítačová fyzika (PS)