Automatic Generation and Analysis of Algorithms -- 2012
Basic knowledge of numerical linear algebra.
Principles of algorithms and programming.
Familiarity with at least one of the following languages: Mathematica,
Maple, Matlab, C.
This course is research-oriented; it covers novel techniques in
computer automation. In this course "automation" means that a
computer makes decisions and performs operations much like a human
would do. The objective is a software system that creates
algorithms without human intervention.
Starting from a problem expressed in symbolic (algebraic) form
(example: Lx = b), it is possible to automatically generate algorithms
and code to solve the problem with only minimal human intevention. Not
only are the algorithms generated automatically, but they are provably
We introduce the concepts of automation,
autotuning and formal correctness of programs.
We first review a variety of
methodologies to automatically generate algorithms in different
We then restrict ourselves to linear algebra and introduce
two different approaches towards automation.
The first approach, based on
program correctness and pattern matching, relies on Partitioned
Matrix Expressions and Loop-invariants. The second approach, also based on
pattern matching, originates a linear algebra compiler. Such techniques
generate algorithms as well as cost and error analyses.
The course is research oriented, participation is crucial.
Summer semester 2012.
CAMPUS #: 12ss-38045
First meeting: Tuesday, April 3rd - 5pm.
Lectures & Exercises:
Tuesdays, 5 - 6.30pm, Rogowski 115 - AICES seminar room (Schinkelstrasse 2)
Thursdays, 5 - 6.30pm, Rogowski 115 - AICES seminar room (Schinkelstrasse 2)
Tuesdays, 11am-1pm, AICES R432 (Rogowski Building - Schinkelstrasse 2)
Linear algebra objects and properties.
Ambiguities: Inputs vs. outputs.
Mathematica - Part 1.
Patterns. Functions & Replacement Rules.
Mathematica - Part 2.
Depth, Replace, ReplaceAll, ReplaceRepeated.
[Slides] (by Markus Pueschel)
BLAS interface, performance.
Automatic modeling and ranking of algorithms.
Formal correctness vs. numerical stability. Hoare triples.
Formal correctness, Chapter 2, pagg.22-30
Semantics of expressions and programs.
Partitioned Matrix Expression.
PME & Loop-Invariants, Chapter 2, pagg.45-55
From PME to Loop Invariants to Algorithms.
Systematic Analysis of Algorithms.
Floating Point Arithmetic. Backward & Forward Analysis.