Bit-level Jacobi-like algorithms for eigenvalue and singular value decompositions
David E. Schimmel · 1991
In recent years, there has been considerable interest in methods for computing eigenvalues and singular values of large matrices$\sp1$. Because these computations rapidly become intractable (due to their $O(n\sp3)$ complexity, assuming for now that the matrices are $n \times n),$ much attention has focused on parallel means of solution. The main contribution of this thesis, will be the introduction of a new class of bit-level algorithms for the solution of these problems which perform up to five times faster than previous algorithms on a suitable parallel architecture. Bit-level means that the algorithms operate on subfields of a floating point number; The basic unit is no longer the floating point number itself. We will begin with the discussion of methodology for meaningful comparison of different algorithms, with respect to both speed and accuracy, and which also takes into account the interaction between algorithm and architecture. Next, we will present a generalization of the notion of C scORDIC$\sp2$ arithmetic, which we call p-C scORDIC, which will form the underpinning for some of our subsequent developments. This will lead to the exposition of new algorithmic techniques applicable to singular value and eigenvalue decompositions, which have significantly reduced communication bandwidth requirements as well as improved load balance on some parallel computers. We will make explicit the conditions under which these techniques will prove to be useful. We will derive new algorithms for various cases of these decompositions, and prove some convergence properties of them. We are also concerned with the mapping of these techniques on to specific machines. We consider two architectural scenarios. After studying the specific details of the architecture, we describe implementations on the massively parallel Connection Machine (CM). Our results indicate that on the CM, our algorithm is up to several times faster than the best traditional algorithm of this type. Then we discuss the design of a special purpose linear array of processors, for very efficient computation of singular values and vectors of a complex matrix. ftn$\sp1$By large, we mean of dimension greater than, say 250. $\sp2$The arithmetic used by the COordinate Rotation DIgital Computer introduced by J. E. Volder.