Designing Systolic Architecture For Symmetrizing Hessenberg Matrices

Abstract:  In this paper, we describe a systematic method for mapping the problem of symmetrizing Hessenberg matrices onto systolic architectures. The starting point of our method is a graphical abstraction of the system of linear recurrence equations that specifies the problem. Using a procedure called cubization, we transform the dependency graph of the problem into a graph we term the Modified Dependency Graph. Using the modified dependency graph, we design systolic programs on a very general architecture referred to as a basic systolic architecture. Next, we map the basic systolic architecture onto a given systolic architecture using a set of semantics-preserving transformations and hence, the correctness of the solution comes for free. Finally, we compare the architectures for symmetrizing Hessenberg matrices obtained by our method with those proposed previously. 1 Introduction The aim of this paper is to describe a systematic approach for mapping the problem of symmetrizing Hessenberg matr...