Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



An algorithm for the exact reduction of a matrix to Frobenius form using modular arithmetic. I

Author: Jo Ann Howell
Journal: Math. Comp. 27 (1973), 887-904
MSC: Primary 65F30
MathSciNet review: 0378381
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This paper is in two parts. Part I contains a description of the Danilewski algorithm for reducing a matrix to Frobenius form using rational arithmetic. This algorithm is modified for use over the field of integers modulo p. The modified algorithm yields exact integral factors of the characteristic polynomial. A description of the single-modulus algorithm is given. Part II contains a description of the multiple-modulus algorithm. Since different moduli may yield different factorizations, an algorithm is given for determining which factorizations are not correct factorizations over the integers of the characteristic polynomial.

References [Enhancements On Off] (What's this?)

  • [B] A. Chartres [1964], Controlled Precision Calculations and the Danilewski Method, Brown University, Division of Applied Mathematics Report.
  • [A] Danilewski [1937], "On a numerical solution of Vekua's equation," Mat. Sb., v. 2, pp. 169-171. (Russian)
  • [W] L. Frank [1958], "Computing eigenvalues of complex matrices by determinant evaluation and by methods of Danilewski and Wielandt," J. SIAM, v. 6, pp. 378-392. MR 21 #2354. MR 0103586 (21:2354)
  • [E] R. Hansen [1963], "On the Danilewski method," J. ACM, v. 10, pp. 102-109. MR 27 #5360. MR 0155426 (27:5360)
  • [I] N. Herstein [1964], Topics in Algebra, Blaisdell, Waltham, Mass. MR 30 #2028. MR 0171801 (30:2028)
  • [A] S. Householder [1964], The Theory of Matrices in Numerical Analysis, Blaisdell, New York. MR 30 #5475. MR 0175290 (30:5475)
  • [A] S. Householder & F. L. Bauer [1959], "On certain methods for expanding the characteristic polynomial," Numer. Math., v. 1, pp. 29-37. MR 20 #7387. MR 0100962 (20:7387)
  • [J] A. Howell, [1972], An Algorithm for the Exact Reduction of a Matrix to Frobenius Form Using Modular Arithmetic, University of Texas at Austin Center for Numerical Analysis, Report CNA-39, Austin, Texas.
  • 1. Michael T. McClellan [1971], The Exact Solution of Linear Equations with Polynomial Coefficients, University of Wisconsin Computer Sciences Department, Technical Report #136, Madison, Wisconsin.
  • [D] L. Slotnick [1963], Modular Arithmetic Computing Techniques, Westinghouse Electric Corporation, Technical Report ASD-TDR-63-280, Baltimore; Clearinghouse for Federal Scientific and Technical Information, Report No. AD410534, Springfield, Virginia 22151.
  • [H] Wayland [1945], "Expansion of determinantal equations into polynomial form," Quart. Appl. Math., v. 2, pp. 277-306. MR 6, 218. MR 0011799 (6:218f)
  • [J] H. Wilkinson [1965], The Algebraic Eigenvalue Problem, Clarendon Press, Oxford. MR 32 #1894. MR 0184422 (32:1894)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65F30

Retrieve articles in all journals with MSC: 65F30

Additional Information

Keywords: Modular arithmetic, residue arithmetic, modulus, Frobenius form, Danilewski method, characteristic polynomial, similarity transformation, prime number, Chinese Remainder Theorem
Article copyright: © Copyright 1973 American Mathematical Society

American Mathematical Society