A fast parallel algorithm to compute the rank of a matrix over an arbitrary field

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A fast parallel algorithm to compute the rank of a matrix over an arbitrary field

Full text

Pdf (166 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the eighteenth annual ACM symposium on Theory of computing table of contents

Berkeley, California, United States

Pages: 338 - 339

Year of Publication: 1986

ISBN:0-89791-193-8

Author

K Mulmuley

EECS Department, Computer Science Division, University of California, Berkeley, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 68, Citation Count: 6

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

	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]
	BCP	A Borodin , S Cook , N Pippenger, Parallel computation for well-endowed rings and space-bounded probabilistic machines, Information and Control, v.58 n.1-3, p.113-136, July/Aug./Sept. 1983 [doi>10.1016/S0019-9958(83)80060-6]
	BGH	A. Borodin, J. von zur Gathen, J. Hopcraft, Fast parallel matrix and GCD computations, Proc. 23rd STOC (1982).
	CS	L. Csanky, Fast parallel matrix inversion algorithms, SIAM J. Comput. 5 (1976).
	GA	J. von zur Gathen, private communication.
	IMR	O. Ibarra, S. Moran, L.E. Rosier, A note on the parallel complexity of computing the rank of order n matrices, Information Processing Letters 11 (1980), 162.
	LM	E.M. Luks, P. McKenzle, Fast parallel computation with permutation groups, 25th FOCS, 1985.
	MC	P. McKenzie, S.A. Cook, The parallel complexity of the abelian permutation group membership, 24th FOCS, 1983.

CITED BY 6

	Klaus Kühnle , Ernst W. Mayr, Exponential space computation of Gröbner bases, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.63-71, July 24-26, 1996, Zurich, Switzerland
	Dima Yu. Grigoriev , Marek Karpinski, Algorithms for sparse rational interpolation, Proceedings of the 1991 international symposium on Symbolic and algebraic computation, p.7-13, July 15-17, 1991, Bonn, West Germany
	E. Kaltofen , M. Krishnamoorthy , B. D. Saunders, Fast parallel algorithms for similarity of matrices, Proceedings of the fifth ACM symposium on Symbolic and algebraic computation, p.65-70, July 21-23, 1986, Waterloo, Ontario, Canada
	Dima Yu. Grigoriev , Marek Karpinski , Andrew M. Odlyzko, Existence of short proofs for nondivisibility of sparse polynomials under the extended Riemann hypothesis, Papers from the international symposium on Symbolic and algebraic computation, p.117-122, July 27-29, 1992, Berkeley, California, United States
	Carsten Damm , Markus Holzer , Pierre McKenzie, The complexity of tensor calculus, Computational Complexity, v.11 n.1/2, p.54-89, January 2003
	Carl G. Ponder, Parallelism and algorithms for algebraic manipulation: current work, ACM SIGSAM Bulletin, v.22 n.3, p.7-14, July 1988