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

DOI:
https://doi.org/10.1090/S0025-5718-73-99694-4

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.

**[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**, https://doi.org/10.1112/jlms/s1-27.2.253**[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.

Retrieve articles in *Mathematics of Computation*
with MSC:
65F30

Retrieve articles in all journals with MSC: 65F30

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-73-99694-4

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