Automatic Generation and Analysis of Algorithms -- 2012
Prerequisites:
Basic knowledge of numerical linear algebra.
Principles of algorithms and programming.
Familiarity with at least one of the following languages: Mathematica,
Maple, Matlab, C.
Overview:
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
correct!
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
fields.
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)
-
Office hours:
Tuesdays, 11am-1pm, AICES R432 (Rogowski Building - Schinkelstrasse 2)
Lectures
-
Linear algebra objects and properties.
Ambiguities: Inputs vs. outputs.
BLAS.
-
Partitionings.
-
Mathematica - Part 1.
Patterns. Functions & Replacement Rules.
Primer:
[Part 1],
[Part 2]
-
Mathematica - Part 2.
Depth, Replace, ReplaceAll, ReplaceRepeated.
Mathematica sessions:
[Notebook 1],
[Notebook 2],
[Notebook 3]
-
Autotuning.
[Slides] (by Markus Pueschel)
-
BLAS interface, performance.
Reference BLAS
BLAS interface
Source
Timer
-
Automatic modeling and ranking of algorithms.
[Slides]
-
Formal correctness vs. numerical stability. Hoare triples.
[Dissertation]:
Formal correctness, Chapter 2, pagg.22-30
-
Semantics of expressions and programs.
Loop Invariants.
-
Partitioned Matrix Expression.
[PDF]
[Dissertation]:
PME & Loop-Invariants, Chapter 2, pagg.45-55
-
From PME to Loop Invariants to Algorithms.
[PDF]
-
Systematic Analysis of Algorithms.
Cost Analysis.
-
Floating Point Arithmetic. Backward & Forward Analysis.
Extended Worksheet.
[PDF]
-
Final Project
[PDF]