Rational solutions of singular linear systems
Thom Mulders, Arne Storjohann · 2000
A deterministic algorithm is presented for computing a particular solution to a linear system of equations with polynomial coefficients. Given an A ∈ F[x]n × m and b ∈ F[x]n, where F is a field, the algorithm will either return a particular solution v ∈ F(x)m to the system Av = b or determine that the system is inconsistent. The cost of the algorithm is O((n + m)r2d1 + ε) field operations from F, where r is the rank of A and d - 1 is a bound for the degrees of entries in A and b.