Aart Bik's PhD Research

MT1: A Sparse Compiler

The Fortran compiler MT1 is a sparse compiler, i.e. a special kind of source-to-source restructuring compiler that can automatically transform a dense program (in which all operations on matrices are implemented using two-dimensional arrays) into a semantically equivalent sparse program (operating on more complicated sparse data structures), thereby reducing storage requirements and computational time of the original application. The methodology used by this compiler is described in detail in Aart Bik's PhD thesis.

• Compiler Support for Sparse Matrix Computations. ISBN 90-9009442-3, NUGI 855, Leiden University, 1996.
• PDF download
• Kindle Edition on Amazon

This PhD thesis, supervised by prof. dr. H.A.G. Wijshoff, received the C.J. Kok Award (outstanding thesis award) from the Leiden University. Below, the compiler is made available without fee for education, research, and non-profit purposes.

• mt1linux.tar.gz (Linux version, 293KB)

• LICENSE.TXT (license)
• manual.ps.gz (reference manual)
• library.f (runtime support)

PhD Thesis Errata

• page 73: In reference [235], the 'p' is missing before 30--40.
• page 87: In figure 4.14, a bold-face line between 2 and 3 is missing, while there should not be space in between 7 and 8.
• page 100: ... as actual arguments IS replaced ...
• page 106: In the 8th line from below, the '.' should be a ','.
• page 137: The call 'stack()' should be 'push()'.
• page 142: O(N log N) should be O(\tau log N).
• page 145: Only in this manner, the the .... => 'the the' should be 'the'.
• page 148--161: The reshaping method can be simply improved in case scalar-wise access patterns results in a d-nested loop (with d>2) by recursively applying the reshaping method to the (d-1)-nested loop for all occurrences with scalar-wise access patterns.
• page 155: extended completion METHOD is used.
• page 160: In figure 7.3, the second I_2-axis should be thick.
• page 191: Keyword PROCEDURE should be SUBROUTINE.
• page 195: 'on hand hand' => 'on one hand'.
• page 196: Starting at the code fragment 'IF (.NOT. SWT(...', all subsequent occurrences of e' must be replaced by f' (since the f-tag denotes the index information).
• page 196: may be omitted for a right-hand side occurrence ... should be ... LEFT-hand side ...
• page 199: Second S_1 in IF-statement should be S_2.
• page 202: ... for initializing general SPARSE row-wise storage ...
• page 211: ... of general sparse row-wise OR static dense ...
• page 218: In the first program fragment, all occurrences of SP_20 should be SAP_20.
• page 223: In Sparse Back 'IF ((I+1...' should be 'IF (I+1...'.
• page 228: VAL_G should be VAL_W.
• page 240: TMP__ should be TEMP__.
• page 241: All occurrences of SP_10 and SWT_10 should be SAP_20 and SWT_20.
• page 242: All occurrences of X and Y should be replaced by B (vectors are computed in place).
• page 277/278: Dr. Duff does not work at the Leiden University, as incorrectly stated in the references [74] and [81]. I apologize for this cut-and-paste error.
• There are (obvious) typos in references [74,81,87,88,97,123,160,192,208,220].