An O(n3) algorithm for the Frobenius normal form

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An O(n3) algorithm for the Frobenius normal form

Full text

Pdf (206 KB)

Source

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

Rostock, Germany

Pages: 101 - 105

Year of Publication: 1998

ISBN:1-58113-002-3

Author

Arne Storjohann

Institute of Scientific Computing, ETH Zurich, Switzerland

Sponsors

German Comp Soc : GI - Gesellshaft for Informatik
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): 18, Downloads (12 Months): 120, Citation Count: 8

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/281508.281570 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	AUGOT, D., AND CAMION, P. Frobenius form and cyclic vectors. C.-R.-Acad.-Sci.-Paris-Ser.-I-Math. 318, 2 (1994), 183-188.
	2	BAUR, W., AND STRASSEN, V. The complexity of partial derivatives. Theoretical Computer Science 22, 3 (1983), 317--330.
	3	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]
	4	Mark William Giesbrecht, Nearly optimal algorithms for canonical matrix forms, University of Toronto, Toronto, Ont., Canada, 1993
	5	Mark Giesbrecht, Nearly Optimal Algorithms For Canonical Matrix Forms, SIAM Journal on Computing, v.24 n.5, p.948-969, Oct. 1995 [doi>10.1137/S0097539793252687]
	6	LUNEBURG, H. On Rational Normal Form of Endomorphisms: a Primer to Constructive Algebra. Wissenschaftsverlag, Mannheim, 1987.
	7	NEWMAN, M. Integral Matrices. Academic Press, 1972.
	8	OZELLO, P. Calcul Exact Des Formes De Jordan et de Frobenius d'une Matrice. PhD thesis, Universit~ Scientifique Technologique et Medicale de Grenoble, 1987.
	9	Allan Steel, A new algorithm for the computation of canonical forms of matrices over fields, Journal of Symbolic Computation, v.24 n.3-4, p.409-432, Sept./Oct. 1997 [doi>10.1006/jsco.1996.0142]
	10	STORJoHANN, A. Computing Hermite and Smith normal forms of triangular integer matrices. Linear Algebra and its Applications (1998). To appear.

CITED BY 8

	Wayne Eberly, Black box Frobenius decompositions over small fields, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.106-113, July 2000, St. Andrews, Scotland
	Guoting Chen , Jean Della Dora, Rational normal form for dynamical systems by Carleman linearization, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.165-172, July 28-31, 1999, Vancouver, British Columbia, Canada
	Johannes Grabmeier , Erich Kaltofen , Volker Weispfenning, Cited References, Computer algebra handbook, Springer-Verlag New York, Inc., New York, NY, 2003
	Elisabetta Fortuna , Patrizia Gianni, Square-free decomposition in finite characteristic: an application to Jordon Form computation, ACM SIGSAM Bulletin, v.33 n.4, p.14-32, 12/01/1999
	Mark Giesbrecht , Arne Storjohann, Computing rational forms of integer matrices, Journal of Symbolic Computation, v.34 n.3, p.157-172, September 2002
	Thanh Minh Hoang , Thomas Thierauf, The complexity of the characteristic and the minimal polynomial, Theoretical Computer Science, v.295 n.1-3, p.205-222, 24 February 2003
	Dimitri Kagaris, A similarity transform for linear finite state machines, Discrete Applied Mathematics, v.154 n.11, p.1570-1577, 1 July 2006
	Dorothy Bollman , Omar Colón-Reyes , Edusmildo Orozco, Fixed points in discrete models for regulatory genetic networks, EURASIP Journal on Bioinformatics and Systems Biology, v.2007 n.1, p.10-10, 01 January 2007