The exact solution of systems of linear equations with polynomial coefficients

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.

REFERENCES

• 1: Bareiss, Erwin H., "Sylvester's Identity and Multistep Integer - Preserving Gaussian Elimination," Math Comp, July, 1968.
• 2: Birkhoff, Garrett and MacLane, Saunders, A Survey of Modern Algebra, Macmillan, New York, 1965.
• 3: Bodwig, E., Matrix Calculus, Interscience, New York, 1959.
• 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.
• 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.
• 6: Collins, George E., Algebraic Algorithms, Prentice Hall, New Jersey (to appear).
• 7: Fox, L., An Introduction to Numerical Linear Algebra, Clarendon Press, Oxford, 1964.
• 8: Gantmacher, F. R., Matrix Theory, Vol. 1, Chelsea, New York, 1959.
• 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.
• 10: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 11: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 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.
• 13: H. A. Luther , L. F. Guseman, Jr., A finite sequentially compact process for the adjoints of matrices over arbitrary integral domains, Communications of the ACM, v.5 n.8, p.447-448, Aug. 1962 [doi>10.1145/368637.368764]
• 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.
• 15: Newman, Morris, "Solving Equations Exactly," J. of Res., N.B.S., Vol. 71B, No. 4, Oct. - Dec, 1967.
• 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.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra

General Terms:
Algorithms, Theory