Triangular xx-basis decompositions and derandomization of linear algebra algorithms over K[x]

Deterministic algorithms are given for some computational problems that take as input a nonsingular polynomial matrix AA over K[x], K an abstract field, including solving a linear system involving AA and computing a row reduced form of AA. The fastest known algorithms for linear system solving based on the technique of high-order lifting by Storjohann (2003), and for row reduction based on the fast minimal approximant basis computation algorithm by Giorgi et al. (2003), use randomization to find either a linear or small degree polynomial that is relatively prime to detAdetA. We derandomize these algorithms by first computing a factorization of A=UHA=UH, with xx not dividing detUdetU and x−1x−1 not dividing detHdetH. A partial linearization technique, that is applicable also to other problems, is developed to transform a system involving HH, which may have some columns of large degrees, to an equivalent system that has degrees reduced to that of the average column degree.

► Linear algebra over the univariate polynomials with coefficients from a field. ► Derandomization of known reduction to matrix multiplication. ► Deterministic algorithms for rational linear system solving and row reduction. ► Partial linearization of input matrices having only some large degree entries.