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 researchoriented; 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 Loopinvariants. 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 #: 12ss38045

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, 11am1pm, 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.2230

Semantics of expressions and programs.
Loop Invariants.

Partitioned Matrix Expression.
[PDF]
[Dissertation]:
PME & LoopInvariants, Chapter 2, pagg.4555

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]