Supereffective slow-down of parallel computations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Supereffective slow-down of parallel computations

Full text

Pdf (714 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures table of contents

San Diego, California, United States

Pages: 402 - 409

Year of Publication: 1992

ISBN:0-89791-483-X

Authors

Victor Y. Pan
Franco P. Preparata

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 13, Citation Count: 2

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/140901.141926 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.

	AHU	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	Be	Stuart J. Berkowitz, On computing the determinant in small parallel time using a small number of processors, Information Processing Letters, v.18 n.3, p.147-150, March 1984 [doi>10.1016/0020-0190(84)90018-8]
	BP	D. Bini, V. Pan, Numerical and Algebraic Computations with Matrices and Polynomials. Birkhauser, Boston, 1992.
	BPa	D. Bini , V. Pan, Parallel polynomial computations by recursive processes, Proceedings of the international symposium on Symbolic and algebraic computation, p.294, August 20-24, 1990, Tokyo, Japan [doi>10.1145/96877.96963]
	BPb	Dario Bini , Victor Pan, Improved parallel polynomial division, SIAM Journal on Computing, v.22 n.3, p.617-626, June 1993 [doi>10.1137/0222041]
	Br	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]
	Ca	B.A. Cart6, Graphs and Networks, The Claredon Press, Oxford University Press, 1979.
	Ch	Alexander L. Chistov, Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic, Fundamentals of Computation Theory, p.63-69, September 09-13, 1985
	CKL-A	J. Chun , T. Kailath , H. Lev-Ari, Fast parallel algorithms for QR and triangular factorization, SIAM Journal on Scientific and Statistical Computing, v.8 n.6, p.899-913, November 1, 1987 [doi>10.1137/0908073]
	CW	Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
	Cs	L. Csunky, Fast Parallel Matrix inversion AI- gorithms, SIAM J. on Computing, 5,4, pp. 618- 623, 1976.
	GP	Zvi Galil , Victor Pan, Parallel evaluation of the determinant and of the inverse of a matrix, Information Processing Letters, v.30 n.1, p.41-45, January 1989 [doi>10.1016/0020-0190(89)90173-7]
	GL	G.H. Golub, C.F. van Loan, Matrix Computations, Johns Hopkins Univ. Press, Baltimore, Maryland, 1989.
	KP	Erich Kaltofen , Victor Pan, Processor efficient parallel solution of linear systems over an abstract field, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.180-191, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113396]
	KPa	E. Kaltofen, V. Pan, Parallel and Processor Efficient Solution of Linear Systems II. The General Case. Manuscript, 1991.
	KR	Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	LPS	J. Laderman, V. Pan, X.-H Sha, On Practical Acceleration of Matrix Multiplication, Linear Algebra and Its Applications, 162-164, pp. 557- 588, 1992.
	P87	V. Pan, Complexity of parallel matrix computations, Theoretical Computer Science, v.54 n.1, p.65-85, 1987 [doi>10.1016/0304-3975(87)90019-3]
	P90	V. Pan, Parameterization of Newton's Iteration for Computations with Structured Matrices and Applications, to appear in Computers and Math. (with Applications),1992.
	P90a	V. Pan, On Computations with Dense Structured Matrices, Math. of Computations, 55, 191, pp. 179-190, 1990.
	P92	V. Pan, Parallel Solution of Sparse Linear and Path Systems, in Synthesis of Parallel Algorithms (j. Reif ed.), Morgan Kaufmann, San Mateo, California, 1992.
	PR	V. Pan , J. Reif, Fast and efficient solution of path algebra problems, Journal of Computer and System Sciences, v.38 n.3, p.494-510, June 1989 [doi>10.1016/0022-0000(89)90013-5]
	PS	F.P. Preparata, D.V. Sarwate, An Improved Parallel Processor Bound in Fast Matrix Inversion, Inform. Proc. Letters, 7,3, pp. 148-149, 1978.
	S	Thomas H. Spencer, Time-work tradeoffs for parallel graph algorithms, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.425-432, January 28-30, 1991, San Francisco, California, United States
	S,a	Thomas H. Spencer, More time-work tradeoffs for parallel graph algorithms, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.81-93, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113387]
	Val	L. G. Valiant, General purpose parallel architectures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	UY	Jeffrey D. Ullman , Mihalis Yannakakis, High probability parallel transitive-closure algorithms, SIAM Journal on Computing, v.20 n.1, p.100-125, Feb. 1991 [doi>10.1137/0220006]

CITED BY 2

	Dario Bini , Victor Pan, Parallel computations with Toeplitz-like and Hankel-like matrices, Proceedings of the 1993 international symposium on Symbolic and algebraic computation, p.193-200, July 06-08, 1993, Kiev, Ukraine
	Victor Y. Pan , Isdor Sobze , Antoine Atinkpahoun, Optimum parallel computations with banded matrices, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.649-658, January 23-25, 1994, Arlington, Virginia, United States