Fast rectangular matrix multiplications and improving parallel matrix computations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast rectangular matrix multiplications and improving parallel matrix computations

Full text

Pdf (1.26 MB)

Source

International Symposium on Parallel Symbolic Computation archive
Proceedings of the second international symposium on Parallel symbolic computation table of contents

Maui, Hawaii, United States

Pages: 11 - 23

Year of Publication: 1997

ISBN:0-89791-951-3

Authors

Xiaohan Huang	Ph.D. Program in Mathematics, Graduate School and University Center, City University of New York, 33 West 42nd Street, New York, NY
Victor Y. Pan	Department of Mathematics and Computer Science, Lehman College, City University of New York, Bronx, NY

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation
SIGNUM: ACM Special Interest Group on Numerical Mathematics

Publisher

ACM New York, NY, USA

Bibliometrics

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

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

	BCLR	D. Bini. M. Capovani, G. Lotti, and F. Romani, O(n2"7r~9) complexity for matrix multiplication, Inform. Process. Left., 8, 234-235, 1979.
	BD76	R. W. Brockett and D. Dobkin, On the Number of Multiplications Required for Matrix Multiplications, SIAM J. on Complexity, 5, 4, 624-628, 1976.
	Be46	F.A. Behrend, On Sets of Integers Which Contain No Three Terms in Arithmetical Progression. Proc. Nat. Acad. Sci. USA, 32, 331-332, 1946.
	BM75	A. Borodin and I. Munro, The Computational Complexity of Algebraic and Numeric Problems, American Elsevier, New York, 1975.
	BP94	Dario Bini , Victor Y. Pan, Polynomial and matrix computations (vol. 1): fundamental algorithms, Birkhauser Verlag, Basel, Switzerland, 1994
	Co82	D. Coppersmith, Rapid Multiplication of Rectangular Matrices, SIAM J. Comput., 11, 3, 467-471, 1982.
	Co	D. Coppersmith, Rectangular Matrix Multiplication Revisited, Research Report 20498, IBM Thomas J. Watson Research Center, Yorktown Heights, NY 10598, USA, 1996.
	Cs76	L. Csanky, Fast Parallel Matrix Inversion Algorithm, SIAM J. Computing, 5, 4, 618-623, 1976.
	CW81	D. Coppersmith and S. Winograd, On the Aysmptotic Complexity of Matrix Multiplication, SIAM J. Comput., 11, 472-492, 1981.
	CW90	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]
	GP89	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]
	KP91	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]
	KP92	E. Kaltofen and V. Y. Pan, Processor Efficient Parallel Solution of Linear Systems Ii. The Positive Characteristic and Singular Cases, Proc. of 33rd Ann. IF, BE Syrup. on Foundations of Computer Science, 714-723, IEEE Computer Society Press, 1992.
	KP94	E. Kaltofen and V. Y. Pan, Parallel Solution of Toeplitz and Toeplitz-like Linear Systems over Fields of Small Positive Characteristic, Proc. of 1st Intern. Syrup. on Parallel Symbolic Computation (PASCO'94), Linz, Austria (Sept. 1994), Lecture Notes Series in Computing, 5, 225-233, World Scientific Publishing Company, Singapore, 1994.
	P72	V.Y. Pan, On Schemes for the Computation of Products and Inverse of Matrices, Uspekhi Mat. Nauk, 27', 5, 249-250, 1972. (In Russian.)
	Pan	Victor Pan, How to multiply matrices faster, Springer-Verlag New York, Inc., New York, NY, 1984
	Pan,a	Victor Pan, How can we speed up matrix multiplication?, SIAM Review, v.26 n.3, p.393-415, July 1984 [doi>10.1137/1026076]
	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]
	P96	Victor Y. Pan, Parallel computation of polynomial GCD and some related parallel computations over abstract fields, Theoretical Computer Science, v.162 n.2, p.173-223, Aug. 20, 1996 [doi>10.1016/0304-3975(96)00030-8]
	PS78	F.P. Preparata and D. V. Sarwate, An Improved Parallel Processor Bound in Fast Matrix Inversion, Inform. Proc. Letters, 7, 3, 148-149, 1978.
	Sc81	A. SchSnhage, Partial and Total Matrix Multiplication, SIAM J. Comput., 10, 3, 434-456, 1981.
	SS42	R. Salem and D. C. Spencer, On Sets of Integers Which Contain No Three Terms in Arithmetical Progresion. Proc. Nat. Acad. Sci. USA, 28, 561- 563, 1942.
	St69	V. Strassen, Gaussian Elimination Is Not Optimal, Numerische Math., 13, 354-356, 1969.
	St86	V. Strassen, The Asymptotic Spectrum of Tensors and the Exponent of Matrix Multiplication, Proc. 27th Ann. IEEE Syrup. on Foundations of Computer Science, 49-54, 1986.

CITED BY 4

	Tatsuya Akutsu , Satoru Miyano , Satoru Kuhara, Algorithms for identifying Boolean networks and related biological networks based on matrix multiplication and fingerprint function, Proceedings of the fourth annual international conference on Computational molecular biology, p.8-14, April 2000, Tokyo, Japan
	Erich Kaltofen , Victor Shoup, Fast polynomial factorization over high algebraic extensions of finite fields, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.184-188, July 21-23, 1997, Kihei, Maui, Hawaii, United States
	Erich Kaltofen, An output-sensitive variant of the baby steps/giant steps determinant algorithm, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.138-144, July 07-10, 2002, Lille, France
	Jean-Guillaume Dumas , Pascal Giorgi , Clément Pernet, FFPACK: finite field linear algebra package, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.119-126, July 04-07, 2004, Santander, Spain