Languages for Scientific Computing 2: Automation -- 2010

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:

The focus of the second part of Languages for Scientific Computing is:
* symbolic computations
* automatic generation of algorithms and code
* high-performance on multi-core processors.

The course is research oriented.

Mathematica and other languages with symbolic capabilities (Maple, Sage, Matlab) are used to continue comparison between different programming paradigms: functional vs. imperative, discrete vs. numerical vs. symbolic.

We will cover topics such as pattern matching, textual substitution, functions and functionals, algebraic manipulations. The concepts of automation, program correctness and numerical stability are then introduced. 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.

Finally, symbolic technique are used to show how to automatically generate and analyze algorithms and routines. 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! Programs will be evaluated with respect to metrics like performance, size, elegance.

NOTE: The course "Languages for Scientific Computing 1" is NOT a prerequisite.


• Summer semester 2010.


• CAMPUS #: 10ss-24886


• Lectures begin: Thursday, April 22nd - 10.30am.


• Lectures & Exercises:
  Thursdays, 10.30-12.00, Rogowski 115 - AICES seminar room (Schinkelstrasse 2)
  Thursdays, 17.00-18.30, Rogowski 115 - AICES seminar room (Schinkelstrasse 2)


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


• Lectures:
  
  
  • Intro: Symbolic vs. numerical computations.
  
  
  • Intro: Automation.
  
  
  • Preliminaries: Linear algebra by blocks.
  
  
  • Crash course on symbolic & functional programming.
    
  
  
  • Program correctness: semantics of Expressions and Commands.
  
  
  • Assignment: are the following three statements equivalent?
    1. While Exp do Com endw
    2. If Exp then Com; While Exp do Com endw else null fi
    3. If Exp then Com else null fi; While Exp do Com endw
  
  
  • Loop Invariants.
  
  
  • Autotuning.
  
  
  • Partitioned Matrix Expressions and Loop Invariants.
  
  
  • E. Chan: "Runtime data flow graph scheduling of matrix computations"
  
  
  • Automation of PME generation.
  
  
  • Generation: from loop-invariant to algorithm.
  
  
  • Material: [Dissertation]
    

    Formal correctness	Chapter 2, pagg.22-30
    Worksheet	Chapter 2, pagg.31-35
    Example	Chapter 2, pagg.35-45
    PME & Loop-Invariants	Chapter 2, pagg.45-55
    Automation	Chapter 3, pagg.59-83