frederic@degas.cs.unc.edu (Robin Fredericksen) (10/05/90)
Does anyone know of a sparse matrix (Gauss Elim., etc) algorithm for a SIMD machine? (if possible, specifically for a Maspar MP1?) I am interested in references, actual code, or whatever I can get my hands on. The matrices that I am interested in are usually VERY sparse, and pretty close to tridiagonal. (A set of ?loosely? coupled equations, but possibly {tens of?} thousands of them...) Eric ------------------------------------------------------------------------------- Eric Fredericksen : Insert amazingly funny or enlightening quote frederic@cs.unc.edu : in this space here. I don't need a disclaimer, I'm a graduate student so no one cares what I say...
weeks@decwrl.dec.com (Dennis Weeks) (10/06/90)
John R. Gilbert and Hjalmtyr Hafsteinsson, "Parallel Solution of Sparse Linear Systems" SWAT 88 Proceedings (1st Scandinavian Workshop on Algorithm Theory, Halmstad, Sweden, July 5-8 1988), published as Springer-Verlag's 'Lecture Notes in Computer Science' #318 (pp. 145-153) H. S. Stone, "An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of Equations" Journal of the ACM, 20 (1973) p. 27-??. There is a more general piece by Peter Kogge (he was a student of Harold Stone at Stanford) which has an algorithmic approach that includes tridiagonal solvers as a specific case: P. Kogge, "Parallel Solution of Recurrence Problems" IBM Journal of Research and Development, 1974, pp. 368-??