Functional Implementations of the Jacobi Eigensolver

Issue title: High-Performance Functional Computing

Article type: Research Article

Authors: BÖHM, A. P. W. | HIROMOTO, R. E.

Affiliations: Computer Science Department, Colorado State University, Fort Collins, CO 90523; e-mail: bohm@cs.colostate.edu | Division of Mathematics, Computer Science and Statistics, The University of Texas at San Antonio, San Antonio, TX

Abstract: In this article we describe the systematic development of two implementations of the Jacobi eigensolver and give their initial performance results for the MIT/Motorola Monsoon dataflow machine. Our study is carried out using MINT, the MIT Monsoon simulator. The functional semantics with respect to array updates, which cause excessive array copying, have led us to an implementation of a parallel "group rotations" algorithm first described by Sameh. Our version of this algorithm requires O(n^3) operations, whereas Sameh's original version requires O(n^4) operations. The convergence of the group algorithm is briefly treated. We discuss the issues involved in rewriting the algorithm in Sisal, a strict, purely functional language without explicit l-structures.

Journal: Scientific Programming, vol. 5, no. 2, pp. 111-120, 1996