Exact solution of general integer systems of linear equations

ABSTRACT

Methods are known for the exact computation of the solution of integer systems of linear equations AX = B with a nonsingular coefficient matrix A by congruence techniques. These methods are now generalized for systems with an arbitrary integer coefficient matrix A. To make congruence techniques applicable, a common denominator of all elements of the solution X = A+B must be computed. This is achieved by defining the natural denominator CODE of A+ and describing it by some formulas. Methods for the exact computation of additional results (consistency, null space, solution of at most R nonzero elements), a recursive test to save computing time, and a comparison with some results from the literature are presented.

REFERENCES

• 1: BAREISS, E.H. Computational solutions of matrix problems over an integral domain. J. Inst. Math. Appl. 10 (1972), 68-104.
• 2: BOROSH, I., AND FRAENKEL, A.S. Exact solutions of linear equations with rational coefficients by congruence techniques. Math. Comp. 20 (1966), 107-112.
• 3: Stanley Cabay, Exact solution of linear equations, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.392-398, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806310]
• 4: S. Cabay , T. P. L. Lam, Congruence Techniques for the Exact Solution of Integer Systems of Linear Equations, ACM Transactions on Mathematical Software (TOMS), v.3 n.4, p.386-397, Dec. 1977 [doi>10.1145/355759.355765]
• 5: S. Cabay , T. P. L. Lam, Algorithm 522: ESOLVE, Congruence Techniques for the Exact Solution of Integer Systems of Linear Equations [F4], ACM Transactions on Mathematical Software (TOMS), v.3 n.4, p.404-410, Dec. 1977 [doi>10.1145/355759.355767]
• 6: DECELL, H.P. An application of the Cayley-Hamilton theorem to generalized matrix inversion. SIAM Rev. 7 (1965), 526-528.
• 7: FRAENKEL, A. S., AND LOEWENTHAL, D. Exact solutions of linear equations with rational coefficients. J. Res. Nat. Bur. Stand. 75B (1971), 67-75.
• 8: HOWELL, J. A., AND GREGORY, R.T. An algorithm for solving linear algebraic equations using residue arithmetic, I-II. BIT 9 (1969), 200-224, 324-337.
• 9: HOWELL, J. A., AND GREGORY, R. T. Solving linear equations using residue arithmetic-- Algorithm II. Bit 10 (1970), 23-37.
• 10: Jo Ann Howell, Algorithm 406: exact solution of linear equations using residue arithmetic [F4], Communications of the ACM, v.14 n.3, p.180-184, March 1971 [doi>10.1145/362566.362572]
• 11: NEWMAN, M. Solving equations exactly. J. Res. Nat. Bur. Stand. Sect. B, 17 (1967), 171-179.
• 12: RAO, T. M., SUBRAMANIAN, K., AND KRISHNAMURTHY, E.V. Residue arithmetic algorithms for exact computation of g-inverses of matrices. SIAM J. Numer. Anal. 13 (1976), 155-171.
• 13: SPRINGER, J. Exakte Rechnung durch Residuenarithmetik und einige MLglichkeiten ihrer Anwendung. Diss. A, Martin-Luther-Universit~it Halle-Wittenberg, Sektion Mathematik, Halle.
• 14: SPRINGER, J. Die exakte Berechnung der Moore-Penrose-Iversen einer Matrix dutch Residuenarithmetik. ZAMM 63 (March 1983), 203-210.
• 15: STALLINGS, W. T., AND BOULLION, T.L. Computation of pseudo-inverse matrices using residue arithmetic. SIAM Rev. 14 (1972), 152-163.
• 16: ZIELKE, G. Die AuflLsung beliebiger linearer algebraischer Gleichungssysteme dutch Blockzerlegung. Beitr. Numer. Math. 8 (1980), 181-199.

INDEX TERMS

Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Least squares approximation
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

General Terms:
Algorithms, Theory