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

摘要

Deterministic algorithms are given for some computational problems that take as input a nonsingular polynomial matrix A over K[χ], K an abstract field, including solving a linear system involving A and computing a row reduced form of A 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 det A. We derandomize these algorithms by first computing a factorization of A = UH, with x not dividing det U and x — 1 not dividing detH. A partial linearization technique, that is applicable also to other problems, is developed to transform a system involving H, which may have some columns of large degrees, to an equivalent system that has degrees reduced to that of the average column degree.