Automatic Generation and Analysis of Algorithms --- 2009

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 on automation.
In this course "automation" means that a computer makes decisions and performs operations much like a human would do. This is in constrast to the scenario in which automation means that a computer is used to test a very large number of cases.
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 will study the generation methodology and we will explore the following topics: generation of parallel algorithms for multi-core processors, cost analysis, error analysis.



• Summer semester 2009.


• CAMPUS #: 09ss-24886


• First meeting: Thursday, April 16th - 17.15 in Wullnerstrasse.
  Lectures begin: Thursday, April 23rd - 10.30am.


• Lectures:
  Thursdays, 10.00-11.30, 2356|5055 (Ahornstrasse 55)
  Thursdays, 17.15-18.45, 1810|013 (Wullnerstrasse 5 u.7)


• Office hours:
  Tuesdays, 11am-1pm, AICES R432 (Rogowski Building - Schinkelstrasse 2)


• Lectures:
  
  
  • Preliminaries: Lectures 1 & 2.
  
  
  • Lectures 3 & 4: Matrix partitionings; intro to Mathematica pt.1.
    Presentations: Code generation, ATLAS.
  
  
  • Lectures 5 & 6: Semantics of Expressions and Commands.
    
  
  
  • Lectures 7 & 8: Fundamental Theorem of Invariance.
    Presentations: Theorem provers, ACL2.
  
  
  • Lectures 9 & 10: Partitioned Matrix Expression.
    
  
  
  • Lectures 12 & 13: Algorithm Generation.
    
  
  
  • Lectures 14 & 15: From PMEs to high-performance.
    Presentation: Overview of Spiral.
  
  
  • Lectures 16 & 17: Floating point arithmetic and error analysis.
    Presentation: Spiral: parallelization and vectorization.
  
  
  • Lectures 18 & 19: Modular and systematic error analysis.
    Presentation: Overview of FFTW.
  
  
  • Lectures 20 & 21: Stability analisys: TRSV, TRSM, LU, Blocked LU.
    Presentation: Performance of FFTW.
  
  
  • Lecture 22: Cost analysis: projects.
    Lecture 23: How to give a presentation.