CS 560 HW4: Moving on with Alpha


The purpose of this exercise is for you to (i) continue developing Alpha programs, (ii) reinforce the ideas that the volume of polyhedra correspond to the asymptotic complexity, (this time to study the effects of constant factors), (iii) start getting familiar with the powerful static analysis that AlphaZ does (it essentially guarantees that your program will never throw an out-of-bound exception). You will also sharpen your mathematical reasoning skills to develop/derive algorithms, and start understanding what it means to manipulate polyhedra and affine functions.

Problem 1

If you haven't done so yet, work your way through the LUD Tutorial off the AlphaZ wiki. When you encounter the "teaching moment" please email Sanjay with the symptom, and/or how you fixed the problem.

Part 2: Please be ready to discuss this in the next class. When you fixed the problem, did you modify only one of the reductions or both of them. Why/why not?

Problem 2

Part 1 Start with a simple one-liner program for square matrix multiplication that returns C=AB. Modify it (simply change the domains of the declarations of the input variables) so that it now handles the case when A is lower triangular, and B is upper triangular. Generate the C code and empirically measure the complexity of the program. Deduce and report a formula for the complexity (the constant factor is important). Compare this complexity with that of the original program for full matric multiplication.

Part 2: Modify the program once again, so that this time A is upper triangular and B is lower triangular. Again, empirically measure the execution times and deduce the complexity of the generated program, and compare it with the previous two programs.

Problem 3

You are given a square, upper triangular matrix, U.

Part 1:Using mathematical reasoning as in the foundation notes and in class, systematically derive the equational program to invert the matrix [Hint: the inverse is known to also be upper triangular]. This is a paper an pencil exercise, and you will need to come up with a proof. It may be helpful if you show write the equations for the different regions of the identity matrix (on and off-diagonal) and simplify them like in the above examples.

Part 2: Next, write the Alphabets program for this, use AlphaZ to generate the corresponding C program, and validate it. You will turn in only a tarball of your code including the generated files (using the same structure as in AlphaZ (a set of directories for the different Alpha programs, and one (under test-out) for the generated (and modified) C code. Separately, you will also turn in a pdf report documenting your experiments and results.

Last updated February 2013