Details:
Title  Triangular basis decompositions and derandomization of linear algebra algorithms over  Author(s)  Somit Gupta, Soumojit Sarkar, Arne Storjohann, Johnny Valeriote  Type  Article in Journal  Abstract  Deterministic algorithms are given for some computational problems that take as input a nonsingular polynomial matrix A over K [ x ] , 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 highorder 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 = U H , with x not dividing det U and x − 1 not dividing det H . 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.  Keywords  Polynomial matrices, Linear system solving, Row reduction, Derandomization  ISSN  07477171 
URL 
http://www.sciencedirect.com/science/article/pii/S0747717111001416 
Language  English  Journal  Journal of Symbolic Computation  Volume  47  Number  4  Pages  422  453  Year  2012  Note  Special Issue for Joachim von zur Gathen at 60  Edition  0  Translation 
No  Refereed 
No 
