Some Complexity Results for Matrix Computations on Parallel Processors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Some Complexity Results for Matrix Computations on Parallel Processors

Full text

Pdf (292 KB)

Source

Journal of the ACM (JACM) archive
Volume 25 , Issue 1 (January 1978) table of contents

Pages: 112 - 115

Year of Publication: 1978

ISSN:0004-5411

Author

W. Morven Gentleman

University of Waterloo, Waterloo, Ontario, Canada N2L 3G1

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 38, Citation Count: 19

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/322047.322057 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	Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974 [doi>10.1145/321812.321815]
	2	CSANKY, L Fast parallel matrix reversion algorithms Conf. Rec 16th Annual IEEE Symp. on Foundations of Comptr Scl, 1975, pp 11-12
	3	KtrcK, D J, AND SAMEH, A H Parallel computations of elgenvalues of real matrices Information Processing 71, North-Holland Pub Co , Amsterdam, 1972, pp 1266-1272.
	4	MIRANKER, W L A survey of parallehsm in numerical analysis SIAM Rev 13, 4 (Oct 1971), 524- 547
	5	Marshall C. Pease, Matrix Inversion Using Parallel Processing, Journal of the ACM (JACM), v.14 n.4, p.757-764, Oct. 1967 [doi>10.1145/321420.321434]
	6	POOLE, W G Jl~, AND VOIGT, R G B~bhography 35 Numerical algorithms for parallel and vector computers An annotated blbhography Comptng Rev 15, 10 (Oct 1974), 379-388
	7	Harold S. Stone, Parallel Tridiagonal Equation Solvers, ACM Transactions on Mathematical Software (TOMS), v.1 n.4, p.289-307, Dec. 1975 [doi>10.1145/355656.355657]
	8	STONE, H S Parallel processing with the perfect shuffle IEEE Trans on Comptrs. C-20, 2 (Feb 1971), 153-161
	9	STgASSEN, V Gausslan ehmlnatlon is not optimal Num Math 13, 4 (1969), 354-356.
	10	S. Winograd, On the Parallel Evaluation of Certain Arithmetic Expressions, Journal of the ACM (JACM), v.22 n.4, p.477-492, Oct. 1975 [doi>10.1145/321906.321911]

CITED BY 19

	S. Lennart Johnsson, Solving narrow banded systems on ensemble architectures, ACM Transactions on Mathematical Software (TOMS), v.11 n.3, p.271-288, Sept. 1985
	Harold Abelson, Lower Bounds on Information Transfer in Distributed Computations, Journal of the ACM (JACM), v.27 n.2, p.384-392, April 1980
	P. J. Varman , I. V. Ramakrishnan, Optimal Matrix Multiplication on Fault-Tolerant VLSI Arrays, IEEE Transactions on Computers, v.38 n.2, p.278-283, February 1989
	D. H. Bailey , H. R. P. Gerguson, A Strassen-Newton algorithm for high-speed parallelizable matrix inversion, Proceedings of the 1988 ACM/IEEE conference on Supercomputing, p.419-424, November 12-17, 1988, Orlando, Florida, United States
	A. Bar-Noy , D. Peleg, Square meshes are not always optimal, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.138-147, June 18-21, 1989, Santa Fe, New Mexico, United States
	Amotz Bar-Noy , David Peleg, Square Meshes are Not Always Optimal, IEEE Transactions on Computers, v.40 n.2, p.196-204, February 1991
	Franco P. Preparata , Jean Vuillemin, The cube-connected cycles: a versatile network for parallel computation, Communications of the ACM, v.24 n.5, p.300-309, May 1981
	Robert H. Kuhn, Efficient mapping of algorithms to single-stage interconnections, Proceedings of the 7th annual symposium on Computer Architecture, p.182-189, May 06-08, 1980, La Baule, United States
	David Nassimi , Sartaj Sahni, An optimal routing algorithm for mesh-connected Parallel computers, Journal of the ACM (JACM), v.27 n.1, p.6-29, Jan. 1980
	Rajani M. Kant , Takayuki Kimura, Decentralized parallel algorithms for matrix computation, Proceedings of the 5th annual symposium on Computer architecture, p.96-100, April 03-05, 1978
	Robert A. Wagner, The Boolean Vector Machine [BVM], ACM SIGARCH Computer Architecture News, v.11 n.3, p.59-66, June 1983
	Allan Gottlieb , Clyde P. Kruskal, Complexity Results for Permuting Data and Other Computations on Parallel Processors, Journal of the ACM (JACM), v.31 n.2, p.193-209, April 1984
	Debasish Das , Mallika De , Bhabani P. Sinha, A New Network Topology with Multiple Meshes, IEEE Transactions on Computers, v.48 n.5, p.536-551, May 1999
	Rita Loogen , Yolanda Ortega , Ricardo Peña , Steffen Priebe , Fernando Rubio, Parallelism abstractions in eden, Patterns and skeletons for parallel and distributed computing, Springer-Verlag, London, 2003
	V. K. Prasanna Kumar , C. S. Raghavendra, Array processor with multiple broadcasting, ACM SIGARCH Computer Architecture News, v.13 n.3, p.2-10, June 1985
	Alberto Moreira , Bryant W. York, Matrix inversion in O(log n) on a scan-enhanced reconfigurable mesh computer, Proceedings of the 1996 ACM 24th annual conference on Computer science, p.67-75, February 15-18, 1996, Philadelphia, Pennsylvania, United States
	Ricardo Peña , Fernando Rubio, Parallel functional programming at two levels of abstraction, Proceedings of the 3rd ACM SIGPLAN international conference on Principles and practice of declarative programming, p.187-198, September 05-07, 2001, Florence, Italy
	Norman Scaife , Susumi Horiguchi , Greg Michaelson , Paul Bristow, A parallel SML compiler based on algorithmic skeletons, Journal of Functional Programming, v.15 n.4, p.615-650, July 2005
	Michael J. Quinn , Narsingh Deo, Parallel graph algorithms, ACM Computing Surveys (CSUR), v.16 n.3, p.319-348, Sept. 1984