Two Fast Algorithms for Sparse Matrices: Multiplication and Permuted Transposition

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Two Fast Algorithms for Sparse Matrices: Multiplication and Permuted Transposition

Full text

Pdf (1.27 MB)

Source

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

Pages: 250 - 269

Year of Publication: 1978

ISSN:0098-3500

Author

Fred G. Gustavson

Mathematical Sciences Department, IBM T.J. Watson Research Center, P.O. Box, 218, Yorktown Heights, NY

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 40, Downloads (12 Months): 308, Citation Count: 8

Additional Information:

references cited by index terms 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/355791.355796 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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	CURTIS, A., AND REID, J The solution of large sparse unsymmetric systems of linear equations J. Inst. Math Appl 8 (1971), 344-353.
	3	GEORGE, J.A. On block ehmmatlon for sparse linear systems. SIAM J. Numer. Anal. 11 (1974), 585-6O3.
	4	GUSTAVSON, F G. Finding the block lower triangular form of a sparse matrix. In Sparse Matrix Computattons, J Bunch and D. Rose, Eds., Academic Press, New York, 1976, pp. 275-289
	5	GUSTAVSON, F G Some basic techmques for solving sparse systems of linear equations. In Sparse Matrtces and Thew Apphcattons, D. Rose and R. Wdloughby, Eds., Plenum Press, New York, Jan 1973, pp. 67-76.
	6	GUSTAVSON, F.G. Permuting matrices stored m sparse format. Disclosure No. 8-72-001, IBM Tech. D~sclosure Bull. 16, 1 (June 1973), 357-359
	7	F. Gustavson , D. Y. Y. Yun, Arithmetic complexity of unordered sparse polynomials, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.149-153, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806333]
	8	GUSTAVSON, F G. Some algorithms for sparse Gaussian elimination. To appear.
	9	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	10	LORIN, H Sorting and Sort Systems. Addison-Wesley, Reading, Mass., 1975, p. 152.
	11	John Michael McNamee, Algorithm 408: a sparse matrix package (part I) [F4], Communications of the ACM, v.14 n.4, p.265-273, April 1971 [doi>10.1145/362575.362584]
	12	REID, J. Sparse matrices. Proc. IMA Conf on State-of-the-Art m Numer. Anal., York, April 1976, p6.
	13	ROSE, D., AND TARJAN, R. Algorithmic aspects of vertex elimination on directed graphs. To appear in SIAM J. Computng.
	14	Andrew Harry Sherman, On the efficient solution of sparse systems of linear and nonlinear equations., 1975
	15	STRASSEN, V. Gausslan ehmlnatlon is not optimal. Numer Math. 13 (1964), 354-356.
	16	TINNEY, W., AND WALKER, J. Dtrect solutions of sparse network equations optimally ordered triangular factonzation Proc. IEEE 55, 11 (Nov. 1967), 1801-1809
	17	WILLOUGHBY, R.A. Sparse matrix algorithms and their relation to problem classes and computer architecture. In Large Sparse Sets of L~near Equations, J. Reid, Ed., Academic Press, London and New York, pp. 255-277.

CITED BY 8

	R. C. Agarwal , F. G. Gustavson , M. Zubair, A high performance algorithm using pre-processing for the sparse matrix-vector multiplication, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.32-41, November 16-20, 1992, Minneapolis, Minnesota, United States
	Nicola Santoro, Chain mulitplication of matrices of approximately or exactly the same size, Communications of the ACM, v.27 n.2, p.152-156, Feb. 1984
	J. M. McNamee, A Sparse Matrix Package—Part II: Special Cases, ACM Transactions on Mathematical Software (TOMS), v.9 n.3, p.340-343, Sept. 1983
	Fred G. Gustavson, Remark on algorithm 408: a sparse matrix package (part 1) [F4], ACM Transactions on Mathematical Software (TOMS), v.4 n.3, p.295, Sept. 1978
	John P. Coleman, Remark on “Algorithm 49: Spherical Neumann Function”, ACM Transactions on Mathematical Software (TOMS), v.4 n.3, p.295, Sept. 1978
	Timothy A. Davis , John R. Gilbert , Stefan I. Larimore , Esmond G. Ng, A column approximate minimum degree ordering algorithm, ACM Transactions on Mathematical Software (TOMS), v.30 n.3, p.353-376, September 2004
	Raphael Yuster , Uri Zwick, Fast sparse matrix multiplication, ACM Transactions on Algorithms (TALG), v.1 n.1, p.2-13, July 2005
	Aart J. C. Bik , Harry A. G. Wijshoff, Automatic Data Structure Selection and Transformation for Sparse Matrix Computations, IEEE Transactions on Parallel and Distributed Systems, v.7 n.2, p.109-126, February 1996

INDEX TERMS

Primary Classification:
G. Mathematics of Computing

Additional Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.1 Numerical Algorithms and Problems
Subjects: Computations on matrices

G. Mathematics of Computing
G.2 DISCRETE MATHEMATICS
G.2.1 Combinatorics
Subjects: Permutations and combinations

General Terms:
Algorithms, Design, Theory

Collaborative Colleagues:

Fred G. Gustavson: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player