High-order lifting and integrality certification (Q1878491)

The author studies some classical problems that involve a nonsingular matrix \(A\in K[x]^{n\times n}\) over the ring \(K[x]\) of univariate polynomials with coefficients from a field \(K\) and proves that they can be solved at approximately the same cost as that for matrix multiplication. The most fundamental of these is linear system solving, i.e. to compute the solution to \(Ax=b\) where \(b\in K[x]^{n\times n}\). The second is integrality certification, i.e. to answer the following question: If \(B\in K[x]^{n\times m}\) is given, can every column of \(B\) be expressed as a \(K[x]\)-linear combination of the columns of \(A\)? The third problem is determinant computation. For this the author proposes a Las Vegas probabilistic algorithm whose expected number of operations is an order of magnitude smaller than the best known deterministic method. In the same time the Smith form of the matrix is computed.