Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

An algorithm for the exact reduction of a matrix to Frobenius form using modular arithmetic. I
HTML articles powered by AMS MathViewer

by Jo Ann Howell PDF
Math. Comp. 27 (1973), 887-904 Request permission

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
    A. Chartres [1964], Controlled Precision Calculations and the Danilewski Method, Brown University, Division of Applied Mathematics Report. Danilewski [1937], "On a numerical solution of Vekua’s equation," Mat. Sb., v. 2, pp. 169-171. (Russian)
  • Werner L. Frank, Computing eigenvalues of complex matrices by determinant evaluation and by methods of Danilewski and Wielandt, J. Soc. Indust. Appl. Math. 6 (1958), 378–392. MR 103586
  • Eldon R. Hansen, On the Danilewski method, J. Assoc. Comput. Mach. 10 (1963), 102–109. MR 155426, DOI 10.1145/321150.321158
  • I. N. Herstein, Topics in algebra, Blaisdell Publishing Co. [Ginn and Co.], New York-Toronto-London, 1964. MR 0171801
  • Alston S. Householder, The theory of matrices in numerical analysis, Blaisdell Publishing Co. [Ginn and Co.], New York-Toronto-London, 1964. MR 0175290
  • Alston S. Householder and Friedrich L. Bauer, On certain methods for expanding the characteristic polynomial, Numer. Math. 1 (1959), 29–37. MR 100962, DOI 10.1007/BF01386370
    • 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. Michael T. McClellan [1971], The Exact Solution of Linear Equations with Polynomial Coefficients, University of Wisconsin Computer Sciences Department, Technical Report #136, Madison, Wisconsin. 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.
  • Harold Wayland, Expansion of determinantal equations into polynomial form, Quart. Appl. Math. 2 (1945), 277–306. MR 11799, DOI 10.1090/S0033-569X-1945-11799-8
  • J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC: 65F30
  • Retrieve articles in all journals with MSC: 65F30
Additional Information
  • © Copyright 1973 American Mathematical Society
  • Journal: Math. Comp. 27 (1973), 887-904
  • MSC: Primary 65F30
  • DOI: https://doi.org/10.1090/S0025-5718-1973-0378381-9
  • MathSciNet review: 0378381