An error-free algorithm to solve a linear system of polynomial equations (Q1334719)

This paper concerns an algorithm for solving the linear system \(A(s)\cdot \bar x(s)= \bar y(s)\), where the elements of the polynomial matrix \(A\) and the output vector are \[ a_{i,j}(s)={^{p-1} a_{i,j}}\cdot s^{p-1}+\cdots +{^ 1 a_{i,j}}\cdot s^ 1+ {^ 0 a_{i,j}},\quad y_ i(s)= {^{p-1} y_ i}\cdot s^{p-1}+\cdots+ {^ 1 y_ i}\cdot s^ 1+ {^ 0 y_ i}, \] with \(i,j\in \{0,\dots, n-1\}\). Applications of some classic algorithms lead to very large degrees \((n,p)\) of the polynomials of the inverse matrix \(A^{-1}(s)\) and the determinant of the matrix \(A(s)\). The algorithm presented restricts the degree of polynomial elements during the calculation to the constant value \(p\) and therefore restricts memory space for the calculation of \(A^{-1}(s)\). Modular arithmetics in the residual polynomial class and in the residual numerical class are employed.