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. II

Author: Jo Ann Howell
Journal: Math. Comp. 27 (1973), 905-920
MSC: Primary 65F30
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Part I contained a description of the single-modulus algorithm for reducing a matrix to Frobenius form, obtaining exact integral factors of the characteristic polynomial. 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. Part II also contains a discussion of the selection of the moduli and numerical examples.

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

  • [P] P. J. Eberlein, A Jacobi-like method for the automatic computation of eigenvalues and eigenvectors of an arbitrary matrix, J. Soc. Indust. Appl. Math. 10 (1962), 74–88. MR 0139264
  • [R] Robert T. Gregory and David L. Karney, A collection of matrices for testing computational algorithms, Wiley-Interscience A Division of John Wiley & Sons, Inc., New York-London-Sydney, 1969. MR 0253538
  • [J] Jo Ann Howell and Robert T. Gregory, Solving linear equations using residue arithmetic—Algorithm II, Nordisk Tidskr. Informationsbehandling (BIT) 10 (1970), 23–37. MR 0261777
  • [D] Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 0378456
  • [D] N. Lehmer [1914], List of Prime Numbers from 1 to 10,006,721, Carnegie Institute of Washington (165), Washington, D. C.
  • [J] D. Lipson [1971], "Chinese remainder and interpolation algorithms," Proceedings of the Second Symposium on Symbolic and Algebraic Manipulation, SIGSAM-ACM.
  • [A] A. Ostrowski, Bounds for the greatest latent root of a positive matrix, J. London Math. Soc. 27 (1952), 253–256. MR 0049152,
  • [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.
  • [N] S. Szabó & R. I. Tanaka [1967], Residue Arithmetic and Its Applications to Computer Technology, McGraw-Hill, New York.

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