Processor efficient parallel solution of linear systems over an abstract field

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Processor efficient parallel solution of linear systems over an abstract field

Full text

Pdf (980 KB)

Source

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

Hilton Head, South Carolina, United States

Pages: 180 - 191

Year of Publication: 1991

ISBN:0-89791-438-4

Authors

Erich Kaltofen	Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New York and Department of Computer Science, University of Toronto, Toronto, Canada M5S 1A4
Victor Pan	Department of Mathematics and Computer Science, Lehman College, City University of New York, Bronx, New York

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): 8, Downloads (12 Months): 30, Citation Count: 29

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/113379.113396 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	Baur, W. and Strassen, V., "The complexity of partial derivatives," Theoretical Comp. Sci. 22, pp. 317-330 (1983).
	2	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]
	3	Bini, D. and Pan, V., Numerical and Algebraic Computations with Matrices and Polynomials; Lecture Notes in Theor. Comput. Sci., edited by R. V. Book; Birkh~iuser Boston, Inc., 1991. To appear.
	4	Borodin, A., von zur Gathen, J., and ttopcrot't, J. E., "Fast parallel matrix and GCD computations," Inf. Control 52, pp. 241-256 (1982).
	5	Borodin, A. and Munro, I., Computational Complexity of Algebraic and Numeric Problems; American Elsevier, New York, N.Y., 1975.
	6	Brent, R. P., Gustavson, F. G., and Yun, D. Y. Y., "Fast solution of Toeplitz systems of equations and compuration of Pad~ approximants," J. Algorithms 1, pp. 259-295 ( 980).
	7	Bunch, J. R. and Hopcroft, J. E., "Triangular factorization and inversion by fast matrix multiplication," Math. Comp. 28, pp. 231-236 (1974).
	8	David G. Cantor , Erich Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Informatica, v.28 n.7, p.693-701, Oct. 1991 [doi>10.1007/BF01178683]
	9	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
	10	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]
	11	Csanky, L., "Fast parallel matrix inversion algorithms," SIAM J. Comput. 5/4, pp. 618-623 (1976).
	12	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]
	13	H. J. Hoover , M. M. Klawe , N. J. Pippenger, Bounding Fan-out in Logical Networks, Journal of the ACM (JACM), v.31 n.1, p.13-18, Jan. 1984 [doi>10.1145/2422.322412]
	14	Kaltofen, E. and Singer, M. F., "Size efficient parallel algebraic circuits for partial derivatives," Tech. I~eport 90-32, Dept. Comput. Sci., P~ensselaer Polytech~lic Inst., Troy, N.Y., October 1990.
	15	Michael Kaminski , David G. Kirkpatrick , Nader H. Bshouty, Addition requirements for matrix and transposed matrix products, Journal of Algorithms, v.9 n.3, p.354-364, September 1988 [doi>10.1016/0196-6774(88)90026-0]
	16	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
	17	Walter Keller-Gehrig, Fast algorithms for the characteristic polynomial, Theoretical Computer Science, v.36 n.2-3, p.309-317, June 1985
	18	Lipson, J., Elements of Algebra and Algebraic Computing; Addison-Wesley Publ., Reading, Mass., 1981.
	19	V. Pan, Parallel least-squares solution of general and Toeplitz systems, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.244-253, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97691]
	20	Pan, V., "Parameterization of Newton's iteration for computations with structured matrices and applications," Tech. Report CUCS-032-90, Comput. Sci. Dept., Columbia University, New York, N. Y., 1990b.
	21	Preparata, F. P. and Sarwate, D. V., "An improved parallel processor bound in fast matrix inversion," Inform. Process. Letters 7/3, pp. 148-150 (1978).
	22	J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
	23	SchSnhage, A., "The fundamental theorem of algebra in terms of computational complexity," Tech. Report, Univ. Tiibingen, 1982.
	24	D H Wiedemann, Solving sparse linear equations over finite fields, IEEE Transactions on Information Theory, v.32 n.1, p.54-62, Jan. 1986 [doi>10.1109/TIT.1986.1057137]
	25	Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979

CITED BY 29

	G. Villard, Computing Popov and Hermite forms of polynomial matrices, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.250-258, July 24-26, 1996, Zurich, Switzerland
	Victor Y. Pan , Franco P. Preparata, Supereffective slow-down of parallel computations, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.402-409, June 29-July 01, 1992, San Diego, California, United States
	Erich Kaltofen, On computing determinants of matrices without divisions, Papers from the international symposium on Symbolic and algebraic computation, p.342-349, July 27-29, 1992, Berkeley, California, United States
	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
	Victor Y. Pan , Zhao Q. Chen, The complexity of the matrix eigenproblem, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.507-516, May 01-04, 1999, Atlanta, Georgia, United States
	G. Villard, Further analysis of Coppersmith's block Wiedemann algorithm for the solution of sparse linear systems (extended abstract), Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.32-39, July 21-23, 1997, Kihei, Maui, Hawaii, United States
	Joseph Cheriyan , John H. Reif, Parallel and output sensitive algorithms for combinatorial and linear algebra problems, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.50-56, June 30-July 02, 1993, Velen, Germany
	Wayne Eberly, Processor-efficient parallel matrix inversion over abstract fields: two extensions, Proceedings of the second international symposium on Parallel symbolic computation, p.38-45, July 20-22, 1997, Maui, Hawaii, United States
	Ioannis Z. Emiris , Victor Y. Pan, Symbolic and numeric methods for exploiting structure in constructing resultant matrices, Journal of Symbolic Computation, v.33 n.4, p.393-413, April 2002
	Joseph Cheriyan , John H. Reif, Directed s-t numberings, rubber bands, and testing digraph k-vertex connectivity, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.335-344, September 1992, Orlando, Florida, United States
	Wayne Eberly , Erich Kaltofen, On randomized Lanczos algorithms, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.176-183, July 21-23, 1997, Kihei, Maui, Hawaii, United States
	John H. Reif, O(log2 n) time efficient parallel factorization of dense, sparse separable, and banded matrices, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.278-289, June 27-29, 1994, Cape May, New Jersey, United States
	Wayne Eberly, Efficient parallel computations for singular band matrices, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.132-138, January 22-24, 1995, San Francisco, California, United States
	Joseph Cheriyan, A Las Vegas O(n2.38 algorithm for the cardinality of a maximum matching, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.442-451, January 23-25, 1994, Arlington, Virginia, United States
	Victor Y. Pan , Xinmao Wang, Acceleration of Euclidean algorithm and extensions, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.207-213, July 07-10, 2002, Lille, France
	Ioanis Z. Emiris , Victor Y. Pan, The structure of sparse resultant matrices, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.189-196, 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
	Erich Kaltofen , Victor Shoup, Subquadratic-time factoring of polynomials over finite fields, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.398-406, May 29-June 01, 1995, Las Vegas, Nevada, United States
	John H. Reif, Work efficient parallel solution of Toeplitz systems and polynomial GCD, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.751-761, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Johannes Grabmeier , Erich Kaltofen , Volker Weispfenning, Cited References, Computer algebra handbook, Springer-Verlag New York, Inc., New York, NY, 2003
	Johannes Grabmeier , Erich Kaltofen , Volker Weispfenning, Cited References, Computer algebra handbook, Springer-Verlag New York, Inc., New York, NY, 2003
	Wayne Eberly, Early termination over small fields, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.80-87, August 03-06, 2003, Philadelphia, PA, USA
	Xiaohan Huang , Victor Y. Pan, Fast rectangular matrix multiplications and improving parallel matrix computations, Proceedings of the second international symposium on Parallel symbolic computation, p.11-23, July 20-22, 1997, Maui, Hawaii, United States
	Victor Y. Pan, A new approach to parallel computation of polynomial GCD and to related parallel computations over fields and integer rings, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.518-527, January 28-30, 1996, Atlanta, Georgia, United States
	Ioannis Z. Emiris , Victor Y. Pan, Improved algorithms for computing determinants and resultants, Journal of Complexity, v.21 n.1, p.43-71, February 2005
	Piotr Sankowski, Processor efficient parallel matching, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	John H. Reif, Efficient parallel factorization and solution of structured and unstructured linear systems, Journal of Computer and System Sciences, v.71 n.1, p.86-143, July 2005
	William J. Turner, A block Wiedemann rank algorithm, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy
	Gilles Villard, Some recent progress in exact linear algebra and related questions, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada