The critical bottlenecks in the implementation of the conjugate gradient algorithm on distributed memory computers are the communication requirements of the sparse matrix-vector multiply and of the vector recurrences. The data distribution and communication patterns of five general implementations whose realizations demonstrate that the cost of communication can be overcome to a much larger extent than is often assumed are described. The results also apply to more general settings for matrix-vector products, both sparse and dense.

This paper describes an extension to the set of Basic Linear Algebra Subprograms. The extension is targeted at sparse vector operations, with the goal of providing efficient, but portable, implementations of algorithms for high-performance computers.

This paper desribes a model implementation and test software for the Sparse Basic Linear Algebra Subprograms (Sparse BLAS). The Sparse BLAS perform vector operations common in sparse linear algebra, with the goal of providing efficient, but portable, implementations of algorithms for high performance computers. The model implementation provides a portable set of FORTRAN 77 Sparse BLAS for the use on machines where specially tuned implementations do not exist or are not required. The test software is designed to verify that tuned implementations meet the specifications of the Sparse BLAS and that implementations are correctly installed.

We describe the Harwell-Boeing sparse matrix collection, a set of standard test matrices for sparse matrix problems. Our test set comprises problems in linear systems, least squares, and eigenvalue calculations from a wide variety of scientific and engineering disciplines. The problems range from small matrices, used as counter-examples to hypotheses in sparse matrix research, to large test cases arising in large-scale computation. We offer the collection to other researchers as a standard benchmark for comparative studies of algorithms. The procedures for obtaining and using the test collection are discussed. We also describe the guidelines for contributing further test problems to the collection.

Two effective reordering algorithms for sparse linear systems are ACM Algorithm 508, an implementation of the Glbbs-Poole-Stockmeyer method to reduce matrix bandwidth, and ACM Algorithm 509, an Implementation of the Gibbs-King method to reduce the profile of a matrix.Reduction of matrix profile is more often reqmred than bandwidth reduction, but Algorithm 509 is substantially slower than 508.Consequently, the Glbbs-Poole-Stockmeyer algorithm has been recommended and used m contexts where the better profile reduction of the Gibbs-King algorithm is more appropriate A new FORTRAN implementation of these algorithms, ACM Algorithm 582, which is portable, faster, more reliable, and which uses less storage, is described.In addition, certain unnecessary restrictions on the problem size present in Algorithm 508 and 509 are removed.The new implementation of the Gibbs-King method is much faster than Algorithm 509, generally slightly faster than Algorithm 508, and nearly as fast as the new implementation of the Gibbs-Poole-Stockmeyer method Categories and Subject Descriptors G.1.

Given the structure of a symmetric or structurally s y m m e t r i c sparse matrix, G P S K C A a t t e m p t s to find a synlnaetric reordering of the matrix that produces a smaller bandwidth or profile.References [1], [4], [5], and [6] explain in detail the algorithms realized by G P S K C A .This algorithm provides the same m a t h e m a t i c a l capabilities as provided by R E D U C E , Algorithms 508, and 509, but requires less m e m o r y and time and removes some implicit restrictions on the matrices t h a t can be reordered.A description of the differences in the implementation and their effects is given in [7]; G P S K C A and R E D U C E produce the same bandwidth and profile on all problems for which R E D U C E executes successfully.T h e package of subroutines is evoked by the F O R T R A N s t a t e m e n t CALL GPSKCA (N, NZ, CONNEC, RSTART, DEGREE, OPTPRO, PERMUT, WORK, WRKLEN, ERROR, SPACE)where the p a r a m e t e r s are described in the listing given here.T h e subroutines a t t e m p t ' t o find a symmetric (row and column) p e r m u t a t i o n t h a t reduces the bandwidth or profile of the reordered matrix.W h e t h e r to emphasize profile reduction or bandwidth reduction is determined by the logical p a r a m e t e r O P T -PRO.A c o m m o n use for this algorithm will be prior to the solution of sparse linear algebraic equations or algebraic eigenvalue problems of moderately large size.

No abstract available.

article Free Access Share on Certification of “Algorithm 349: Polygamma Functions with Arbitrary Precision” Author: John Gregg Lewis Computer Science Department, Stanford University, Stanford, CA Computer Science Department, Stanford University, Stanford, CAView Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 1Issue 4Dec. 1975 pp 380–382https://doi.org/10.1145/355656.355664Published:01 December 1975Publication History 1citation268DownloadsMetricsTotal Citations1Total Downloads268Last 12 Months5Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF