An algorithm for the exact reduction of a matrix to Frobenius form using modular arithmetic. II
HTML articles powered by AMS MathViewer
- by Jo Ann Howell PDF
- Math. Comp. 27 (1973), 905-920 Request permission
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
- 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 139264
- 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
- Jo Ann Howell and Robert T. Gregory, Solving linear equations using residue arithmetic—Algorithm II, Nordisk Tidskr. Informationsbehandling (BIT) 10 (1970), 23–37. MR 261777, DOI 10.1007/bf01940889
- Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms. MR 0378456 N. Lehmer [1914], List of Prime Numbers from 1 to 10,006,721, Carnegie Institute of Washington (165), Washington, D. C. D. Lipson [1971], "Chinese remainder and interpolation algorithms," Proceedings of the Second Symposium on Symbolic and Algebraic Manipulation, SIGSAM-ACM.
- A. Ostrowski, Bounds for the greatest latent root of a positive matrix, J. London Math. Soc. 27 (1952), 253–256. MR 49152, DOI 10.1112/jlms/s1-27.2.253 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. S. Szabó & R. I. Tanaka [1967], Residue Arithmetic and Its Applications to Computer Technology, McGraw-Hill, New York.
Additional Information
- © Copyright 1973 American Mathematical Society
- Journal: Math. Comp. 27 (1973), 905-920
- MSC: Primary 65F30
- DOI: https://doi.org/10.1090/S0025-5718-73-99694-4