Efficient matrix computations through hierarchical type specifications
Timothy Scott Collins · 1996
Matrix computations arise in the implementations of almost all scientific and engineering applications. Due to the physical properties of these problems and the nature of the solution methods, the resulting matrices often have complicated structure. That is, the values in the matrices have some regular pattern in their organization. Although it is well known that structure plays a crucial role in both the representational and computational efficiency of matrix computations, current programming systems offer little direct support for the representation of complicated structured matrices that arise in modern applications. Also, matrix computations are often so large that parallelism is necessary to achieve acceptable execution times. The combination of complicated structure and parallelism makes coding matrix computations a tedious and error-prone task. This dissertation investigates both the formal and pragmatic issues involved in providing powerful language and compiler capabilities for simplifying the task of constructing efficient sequential and parallel implementations for matrix computations. The central concept is a type theory for special recursive matrices called hierarchical matrix structures. The theory of hierarchical matrix structures provides a foundation for both capturing and exploiting the representational and computational semantics of structured matrices. The MaTRiX+$\sp+$ environment is a prototype language and compiler implementation of the hierarchical matrix theory. Evaluation of the system suggests that the specifications of matrix computations in MaTRiX+$\sp+$ are concise. Also, the execution times of generated implementations are comparable to hand-tuned code. Contributions of this work are both formal and practical: the theory of recursive matrices provides a model for describing and exploiting matrix computation semantics; the MaTRiX+$\sp+$ prototype environment supports rapid specification of complicated matrix computations without sacrificing efficiency. In addition, the hierarchical typing methodology presents a metaphor for exposing the deep relationship between the physical problem and its matrix structure.