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]