On computing determinants of matrices without divisions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On computing determinants of matrices without divisions

Full text

Pdf (700 KB)

Source

International Conference on Symbolic and Algebraic Computation archive
Papers from the international symposium on Symbolic and algebraic computation table of contents

Berkeley, California, United States

Pages: 342 - 349

Year of Publication: 1992

ISBN:0-89791-489-9

Author

Erich Kaltofen

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): 10, Downloads (12 Months): 39, Citation Count: 14

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/143242.143350 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	Brent, P~. P., Gustavson, F. G., and Yun, D. Y. Y., "Fast solution of Toeplitz systems of equations and computation of Pad6 approximants," J. Algorithms 1, pp. 259-295 (1980).
	4	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]
	5	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
	6	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]
	7	James H. Davenport , Barry M. Trager, Scratchpad's View of Algebra I: Basic Commutative Algebra, Proceedings of the International Symposium on Design and Implementation of Symbolic Computation Systems, p.40-54, April 10-12, 1990
	8	Jean Louis Dornstetter, On the equivalence between Berlekamp's and Euclid's algorithms, IEEE Transactions on Information Theory, v.33 n.3, p.428-431, May 1, 1987 [doi>10.1109/TIT.1987.1057299]
	9	D. Duval, Simultaneous computations in fields of different characteristics, Proceedings of the third conference on Computers and mathematics, p.321-326, May 1989, Boston, Massachusetts, United States
	10	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]
	11	Ronald L. Graham , Donald E. Knuth , Oren Patashnik, Concrete mathematics: a foundation for computer science, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
	12	Jacobson, N., Basic Algebra I; W. H. Freeman &5 Co., San Francisco, 1974.
	13	Erich Kaltofen, Greatest common divisors of polynomials given by straight-line programs, Journal of the ACM (JACM), v.35 n.1, p.231-264, Jan. 1988 [doi>10.1145/42267.45069]
	14	Kaltofen, E., "Factorization of polynomials given by straight-line programs," in Randomness and Computation, Advances in Computing Research 5, edited by S. Micali; JAI Press, Greenwhich, Connecticut, pp. 375-412, 1989.
	15	Kaltofen, E., "Efficient Solution of Sparse Linear Systems," Leer. Notes, Dept. Comput. Sci., Rensselaer Polytech. Inst., Troy, New York, 1992.
	16	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]
	17	Erich Kaltofen , B. David Saunders, On Wiedemann's Method of Solving Sparse Linear Systems, Proceedings of the 9th International Symposium, on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.29-38, October 07-11, 1991
	18	Erich Kaltofen , Barry M. Trager, Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators, Journal of Symbolic Computation, v.9 n.3, p.301-320, March 1990 [doi>10.1016/S0747-7171(08)80015-6]
	19	Knuth, D. E., "The analysis of algorithms," Acres du congr~s international des Mathdmaticiens 3, pp. 269- 274 (19 0).
	20	Kung, It. T., "On computing reciprocals of power series," Numer. Math. 22, pp. 341-348 (1974).
	21	Linnainmaa, S., "Taylor expansion of the accumulated rounding error," BIT 16, pp. 146-160 (1976).
	22	Massey, J. L., "Shift-register synthesis and BCH decoding," IEEE Trans. Inf. Theory IT-15, pp. 122-127 (1969).
	23	R. T. Moenck, Fast computation of GCDs, Proceedings of the fifth annual ACM symposium on Theory of computing, p.142-151, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804045]
	24	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).
	25	Richardson, D., "Some undecidable problems involving elementary functions of a real variable," J. Symbolic Logic 33/4, pp. 511-520 (1968).
	26	Tateaki Sasaki , Hirokazu Murao, Efficient Gaussian Elimination Method for Symbolic Determinants and Linear Systems, ACM Transactions on Mathematical Software (TOMS), v.8 n.3, p.277-289, Sept. 1982 [doi>10.1145/356004.356007]
	27	SchSnhage, A., "Schnelle Kettenbruchentwicklungen," Acta Inform. 1, pp. 139-144 (1971). in German.
	28	Sieveking, M., "An algorithm for division of power series," Computing 10, pp. 153-156 (1972).
	29	Strassen, V., "Vermeidung yon Divisionen," J. reine u. angew. Math. 264, pp. 182-202 (1973). In German.
	30	Strassen, V., "The computational complexity of continued fractions," SIAM J. Comput. 12/1, pp. 1-27 (1983).
	31	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]

CITED BY 14

	T. R. Seifullin, Computation of Determinants, Adjoint Matrices, and Characteristic Polynomials without Division, Cybernetics and Systems Analysis, v.38 n.5, p.650-672, September-October 2002
	Angel Díaz , Erich Kaltofen, FOXBOX: a system for manipulating symbolic objects in black box representation, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.30-37, August 13-15, 1998, Rostock, Germany
	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
	Johannes Grabmeier , Erich Kaltofen , Volker Weispfenning, Cited References, Computer algebra handbook, Springer-Verlag New York, Inc., New York, NY, 2003
	Erich Kaltofen , Gilles Villard, Computing the sign or the value of the determinant of an integer matrix, a complexity survey, Journal of Computational and Applied Mathematics, v.162 n.1, p.133-146, 1 January 2004
	Arne Storjohann , Gilles Villard, Computing the rank and a small nullspace basis of a polynomial matrix, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.309-316, July 24-27, 2005, Beijing, China
	Claude-Pierre Jeannerod , Gilles Villard, Essentially optimal computation of the inverse of generic polynomial matrices, Journal of Complexity, v.21 n.1, p.72-86, February 2005
	Jean-Guillaume Dumas , Clément Pernet , Zhendong Wan, Efficient computation of the characteristic polynomial, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.140-147, July 24-27, 2005, Beijing, China
	Arne Storjohann, The shifted number system for fast linear algebra on integer matrices, Journal of Complexity, v.21 n.4, p.609-650, August 2005
	Valentine Kabanets , Russell Impagliazzo, Derandomizing polynomial identity tests means proving circuit lower bounds, Computational Complexity, v.13 n.1/2, p.1-46, January 2004
	Itnuit Janovitz-Freireich , Lajos Rónyai , Ágnes Szántó, Approximate radical of ideals with clusters of roots, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy
	T. R. Seifullin, Acceleration of Computation of Determinants and Characteristic Polynomials without Divisions, Cybernetics and Systems Analysis, v.39 n.6, p.805-815, November-December 2003
	Cyril Pascal , Éric Schost, Change of order for bivariate triangular sets, 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