Abstract
This paper is in two parts. Part I contains a survey of the elementary theory of residue arithmetic and a description of an algorithm for solvingAx=b using single-modulus residue arithmetic. In Part II there is a description of the algorithm using more than one modulus. Part II also contains a discussion of how to select the moduli along with some numerical results. There is a sketch of this procedure in Newman [1]. However, the treatment here is complete and uses the notation of Szabó and Tanaka [2]. It lays the foundation for a subsequent paper which will extend these results.
Similar content being viewed by others
References
Newman, M.,Solving Equations Exactly, Jour. Res. N.B.S., v. 17B (1967), 171–179.
Szabó, S., and R. Tanaka,Residue Arithmetic and Its Applications to Computer Technology, New York, McGraw Hill, 1967.
Howell, J. A., and R. T. Gregory,Solving Systems of Linear Algebraic Equations Using Residue Arithmetic, University of Texas Computation Center Report TNN-82 (revised), Austin 1969.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Howell, J.A., Gregory, R.T. An algorithm for solving linear algebraic equations using residue arithmetic I. BIT 9, 200–224 (1969). https://doi.org/10.1007/BF01946813
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01946813