Efficient sparse matrix factorization on high performance workstations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient sparse matrix factorization on high performance workstations—exploiting the memory hierarchy

Full text

Pdf (1.60 MB)

Source

ACM Transactions on Mathematical Software (TOMS) archive
Volume 17 , Issue 3 (September 1991) table of contents

Pages: 313 - 334

Year of Publication: 1991

ISSN:0098-3500

Authors

Edward Rothberg	Stanford Univ., Stanford, CA
Anoop Gupta	Stanford Univ., Stanford, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 45, Citation Count: 10

Additional Information:

references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/114697.116809 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	ASHCRAFT, C. C., GRIMES, R. G., LEWIS, J. G., PEYTON, B. W., ANY SrMON, H. D. Recent progress in sparse matrix methods for large linear systems. Int. J. Supercomput. Appl. 1, 4 (Winter 1987), 10-30.
	2	Jack J. Dongarra , Stanley C. Eisenstat, Squeezing the most out of an algorithm in CRAY FORTRAN, ACM Transactions on Mathematical Software (TOMS), v.10 n.3, p.219-230, Sept. 1984 [doi>10.1145/1271.319413]
	3	I. S. Duff , Roger G. Grimes , John G. Lewis, Sparse matrix test problems, ACM Transactions on Mathematical Software (TOMS), v.15 n.1, p.1-14, March 1989 [doi>10.1145/62038.62043]
	4	I. S. Duff , J. K. Reid, The Multifrontal Solution of Indefinite Sparse Symmetric Linear, ACM Transactions on Mathematical Software (TOMS), v.9 n.3, p.302-325, Sept. 1983 [doi>10.1145/356044.356047]
	5	EISENSTAT, S. C., SCttULTZ, M., AND SHERMAN, A. Algorithms and data structures for sparse symmetric Gaussian elimination. SIAM J. Sc~. Stat. Comput. 2, 2 (June 1981), 225-237.
	6	GALLIVAN, K., JALBY, W., MEIER, U , AND SAMEH, A. The impact of hierarchical memory systems on linear algebra algorithm design. CSRD Tech. Rep. 625, University of Illinois, 1987.
	7	Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
	8	GEORGE, A., LIU, J., AND NG, E. User's guide for SPARSPAK: Waterloo sparse linear equations package. Res. Rep. CS-78-30, Dept. of Computer Science, Univ. of Waterloo, 1980.
	9	Joseph W. Liu, A compact row storage scheme for Cholesky factors using elimination trees, ACM Transactions on Mathematical Software (TOMS), v.12 n.2, p.127-148, June 1986 [doi>10.1145/6497.6499]
	10	Joseph W. H. Liu, Modification of the minimum-degree algorithm by multiple elimination, ACM Transactions on Mathematical Software (TOMS), v.11 n.2, p.141-153, June 1985 [doi>10.1145/214392.214398]
	11	Joseph W. H. Liu, A note on sparse factorization in a paging environment, SIAM Journal on Scientific and Statistical Computing, v.8 n.6, p.1085-1088, November 1, 1987 [doi>10.1137/0908087]
	12	SIMON, H. D., Vu, P, AND YANG, C. Performance of a supernodal general sparse solver on the CRAY Y-MP: 1.68 GFLOPS with autotasking. Tech. Rep. SCA-TR-117, Boeing Computer Services, 1989.

CITED BY 10

	Martin C. Rinard , Monica S. Lam, Semantic foundations of Jade, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.105-118, January 19-22, 1992, Albuquerque, New Mexico, United States
	Edward Rothberg , Anoop Gupta, Techniques for improving the performance of sparse matrix factorization on multiprocessor workstations, Proceedings of the 1990 conference on Supercomputing, p.232-241, October 1990, New York, New York, United States
	Mark W. Goudreau , Kevin Lang , Girija Narlikar , Satish B. Rao, BOS is boss: a case for bulk-synchronous object systems, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.115-125, June 27-30, 1999, Saint Malo, France
	Monica S. Lam , Martin C. Rinard, Coarse-grain parallel programming in Jade, ACM SIGPLAN Notices, v.26 n.7, p.94-105, July 1991
	Vladimir Rotkin , Sivan Toledo, The design and implementation of a new out-of-core sparse cholesky factorization method, ACM Transactions on Mathematical Software (TOMS), v.30 n.1, p.19-46, March 2004
	Timothy A. Davis, Algorithm 849: A concise sparse Cholesky factorization package, ACM Transactions on Mathematical Software (TOMS), v.31 n.4, p.587-591, December 2005
	Omer Meshar , Dror Irony , Sivan Toledo, An out-of-core sparse symmetric-indefinite factorization method, ACM Transactions on Mathematical Software (TOMS), v.32 n.3, p.445-471, September 2006
	Haim Avron , Gil Shklarski , Sivan Toledo, Parallel unsymmetric-pattern multifrontal sparse LU with column preordering, ACM Transactions on Mathematical Software (TOMS), v.34 n.2, p.1-31, March 2008
	Yanqing Chen , Timothy A. Davis , William W. Hager , Sivasankaran Rajamanickam, Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate, ACM Transactions on Mathematical Software (TOMS), v.35 n.3, p.1-14, October 2008
	Timothy A. Davis , William W. Hager, Dynamic Supernodes in Sparse Cholesky Update/Downdate and Triangular Solves, ACM Transactions on Mathematical Software (TOMS), v.35 n.4, p.1-23, February 2009

INDEX TERMS

Primary Classification:
B. Hardware
B.3 MEMORY STRUCTURES
B.3.2 Design Styles
Subjects: Cache memories

Additional Classification:
C. Computer Systems Organization
C.5 COMPUTER SYSTEM IMPLEMENTATION
C.5.3 Microcomputers
Subjects: Workstations

G. Mathematics of Computing
G.1 NUMERICAL ANALYSIS
G.1.3 Numerical Linear Algebra
Subjects: Sparse, structured, and very large systems (direct and iterative methods)

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
Cholesky factorization, hierarchical memory systems, sparse matrices

REVIEW

"Andrew Donald Booth : Reviewer"

The problem of solving sparse matrix problems on RISC workstations is considered in this interesting paper. The authors point out that recent technological advances make the use of desktop devices, if not timewise competitive with Cray-type su more...

Collaborative Colleagues:

Edward Rothberg: colleagues

Anoop Gupta: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player