Error-free algorithms to solve special and general discrete systems of linear equations

摘要

This paper presents a survey of error-free algorithms to solve various systems of linear equations. The presented algorithms do not introduce computational errors into the solution and thus they are well suited to solve ill-conditioned linear systems. The error-free algorithms are based on modulo arithmetic. Two basic approaches have been investigated in the paper. The first one is based on iterative scheme using one modulus only. The other one is parallel and uses several moduli and the Chinese theorem. It is based on polynomial algebra operations that allow to express the operation of deconvolution as a sequence of convolutions of both response and output signals.