High-Performance Exact Computations

English Français

Monday, 2pm -- 5pm
Ensimag B001
UJF > UFR-IM²AG / ENSIMAG > M2 MSIAM > HPEC
Lecturer: Jean-Guillaume Dumas


Credits Prerequisite Contents Planning Evaluation References Attendance certificate

Credits: 3ECTS, 18h

Keywords:

algebraic computations, linear algebra, algorithmic complexity, verified computations, cryptology and codes

Introduction

This course presents theoretical and practical aspects of exact computations with an accent on high-performance modelling.
- How difficult is it to compute a determinant over Z?
- What about optimal complexities in linear algebra?
- Are asymptotic complexities useful in practice?
- How to augment or verify the precision of computations?
We will study a selection of recent algorithmic break-through in the domain as well as their use in the solution of various problems, like analysis of DNA sequences, pattern recognition, coding theory, etc.
The course will have the favor of students interested in algorithmic complexity theory as well as mathematical computations and applications.

Prerequisites

None

Contents

  • Arbitrary precison integer, polynomial and floating point arithmetics.
  • Exact modelizations:
    • Pattern analysis in DNA.
    • Pseudo-random generators and the liryc poetry of troubadours.
    • Algebraic topology (pattern recognition, molecular interactions).
    • Combinatorics (graph isomorphism).
    • Error correcting codes and fault tolerance.
    • Cryptology (breaking RSA and the Discrete Logarithm).
  • Exact Linear Algebra
    • Dense matrices and Sparse/Structured/blackbox matrices
    • Exact direct and iterative methods
    • Liftings and rational reconstruction
    • Adaptive algorithms and international library LinBox
    • Interactive certificates
  • Efficient algorithms
    • Determinant, rank, system solving, minimal and characteristic polynomials, normal forms.
    • Methods of Danilevski, FFLAS, Dixon, Wiedemann, Villard, Krylov, etc.


Planning

PART 1: Arithmetics and complexity PART 2: Linear algebra in a field PART 3: Sparse and Blackbox linear algebra PART 4: Arbitrary precision linear algebra (Z or K[X]) Talks (Monday February 1st, 2016)

Evaluation

The evaluation is by a bibliographic study with a report and an oral presentation (about 15 minutes + questions).
The goal is to study in details a research paper (and potentially a complementary paper). The choice of research paper is free but should be related to the course. Some examples follow:

Bibliography

Some course supports

Related books

Papers

Most of these can be found on line. Use for instance google scholar to find them. Ask me if a library account is needed.