Michael T. McClellan
ABSTRACT
An algorithm for computing exactly a general solution to a system of linear equations with coefficients that are polynomials over the integers is presented. The algorithm applies mod-p mappings and then evaluation mappings, eventually solving linear systems of equations with coefficients in GF(p) by a special Gaussian elimination algorithm. Then by applying interpolation and the Chinese Remainder Theorem a general solution is obtained.
For a consistent system, the evaluation-interpolation part of the algorithm computes the determinantal RRE form of the mod-p reduced augmented system matrices. The Chinese Remainder Theorem then uses these to construct an RRE matrix with polynomial entries over the integers, from which a general solution is constructed. For an inconsistent system, only one mod-p mapping is needed.
The average computing time for the algorithm is obtained and compared to that for the exact division method. The new method is found to be far superior. Also, a mod-p/evaluation mapping algorithm for computing matrix products is discussed briefly.
- 1.Bareiss, Erwin H., "Sylvester's Identity and Multistep Integer - Preserving Gaussian Elimination," Math Comp, July, 1968.Google Scholar
- 2.Birkhoff, Garrett and MacLane, Saunders, A Survey of Modern Algebra, Macmillan, New York, 1965.Google Scholar
- 3.Bodwig, E., Matrix Calculus, Interscience, New York, 1959.Google Scholar
- 4.Borosh, I. and Fraenkel, A. S., "Exact Solutions of Linear Equations with Rational Coefficients by Congruence Techniques," Math Comp, Vol. 20, No. 93, Jan. 1966.Google Scholar
- 5.Collins, George E., "Computing Time Analysis for Some Arithmetic and Algebraic Algorithms," Proc. of the 1968 Summer Institute on Symbolic Mathematical Computation, R. Tobey (Ed.), June, 1969.Google Scholar
- 6.Collins, George E., Algebraic Algorithms, Prentice Hall, New Jersey (to appear).Google Scholar
- 7.Fox, L., An Introduction to Numerical Linear Algebra, Clarendon Press, Oxford, 1964.Google Scholar
- 8.Gantmacher, F. R., Matrix Theory, Vol. 1, Chelsea, New York, 1959.Google Scholar
- 9.Howell, J. A. and Gregory, R. T., "An Algorithm for Solving Linear Algebraic Equations Using Residue Arithmetic," BIT, 9 (1969), pp. 200-234, 324-337.Google ScholarDigital Library
- 10.Knuth, D. E., The Art of Computer Programming, Vol. 1: Fundamental Algorithms, Addison Wesley, Reading, Mass., 1968. Google ScholarDigital Library
- 11.Knuth, D. E., The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, Addison Wesley, Reading, Mass., 1969. Google ScholarDigital Library
- 12.Lipson, John D., "Symbolic Methods for the Computer Solution of Linear Equations with Applications to Flowgraphs," Proc. of the 1968 Summer Institute on Symbolic Mathematical Computation, R. Tobey (Ed.), June 1969.Google Scholar
- 13.Luther, H. A. and Guseman, L. F., Jr., "A Finite Sequentially Compact Process for the Adjoints of Matrices over Arbitrary Integral Domains," CACM, Vol. 5, No. 8, (Aug. 1962). Google ScholarDigital Library
- 14.McClellan, Michael T., Algorithms for Exact Solution of Systems of Linear Equations with Polynomial Coefficients, Ph.D. Thesis, Computer Science Dept., Univ. of Wisconsin. In preparation.Google Scholar
- 15.Newman, Morris, "Solving Equations Exactly," J. of Res., N.B.S., Vol. 71B, No. 4, Oct. - Dec, 1967.Google Scholar
- 16.Takahasi, H. and Ishibashi, Y., "A New Method for 'Exact Calculation' by a Digital Computer," Information Processing in Japan, Vol. 1 (1961), pp. 28-42.Google Scholar
Index Terms
- The exact solution of systems of linear equations with polynomial coefficients
Recommendations
Linear partial q-difference equations on q-linear lattices and their bivariate q-orthogonal polynomial solutions
Orthogonal polynomial solutions of an admissible potentially self-adjoint linear second-order partial q-difference equation of the hypergeometric type in two variables on q-linear lattices are analyzed. A q-Pearson's system for the orthogonality weight ...
Bidiagonalization of Matrices and Solution of Linear Equations
An algorithm given by Golub and Kahan [2] for reducing a general matrix to bidiagonal form is shown to be very important for large sparse matrices. The singular values of the matrix are those of the bidiagonal form, and these can be easily computed. The ...
Taylor polynomial solution of hyperbolic type partial differential equations with constant coefficients
The purpose of this study is to give a Taylor polynomial approximation for the solution of hyperbolic type partial differential equations with constant coefficients. The technique used is an improved Taylor matrix method, which has been given for ...
Comments