Exact solution of linear equations

ABSTRACT

The congruential method of obtaining the exact solution of a system of linear equations with integral coefficients is critically reviewed. A new and efficient test for checking that a sequence of residue solutions determines the correct integer solution of the system of equations is presented. Also discussed is an improved method for finding the adjoint of a singular matrix.

REFERENCES

• 1: E.H. Bareiss, "Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination", Math. Comp. 22 (1968), 565-578.
• 2: W.A. Blankinship, "A New Version of the Euclidean Algorithm", Amer. Math. Month. 70 (1963), 742-745.
• 3: W. A. Blankinship, Algorithm 288: solution of simultaneous linear Diophantine equations [F4], Communications of the ACM, v.9 n.7, p.514, July 1966 [doi>10.1145/365719.365971]
• 4: E. Bodewig, Matrix Calculus, North-Holland, 1959.
• 5: I. Borosh and A.S. Fraenkel, "Exact Solutions of Linear Equations with Rational Coefficients by Congruence Techniques", Math. Comp. 20 (1966), 107-112.
• 6: G.E. Collins, "Computing Multiplicative Inverses in GF(p)", Math. Comp. 23 (1969), 197-200.
• 7: G. Forsythe and C.B. Moler, Computer Solution of Linear Algebraic Equations, Prentice-Hall, 1967.
• 8: L. Fox, An Introduction to Numerical Linear Algebra, Clarendon Press, 1964.
• 9: J.A. Howell and R.T. Gregory, "An Algorithm for Solving Linear Algebraic Equations using Residue Arithmetic I", BIT 9 (1969), 200-224.
• 10: J.A. Howell and R.T. Gregory, "An Algorithm for Solving Linear Algebraic Equations using Residue Arithmetic II", BIT 9 (1969), 324-337.
• 11: J.A. Howell and R.T. Gregory, "Solving Linear Equations using Residue Arithmetic - Algorithm II", BIT 10 (1970), 23-37.
• 12: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 13: J.D. Lipson, "Interpolation and Chinese Remainder Algorithms", University of Toronto Computer Science Technical Report, 1970.
• 14: 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]
• 15: M. Newman, "Solving Equations Exactly", J. Res. Nat. Bureau Standards-B, 71B (1967), 171-179.
• 16: J.B. Rosser, "A Method of Computing Exact Inverses of Matrices with Integer Coefficients", J. Res. Nat. Bureau Standards, 49 (1952), 349-358.
• 17: G. Shapiro, "Gauss Elimination for Singular Matrices", Math. Comp. 17 (1963), 441-445.
• 18: H. Takahasi and Y. Ishibashi, "A New Method for 'Exact Calculation' by a Digital Computer", Information Processing in Japan, 1 (1961), 28-42.

INDEX TERMS

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

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

General Terms:
Algorithms, Theory